RoboCup中的帶球路徑策略

1、    RoboCup中的帶球路徑策略        彭 軍，丁晨陽(yáng)，吳 敏，張曉 時(shí)間:2008年05月27日     字 體: 大 中 小        關(guān)鍵詞:        摘要：關(guān)鍵詞： 帶球策略 細(xì)胞自動(dòng)機(jī) 啟發(fā)式搜索 機(jī)器人足球在RoboCup中，帶球具有相當(dāng)重要的

2、作用。研究RoboCup中帶球等動(dòng)作的意義不僅僅局限于RoboCup本身，它對(duì)于Agent的計(jì)算、甚至人工智能基礎(chǔ)理論的發(fā)展都具有重要意義。帶球是智能體控球同時(shí)移動(dòng)到目標(biāo)點(diǎn)的技術(shù)，對(duì)于帶球最關(guān)鍵的策略是下一步應(yīng)采取哪條路徑。這個(gè)過(guò)程至少要完成兩個(gè)任務(wù)：避免跟對(duì)方球員的沖突和運(yùn)用路徑搜索算法找到從起點(diǎn)到目標(biāo)點(diǎn)的帶球路徑。帶球路徑可以采取多種不同的搜索求解方法，本文集中考慮對(duì)方球員的影響，找到適合智能體帶球的較優(yōu)路徑。首先建立一個(gè)優(yōu)化的環(huán)境狀態(tài)描述圖，使它支持球員智能體在比賽場(chǎng)地中的路徑搜索；然后設(shè)計(jì)使智能體高效執(zhí)行的路徑搜索策略，估算出一條到達(dá)目標(biāo)點(diǎn)的較優(yōu)帶球路徑。1 策略總體設(shè)計(jì)2 基于細(xì)胞自

3、動(dòng)機(jī)對(duì)環(huán)境的建模細(xì)胞自動(dòng)機(jī)是由一組規(guī)則網(wǎng)格組成的陣列，每個(gè)格子就是一個(gè)細(xì)胞，其組成三要素為細(xì)胞的狀態(tài)、鄰居細(xì)胞以及演化規(guī)則。它具有組成單元的簡(jiǎn)單性、單元之間作用的局部性和信息處理的高度并行性等特點(diǎn)，適合對(duì)復(fù)雜實(shí)時(shí)的動(dòng)態(tài)系統(tǒng)進(jìn)行有效建模。將球員智能體進(jìn)行帶球決策的區(qū)域(設(shè)定為智能體前方一塊矩形區(qū)域)用一系列離散方格細(xì)胞序列表示，細(xì)胞自動(dòng)機(jī)算法的輸入即為智能體的感知信息。細(xì)胞自動(dòng)機(jī)通過(guò)不斷的狀態(tài)刷新，進(jìn)行決策區(qū)域內(nèi)環(huán)境狀態(tài)的演化。2.1 構(gòu)造模型1 (1)定義細(xì)胞狀態(tài)：沒(méi)有被任何球員占據(jù)的狀態(tài)為0；被對(duì)方隊(duì)員占據(jù)時(shí)根據(jù)對(duì)方隊(duì)員的身體朝向可以離散化地定義各種狀態(tài)：北1、東北2、東3、東南4、南5、西

4、南6、西7、西北8(根據(jù)比賽服務(wù)器所提供的參數(shù)設(shè)置，設(shè)定各狀態(tài)代表的角度范圍是：東(-22.522.5)、南(-112.5-67.5)、西(-180-157.5 && 157.5180)、北(67.5112.5)、東南(-67.5-22.5)、東北(22.567.5)、西南(-157.5-112.5)、西北(112.5157.5)。(2)鄰居細(xì)胞：每個(gè)細(xì)胞周?chē)?個(gè)細(xì)胞為其鄰居細(xì)胞，分別位于北面、東北面、東面、東南面、南面、西南面、西面、西北面。(3)演化規(guī)則：根據(jù)當(dāng)前對(duì)方球員朝向狀態(tài)進(jìn)行演化，對(duì)每個(gè)被對(duì)方隊(duì)員占據(jù)的細(xì)胞演化出它們最可能的影響范圍。為方便描述，設(shè)Sit為細(xì)胞i在

5、t時(shí)刻的狀態(tài)，i為演化細(xì)胞代號(hào)，Sj1t、Sj2t、Sj3t、Sj4t、Sj5t、Sj6t、Sj7t、Sj8t分別為位于i細(xì)胞北面、東北面、東面、東南面、南面、西南面、西面、西北面八個(gè)方向上的鄰居細(xì)胞狀態(tài)，jn(n=1，2，8)為鄰居細(xì)胞代號(hào)，下面是此算法的偽碼實(shí)現(xiàn)。帶球隊(duì)員每進(jìn)行一次信息更新即可對(duì)環(huán)境狀態(tài)圖進(jìn)行幾次演化迭代，演化迭代次數(shù)由所選細(xì)胞尺寸、對(duì)方能力強(qiáng)弱等確定。這種根據(jù)朝向演化的影響區(qū)域是合理的。因?yàn)槊總€(gè)智能體一般只能對(duì)本身的朝向做出快速反應(yīng)，所以考慮對(duì)方隊(duì)員的朝向因素，預(yù)測(cè)以后可能的環(huán)境狀態(tài)。假定在某影響區(qū)域內(nèi)，對(duì)方隊(duì)員會(huì)在我方隊(duì)員之前到達(dá)這個(gè)區(qū)域內(nèi)的任何一個(gè)位置，所以我方隊(duì)員以

6、后的路徑規(guī)劃必須避開(kāi)此區(qū)域。演化后得到的細(xì)胞狀態(tài)圖如圖1所示，是構(gòu)造下一個(gè)細(xì)胞自動(dòng)機(jī)模型的基礎(chǔ)。2.2 構(gòu)造模型2這里的演化規(guī)則即是對(duì)對(duì)方隊(duì)員控制能力值的耗散處理，使智能體可以通過(guò)演化后環(huán)境狀態(tài)描述圖中的各個(gè)細(xì)胞位置的狀態(tài)值預(yù)見(jiàn)對(duì)方球員以后可能的影響狀況，這些信息使智能體知道某個(gè)位置作為帶球路徑的價(jià)值信息。3 帶球路徑搜索策略的實(shí)現(xiàn)最終演化好的細(xì)胞狀態(tài)圖描述了對(duì)方球員的影響，提供了各個(gè)位置作為帶球路徑的價(jià)值信息。下面運(yùn)用人工智能的啟發(fā)式搜索策略，設(shè)計(jì)有效的啟發(fā)函數(shù)加速問(wèn)題求解，使路徑搜索向著最有希望的方向前進(jìn)，找到最優(yōu)路徑。整個(gè)路徑搜索算法主要完成以下工作：(1)取得代價(jià)值最小的節(jié)點(diǎn)；(2)判

7、斷產(chǎn)生當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)集合；(3)把節(jié)點(diǎn)放入Closed表。路徑搜索核心流程的偽碼實(shí)現(xiàn)如下：FindPath(Constrain)/在Open表中加入新節(jié)點(diǎn)AddNodeToList(Open，startNode)；/Open表非空，進(jìn)行路徑搜索while !OpenIsEmpty() do/Open表中代價(jià)值最小的節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)Node CurNode=Open.pop_front()；if ArriveGoal(CurNode) thenflag=1；/標(biāo)志路徑搜索成功/返回起點(diǎn)到當(dāng)前節(jié)點(diǎn)的所有節(jié)點(diǎn)形成路徑return GeneratePath(curNode)；else/把當(dāng)前節(jié)點(diǎn)加入到

8、Closed表中AddNodeToList(Closed，CurNode)；/產(chǎn)生當(dāng)前節(jié)點(diǎn)子節(jié)點(diǎn)集合List SubNodeList=getSubNodes(CurNode，Constrain，increment)；for i=0；i<SUBNODELIST.SIZE()；I+/子節(jié)點(diǎn)在Closed表中if InClosedList(SubNode) thencontinue；/子節(jié)點(diǎn)不在Closed表中else/子節(jié)點(diǎn)不在Open表中if !InOpenList(SubNode) then/計(jì)算子節(jié)點(diǎn)的代價(jià)值TotalCost(SubNode)=gCost(SubNode)+hCost

9、(SubNode)；/當(dāng)前節(jié)點(diǎn)作為子節(jié)點(diǎn)的父節(jié)點(diǎn)SubNode.parent=CurNode；/將子節(jié)點(diǎn)放到Open列表中AddNodetoList(Open，SubNode)；else /子節(jié)點(diǎn)在Open表更新父節(jié)點(diǎn)，重排Open表if gCost(SubNode)CurNode=SubNode.parent；TotalCost(SubNode)=gCost(SubNode)+hCost(SubNode)；/按代價(jià)值給Open表中元素排序Sort(OpenList)；end ifend ifend ifend forend ifend whilereturn null；3.1 設(shè)計(jì)啟發(fā)函數(shù)以

10、上搜索算法的關(guān)鍵是設(shè)計(jì)啟發(fā)函數(shù)評(píng)價(jià)路徑，不同的啟發(fā)函數(shù)會(huì)導(dǎo)致不同的解路徑。根據(jù)帶球策略，將Costs、Cost1、Cost2三個(gè)因素作為啟發(fā)函數(shù)的參數(shù)，設(shè)計(jì)如下：hCost(Node)/Costs為節(jié)點(diǎn)細(xì)胞當(dāng)前狀態(tài)值Costs=GetState(Node)；/Cost1為相對(duì)目標(biāo)位置的偏移角度Cost1=AngDeviate(Node，Node.parent)；/Cost2為相對(duì)上次搜索過(guò)節(jié)點(diǎn)位置的偏移角度Cost2=AngDeviate(Node，goalNode)；h(Cost)=Costs+Cost1+Cost23.2 路徑搜索的優(yōu)化執(zhí)行為提高路徑搜索算法的效率，結(jié)合前一節(jié)中介紹的細(xì)胞自

11、動(dòng)機(jī)的演化結(jié)果，采取制定搜索界限的方法進(jìn)行路徑搜索。即在搜索算法上附加表示當(dāng)前調(diào)用的界限參數(shù)。這樣算法占用較小的內(nèi)存，被考察的節(jié)點(diǎn)較少，以下是根據(jù)界限參數(shù)獲得子節(jié)點(diǎn)集合的示例：getSubNodes (CurNode，Constrain，increment)/循環(huán)構(gòu)造當(dāng)前位置的鄰居位置子節(jié)點(diǎn)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 thencontinue；end ifif !InConstra

12、in(SubNode) thencontinue；/不在界限內(nèi)的節(jié)點(diǎn)排除end if/將在界線參數(shù)限定范圍內(nèi)的節(jié)點(diǎn)加入子節(jié)點(diǎn)集合AddNodeToList(SubNodeList，SubNode)；return SubNodeList；/返回界限內(nèi)子節(jié)點(diǎn)集合end forend for本文的策略對(duì)于細(xì)胞位置允許的最大狀態(tài)值為界限參數(shù)。在環(huán)境狀態(tài)描述圖的基礎(chǔ)上，設(shè)定界限1：細(xì)胞狀態(tài)值為0，此界限區(qū)域?yàn)閹蛩阉髯畎踩珔^(qū)域，不在對(duì)方球員的控制之下；界限2：相對(duì)界限1放寬一些，定細(xì)胞狀態(tài)值稍大，此界限區(qū)域?yàn)閺淖畎踩珔^(qū)域出發(fā)分別向左向右擴(kuò)散出的帶球搜索較安全區(qū)域，對(duì)方球員對(duì)此區(qū)域的控制能力增加；根據(jù)情況

13、還可繼續(xù)放寬界限，制定界限3、界限4等。如果一個(gè)小界限的初始搜索能找到路徑，則搜索算法只要在最安全區(qū)域嘗試少數(shù)幾個(gè)位置就能找到正確的路徑。如果沒(méi)有成功找到路徑，將在隨后的調(diào)用中逐漸放寬界限，取界限2、3，即讓其在較安全區(qū)域甚至弱安全區(qū)域搜索路徑，直到搜索成功或者到達(dá)取值范圍的端點(diǎn)。這樣，即使是失敗的幾次調(diào)用findpath()也只使用了較少的內(nèi)存；同時(shí)也加快了路徑檢測(cè)的速度。因?yàn)樾〗缦拚{(diào)用會(huì)更快地達(dá)到失敗條件，也提高了路徑暫被其他行動(dòng)者阻斷時(shí)的執(zhí)行性能。如果沒(méi)有成功找到通向目標(biāo)點(diǎn)的帶球路徑，可能是路徑不存在或者搜索已經(jīng)到了強(qiáng)加的極限，這時(shí)不應(yīng)該讓球員反復(fù)調(diào)用失敗的搜索算法而延誤動(dòng)作時(shí)機(jī)。為了使

14、帶球智能體的反應(yīng)更加靈敏，采取返回findpartpath()，先得到部分路徑的策略。只需修改findpath()，即設(shè)定搜索節(jié)點(diǎn)循環(huán)相應(yīng)次數(shù)后停止計(jì)算(循環(huán)次數(shù)確保能產(chǎn)生一條合理長(zhǎng)度的路徑)，把離目標(biāo)點(diǎn)最近的點(diǎn)作為子目標(biāo)點(diǎn)，返回實(shí)現(xiàn)的部分路徑。從小界限開(kāi)始趨向最大界限進(jìn)行路徑搜索的偽碼實(shí)現(xiàn)如下：for i=0；i<MAXCONSTRAIN；I+if flag=1 thenbreak；/某個(gè)界限下路徑搜索成功elseif i=PathCoordinator() thenfindpartpath(constraini)；/返回部分路徑elsefindpath(constraini)；/調(diào)用

15、整體路徑搜索end ifend ifend for帶球隊(duì)員通過(guò)一個(gè)小界限參數(shù)調(diào)用搜索算法，可以立即沿著返回的部分路徑移動(dòng)，然后使用一個(gè)逐漸增大的界限參數(shù)再次調(diào)用搜索算法得到部分或全部路徑，帶球者最終會(huì)找到一條通往目的地的路徑，或者在一個(gè)離終點(diǎn)不遠(yuǎn)的地方停止。總之，界限參數(shù)和返回部分路徑的方法可以使智能體的反應(yīng)更加靈敏，不管發(fā)生什么情況，帶球隊(duì)員總會(huì)有所作為，而不是只站在原地。4 應(yīng)用效果測(cè)試本文進(jìn)行的比賽測(cè)試是在SoccerServer10.xx版本下完成的。將基于細(xì)胞自動(dòng)機(jī)的帶球路徑搜索策略應(yīng)用到中南大學(xué)RoboCup仿真球隊(duì)(CSU_Yunlu 2005)中，先后對(duì)采用本文策略和不采用本文策略的CSU_YunLu仿真球隊(duì)作了長(zhǎng)時(shí)間的測(cè)試。將未采用新策略的球隊(duì)和采用新策略的球隊(duì)與同一支仿真球隊(duì)比賽，運(yùn)用仿真調(diào)試工具SoccerDoctor得到兩次比賽中帶球成功率的統(tǒng)計(jì)圖，如圖3、圖4所示。其中橫坐標(biāo)為球員智能體的編號(hào)，縱坐標(biāo)為帶球次數(shù)，深色柱形為相應(yīng)球員帶球總次數(shù)，淺色柱形為相應(yīng)球員帶球成功的次數(shù)。統(tǒng)計(jì)結(jié)果表明，未采用新策略以前球隊(duì)整體帶球成功率為77%，如圖3；采用新策略后的球隊(duì)整體帶球成功率為90%