《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 嵌入式技術(shù) > 業(yè)界動態(tài) > RoboCup中的帶球路徑策略

RoboCup中的帶球路徑策略

2008-05-27
作者:彭 軍,丁晨陽,吳 敏,張曉

  摘 要: 為提高RoboCup仿真比賽中智能體帶球" title="帶球">帶球的成功率,設(shè)計了帶球路徑策略。通過細(xì)胞自動機(jī)建立了比賽環(huán)境演化模型,能夠?qū)χ悄荏w帶球路徑的搜索空間進(jìn)行分析規(guī)劃,在此基礎(chǔ)上設(shè)計了智能體帶球的路徑搜索" title="路徑搜索">路徑搜索策略。測試結(jié)果說明該策略能保證智能體在復(fù)雜實時的環(huán)境下進(jìn)行有效的帶球。
  關(guān)鍵詞: 帶球策略 細(xì)胞自動機(jī) 啟發(fā)式搜索 機(jī)器人足球


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

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


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


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


  其中橫坐標(biāo)為球員智能體的編號,縱坐標(biāo)為帶球次數(shù),深色柱形為相應(yīng)球員帶球總次數(shù),淺色柱形為相應(yīng)球員帶球成功的次數(shù)。統(tǒng)計結(jié)果表明,未采用新策略以前球隊整體帶球成功率為77%,如圖3;采用新策略后的球隊整體帶球成功率為90%,如圖4。整套策略在RoboCup實時帶球過程中表現(xiàn)出令人滿意的運(yùn)行性能。
  本文將細(xì)胞自動機(jī)算法和啟發(fā)式路徑搜索算法融合進(jìn)帶球路徑搜索策略中,使智能體能夠?qū)Νh(huán)境進(jìn)行實時的分析預(yù)測,有效避免與對方球員的沖突并能高效地執(zhí)行道路搜索。這樣帶球智能體行動得更快,對環(huán)境狀態(tài)改變的響應(yīng)也更加靈敏,從而保證了帶球決策的實時性和高效性。在2005年中國機(jī)器人大賽RoboCup仿真組比賽中,CSU_Yunlu 2005云麓隊獲得了三等獎,達(dá)到了預(yù)期效果。
參考文獻(xiàn)
1 Remco de Boer,Jelle Kok.The Incremental Development of a Synthetic Multi-Agent System:The UvA Trilearn 2001 Robotic Soccer Simulation Team[D].University of Amsterdam,The Netherlands,2002;(2)
2 Coren E,Dorer K,Heintz F et al.Soccer Server Manual[EB/OL].http://ei.etl.go.jp/~noda/soccer/server/index.html,1999-7
3 Aoki T.Motion planning for multiple obstacles avoidance of autonomous mobile robot using hierarchical fuzzy rules[A]. Proceedings of IEEE International Conference on Multisensor Fusion and Integration for Intelligence System(M FI′94)[C]. Las Vegas:IEEE,1994.265~271
4 鐘碧良,張 祺,楊宜民.基于改進(jìn)勢場法的足球機(jī)器人避障路徑規(guī)劃[J].控制理論與應(yīng)用,2003;20(4):623~626
5 蔡自興,徐光佑.人工智能體及其應(yīng)用(第三版)[M].北京:清華大學(xué)出版社,2004
6 彭 軍,吳 敏,曹衛(wèi)華.RoboCup機(jī)器人足球仿真比賽的關(guān)鍵技術(shù)[J].計算機(jī)工程,2004;30 (4):49~51

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,并不代表本網(wǎng)站贊同其觀點。轉(zhuǎn)載的所有的文章、圖片、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認(rèn)版權(quán)者。如涉及作品內(nèi)容、版權(quán)和其它問題,請及時通過電子郵件或電話通知我們,以便迅速采取適當(dāng)措施,避免給雙方造成不必要的經(jīng)濟(jì)損失。聯(lián)系電話:010-82306118;郵箱:aet@chinaaet.com。