RoboCup中基于動(dòng)作序列模型的動(dòng)作決策*

丁晨陽

（揚(yáng)州職業(yè)大學(xué)，江蘇 揚(yáng)州 225009）

RoboCup機(jī)器人足球世界杯賽是多智能體系統(tǒng)MAS（Multi-Agent System）和分布式人工智能的一個(gè)重要研究平臺(tái)。它提供了一個(gè)標(biāo)準(zhǔn)的多智能體環(huán)境，在這樣一個(gè)動(dòng)態(tài)的、連續(xù)的、不可預(yù)知的環(huán)境中，進(jìn)行多智能體決策是一個(gè)難題。

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

本文提出動(dòng)作序列模型將球員智能體的動(dòng)作空間離散化，并對(duì)動(dòng)作進(jìn)行評(píng)價(jià)得到一個(gè)評(píng)價(jià)值，智能體根據(jù)評(píng)價(jià)值挑選出最優(yōu)的動(dòng)作執(zhí)行。動(dòng)作序列模型的設(shè)計(jì)主要在于動(dòng)作空間的劃分和動(dòng)作序列的評(píng)價(jià)。合理的動(dòng)作劃分使得智能體具有更多、更合理的動(dòng)作序列，在當(dāng)前形勢(shì)下能夠進(jìn)行更加周全的分析和決策。對(duì)動(dòng)作序列的評(píng)價(jià)是動(dòng)作序列模型設(shè)計(jì)中的關(guān)鍵環(huán)節(jié)，通過將智能體當(dāng)前情況下執(zhí)行某一動(dòng)作能得到的收益進(jìn)行量化來使得動(dòng)作是可選的。通過對(duì)動(dòng)作序列的離散化并進(jìn)行評(píng)價(jià)，可以實(shí)現(xiàn)一個(gè)適應(yīng)性強(qiáng)、易于擴(kuò)展的整隊(duì)策略。

1 動(dòng)作序列模型的設(shè)計(jì)

動(dòng)作序列模型中所有動(dòng)作都具有三個(gè)相同的操作：判斷動(dòng)作是否能被執(zhí)行、評(píng)價(jià)函數(shù)和取得執(zhí)行動(dòng)作所需的服務(wù)器命令。為了提供一個(gè)統(tǒng)一的接口，可以抽取這些公有操作，設(shè)計(jì)一個(gè)抽象類Action，定義如下：

其中IsPreconditionReady（ ）判斷動(dòng)作的前提條件是否滿足，這是在評(píng)價(jià)動(dòng)作前必須要做的，若前提條件不滿足，比如無人可以傳球，那評(píng)價(jià)動(dòng)作也就沒有意義了；getEstimateAfterAction（ ）對(duì)執(zhí)行動(dòng)作的結(jié)果進(jìn)行評(píng)價(jià)，返回評(píng)價(jià)值；getCurrentCommand（ ）取得當(dāng)前執(zhí)行此動(dòng)作所對(duì)應(yīng)的命令。這三個(gè)操作應(yīng)該按順序調(diào)用。

由Action可派生出各個(gè)具體動(dòng)作，如圖1所示有傳球 passBall、帶球 dribble、射門 shoot等，在這些具體動(dòng)作中實(shí)現(xiàn)其父類的純虛函數(shù)。

圖1 動(dòng)作的類層次

1.1 動(dòng)作空間的劃分

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

圖2 動(dòng)作序列在智能體結(jié)構(gòu)中所處的層次

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

動(dòng)作序列模型里的動(dòng)作序列可以被逐漸擴(kuò)充，在初期的設(shè)計(jì)時(shí)可以足夠簡(jiǎn)單，易于測(cè)試和實(shí)現(xiàn)，而在后期可以通過添加動(dòng)作將動(dòng)作序列逐漸完善。

如果讓智能體遍歷所有動(dòng)作挑選出最優(yōu)，有可能會(huì)無法滿足比賽實(shí)時(shí)性的要求，因此不同角色的球員對(duì)應(yīng)的動(dòng)作序列是不同的，決策時(shí)，球員智能體只需要考慮與自己相關(guān)的動(dòng)作序列，例如一個(gè)充當(dāng)守門員角色的智能體永遠(yuǎn)也不會(huì)進(jìn)入對(duì)方的禁區(qū)，就不需要把這個(gè)狀態(tài)所對(duì)應(yīng)的動(dòng)作考慮在內(nèi)。這樣按球員角色分配動(dòng)作序列，可以縮小每個(gè)智能體動(dòng)作序列的求解空間，智能體的行為選擇越少，將越容易進(jìn)行動(dòng)作決策。

1.2 動(dòng)作序列的評(píng)價(jià)

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

對(duì)動(dòng)作進(jìn)行評(píng)價(jià)的最終結(jié)果是得到一個(gè)評(píng)價(jià)值，評(píng)價(jià)值的計(jì)算方法由式（1）給出，其中 estimate_value是評(píng)價(jià)值，benefit是執(zhí)行動(dòng)作所得到的效益，chance是執(zhí)行此次動(dòng)作的成功率。

1.2.1 效益值

效益值benefit是度量執(zhí)行動(dòng)作對(duì)實(shí)現(xiàn)多智能體系統(tǒng)的最終目標(biāo)能產(chǎn)生多大效果的標(biāo)準(zhǔn)。在RoboCup中全隊(duì)的最終目標(biāo)是進(jìn)球，所以執(zhí)行動(dòng)作后球越靠近對(duì)方球門、越靠近邊路效益越大。為了同時(shí)體現(xiàn)x和y坐標(biāo)在效益中的作用，同時(shí)減少效益值計(jì)算時(shí)產(chǎn)生的振蕩，本文參考了UvA Trilearn曾提出過的分區(qū)的思想[2]，對(duì)球場(chǎng)進(jìn)行了分區(qū)來輔助效益值的計(jì)算。球場(chǎng)被分為7個(gè)區(qū)，如圖3所示。

圖3 球場(chǎng)分區(qū)情況

area_0，area_1，area_2，area_3，area_4，area_5，area_6分 別表示這7個(gè)區(qū)，對(duì)每個(gè)區(qū)都規(guī)定了效益的最小值和最大值。分區(qū)效益的最大值定義如表1所示，當(dāng)且僅當(dāng)在分區(qū)的最大x坐標(biāo)處取得最大值，0區(qū)的最小值為0.0，其余分區(qū)的效益最小值為其相鄰上一個(gè)分區(qū)的最大值（area_6除外）。

表1 球場(chǎng)7個(gè)分區(qū)分別對(duì)應(yīng)的效益最大值

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

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

若pos處于 area_6：

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

1.2.2 成功率

成功率chance代表執(zhí)行此動(dòng)作成功的概率，對(duì)于不同的動(dòng)作，成功率的計(jì)算是不一樣的，下面以傳球?yàn)槔f明成功率的計(jì)算過程。

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

如圖4所示，球的當(dāng)前位置posBall和傳球點(diǎn)posPassTo的連線為傳球路，對(duì)于此傳球路線只考慮一個(gè)最危險(xiǎn)的敵人，計(jì)算得到它的截球點(diǎn)posInter，DistBall為posBall到posInter的距離，DistOpp為最危險(xiǎn)的敵人到posInter的距離，則傳球成功率的計(jì)算如式（4）：

圖4 傳球成功率的計(jì)算

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

當(dāng)效益值和成功率都被計(jì)算以后，動(dòng)作的評(píng)價(jià)也就結(jié)束了，評(píng)價(jià)值就是這兩者的乘積。

2 動(dòng)作決策過程

動(dòng)作序列模型提供動(dòng)作序列以及對(duì)動(dòng)作進(jìn)行評(píng)價(jià)的方法，球員智能體在進(jìn)行動(dòng)作決策時(shí)通過掃描動(dòng)作序列并比較其評(píng)價(jià)值來選出當(dāng)前狀態(tài)下的最優(yōu)動(dòng)作。

動(dòng)作序列被分為兩部分：可評(píng)價(jià)動(dòng)作和非評(píng)價(jià)動(dòng)作。對(duì)于可評(píng)價(jià)動(dòng)作，只需要調(diào)用動(dòng)作序列模型提供的接口取得評(píng)價(jià)值，比較評(píng)價(jià)值的大小即可得到當(dāng)前的最優(yōu)動(dòng)作。對(duì)于非評(píng)價(jià)動(dòng)作，需要為它們確定優(yōu)先級(jí)，這以它們?cè)谛蛄兄械奈恢脕肀硎?，即位置越靠前，?yōu)先級(jí)越高，高優(yōu)先級(jí)的動(dòng)作將首先被掃描，然后是較低優(yōu)先級(jí)的動(dòng)作。非評(píng)價(jià)動(dòng)作的優(yōu)先級(jí)是高于可評(píng)價(jià)動(dòng)作的，即一旦有非評(píng)價(jià)動(dòng)作前提條件滿足，就立刻放棄對(duì)動(dòng)作序列的掃描。整個(gè)決策流程如圖5所示。

圖5 動(dòng)作決策流程

動(dòng)作序列模型根據(jù)球員的角色生成相應(yīng)的動(dòng)作序列，首先判斷是否有非評(píng)價(jià)動(dòng)作滿足條件，如果有則執(zhí)行此動(dòng)作，不再繼續(xù)判斷；如果沒有則對(duì)可評(píng)價(jià)函數(shù)序列進(jìn)行掃描，調(diào)用每個(gè)動(dòng)作的 IsPreconditionReady（ ）計(jì)算動(dòng)作執(zhí)行的前提滿足的可能性，如果可行，再使用getEstimateAfterAction（ ）方法取得動(dòng)作的評(píng)價(jià)值，通過比較評(píng)價(jià)值的大小即可得到當(dāng)前的最優(yōu)動(dòng)作。最后調(diào)用最優(yōu)動(dòng)作的getCurrentCommand（ ）取得服務(wù)器命令發(fā)送給動(dòng)作執(zhí)行模塊。

3 仿真結(jié)果

下面是應(yīng)用基于動(dòng)作序列模型進(jìn)行動(dòng)作決策的實(shí)例（如圖6中的 a-d）。

（1）對(duì)方3號(hào)球員傳球給對(duì)方8號(hào)球員的過程中，我方8號(hào)隊(duì)員判斷自己是能最快到達(dá)球的隊(duì)員，因此選擇執(zhí)行截球動(dòng)作，如圖（a）；

（2）截球后觀察到適合協(xié)作傳球的隊(duì)友周圍都有較危險(xiǎn)敵人，成功率不高，而自己前方區(qū)域較空閑，因此選擇執(zhí)行帶球；我方8號(hào)隊(duì)員帶球的同時(shí)，10號(hào)隊(duì)友跑位至對(duì)方球員較少的區(qū)域?yàn)楹?號(hào)隊(duì)員協(xié)作做準(zhǔn)備，如圖（b）；

（3）在10號(hào)隊(duì)友執(zhí)行跑位動(dòng)作的形勢(shì)下8號(hào)隊(duì)員做出的動(dòng)作選擇就是傳球給10號(hào)隊(duì)友，將球推進(jìn)至對(duì)方球門附近，如圖（c）；

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

經(jīng)過對(duì)球員在比賽中表現(xiàn)的觀察，采用該動(dòng)作決策機(jī)制的效果還是顯而易見的。

在Robocup中，執(zhí)行動(dòng)作是智能體影響周圍環(huán)境的唯一途徑，因此智能體是否能挑選出當(dāng)前周期的最優(yōu)動(dòng)作是RoboCup仿真球隊(duì)設(shè)計(jì)的重點(diǎn)。

本文提出一種基于動(dòng)作序列模型的決策機(jī)制，所構(gòu)建的動(dòng)作序列模型包括兩個(gè)主要部分：建立動(dòng)作序列和對(duì)動(dòng)作序列進(jìn)行評(píng)價(jià)。通過離散化動(dòng)作空間預(yù)先定義好動(dòng)作集合，在比賽時(shí)可以根據(jù)動(dòng)作集合動(dòng)態(tài)地生成動(dòng)作序列；對(duì)動(dòng)作的評(píng)價(jià)是算法的核心部分，評(píng)價(jià)值是高層決策對(duì)動(dòng)作的重要標(biāo)準(zhǔn)。決策機(jī)制對(duì)評(píng)價(jià)值進(jìn)行比較并挑選出最優(yōu)動(dòng)作，克服了傳統(tǒng)的決策樹策略人為設(shè)定優(yōu)先級(jí)的不靈活的缺點(diǎn)，對(duì)環(huán)境具有較好的適應(yīng)性。此外，這種決策機(jī)制簡(jiǎn)單而又清晰，其復(fù)雜性被封裝在動(dòng)作序列模型中，其擴(kuò)展性也由動(dòng)作序列中動(dòng)作的添加而得到很好的支持。

[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]彭軍，劉亞，吳敏等.基于狀態(tài)預(yù)測(cè)的多智能體動(dòng)態(tài)協(xié)作算法[J].系統(tǒng)仿真學(xué)報(bào)，2008，20（20）.

[4]王騁，王浩，方寶富.使用基于值規(guī)則的協(xié)作圖實(shí)現(xiàn)多agent的動(dòng)作選擇[J].計(jì)算機(jī)工程與應(yīng)用，2004，40（19）：61-65.