章惠龍,李龍澍
安徽大學 計算機科學與技術(shù)學院,合肥230039
RoboCup 仿真組比賽是在不受硬件平臺約束的純仿真軟件環(huán)境中進行的,Agent 能夠通過機器學習等方法,達到類似或者接近人類的那種各種選擇的最優(yōu)決策。反應(yīng)到比賽場上,就是使11 個分布式的Agent 在仿真的對抗環(huán)境中,通過協(xié)同工作,能夠最優(yōu)、快速、高效地處理球場上的一切問題,比如說動作選擇的決策、視覺選擇的決策、個體動作的執(zhí)行等。Q 學習常被用于RoboCup 環(huán)境中的強化學習問題,然而大部分是運用在Agent 的個體動作學習上,比如傳球、帶球、射門等。本文將Q 學習運用到局部范圍的RoboCup 前場進攻動作決策中,通過引入?yún)^(qū)域劃分,基于區(qū)域劃分的獎懲函數(shù)和對真人足球賽中動作決策的模擬,使Agent的進攻能力得到一定程度上的加強。
強化學習(Reinforcement Learning,RL)是一種非監(jiān)督的Agent 自學習算法,它的基本思想是從環(huán)境中得到反饋而進行學習,就是所謂的trial and error 學習方法。在學習過程中,Agent 不斷嘗試進行動作選擇,并根據(jù)環(huán)境的反饋信號(即回報)調(diào)整動作的評價值,最終使得Agent 能夠獲得最大回報的策略。
Q 學習算法是一種普遍采用的強化學習算法。Q 學習的特點是不需要知道環(huán)境模型,直接利用經(jīng)歷的動作序列學習最優(yōu)的動作,因此Q 學習常被用于解決不確定環(huán)境下的強化學習問題。
在馬爾科夫決策過程(Markov Decision Processes,MDP)中,Agent 可以感知周圍環(huán)境不同周期時候的不同狀態(tài),并且可以執(zhí)行動作庫中的任何一個動作。在t 周期,環(huán)境狀態(tài)為St,Agent 選擇動作at執(zhí)行后,環(huán)境狀態(tài)由St變?yōu)镾t+1,同時反饋回報r(st,at)給Agent。在以后的每個周期,Agent 重復迭代,直至達到終止周期。用動作評價函數(shù)Q(st,at)表示在st狀態(tài)Agent 選擇動作at后的最大折算累積回報,即由Agent 執(zhí)行動作后的立即回報加上以后每個周期都遵循最優(yōu)策略的值,可以用公式表示為:
其中,γ(0 ≤γ ≤1)為折算因子,是一常量,a 為動作庫中的任一動作。Agent 每周期進行動作選擇時,總是選擇對應(yīng)此狀態(tài)擁有最大Q 值的動作,然后依照此策略進行迭代。經(jīng)過反復的迭代,Q 值不斷的更新,這就是Q 學習算法的學習過程。
為了使Q 學習能夠在適當周期內(nèi)收斂,需要在公式中加入適當大小的學習率。引入學習率α 以后,Q 學習算法的公式可以表示為:
其中,α(0 <α <1)為控制收斂的學習率,γ 為折算因子。
在RoboCup2D 仿真環(huán)境中,Server 為Agent 提供了6種基本原子動作,分別是dash(加速)、turn(身體轉(zhuǎn)向)、kick(踢球)、tackle(鏟球)、catch(撲球)、move(瞬移),其中catch動作只提供給守門員使用。Agent 在一個仿真周期內(nèi)可以任選其一發(fā)送給Server,但是不能重復發(fā)送。而在Client端,球隊可以根據(jù)自己的需要,將這6 種原子動作組合成為一些高級個體動作,供Agent 調(diào)用執(zhí)行。不同的球隊可能擁有自己不同的高級個體動作集。本文依照的是Agent 2D 底層代碼,該底層提供了5 種個體高級動作供Agent 持球時候調(diào)用。由于本文實驗著重研究前場進攻,所以只列出了Agent 持球時候可以執(zhí)行的一些高級動作,并且守門員專有的catch 動作并沒有包括在內(nèi)。
圖1 中,Agent 通過ActionGenerator(動作發(fā)生器)選擇需要執(zhí)行的動作,動作執(zhí)行后WorldModel(世界模型)發(fā)生改變,作用于Field Evaluator(球場評估器),F(xiàn)ield Evaluator反饋一個reward(回報)給Agent,接著Agent 進行下一輪的動作選擇。這個過程就是Agent 的一次動作決策的過程,也就構(gòu)成了Agent 的動作決策框架。仔細觀察該圖不難發(fā)現(xiàn),這個過程與Q 學習的學習過程相當類似,將Action-Generator內(nèi)的動作選擇機制用Q 學習算法進行訓練,Agent的動作決策過程就變成了一個Q 學習算法的學習過程。
圖1 Agent的動作決策框架圖
在Agent 的前場進攻中,需要考慮的因素非常多。大多數(shù)情況下,前場進攻中都會出現(xiàn)這樣一個情況:持球的Agent 面對一個緊逼的防守隊員,旁邊還有一個己方隊員,這時候他該怎么辦。此時就可以選取球的位置(SA),離自己最近的己方球員的位置(SB),離自己最近的對方球員的位置(SC)來描述一個特定的環(huán)境狀態(tài)。持球球員的位置與球的位置大致相同,所以這里就不予考慮了,于是<SA,SB,SC>就可以用來描述球場上局部范圍內(nèi)的一個環(huán)境狀態(tài)。
在球場上是用X 和Y 坐標來描述一個單位的位置的,此時Agent 的位置信息SA、SB、SC都是連續(xù)的,這不利于狀態(tài)描述,需要人工離散它們。本文將前場區(qū)域劃分為30×10個小的區(qū)域,其中X 軸方向分為30 等份,Y 軸方向分為10等份,此時就可以用一對離散化的(i,j)來描述任何一個Agent的位置信息(0 ≤i ≤29,0 ≤j ≤9)。
直接使用Agent 動作決策框架中給出的5 種高級個體動作作為Agent 執(zhí)行的動作集,Agent 的動作集可以表示為:{shoot,pass,cross,dribble,selfpass}。
本文實驗中獎懲回報的確定相對復雜,可以表示如下:
(1)己方進球,r=1;
(2)球到達射門點,r=0.9;
(3)球出界,r=0;
(4)以上情況都不是,r=區(qū)域基礎(chǔ)回報+區(qū)域內(nèi)部回報。
所謂的射門點是綜合前場特別是禁區(qū)內(nèi)的各個因素,經(jīng)過數(shù)學運算得到的射門位置,可以通過給出的球的位置信息直接判斷此時能否進行射門,這里暫不研究。下面著重介紹情況(4)時獎懲回報是如何給出的。
前面討論狀態(tài)描述的時候,為了離散Agent 的位置信息,將前場區(qū)域劃分為了30×10 個小區(qū)域。這里為了確定獎懲回報,將前場區(qū)域劃分為4 個大區(qū)域,關(guān)于X 軸對稱的上下區(qū)塊為同一區(qū)域,劃分之后不同的區(qū)域擁有不同的獎懲基礎(chǔ)回報,球落在哪個區(qū)域,就選擇那個區(qū)域的基礎(chǔ)回報作為整體回報的一部分。
圖2 中相同的號碼代表相同的區(qū)域。4 號區(qū)域基礎(chǔ)回報最大,因為此區(qū)域非常有利于進球,其次為3 號區(qū)域,再其次為1、2 號區(qū)域。如果球隊進攻側(cè)重于中路突破,則2號區(qū)域基礎(chǔ)回報大于1 號區(qū)域;如果側(cè)重于邊路突破,則2號區(qū)域基礎(chǔ)回報小于1 小區(qū)域。
圖2 前場區(qū)域劃分
除了區(qū)域基礎(chǔ)回報外,還需要加上區(qū)域內(nèi)部回報來更加細化整體回報。區(qū)域內(nèi)部回報主要是由球的位置信息和離球最近的對方、己方球員與球之間的距離確定的。
在情況(4)下,r=區(qū)域基礎(chǔ)回報+區(qū)域內(nèi)部回報,需要保證此時的r<0.9,而且區(qū)域基礎(chǔ)回報至少應(yīng)該大于10 倍的區(qū)域內(nèi)部回報。至于具體如何確定這兩種回報,可以有多種方法。在本文的實驗中,1、2、3、4 號區(qū)域的基礎(chǔ)回報分別被設(shè)定為0.5、0.5、0.6、0,7。
通過仔細觀察現(xiàn)實生活中的真人足球賽可以發(fā)現(xiàn)這樣一個現(xiàn)象:一個球員拿到球的時候,當防守隊員距離自己很遠的情況下,他會快速帶球推向?qū)Ψ角蜷T;當防守隊員距離自己稍近但是又不至于能夠搶斷球的情況下,他會慢速帶球試圖擺脫對手,同時觀察場上隊友的位置準備傳球;當防守隊員繼續(xù)逼近以至于可以搶斷球的情況下,他就會將球傳給隊友,或是進行射門。將這種真人足球賽中的動作決策模式引入到區(qū)域內(nèi)部回報中,通過修改區(qū)域內(nèi)部回報,使得Agent 能夠做出接近或者是類似的這種動作決策。本文的實驗中,區(qū)域內(nèi)部回報給定如下:
Ifd1>5.0
區(qū)域內(nèi)部回報=(XA+(d1-5.0)×2.0×XA-d3)/100
If 3.0 <d1≤5.0
區(qū)域內(nèi)部回報=(XA+(d1-d2)×2)/100
Ifd1≤3.0
區(qū)域內(nèi)部回報=(XA-d3)/100-本區(qū)域基礎(chǔ)回報
式中,XA為球的X坐標,d1為離球最近的防守球員與球之間的距離,d2為離球最近的己方球員與球之間的距離,d3為球到對方球門之間的距離。公式中通過控制XA的倍數(shù)來控制帶球速度;通過控制d3的大小來控制是否將球推向?qū)Ψ角蜷T;通過控制d1的大小來在一定程度上控制是否擺脫最近的防守隊員;通過在區(qū)域內(nèi)部回報中減去本區(qū)域基礎(chǔ)回報,使得此時Agent 的總體獎懲回報急劇減小,Agent為了快速擺脫這種狀態(tài),就會進行傳球,或是射門。
從此公式可以看出,當防守隊員距離持球隊員很遠時(d1>5.0),快速帶球推向?qū)Ψ角蜷T;當防守隊員距離持球隊員稍近時(3.0 <d1≤5.0) ,慢速帶球,擺脫防守,尋找傳球點;當防守隊員距離持球隊員很近時(d1≤3.0),將球傳給隊友,或是射門。
本文實驗依照的Q值更新公式為:
其中,規(guī)定α=0.15,γ=0.85。當環(huán)境處于終止狀態(tài)時就可以根據(jù)此公式更新一次Q值。終止狀態(tài)包括己方進球,球出界外,球被對方球員攔截這幾種狀態(tài),一些由于犯規(guī)造成的情況沒有考慮在內(nèi)。
通過大量周期的仿真學習后,各個狀態(tài)下Q值逐漸趨近于收斂到一個穩(wěn)定的值。將經(jīng)過學習訓練后的Agent 投入到實際比賽中,以進球為最終統(tǒng)計數(shù)據(jù),讓Agent 完全按照學習到的Q表進行自主動作決策,取得了良好的效果。特別是訓練場景設(shè)置在禁區(qū)邊緣的時候,Agent 經(jīng)過學習訓練后能夠在小范圍內(nèi)靈活帶球躲避守門員和防守隊員,將球帶到或者傳到射門點,大大增加了射門的次數(shù)。
表1 給出了底層代碼、手工代碼和Q學習代碼分別與UVA 優(yōu)秀代碼、底層代碼進行100 場比賽后,平均每場比賽的進球數(shù)。其中底層代碼是手工代碼和Q學習代碼的基礎(chǔ),手工代碼和Q學習代碼都是在其上經(jīng)過修改而成的,UVA 優(yōu)秀代碼是國內(nèi)一支以UVA 為底層的RoboCup2010全國賽8 強之一的球隊代碼。從表1 中可以看出,Q學習代碼相對于底層代碼和手工代碼,無論對手是UVA 優(yōu)秀代碼還是底層代碼,進攻實力都大大增強,符合實驗的初始設(shè)計目標。
表1 實驗統(tǒng)計結(jié)果
本文將Q學習算法應(yīng)用到RoboCup 前場進攻動作決策中,通過大量周期的訓練學習,使得Agent 能夠進行自主動作決策,進而加強Agent 的進攻能力。通過觀察實驗之后的統(tǒng)計結(jié)果,表明將Q學習應(yīng)用于Agent 的動作決策之中取得了一定的效果。然而不足之處也是很明顯的,如環(huán)境狀態(tài)描述過于簡單粗糙,并沒有細致地描述出球場上的實時狀態(tài)。將此方法應(yīng)用于安徽大學最新版本的DreamWing仿真2D 球隊代碼中,通過進行多場實際的對抗性比賽,發(fā)現(xiàn)球隊進攻能力取得了明顯的提高,符合本文的設(shè)計目標。
[1] Akiyama H,Shimora H.HELIOS2010 team description[C]//Proceedings of the Robocup 2010 Conference,2010.
[2] 馬勇,李龍澍,李學俊.基于Q學習的Agent 智能防守策略研究與應(yīng)用[J].計算機技算與發(fā)展,2008,18(12).
[3] 周勇,劉峰.基于改進的Q學習的RoboCup 傳球策略研究[J].計算機技術(shù)與發(fā)展,2008(4):63-66.
[4] Kostas K,Hu Huosheng.Reinforcement learning and co-operation in a simulated multi-agent system[C]//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems,17-21 Oct,1999,2:990-995.
[5] de Boer R,Kok J.The incremental development of a synthetic multi-agent system:the UVA Trilearn 2001 robotic soccer simulation team[D].The Netherlands:University of Amsterdam,2002.