丁晨陽

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

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

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

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

1 動作序列模型的設(shè)計

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

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

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

圖1 動作的類層次

1.1 動作空間的劃分

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

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

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

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

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

1.2 動作序列的評價

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

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

1.2.1 效益值

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

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

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

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

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

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

若pos處于 area_6：

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

1.2.2 成功率

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

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

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

圖4 傳球成功率的計算

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

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

2 動作決策過程

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

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

圖5 動作決策流程

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

3 仿真結(jié)果

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

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

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

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

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

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

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

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

[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ù)測的多智能體動態(tài)協(xié)作算法[J].系統(tǒng)仿真學(xué)報，2008，20（20）.

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