基于多Agent Q學習的RoboCup局部配合策略

趙發君，李龍澍

安徽大學 計算機科學與技術學院，合肥 230601

基于多Agent Q學習的RoboCup局部配合策略

趙發君，李龍澍

安徽大學 計算機科學與技術學院，合肥 230601

1 引言

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

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

2 強化學習與Q學習

2.1 強化學習

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

圖1 強化學習模型

2.2 Q學習

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

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

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

其中，α(0＜α＜1)為控制收斂的學習率，Vi(st+1)是一個狀態值函數：

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

3 Agent球員執行策略

傳統的球員執行策略是根據決策樹來進行動作選擇的[9-10]，決策樹的執行過程如圖2。

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

圖2 agent球員執行的決策樹

圖3 帶球球員動作執行框架

而當Agent不控球時，則根據陣型文件或者一定策略來執行相應的動作，因此這個方法嚴格來說屬于單Agent的學習算法，球隊的協作很少，進攻防守方式單一。下面一章將重點介紹改進的多Agent Q學習。

4 改進的配合策略

4.1 狀態-動作對的確定

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

為了減少因為SA，SB連續的坐標信息而增加的環境狀態的數量，對球場上的位置進行了離散。本文中的位置都是在這個離散方式的基礎上討論的。具體的離散方法如下：將球場劃分為60×10個小的區域，其中 X軸方向分為60等份，Y軸方向分為10等份，這樣就可以用一對離散化的(i，j)來描述球場上的位置信息。LA，LB的取值為0或1，0表示不控球，1表示控球，當球處于自由狀態時（即任何一方都不控球），LA，LB取0。

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

根據狀態信息來確定相應動作集：當Agent為控球球員，動作集為上述決策樹中控球時的動作，即{shoot，pass，cross，dribble，selfpass}；當 Agent不控球時，但是控球方為我方時，動作集為{gotopoint，turntoball}；當Agent不控球時且對方控球時，動作集為{gotopoint，turntoball，tackle}。

4.2 reward值的確定

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

4.2.1 Agent控球

（1）我方進球，r=1；

（2）球到達射門點，r=0.9；

（3）球出界，r=0；

（4）變為對方控球，r=-0.9；

（5）對方進球，r=-1；

（6）否則，r=區域基礎回報+區域內部回報+f(x)。

上述的射門點是球隊根據球隊特點和禁區內的各種復雜情況事先計算出來的位置，在這些位置射門時進球的概率很高，因此到達這些點時回報值應僅次于進球時的回報值。

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

圖4 球場劃分策略

如圖4，將球場劃分為關于 X軸對稱的9個區域，將這9個區分的基礎回報分別設定為-0.4，-0.6，-0.5，-0.3，-0.3，0.3，0.3，0.5，0.7 。

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

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

當 d1＞5.0，區域內部回報 =(XA+(d1-5.0)×2.0× XA-d3)/100；

當 3.0＜d1≤5.0，區域內部回報 =(XA+(d1-d2)×2)/ 100；

當d1≤3.0，區域內部回報 =(XA-d3)/100-本區域基礎回報。

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

4.2.2 Agent不控球但我方有控球權

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

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

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

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與目標的距離有關，用來控制球員的跑動速度。由此可見，當對方控球時，己方球員首先是爭取獲得控球權，如果不能取得控球權，則先主動上前去攔截，否則盯防距離自己最近的進攻球員，擋在球與該球員P3之間，防止控球球員傳球。

4.3 更新狀態-動作表中的Q值

本文實驗的Q值是按照下面公式進行更新的：

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

其中，當在訓練的時候α=0.35，當Q值趨于穩定的時候 α=0.1，β=0.8，

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

5 實驗及結果

將上述算法植入到校隊代碼中并在RoboCup仿真2D的平臺上進行實驗。通過大量的反復學習，使得Q值收斂于一個穩定的值，以進球和配合數作為統計數據，通過實驗發現，配合數和進球數較采用傳統Q學習的方法有明顯上升。

如圖5（a）所示，改進的多Agent方法進攻能力有所提升，圖5（b）所示，改進的多Agent Q學習的配合數明顯增多，另外還可以發現傳統的多Agent Q學習的配合數一直不穩定，這說明傳統多Agent Q學習不存在配合，即使有配合也只是偶然出現的巧合，因為它設計時沒有考慮到Agent配合的情形。當Q值趨于穩定時，再進行200次防守實驗，實驗結果如表1。

圖5 進球數和配合數的統計數據

表1 平均被進球數統計結果

從表1可以看出，多Agent Q學習的代碼相對于傳統多Agent Q學習代碼，防守實力都大大增強，與實驗的初始設計目標相符。

6 結束語

本文主要是將多Agent的Q學習應用到了RoboCup仿真2D中，使得球隊在比賽中配合更多，進而使球隊的進攻和防守能力得到一定的增強。實驗結果表明，學習效果有明顯的提高。因此，采用此方法解決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學習角色值法在機器人足球比賽中的應用[J].電子科技大學學報，2007，36（4）：809-812.

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

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

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

[11]顧曉鋒，張代遠.機器人足球比賽接球策略設計[J].計算機應用，2005，25（8）：1858-1859.

[12]李實，陳江.清華機器人足球的結構設計與實現[J].清華大學學報，2001，41（7）：94-97.

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

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

[15]李實，徐旭明.國際機器人足球比賽及其相關技術[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-學習方法：通過細分球場區域和Agent回報值的方法，加強了Agent之間的協作能力，從而增強了隊伍的進攻和防守能力。同時通過約束此算法的使用范圍，減少了學習所用的時間，確保了比賽的實時性。最后在仿真2D平臺上進行的實驗證明，該方法比以前的效果更好，完全符合初期的設計目標。

隨機對策；Q-學習；實時性；局部合作；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.

安徽省自然科學基金（No.090412054）；安徽高等學校省級自然科學基金（No.KJ2011Z020）。

趙發君（1988—），男，碩士研究生，主要研究方向為仿真機器人足球研究；李龍澍，教授，博士生導師，主要研究方向為軟件設計技術、智能信息處理和Agent應用技術等。E-mail：zhaofajun216@126.com

2013-01-10

2013-02-22

1002-8331（2014）23-0127-04

CNKI網絡優先出版：2013-04-08,http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1648.013.html