趙發(fā)君，李龍澍

安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

基于多Agent Q學(xué)習(xí)的RoboCup局部配合策略

趙發(fā)君，李龍澍

安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

1 引言

RoboCup是近年世界上規(guī)模最大的機(jī)器人足球大賽，包括仿真和實(shí)體兩類(lèi)比賽項(xiàng)目[1]。RoboCup仿真2D是RoboCup最早的項(xiàng)目，也是軟件仿真項(xiàng)目的重要組成部分。是各個(gè)研究團(tuán)體在人工智能和多Agent智能體協(xié)作方面研究的交流平臺(tái)[2-4]。

RoboCup仿真2D的比賽平臺(tái)是模仿人類(lèi)足球賽的場(chǎng)地和規(guī)則制作出來(lái)的。整場(chǎng)比賽分為上下半場(chǎng)，各10 min。比賽中以100 ms為周期，每個(gè)球員為單獨(dú)的程序，是由客戶(hù)端開(kāi)辟出來(lái)的一個(gè)獨(dú)立的線(xiàn)程，仿真球員通過(guò)向服務(wù)器發(fā)送命令來(lái)完成自身所要進(jìn)行的動(dòng)作[5]。為了使球員在每個(gè)周期都能選擇最優(yōu)的動(dòng)作，現(xiàn)在的很多隊(duì)伍都采用Q-學(xué)習(xí)來(lái)實(shí)現(xiàn)[1，5-8]，并且在一定程度上實(shí)現(xiàn)了Agent間的協(xié)作效果。但是現(xiàn)行的隊(duì)伍很多采用的方法是：只有帶球球員才進(jìn)行Q-學(xué)習(xí)獲得最優(yōu)動(dòng)作[5-8]，即在馬爾科夫決策環(huán)境中（MDP）[3-4，9]選擇Q值最大的動(dòng)作執(zhí)行，并根據(jù)執(zhí)行動(dòng)作后的球場(chǎng)評(píng)估來(lái)更新該動(dòng)作的Q值，不帶球球員則使用事先規(guī)定好的策略選擇動(dòng)作，比如，跑位，鏟球等[6]，這樣并不能很好地與帶球球員互相協(xié)作，更不能對(duì)多變的球場(chǎng)狀態(tài)做出很好的反應(yīng)。本文采用改進(jìn)的Q-學(xué)習(xí)算法使得不帶球球員也可以用Q-學(xué)習(xí)算法得到最優(yōu)動(dòng)作來(lái)實(shí)現(xiàn)多Agent之間的協(xié)作，并且約束了算法的使用范圍，從而減少了計(jì)算量，確保了比賽的實(shí)時(shí)性。

2 強(qiáng)化學(xué)習(xí)與Q學(xué)習(xí)

2.1 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)[1]是一種無(wú)指導(dǎo)的學(xué)習(xí)，它的主要思想是“與環(huán)境交互（Interaction with Environment）”和“試錯(cuò)（trial-and-error）”。這也是自然界中人或動(dòng)物學(xué)習(xí)的基本途徑。強(qiáng)化學(xué)習(xí)模型如圖1，在學(xué)習(xí)過(guò)程中，Agent不斷嘗試動(dòng)作選擇，并根據(jù)環(huán)境的反饋信號(hào)調(diào)整動(dòng)作的評(píng)價(jià)值，最終使得Agent能夠獲得最大的回報(bào)值。

圖1 強(qiáng)化學(xué)習(xí)模型

2.2 Q學(xué)習(xí)

Q-學(xué)習(xí)[6]是一種普遍采用的強(qiáng)化學(xué)習(xí)算法。Q學(xué)習(xí)的特點(diǎn)是不需要了解環(huán)境模型，直接通過(guò)學(xué)習(xí)從動(dòng)作序列中得到最優(yōu)的動(dòng)作，因此Q學(xué)習(xí)常被用于解決不確定環(huán)境下的強(qiáng)化學(xué)習(xí)問(wèn)題。

馬爾可夫決策過(guò)程（Markov Decision Process，MDP）理論在強(qiáng)化學(xué)習(xí)中有著堅(jiān)實(shí)的理論基礎(chǔ)，但是它假定的是Agent所處的環(huán)境是固定并且不存在其他自適應(yīng)Agent的，因此它不滿(mǎn)足多Agent環(huán)境；Michael L.Littman提出隨機(jī)對(duì)策[2]（SG）來(lái)作為多Agent強(qiáng)化學(xué)習(xí)的框架，隨機(jī)對(duì)策是將對(duì)策論應(yīng)用到類(lèi)MDP環(huán)境，是MDP的一般化，也是矩陣對(duì)策在多狀態(tài)下的延伸。

隨機(jī)對(duì)策可定義為五元組 ＜ N，S，{A1，A2，…，An}，T，{R1，R2，…，Rn}＞，其中，N 為 n 個(gè)agent的集合，N= {1，2，…，n}，S 是環(huán)境的離散狀態(tài)有限集，Ai為 agenti的動(dòng)作可選集，T:S×A×S→[0，1]為狀態(tài)轉(zhuǎn)移模型。T(si，a，si+1)表示從狀態(tài) si經(jīng)過(guò) agent的聯(lián)合行動(dòng) a= {a1，a2，…，an}到達(dá)狀態(tài) si+1的概率；Ri:S×A×S→R 為agenti的回報(bào)函數(shù)。在隨機(jī)對(duì)策的框架下，Q值可定義為：

其中，α(0＜α＜1)為控制收斂的學(xué)習(xí)率，Vi(st+1)是一個(gè)狀態(tài)值函數(shù)：

Q值是通過(guò)上述公式的反復(fù)迭代而收斂的，上述公式的關(guān)鍵因素是學(xué)習(xí)策略，即行為a的選擇方式和函數(shù)Vi(st+1)的定義[3，6]。不同的選擇方式會(huì)產(chǎn)生不同的多Agent學(xué)習(xí)算法[1]。

3 Agent球員執(zhí)行策略

傳統(tǒng)的球員執(zhí)行策略是根據(jù)決策樹(shù)來(lái)進(jìn)行動(dòng)作選擇的[9-10]，決策樹(shù)的執(zhí)行過(guò)程如圖2。

其中，只有當(dāng)Agent控球時(shí)，才使用球場(chǎng)評(píng)估函數(shù)運(yùn)算得到該Agent下周期的動(dòng)作[6]，如圖3。

圖2 agent球員執(zhí)行的決策樹(shù)

圖3 帶球球員動(dòng)作執(zhí)行框架

而當(dāng)Agent不控球時(shí)，則根據(jù)陣型文件或者一定策略來(lái)執(zhí)行相應(yīng)的動(dòng)作，因此這個(gè)方法嚴(yán)格來(lái)說(shuō)屬于單Agent的學(xué)習(xí)算法，球隊(duì)的協(xié)作很少，進(jìn)攻防守方式單一。下面一章將重點(diǎn)介紹改進(jìn)的多Agent Q學(xué)習(xí)。

4 改進(jìn)的配合策略

4.1 狀態(tài)-動(dòng)作對(duì)的確定

球場(chǎng)上情況復(fù)雜，需要考慮的因素太多。但是要達(dá)到局部的配合，首先要知道自己所處的位置SA和球的位置SB，這樣才能確定球員本身是否出在配合的范圍內(nèi)；其次是否自己控球LA還有是否是我方控球LB，用來(lái)確定配合的策略是防守還是進(jìn)攻。于是將＜SA，SB，LA，LB＞作為球場(chǎng)上局部范圍內(nèi)環(huán)境狀態(tài)的描述。

為了減少因?yàn)镾A，SB連續(xù)的坐標(biāo)信息而增加的環(huán)境狀態(tài)的數(shù)量，對(duì)球場(chǎng)上的位置進(jìn)行了離散。本文中的位置都是在這個(gè)離散方式的基礎(chǔ)上討論的。具體的離散方法如下：將球場(chǎng)劃分為60×10個(gè)小的區(qū)域，其中 X軸方向分為60等份，Y軸方向分為10等份，這樣就可以用一對(duì)離散化的(i，j)來(lái)描述球場(chǎng)上的位置信息。LA，LB的取值為0或1，0表示不控球，1表示控球，當(dāng)球處于自由狀態(tài)時(shí)（即任何一方都不控球），LA，LB取0。

因 此 環(huán) 境 的 狀 態(tài) 信 息 描 述 為 ＜SA，SB，LA，LB＞=＜(iA，jA)，(iB，jB)，{0，1}，{0，1}＞ (0 ≤ i≤ 59，0 ≤ j≤ 9)。

根據(jù)狀態(tài)信息來(lái)確定相應(yīng)動(dòng)作集：當(dāng)Agent為控球球員，動(dòng)作集為上述決策樹(shù)中控球時(shí)的動(dòng)作，即{shoot，pass，cross，dribble，selfpass}；當(dāng) Agent不控球時(shí)，但是控球方為我方時(shí)，動(dòng)作集為{gotopoint，turntoball}；當(dāng)Agent不控球時(shí)且對(duì)方控球時(shí)，動(dòng)作集為{gotopoint，turntoball，tackle}。

4.2 reward值的確定

本文中的reward值的確定比較復(fù)雜，分為：Agent控球，Agent不控球但我方有控球權(quán)，對(duì)方控球三種情況，下面將分別討論這三種情況下的reward值的確定。

4.2.1 Agent控球

（1）我方進(jìn)球，r=1；

（2）球到達(dá)射門(mén)點(diǎn)，r=0.9；

（3）球出界，r=0；

（4）變?yōu)閷?duì)方控球，r=-0.9；

（5）對(duì)方進(jìn)球，r=-1；

（6）否則，r=區(qū)域基礎(chǔ)回報(bào)+區(qū)域內(nèi)部回報(bào)+f(x)。

上述的射門(mén)點(diǎn)是球隊(duì)根據(jù)球隊(duì)特點(diǎn)和禁區(qū)內(nèi)的各種復(fù)雜情況事先計(jì)算出來(lái)的位置，在這些位置射門(mén)時(shí)進(jìn)球的概率很高，因此到達(dá)這些點(diǎn)時(shí)回報(bào)值應(yīng)僅次于進(jìn)球時(shí)的回報(bào)值。

在情況（6）中，繼續(xù)沿用以前的章惠龍等提出的算法[10]，但是區(qū)域的劃分不同，劃分的具體情形如圖4。

圖4 球場(chǎng)劃分策略

如圖4，將球場(chǎng)劃分為關(guān)于 X軸對(duì)稱(chēng)的9個(gè)區(qū)域，將這9個(gè)區(qū)分的基礎(chǔ)回報(bào)分別設(shè)定為-0.4，-0.6，-0.5，-0.3，-0.3，0.3，0.3，0.5，0.7 。

上面兩個(gè)參數(shù)的設(shè)定不僅保證了區(qū)域之間的差異性，也保證了區(qū)域值得連續(xù)性，使得兩個(gè)區(qū)域的交界處的回報(bào)值差距不至于太大。

區(qū)域內(nèi)部回報(bào)是由球員之間的位置關(guān)系確定的，在球隊(duì)中事先用一個(gè)函數(shù)確定在這個(gè)范圍中的最適合配合球員P1和最危險(xiǎn)的對(duì)方球員P2，因此區(qū)域內(nèi)部回報(bào)：

當(dāng) d1＞5.0，區(qū)域內(nèi)部回報(bào) =(XA+(d1-5.0)×2.0× XA-d3)/100；

當(dāng) 3.0＜d1≤5.0，區(qū)域內(nèi)部回報(bào) =(XA+(d1-d2)×2)/ 100；

當(dāng)d1≤3.0，區(qū)域內(nèi)部回報(bào) =(XA-d3)/100-本區(qū)域基礎(chǔ)回報(bào)。

公式中 XA為球的 X坐標(biāo)，d1為P2與球之間的距離，d2為P1與球之間的距離，d3為球與對(duì)方球門(mén)之間的距離。公式中通過(guò)控制XA的倍數(shù)來(lái)控制帶球速度；通過(guò)控制d3的大小來(lái)控制是否將球推向?qū)Ψ角蜷T(mén)；通過(guò)控制d1的大小來(lái)在一定程度上控制是否擺脫P(yáng)2；這里P1、P2是根據(jù)球員是否適合鏟球，有沒(méi)有球員盯住等許多復(fù)雜因素確定的，而不是單純地使用最近的球員，確定方法不是本文重點(diǎn)，這里將不再討論。

4.2.2 Agent不控球但我方有控球權(quán)

（1）如果自身是最佳配合球員，r=區(qū)域基礎(chǔ)回報(bào)+ f(x)+(XB+d4-d5)/100。

（2）如果自身不是最佳配合球員，r=(XB+d4)/100。

其中區(qū)域基礎(chǔ)回報(bào)和 f(x)就是前面討論過(guò)的值，d4為自身與球之間的距離，d5為經(jīng)過(guò)一定方法得到的對(duì)自己最有威脅的對(duì)方球員（一般情況下為離自己最近的對(duì)方球員，除非此隊(duì)員有人盯防）與自己的距離，通過(guò)控制XB的倍數(shù)來(lái)控制跑動(dòng)速度。這樣確定的目的是因?yàn)?，如果自身為最佳配合球員，控球球員可能將球傳給自己，因此要跑向球，并且要保證周?chē)鷽](méi)有對(duì)方球員盯防，如果自身不是最佳配合球員，則跑向?qū)Ψ角騿T進(jìn)行阻擋對(duì)方跑位，此外，由于情況（1）加入了區(qū)域基礎(chǔ)回報(bào)，則會(huì)考慮到區(qū)域之間的差異，盡量向?qū)Ψ角蜷T(mén)方向帶球。

4.2.3 對(duì)方控球

（1）如果得到球，r=1.0；

（2）如果自己是離球最近的球員，r=(XC-d6)/100；

（3）否則，r=(XC+d7×2+d6-d8)/100。

其中，d6為與球的距離，d7為自身與最近對(duì)方球員P3的距離，d8為 P3與球的距離，XC與目標(biāo)的距離有關(guān)，用來(lái)控制球員的跑動(dòng)速度。由此可見(jiàn)，當(dāng)對(duì)方控球時(shí)，己方球員首先是爭(zhēng)取獲得控球權(quán)，如果不能取得控球權(quán)，則先主動(dòng)上前去攔截，否則盯防距離自己最近的進(jìn)攻球員，擋在球與該球員P3之間，防止控球球員傳球。

4.3 更新?tīng)顟B(tài)-動(dòng)作表中的Q值

本文實(shí)驗(yàn)的Q值是按照下面公式進(jìn)行更新的：

Qt+1(s，a)=(1- α)Qt(s，a)+ α[rt+ βV(st+1)] （3）

其中，當(dāng)在訓(xùn)練的時(shí)候α=0.35，當(dāng)Q值趨于穩(wěn)定的時(shí)候 α=0.1，β=0.8，

每個(gè)周期Agent都會(huì)從狀態(tài)-動(dòng)作表中找到對(duì)應(yīng)狀態(tài)中Q值最大的動(dòng)作執(zhí)行，執(zhí)行過(guò)后再根據(jù)上述公式更新對(duì)應(yīng)的Q值。更新時(shí)都會(huì)找到a中的所有動(dòng)作，這時(shí)就要選擇一個(gè)范圍d，在這個(gè)范圍內(nèi)的所有球員都將考慮進(jìn)去，用來(lái)更新Q值，根據(jù)球的最大速度和衰減率得出d=30。

5 實(shí)驗(yàn)及結(jié)果

將上述算法植入到校隊(duì)代碼中并在RoboCup仿真2D的平臺(tái)上進(jìn)行實(shí)驗(yàn)。通過(guò)大量的反復(fù)學(xué)習(xí)，使得Q值收斂于一個(gè)穩(wěn)定的值，以進(jìn)球和配合數(shù)作為統(tǒng)計(jì)數(shù)據(jù)，通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，配合數(shù)和進(jìn)球數(shù)較采用傳統(tǒng)Q學(xué)習(xí)的方法有明顯上升。

如圖5（a）所示，改進(jìn)的多Agent方法進(jìn)攻能力有所提升，圖5（b）所示，改進(jìn)的多Agent Q學(xué)習(xí)的配合數(shù)明顯增多，另外還可以發(fā)現(xiàn)傳統(tǒng)的多Agent Q學(xué)習(xí)的配合數(shù)一直不穩(wěn)定，這說(shuō)明傳統(tǒng)多Agent Q學(xué)習(xí)不存在配合，即使有配合也只是偶然出現(xiàn)的巧合，因?yàn)樗O(shè)計(jì)時(shí)沒(méi)有考慮到Agent配合的情形。當(dāng)Q值趨于穩(wěn)定時(shí)，再進(jìn)行200次防守實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表1。

圖5 進(jìn)球數(shù)和配合數(shù)的統(tǒng)計(jì)數(shù)據(jù)

表1 平均被進(jìn)球數(shù)統(tǒng)計(jì)結(jié)果

從表1可以看出，多Agent Q學(xué)習(xí)的代碼相對(duì)于傳統(tǒng)多Agent Q學(xué)習(xí)代碼，防守實(shí)力都大大增強(qiáng)，與實(shí)驗(yàn)的初始設(shè)計(jì)目標(biāo)相符。

6 結(jié)束語(yǔ)

本文主要是將多Agent的Q學(xué)習(xí)應(yīng)用到了RoboCup仿真2D中，使得球隊(duì)在比賽中配合更多，進(jìn)而使球隊(duì)的進(jìn)攻和防守能力得到一定的增強(qiáng)。實(shí)驗(yàn)結(jié)果表明，學(xué)習(xí)效果有明顯的提高。因此，采用此方法解決RoboCup中的配合問(wèn)題行之有效。采用此方法受到計(jì)算空間和時(shí)間的限制，只能采用局部配合才能保證比賽的實(shí)時(shí)性。

[1]Celiberto L A，Ribeiro C H C.Heuristic reinforcement learning applied to RoboCup simulation agents[C]// LNCS 5001，2008：220-227.

[2]Mota L，Lau N，Reis L P.Co-ordination in RoboCup’s 2D simulation league：setplaysasflexible，multi-robot plans[C]//RAM，2010：362-367.

[3]Bai Aijun，Wu Feng，Chen Xiaoping.Online planning for large MDPs with MAXQ decomposition[C]//Proceedings ofthe 11th InternationalConference on Autonomous Agents and Multiagent Systems，2012：1215-1216.

[4]Zhang Zhongzhang，Chen Xiaoping.A factored hybrid heuristic online planning algorithm for large POMDPs[C]// Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence，2012：934-943.

[5]向中凡.Q學(xué)習(xí)角色值法在機(jī)器人足球比賽中的應(yīng)用[J].電子科技大學(xué)學(xué)報(bào)，2007，36（4）：809-812.

[6]孟祥萍，王欣欣，王圣鑌.多Agent Q學(xué)習(xí)幾點(diǎn)問(wèn)題的研究及改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（9）：2274-2276.

[7]劉亮，李龍澍.基于局部合作的RoboCup多智能體Q-學(xué)習(xí)[J].計(jì)算機(jī)工程，2009，35（9）：11-16.

[8]柯文德，彭志平，蔡則蘇，等.基于π演算的足球機(jī)器人協(xié)作Q學(xué)習(xí)方法[J].計(jì)算機(jī)應(yīng)用，2011，31（3）：654-656.

[9]Kalyanakrishnan S，Liu Y，Stone P.Half field offense in RoboCup soccer：a multiagentreinforcementlearning case study[J].Computer Science，2007，4434：72-85.

[10]章惠龍，李龍澍.Q學(xué)習(xí)在RoboCup前場(chǎng)進(jìn)攻動(dòng)作決策中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（7）：240-242.

[11]顧曉鋒，張代遠(yuǎn).機(jī)器人足球比賽接球策略設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用，2005，25（8）：1858-1859.

[12]李實(shí)，陳江.清華機(jī)器人足球的結(jié)構(gòu)設(shè)計(jì)與實(shí)現(xiàn)[J].清華大學(xué)學(xué)報(bào)，2001，41（7）：94-97.

[13]張波，蔡慶生，陳小平，等.基于智能體團(tuán)隊(duì)的RoboCup仿真球隊(duì)[C]//第三屆全球智能控制與自動(dòng)化大會(huì)論文集，2000.

[14]楊煜普，李曉萌，許曉鳴.多智能協(xié)作技術(shù)綜述[J].信息與控制，2001，30（4）：337-342.

[15]李實(shí)，徐旭明.國(guó)際機(jī)器人足球比賽及其相關(guān)技術(shù)[J].機(jī)器人，2000，22（5）.

ZHAO Fajun,LI Longshu

School of Computer Science and Engineering,Anhui University,Hefei 230601,China

Because many multi-Agent cooperative problems can hardly be solved in RoboCup,this paper investigates a regional cooperative multi-Agent Q-learning method.Through subdividing the stadium area and rewards of agents,the agents’collaboration ability can be strengthened.As a result,the team’s offensive and defensive abilities are enhanced. At the same time,the agents can spend less time learning via restricting the using range of the algorithm.Consequently, the real-time of the game can be ensured.Finally,the experiment on the platform of the simulation 2D proves that the effect of this method is much better than that of the previous one,and it fully complies with the design of the original goal. Key words：stochastic game;Q-learning;real-time;regional cooperation;RoboCup simulation 2D;cooperative strategy

針對(duì)RoboCup（Robot World Cup）中，多Agent之間的配合策略問(wèn)題，采用了一種局部合作的多Agent Q-學(xué)習(xí)方法：通過(guò)細(xì)分球場(chǎng)區(qū)域和Agent回報(bào)值的方法，加強(qiáng)了Agent之間的協(xié)作能力，從而增強(qiáng)了隊(duì)伍的進(jìn)攻和防守能力。同時(shí)通過(guò)約束此算法的使用范圍，減少了學(xué)習(xí)所用的時(shí)間，確保了比賽的實(shí)時(shí)性。最后在仿真2D平臺(tái)上進(jìn)行的實(shí)驗(yàn)證明，該方法比以前的效果更好，完全符合初期的設(shè)計(jì)目標(biāo)。

隨機(jī)對(duì)策；Q-學(xué)習(xí)；實(shí)時(shí)性；局部合作；RoboCup仿真2D；配合策略

A

TP181

10.3778/j.issn.1002-8331.1301-0093

ZHAO Fajun,LI Longshu.RoboCup regional cooperative strategy based on multi-Agent Q-learning.Computer Engineering and Applications,2014,50（23）：127-130.

安徽省自然科學(xué)基金（No.090412054）；安徽高等學(xué)校省級(jí)自然科學(xué)基金（No.KJ2011Z020）。

趙發(fā)君（1988—），男，碩士研究生，主要研究方向?yàn)榉抡鏅C(jī)器人足球研究；李龍澍，教授，博士生導(dǎo)師，主要研究方向?yàn)檐浖O(shè)計(jì)技術(shù)、智能信息處理和Agent應(yīng)用技術(shù)等。E-mail：zhaofajun216@126.com

2013-01-10

2013-02-22

1002-8331（2014）23-0127-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1648.013.html