在RoboCup中，帶球具有相當重要的作用。研究RoboCup中帶球等動作的意義不僅僅局限于RoboCup本身，它對于Agent的計算、甚至人工智能基礎理論的發(fā)展都具有重要意義。
　　帶球是智能體控球同時移動到目標點的技術，對于帶球最關鍵的策略是下一步應采取哪條路徑。這個過程至少要完成兩個任務：避免跟對方球員的沖突和運用路徑搜索算法找到從起點到目標點的帶球路徑。
　　帶球路徑可以采取多種不同的搜索求解方法，本文集中考慮對方球員的影響，找到適合智能體帶球的較優(yōu)路徑。首先建立一個優(yōu)化的環(huán)境狀態(tài)描述圖，使它支持球員智能體在比賽場地中的路徑搜索；然后設計使智能體高效執(zhí)行的路徑搜索策略，估算出一條到達目標點的較優(yōu)帶球路徑。
1 策略總體設計
　　整個策略包括兩部分。第一部分利用細胞自動機對環(huán)境建模，根據(jù)對方球員的影響演化出環(huán)境狀態(tài)描述圖，分析規(guī)劃以后要使用的路徑搜索空間。據(jù)此，智能體能夠對未來可能發(fā)生的狀態(tài)進行分析預測而有效避開對方球員的攻擊。第二部分在規(guī)劃好的搜索空間內，運用合理的路徑搜索算法，設計啟發(fā)函數(shù)" title="啟發(fā)函數(shù)">啟發(fā)函數(shù)為智能體提供最佳可行的解路徑。
2 基于細胞自動機對環(huán)境的建模
　　細胞自動機是由一組規(guī)則網格組成的陣列，每個格子就是一個細胞，其組成三要素為細胞的狀態(tài)、鄰居細胞以及演化規(guī)則。它具有組成單元的簡單性、單元之間作用的局部性和信息處理的高度并行性等特點，適合對復雜實時的動態(tài)系統(tǒng)進行有效建模。
　　將球員智能體進行帶球決策的區(qū)域(設定為智能體前方一塊矩形區(qū)域)用一系列離散方格細胞序列表示，細胞自動機算法的輸入即為智能體的感知信息。細胞自動機通過不斷的狀態(tài)刷新，進行決策區(qū)域內環(huán)境狀態(tài)的演化。
2.1 構造模型1
　　(1)定義細胞狀態(tài)：沒有被任何球員占據(jù)的狀態(tài)為0；被對方隊員占據(jù)時根據(jù)對方隊員的身體朝向可以離散化地定義各種狀態(tài)：北1、東北2、東3、東南4、南5、西南6、西7、西北8(根據(jù)比賽服務器所提供的參數(shù)設置，設定各狀態(tài)代表的角度范圍是：東(-22.5～22.5)、南(-112.5～-67.5)、西(-180~-157.5 && 157.5~180)、北(67.5~112.5)、東南(-67.5~-22.5)、東北(22.5~67.5)、西南(-157.5~-112.5)、西北(112.5~157.5))。
　　(2)鄰居細胞：每個細胞周圍的8個細胞為其鄰居細胞，分別位于北面、東北面、東面、東南面、南面、西南面、西面、西北面。
　　(3)演化規(guī)則：根據(jù)當前對方球員朝向狀態(tài)進行演化，對每個被對方隊員占據(jù)的細胞演化出它們最可能的影響范圍。
　　為方便描述，設S_i^t為細胞i在t時刻的狀態(tài)，i為演化細胞代號，S_j1^t、S_j2^t、S_j3^t、S_j4^t、S_j5^t、S_j6^t、S_j7^t、S_j8^t分別為位于i細胞北面、東北面、東面、東南面、南面、西南面、西面、西北面八個方向上的鄰居細胞狀態(tài)，jn(n=1，2，……8)為鄰居細胞代號，下面是此算法的偽碼實現(xiàn)。
　　

　　
　　帶球隊員每進行一次信息更新即可對環(huán)境狀態(tài)圖進行幾次演化迭代，演化迭代次數(shù)由所選細胞尺寸、對方能力強弱等確定。
　　這種根據(jù)朝向演化的影響區(qū)域是合理的。因為每個智能體一般只能對本身的朝向做出快速反應，所以考慮對方隊員的朝向因素，預測以后可能的環(huán)境狀態(tài)。假定在某影響區(qū)域內，對方隊員會在我方隊員之前到達這個區(qū)域內的任何一個位置，所以我方隊員以后的路徑規(guī)劃必須避開此區(qū)域。演化后得到的細胞狀態(tài)圖如圖1所示，是構造下一個細胞自動機模型的基礎。

2.2 構造模型2
　　模型1得到的結果直接作為第二個模型的初始狀態(tài)。模型2的構造如下：
　　(1)定義細胞狀態(tài)：細胞沒有被任何智能體占據(jù)的狀態(tài)為0；對方球員的控制能力值x作為細胞狀態(tài)值" title="狀態(tài)值">狀態(tài)值，設對方隊員速度值的10倍(取整舍去小數(shù)位)為對方隊員的控制能力值，速度較快的對方隊員進攻性比較強，移動打亂我方隊員進攻的可能性較大，因此按照速度值設定控制能力值。根據(jù)仿真比賽服務器的參數(shù)設置，x可取1～12的自然數(shù)。
　　(2)鄰居細胞包括每個細胞周圍的8個細胞。
　　(3)演化規(guī)則：以影響力地圖的思想為基礎。如果此細胞的狀態(tài)值為0，則將其各鄰居細胞的狀態(tài)值折半取整，再疊加作為此細胞演化后的狀態(tài)值。下面是這個算法的偽碼實現(xiàn)，演化后生成的細胞狀態(tài)圖作為最終的環(huán)境狀態(tài)描述圖，如圖2。

　　
　　這里的演化規(guī)則即是對對方隊員控制能力值的耗散處理，使智能體可以通過演化后環(huán)境狀態(tài)描述圖中的各個細胞位置的狀態(tài)值預見對方球員以后可能的影響狀況，這些信息使智能體知道某個位置作為帶球路徑的價值信息。
3 帶球路徑搜索策略的實現(xiàn)
　　最終演化好的細胞狀態(tài)圖描述了對方球員的影響，提供了各個位置作為帶球路徑的價值信息。下面運用人工智能的啟發(fā)式搜索策略，設計有效的啟發(fā)函數(shù)加速問題求解，使路徑搜索向著最有希望的方向前進，找到最優(yōu)路徑。
　　整個路徑搜索算法主要完成以下工作：(1)取得代價值最小的節(jié)點；(2)判斷產生當前節(jié)點的子節(jié)點集合；(3)把節(jié)點放入Closed表。路徑搜索核心流程的偽碼實現(xiàn)如下：
FindPath(Constrain)
{
　　//在Open表中加入新節(jié)點
　　AddNodeToList(Open，startNode)；
　　//Open表非空，進行路徑搜索
　　while !OpenIsEmpty() do
　　//Open表中代價值最小的節(jié)點為當前節(jié)點
　　Node CurNode=Open.pop_front()；
　　if ArriveGoal(CurNode) then
　　flag=1；//標志路徑搜索成功
　　//返回起點到當前節(jié)點的所有節(jié)點形成路徑
　　return GeneratePath(curNode)；
　　else
　　//把當前節(jié)點加入到Closed表中
　　AddNodeToList(Closed，CurNode)；
　　//產生當前節(jié)點子節(jié)點集合
　　List SubNodeList=getSubNodes(CurNode，Constrain，increment)；
　　for i=0；i　　//子節(jié)點在Closed表中
　　if InClosedList(SubNode) then
　　continue；
　　//子節(jié)點不在Closed表中
　　else
　　//子節(jié)點不在Open表中
　　if !InOpenList(SubNode) then
　　//計算子節(jié)點的代價值
　　TotalCost(SubNode)=gCost(SubNode)+hCost(SubNode)；
　　//當前節(jié)點作為子節(jié)點的父節(jié)點
　　SubNode.parent=CurNode；
　　//將子節(jié)點放到Open列表中
　　AddNodetoList(Open，SubNode)；
　　else //子節(jié)點在Open表更新父節(jié)點，重排Open表
　　if gCost(SubNode)　　CurNode=SubNode.parent；
　　TotalCost(SubNode)=gCost(SubNode)+hCost(SubNode)；
　　//按代價值給Open表中元素排序
　　Sort(OpenList)；
　　end if
　　end if
　　end if
　　end for
　　end if
　　end while
　　return null；
}
3.1 設計啟發(fā)函數(shù)
　　以上搜索算法的關鍵是設計啟發(fā)函數(shù)評價路徑，不同的啟發(fā)函數(shù)會導致不同的解路徑。根據(jù)帶球策略，將Cost_s、Cost_θ1、Cost_θ2三個因素作為啟發(fā)函數(shù)的參數(shù)，設計如下：
　　hCost(Node)
　　{
　　//Cost_s為節(jié)點細胞當前狀態(tài)值
　　Cost_s=GetState(Node)；
　　//Cost_θ1為相對目標位置的偏移角度
　　Cost_θ1=AngDeviate(Node，Node.parent)；
　　//Cost_θ2為相對上次搜索過節(jié)點位置的偏移角度
　　Cost_θ2=AngDeviate(Node，goalNode)；
　　h(Cost)=αCost_s+βCost_θ1+γCost_θ2；
　　return h；
　　}
　　根據(jù)優(yōu)先級的大小分別賦予這三個因素合適的權值" title="權值">權值α、β和γ。這些權值的選取對于帶球路線的搜索十分關鍵，它們的數(shù)值是基于公式中各項的優(yōu)先級以及范圍，可以通過調整權值改變各個因素的優(yōu)先次序。優(yōu)先級較高的因素在結果中應占較大比重，這些權值需要經過大量的測試或使用學習等技術得到。
　　在本應用中，取α＞β＞γ。因為最重要的是避開接近的對方球員，相對于高層規(guī)劃指定的目標位置的角度偏移以及原來帶球方向角度偏移則次之。這樣使智能體向相對對方隊員控制能力較弱位置、朝目標位置方向以及它原本前進的方向帶球前進。這樣選擇是因為方向的改變會額外花費一些時間，有時還會引起不理想的震蕩。
3.2 路徑搜索的優(yōu)化執(zhí)行
　　為提高路徑搜索算法的效率，結合前一節(jié)中介紹的細胞自動機的演化結果，采取制定搜索界限的方法進行路徑搜索。即在搜索算法上附加表示當前調用的界限參數(shù)。這樣算法占用較小的內存，被考察的節(jié)點較少，以下是根據(jù)界限參數(shù)獲得子節(jié)點集合的示例：
　　getSubNodes (CurNode，Constrain，increment)
　　{
　　//循環(huán)構造當前位置的鄰居位置子節(jié)點
　　for i=-1；i<2；i++
　　for j=-1；j<2；j++
　　SubNode.x=CurNode.x+i*increment；
　　SubNode.y=CurNode.y+j*increment；
　　if i==0 && j==0 then
　　　　continue；
　　end if
　　if !InConstrain(SubNode) then
　　　　continue；//不在界限內的節(jié)點排除
　　end if
　　//將在界線參數(shù)限定范圍內的節(jié)點加入子節(jié)點集合
　　AddNodeToList(SubNodeList，SubNode)；
　　return SubNodeList；//返回界限內子節(jié)點集合
　　end for
　　end for
　　}
　　本文的策略對于細胞位置允許的最大狀態(tài)值為界限參數(shù)。在環(huán)境狀態(tài)描述圖的基礎上，設定界限1：細胞狀態(tài)值為0，此界限區(qū)域為帶球搜索最安全區(qū)域，不在對方球員的控制之下；界限2：相對界限1放寬一些，定細胞狀態(tài)值稍大，此界限區(qū)域為從最安全區(qū)域出發(fā)分別向左向右擴散出的帶球搜索較安全區(qū)域，對方球員對此區(qū)域的控制能力增加；根據(jù)情況還可繼續(xù)放寬界限，制定界限3、界限4等。如果一個小界限的初始搜索能找到路徑，則搜索算法只要在最安全區(qū)域嘗試少數(shù)幾個位置就能找到正確的路徑。如果沒有成功找到路徑，將在隨后的調用中逐漸放寬界限，取界限2、3，即讓其在較安全區(qū)域甚至弱安全區(qū)域搜索路徑，直到搜索成功或者到達取值范圍的端點。
　　這樣，即使是失敗的幾次調用findpath()也只使用了較少的內存；同時也加快了路徑檢測的速度。因為小界限調用會更快地達到失敗條件，也提高了路徑暫被其他行動者阻斷時的執(zhí)行性能。
　　如果沒有成功找到通向目標點的帶球路徑，可能是路徑不存在或者搜索已經到了強加的極限，這時不應該讓球員反復調用失敗的搜索算法而延誤動作時機。為了使帶球智能體的反應更加靈敏，采取返回findpartpath()，先得到部分路徑的策略。只需修改findpath()，即設定搜索節(jié)點循環(huán)相應次數(shù)后停止計算(循環(huán)次數(shù)確保能產生一條合理長度的路徑)，把離目標點最近的點作為子目標點，返回實現(xiàn)的部分路徑。從小界限開始趨向最大界限進行路徑搜索的偽碼實現(xiàn)如下：
　　for i=0；i　　if flag=1 then
　　break；//某個界限下路徑搜索成功
　　else
　　if i==PathCoordinator() then
　　findpartpath(constrain[i])；//返回部分路徑
　　else
　　findpath(constrain[i])；//調用整體路徑搜索
　　end if
　　end if
　　end for
　　帶球隊員通過一個小界限參數(shù)調用搜索算法，可以立即沿著返回的部分路徑移動，然后使用一個逐漸增大的界限參數(shù)再次調用搜索算法得到部分或全部路徑，帶球者最終會找到一條通往目的地的路徑，或者在一個離終點不遠的地方停止?？傊缦迏?shù)和返回部分路徑的方法可以使智能體的反應更加靈敏，不管發(fā)生什么情況，帶球隊員總會有所作為，而不是只站在原地。
4 應用效果測試
　　本文進行的比賽測試是在SoccerServer10.xx版本下完成的。將基于細胞自動機的帶球路徑搜索策略應用到中南大學RoboCup仿真球隊(CSU_Yunlu 2005)中，先后對采用本文策略和不采用本文策略的CSU_YunLu仿真球隊作了長時間的測試。
　　將未采用新策略的球隊和采用新策略的球隊與同一支仿真球隊比賽，運用仿真調試工具SoccerDoctor得到兩次比賽中帶球成功率的統(tǒng)計圖，如圖3、圖4所示。