RoboCup中基于動作序列模型的動作決策*

丁晨陽

（揚州職業大學，江蘇 揚州 225009）

RoboCup機器人足球世界杯賽是多智能體系統MAS（Multi-Agent System）和分布式人工智能的一個重要研究平臺。它提供了一個標準的多智能體環境，在這樣一個動態的、連續的、不可預知的環境中，進行多智能體決策是一個難題。

RoboCup仿真比賽中球員智能體快速地采取合理的行動選擇對于球隊的表現有著決定性的影響。作為整隊策略的設計者，要做的工作就是決定智能體在比賽的每一個仿真周期選擇什么動作發送給服務器。傳統的方法是使用決策樹[1]，其動作選擇過程分為兩個步驟：首先確定當前的狀態模式，然后根據相應的狀態模式產生一個恰當的動作命令。這個方法的優點是實現簡單，而且計算量小，反應比較快。然而要確定當前的狀態模式，就必須在設計時將場上狀態離散化成一個有限的集合，而在RoboCup中，由于智能體處于一個動態、連續的環境中，場上狀態的變化是微妙的，這使得狀態的離散化變得很難，而且由于狀態的數量是趨于無窮的，在程序中無法將所有的狀態都考慮到，所以這種方法的效果是有限的。雖然場上狀態是連續、無限的，但球員可選擇的動作卻是有限且易于區分的。

本文提出動作序列模型將球員智能體的動作空間離散化，并對動作進行評價得到一個評價值，智能體根據評價值挑選出最優的動作執行。動作序列模型的設計主要在于動作空間的劃分和動作序列的評價。合理的動作劃分使得智能體具有更多、更合理的動作序列，在當前形勢下能夠進行更加周全的分析和決策。對動作序列的評價是動作序列模型設計中的關鍵環節，通過將智能體當前情況下執行某一動作能得到的收益進行量化來使得動作是可選的。通過對動作序列的離散化并進行評價，可以實現一個適應性強、易于擴展的整隊策略。

1 動作序列模型的設計

動作序列模型中所有動作都具有三個相同的操作：判斷動作是否能被執行、評價函數和取得執行動作所需的服務器命令。為了提供一個統一的接口，可以抽取這些公有操作，設計一個抽象類Action，定義如下：

其中IsPreconditionReady（ ）判斷動作的前提條件是否滿足，這是在評價動作前必須要做的，若前提條件不滿足，比如無人可以傳球，那評價動作也就沒有意義了；getEstimateAfterAction（ ）對執行動作的結果進行評價，返回評價值；getCurrentCommand（ ）取得當前執行此動作所對應的命令。這三個操作應該按順序調用。

由Action可派生出各個具體動作，如圖1所示有傳球 passBall、帶球 dribble、射門 shoot等，在這些具體動作中實現其父類的純虛函數。

圖1 動作的類層次

1.1 動作空間的劃分

本節描述的動作屬于高層決策問題的一部分，是利用仿真比賽服務器提供的底層基本技能 （dash、kick、turn等） 組合而成的 高 層 復 雜 動 作 （passBall、dribble、shoot等）。圖2給出了個人基本技能以及動作序列在智能體結構中所處的層次。

圖2 動作序列在智能體結構中所處的層次

動作序列模型中主要包括以下動作：（1）傳球passBall：在傳球者和各個可能的隊友之間計算出一條合適的路線傳球。（2）帶球dribble：選擇合適的帶球角度以及速度移動球，并將球控制在一定距離內。（3）射門shoot：將球踢向對方球門線上的最佳射門點。（4）過人outplayOpponent：將球傳到對方防守隊員背面的位置。（5）截球 intercept：當智能體是離球最快的隊員時，依據截球周期、截球點等參數執行此動作。（6）清球clearBall：大力將球踢盡量遠。 （7）跑位 moveToPos：根據協作需要搜索一個空閑位置移動過去。（8）盯人mark：選擇盯人對象以及盯人位置，阻止對方截球或者接近球門。（9）找球searchBall：當球不在視覺范圍內時，轉身找球。

動作序列模型里的動作序列可以被逐漸擴充，在初期的設計時可以足夠簡單，易于測試和實現，而在后期可以通過添加動作將動作序列逐漸完善。

如果讓智能體遍歷所有動作挑選出最優，有可能會無法滿足比賽實時性的要求，因此不同角色的球員對應的動作序列是不同的，決策時，球員智能體只需要考慮與自己相關的動作序列，例如一個充當守門員角色的智能體永遠也不會進入對方的禁區，就不需要把這個狀態所對應的動作考慮在內。這樣按球員角色分配動作序列，可以縮小每個智能體動作序列的求解空間，智能體的行為選擇越少，將越容易進行動作決策。

1.2 動作序列的評價

動作序列模型還要求對動作進行評價，依據評價值可給出各動作的優先級。序列中的某些動作被排除在評價的范圍之外，這是由于它們具有比較明確的前提條件，一旦前提條件滿足，則動作必須執行。比如截球動作，只要隊員是最快到達球的位置就去截球。

對動作進行評價的最終結果是得到一個評價值，評價值的計算方法由式（1）給出，其中 estimate_value是評價值，benefit是執行動作所得到的效益，chance是執行此次動作的成功率。

1.2.1 效益值

效益值benefit是度量執行動作對實現多智能體系統的最終目標能產生多大效果的標準。在RoboCup中全隊的最終目標是進球，所以執行動作后球越靠近對方球門、越靠近邊路效益越大。為了同時體現x和y坐標在效益中的作用，同時減少效益值計算時產生的振蕩，本文參考了UvA Trilearn曾提出過的分區的思想[2]，對球場進行了分區來輔助效益值的計算。球場被分為7個區，如圖3所示。

圖3 球場分區情況

area_0，area_1，area_2，area_3，area_4，area_5，area_6分 別表示這7個區，對每個區都規定了效益的最小值和最大值。分區效益的最大值定義如表1所示，當且僅當在分區的最大x坐標處取得最大值，0區的最小值為0.0，其余分區的效益最小值為其相鄰上一個分區的最大值（area_6除外）。

表1 球場7個分區分別對應的效益最大值

給定一個位置 pos（x，y），計算其效益值如式（2）和式（3）。

若 pos處于 area_N，N∈{0，1，2，3，4，5}：

若pos處于 area_6：

其中 getX（ ），getY（ ）分別為取得 pos的 x，y坐標值的方法，由于area_6比較特殊，處于敵方球門的正前方，對我方十分有利，所以對它進行了特殊的處理。

1.2.2 成功率

成功率chance代表執行此動作成功的概率，對于不同的動作，成功率的計算是不一樣的，下面以傳球為例說明成功率的計算過程。

為計算傳球成功率，使用了一個分布函數：s（x）＝1/（1+e-x）。 它是一個 S 形的函數，且 s（x）∈[0，1]；s（0）＝0.5；當 x＜＜0 時，s（x）～0；當 x＞＞1 時，s（x）～1。所以，s（x）提供了一個在（0，1）上的分布。

如圖4所示，球的當前位置posBall和傳球點posPassTo的連線為傳球路，對于此傳球路線只考慮一個最危險的敵人，計算得到它的截球點posInter，DistBall為posBall到posInter的距離，DistOpp為最危險的敵人到posInter的距離，則傳球成功率的計算如式（4）：

圖4 傳球成功率的計算

按照 s（x）函數的分布，當 1.5×DistOpp＝DistBall時，chance＝0；當 1.5×DistOpp＜＜DistBall時，chance→0，即球通過posInter的幾率很小；當 1.5×DistOpp＞＞DistBall時，chance→1，即球通過posInter的幾率很大。在速度一定的情況下，距離越遠，需要的時間越長，由于球的速度通常都比球員的速度大，所以將DistOpp放大了1.5倍作為修正。

當效益值和成功率都被計算以后，動作的評價也就結束了，評價值就是這兩者的乘積。

2 動作決策過程

動作序列模型提供動作序列以及對動作進行評價的方法，球員智能體在進行動作決策時通過掃描動作序列并比較其評價值來選出當前狀態下的最優動作。

動作序列被分為兩部分：可評價動作和非評價動作。對于可評價動作，只需要調用動作序列模型提供的接口取得評價值，比較評價值的大小即可得到當前的最優動作。對于非評價動作，需要為它們確定優先級，這以它們在序列中的位置來表示，即位置越靠前，優先級越高，高優先級的動作將首先被掃描，然后是較低優先級的動作。非評價動作的優先級是高于可評價動作的，即一旦有非評價動作前提條件滿足，就立刻放棄對動作序列的掃描。整個決策流程如圖5所示。

圖5 動作決策流程

動作序列模型根據球員的角色生成相應的動作序列，首先判斷是否有非評價動作滿足條件，如果有則執行此動作，不再繼續判斷；如果沒有則對可評價函數序列進行掃描，調用每個動作的 IsPreconditionReady（ ）計算動作執行的前提滿足的可能性，如果可行，再使用getEstimateAfterAction（ ）方法取得動作的評價值，通過比較評價值的大小即可得到當前的最優動作。最后調用最優動作的getCurrentCommand（ ）取得服務器命令發送給動作執行模塊。

3 仿真結果

下面是應用基于動作序列模型進行動作決策的實例（如圖6中的 a-d）。

（1）對方3號球員傳球給對方8號球員的過程中，我方8號隊員判斷自己是能最快到達球的隊員，因此選擇執行截球動作，如圖（a）；

（2）截球后觀察到適合協作傳球的隊友周圍都有較危險敵人，成功率不高，而自己前方區域較空閑，因此選擇執行帶球；我方8號隊員帶球的同時，10號隊友跑位至對方球員較少的區域為和8號隊員協作做準備，如圖（b）；

（3）在10號隊友執行跑位動作的形勢下8號隊員做出的動作選擇就是傳球給10號隊友，將球推進至對方球門附近，如圖（c）；

（4）10號隊員接到球后，由于前方其他的隊友都被敵方球員盯緊，10號隊員的最佳策略就是選擇一條路徑射門，如圖（d）。

經過對球員在比賽中表現的觀察，采用該動作決策機制的效果還是顯而易見的。

在Robocup中，執行動作是智能體影響周圍環境的唯一途徑，因此智能體是否能挑選出當前周期的最優動作是RoboCup仿真球隊設計的重點。

本文提出一種基于動作序列模型的決策機制，所構建的動作序列模型包括兩個主要部分：建立動作序列和對動作序列進行評價。通過離散化動作空間預先定義好動作集合，在比賽時可以根據動作集合動態地生成動作序列；對動作的評價是算法的核心部分，評價值是高層決策對動作的重要標準。決策機制對評價值進行比較并挑選出最優動作，克服了傳統的決策樹策略人為設定優先級的不靈活的缺點，對環境具有較好的適應性。此外，這種決策機制簡單而又清晰，其復雜性被封裝在動作序列模型中，其擴展性也由動作序列中動作的添加而得到很好的支持。

[1]KONUR S， FERREIN A， LAKEMEYER G.Learning Decision Trees for Action Selection in Soccer Agents[C].In Proceedings of Workshop on Agents in Dynamic and Realtime Environments，16th European Conference on Artificial Intelligence， Valencia， Spain， 2004.

[2]BOER R D，KOK J.The Incremental Development of a SyntheticMulti-Agent System： The UvA Trilearn 2001 Robotic Soccer Simula-tion Team [D].Master′s thesis，University of Amsterdam，2002.

[3]彭軍，劉亞，吳敏等.基于狀態預測的多智能體動態協作算法[J].系統仿真學報，2008，20（20）.

[4]王騁，王浩，方寶富.使用基于值規則的協作圖實現多agent的動作選擇[J].計算機工程與應用，2004，40（19）：61-65.