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

趙發(fā)君，李龍澍

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

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

趙發(fā)君，李龍澍

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

1 引言

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

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

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

2.1 強化學(xué)習(xí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 狀態(tài)-動作對的確定

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

為了減少因為SA，SB連續(xù)的坐標(biāo)信息而增加的環(huán)境狀態(tài)的數(shù)量，對球場上的位置進(jìn)行了離散。本文中的位置都是在這個離散方式的基礎(chǔ)上討論的。具體的離散方法如下：將球場劃分為60×10個小的區(qū)域，其中 X軸方向分為60等份，Y軸方向分為10等份，這樣就可以用一對離散化的(i，j)來描述球場上的位置信息。LA，LB的取值為0或1，0表示不控球，1表示控球，當(dāng)球處于自由狀態(tài)時（即任何一方都不控球），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)信息來確定相應(yīng)動作集：當(dāng)Agent為控球球員，動作集為上述決策樹中控球時的動作，即{shoot，pass，cross，dribble，selfpass}；當(dāng) Agent不控球時，但是控球方為我方時，動作集為{gotopoint，turntoball}；當(dāng)Agent不控球時且對方控球時，動作集為{gotopoint，turntoball，tackle}。

4.2 reward值的確定

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

4.2.1 Agent控球

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

（2）球到達(dá)射門點，r=0.9；

（3）球出界，r=0；

（4）變?yōu)閷Ψ娇厍颍瑀=-0.9；

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

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

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

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

圖4 球場劃分策略

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

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

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

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

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

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

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

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

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

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

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

4.2.3 對方控球

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

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

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

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

4.3 更新狀態(tài)-動作表中的Q值

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

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

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

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

5 實驗及結(jié)果

將上述算法植入到校隊代碼中并在RoboCup仿真2D的平臺上進(jìn)行實驗。通過大量的反復(fù)學(xué)習(xí)，使得Q值收斂于一個穩(wěn)定的值，以進(jìn)球和配合數(shù)作為統(tǒng)計數(shù)據(jù)，通過實驗發(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)定，這說明傳統(tǒng)多Agent Q學(xué)習(xí)不存在配合，即使有配合也只是偶然出現(xiàn)的巧合，因為它設(shè)計時沒有考慮到Agent配合的情形。當(dāng)Q值趨于穩(wěn)定時，再進(jìn)行200次防守實驗，實驗結(jié)果如表1。

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

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

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

6 結(jié)束語

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

[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í)角色值法在機器人足球比賽中的應(yīng)用[J].電子科技大學(xué)學(xué)報，2007，36（4）：809-812.

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

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

[8]柯文德，彭志平，蔡則蘇，等.基于π演算的足球機器人協(xié)作Q學(xué)習(xí)方法[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前場進(jìn)攻動作決策中的應(yīng)用[J].計算機工程與應(yīng)用，2013，49（7）：240-242.

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

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

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

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

[15]李實，徐旭明.國際機器人足球比賽及其相關(guān)技術(shù)[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

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

隨機對策；Q-學(xué)習(xí)；實時性；局部合作；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é)校省級自然科學(xué)基金（No.KJ2011Z020）。

趙發(fā)君（1988—），男，碩士研究生，主要研究方向為仿真機器人足球研究；李龍澍，教授，博士生導(dǎo)師，主要研究方向為軟件設(shè)計技術(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