Q 學習在RoboCup 前場進攻動作決策中的應(yīng)用

章惠龍，李龍澍

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

1 引言

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的進攻能力得到一定程度上的加強。

2 Q 學習算法

強化學習（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)為控制收斂的學習率，γ 為折算因子。

3 Agent動作決策框架

在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的動作決策框架圖

4 使用Q學習算法進行Agent前場局部進攻訓練

4.1 狀態(tài)描述

在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)。

4.2 動作集的確定

直接使用Agent 動作決策框架中給出的5 種高級個體動作作為Agent 執(zhí)行的動作集，Agent 的動作集可以表示為：{shoot，pass，cross，dribble，selfpass}。

4.3 獎懲回報的確定

本文實驗中獎懲回報的確定相對復雜，可以表示如下：

（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)，將球傳給隊友，或是射門。

4.4 Q 值的更新

本文實驗依照的Q值更新公式為：

其中，規(guī)定α=0.15,γ=0.85。當環(huán)境處于終止狀態(tài)時就可以根據(jù)此公式更新一次Q值。終止狀態(tài)包括己方進球，球出界外，球被對方球員攔截這幾種狀態(tài)，一些由于犯規(guī)造成的情況沒有考慮在內(nèi)。

4.5 實驗結(jié)果

通過大量周期的仿真學習后，各個狀態(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é)果

5 結(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.