章惠龍，李龍澍

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

1 引言

RoboCup 仿真組比賽是在不受硬件平臺約束的純仿真軟件環(huán)境中進(jìn)行的，Agent 能夠通過機(jī)器學(xué)習(xí)等方法，達(dá)到類似或者接近人類的那種各種選擇的最優(yōu)決策。反應(yīng)到比賽場上，就是使11 個分布式的Agent 在仿真的對抗環(huán)境中，通過協(xié)同工作，能夠最優(yōu)、快速、高效地處理球場上的一切問題，比如說動作選擇的決策、視覺選擇的決策、個體動作的執(zhí)行等。Q 學(xué)習(xí)常被用于RoboCup 環(huán)境中的強(qiáng)化學(xué)習(xí)問題，然而大部分是運(yùn)用在Agent 的個體動作學(xué)習(xí)上，比如傳球、帶球、射門等。本文將Q 學(xué)習(xí)運(yùn)用到局部范圍的RoboCup 前場進(jìn)攻動作決策中，通過引入?yún)^(qū)域劃分，基于區(qū)域劃分的獎懲函數(shù)和對真人足球賽中動作決策的模擬，使Agent的進(jìn)攻能力得到一定程度上的加強(qiáng)。

2 Q 學(xué)習(xí)算法

強(qiáng)化學(xué)習(xí)（Reinforcement Learning，RL）是一種非監(jiān)督的Agent 自學(xué)習(xí)算法，它的基本思想是從環(huán)境中得到反饋而進(jìn)行學(xué)習(xí)，就是所謂的trial and error 學(xué)習(xí)方法。在學(xué)習(xí)過程中，Agent 不斷嘗試進(jìn)行動作選擇，并根據(jù)環(huán)境的反饋信號（即回報(bào)）調(diào)整動作的評價(jià)值，最終使得Agent 能夠獲得最大回報(bào)的策略。

Q 學(xué)習(xí)算法是一種普遍采用的強(qiáng)化學(xué)習(xí)算法。Q 學(xué)習(xí)的特點(diǎn)是不需要知道環(huán)境模型，直接利用經(jīng)歷的動作序列學(xué)習(xí)最優(yōu)的動作，因此Q 學(xué)習(xí)常被用于解決不確定環(huán)境下的強(qiáng)化學(xué)習(xí)問題。

在馬爾科夫決策過程（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，同時反饋回報(bào)r(st,at)給Agent。在以后的每個周期，Agent 重復(fù)迭代，直至達(dá)到終止周期。用動作評價(jià)函數(shù)Q(st,at)表示在st狀態(tài)Agent 選擇動作at后的最大折算累積回報(bào)，即由Agent 執(zhí)行動作后的立即回報(bào)加上以后每個周期都遵循最優(yōu)策略的值，可以用公式表示為：

其中，γ(0 ≤γ ≤1)為折算因子，是一常量，a 為動作庫中的任一動作。Agent 每周期進(jìn)行動作選擇時，總是選擇對應(yīng)此狀態(tài)擁有最大Q 值的動作，然后依照此策略進(jìn)行迭代。經(jīng)過反復(fù)的迭代，Q 值不斷的更新，這就是Q 學(xué)習(xí)算法的學(xué)習(xí)過程。

為了使Q 學(xué)習(xí)能夠在適當(dāng)周期內(nèi)收斂，需要在公式中加入適當(dāng)大小的學(xué)習(xí)率。引入學(xué)習(xí)率α 以后，Q 學(xué)習(xí)算法的公式可以表示為：

其中，α(0 ＜α ＜1)為控制收斂的學(xué)習(xí)率，γ 為折算因子。

3 Agent動作決策框架

在RoboCup2D 仿真環(huán)境中，Server 為Agent 提供了6種基本原子動作，分別是dash（加速）、turn（身體轉(zhuǎn)向）、kick（踢球）、tackle（鏟球）、catch（撲球）、move（瞬移），其中catch動作只提供給守門員使用。Agent 在一個仿真周期內(nèi)可以任選其一發(fā)送給Server，但是不能重復(fù)發(fā)送。而在Client端，球隊(duì)可以根據(jù)自己的需要，將這6 種原子動作組合成為一些高級個體動作，供Agent 調(diào)用執(zhí)行。不同的球隊(duì)可能擁有自己不同的高級個體動作集。本文依照的是Agent 2D 底層代碼，該底層提供了5 種個體高級動作供Agent 持球時候調(diào)用。由于本文實(shí)驗(yàn)著重研究前場進(jìn)攻，所以只列出了Agent 持球時候可以執(zhí)行的一些高級動作，并且守門員專有的catch 動作并沒有包括在內(nèi)。

圖1 中，Agent 通過ActionGenerator（動作發(fā)生器）選擇需要執(zhí)行的動作，動作執(zhí)行后WorldModel（世界模型）發(fā)生改變，作用于Field Evaluator（球場評估器），F(xiàn)ield Evaluator反饋一個reward（回報(bào)）給Agent，接著Agent 進(jìn)行下一輪的動作選擇。這個過程就是Agent 的一次動作決策的過程，也就構(gòu)成了Agent 的動作決策框架。仔細(xì)觀察該圖不難發(fā)現(xiàn)，這個過程與Q 學(xué)習(xí)的學(xué)習(xí)過程相當(dāng)類似，將Action-Generator內(nèi)的動作選擇機(jī)制用Q 學(xué)習(xí)算法進(jìn)行訓(xùn)練，Agent的動作決策過程就變成了一個Q 學(xué)習(xí)算法的學(xué)習(xí)過程。

圖1 Agent的動作決策框架圖

4 使用Q學(xué)習(xí)算法進(jìn)行Agent前場局部進(jìn)攻訓(xùn)練

4.1 狀態(tài)描述

在Agent 的前場進(jìn)攻中，需要考慮的因素非常多。大多數(shù)情況下，前場進(jìn)攻中都會出現(xiàn)這樣一個情況：持球的Agent 面對一個緊逼的防守隊(duì)員，旁邊還有一個己方隊(duì)員，這時候他該怎么辦。此時就可以選取球的位置(SA),離自己最近的己方球員的位置(SB),離自己最近的對方球員的位置(SC)來描述一個特定的環(huán)境狀態(tài)。持球球員的位置與球的位置大致相同，所以這里就不予考慮了，于是＜SA,SB,SC＞就可以用來描述球場上局部范圍內(nèi)的一個環(huán)境狀態(tài)。

在球場上是用X 和Y 坐標(biāo)來描述一個單位的位置的，此時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 獎懲回報(bào)的確定

本文實(shí)驗(yàn)中獎懲回報(bào)的確定相對復(fù)雜，可以表示如下：

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

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

（3）球出界，r=0；

（4）以上情況都不是，r=區(qū)域基礎(chǔ)回報(bào)+區(qū)域內(nèi)部回報(bào)。

所謂的射門點(diǎn)是綜合前場特別是禁區(qū)內(nèi)的各個因素，經(jīng)過數(shù)學(xué)運(yùn)算得到的射門位置，可以通過給出的球的位置信息直接判斷此時能否進(jìn)行射門，這里暫不研究。下面著重介紹情況（4）時獎懲回報(bào)是如何給出的。

前面討論狀態(tài)描述的時候，為了離散Agent 的位置信息，將前場區(qū)域劃分為了30×10 個小區(qū)域。這里為了確定獎懲回報(bào)，將前場區(qū)域劃分為4 個大區(qū)域，關(guān)于X 軸對稱的上下區(qū)塊為同一區(qū)域，劃分之后不同的區(qū)域擁有不同的獎懲基礎(chǔ)回報(bào)，球落在哪個區(qū)域，就選擇那個區(qū)域的基礎(chǔ)回報(bào)作為整體回報(bào)的一部分。

圖2 中相同的號碼代表相同的區(qū)域。4 號區(qū)域基礎(chǔ)回報(bào)最大，因?yàn)榇藚^(qū)域非常有利于進(jìn)球，其次為3 號區(qū)域，再其次為1、2 號區(qū)域。如果球隊(duì)進(jìn)攻側(cè)重于中路突破，則2號區(qū)域基礎(chǔ)回報(bào)大于1 號區(qū)域；如果側(cè)重于邊路突破，則2號區(qū)域基礎(chǔ)回報(bào)小于1 小區(qū)域。

圖2 前場區(qū)域劃分

除了區(qū)域基礎(chǔ)回報(bào)外，還需要加上區(qū)域內(nèi)部回報(bào)來更加細(xì)化整體回報(bào)。區(qū)域內(nèi)部回報(bào)主要是由球的位置信息和離球最近的對方、己方球員與球之間的距離確定的。

在情況（4）下，r=區(qū)域基礎(chǔ)回報(bào)+區(qū)域內(nèi)部回報(bào)，需要保證此時的r＜0.9，而且區(qū)域基礎(chǔ)回報(bào)至少應(yīng)該大于10 倍的區(qū)域內(nèi)部回報(bào)。至于具體如何確定這兩種回報(bào)，可以有多種方法。在本文的實(shí)驗(yàn)中，1、2、3、4 號區(qū)域的基礎(chǔ)回報(bào)分別被設(shè)定為0.5、0.5、0.6、0，7。

通過仔細(xì)觀察現(xiàn)實(shí)生活中的真人足球賽可以發(fā)現(xiàn)這樣一個現(xiàn)象：一個球員拿到球的時候，當(dāng)防守隊(duì)員距離自己很遠(yuǎn)的情況下，他會快速帶球推向?qū)Ψ角蜷T；當(dāng)防守隊(duì)員距離自己稍近但是又不至于能夠搶斷球的情況下，他會慢速帶球試圖擺脫對手，同時觀察場上隊(duì)友的位置準(zhǔn)備傳球；當(dāng)防守隊(duì)員繼續(xù)逼近以至于可以搶斷球的情況下，他就會將球傳給隊(duì)友，或是進(jìn)行射門。將這種真人足球賽中的動作決策模式引入到區(qū)域內(nèi)部回報(bào)中，通過修改區(qū)域內(nèi)部回報(bào)，使得Agent 能夠做出接近或者是類似的這種動作決策。本文的實(shí)驗(yàn)中，區(qū)域內(nèi)部回報(bào)給定如下：

Ifd1＞5.0

區(qū)域內(nèi)部回報(bào)=(XA+(d1-5.0)×2.0×XA-d3)/100

If 3.0 ＜d1≤5.0

區(qū)域內(nèi)部回報(bào)=(XA+(d1-d2)×2)/100

Ifd1≤3.0

區(qū)域內(nèi)部回報(bào)=(XA-d3)/100-本區(qū)域基礎(chǔ)回報(bào)

式中，XA為球的X坐標(biāo)，d1為離球最近的防守球員與球之間的距離，d2為離球最近的己方球員與球之間的距離，d3為球到對方球門之間的距離。公式中通過控制XA的倍數(shù)來控制帶球速度；通過控制d3的大小來控制是否將球推向?qū)Ψ角蜷T；通過控制d1的大小來在一定程度上控制是否擺脫最近的防守隊(duì)員；通過在區(qū)域內(nèi)部回報(bào)中減去本區(qū)域基礎(chǔ)回報(bào)，使得此時Agent 的總體獎懲回報(bào)急劇減小，Agent為了快速擺脫這種狀態(tài)，就會進(jìn)行傳球，或是射門。

從此公式可以看出，當(dāng)防守隊(duì)員距離持球隊(duì)員很遠(yuǎn)時(d1＞5.0)，快速帶球推向?qū)Ψ角蜷T；當(dāng)防守隊(duì)員距離持球隊(duì)員稍近時(3.0 ＜d1≤5.0) ，慢速帶球，擺脫防守，尋找傳球點(diǎn)；當(dāng)防守隊(duì)員距離持球隊(duì)員很近時(d1≤3.0)，將球傳給隊(duì)友，或是射門。

4.4 Q 值的更新

本文實(shí)驗(yàn)依照的Q值更新公式為：

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

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

通過大量周期的仿真學(xué)習(xí)后，各個狀態(tài)下Q值逐漸趨近于收斂到一個穩(wěn)定的值。將經(jīng)過學(xué)習(xí)訓(xùn)練后的Agent 投入到實(shí)際比賽中，以進(jìn)球?yàn)樽罱K統(tǒng)計(jì)數(shù)據(jù)，讓Agent 完全按照學(xué)習(xí)到的Q表進(jìn)行自主動作決策，取得了良好的效果。特別是訓(xùn)練場景設(shè)置在禁區(qū)邊緣的時候，Agent 經(jīng)過學(xué)習(xí)訓(xùn)練后能夠在小范圍內(nèi)靈活帶球躲避守門員和防守隊(duì)員，將球帶到或者傳到射門點(diǎn)，大大增加了射門的次數(shù)。

表1 給出了底層代碼、手工代碼和Q學(xué)習(xí)代碼分別與UVA 優(yōu)秀代碼、底層代碼進(jìn)行100 場比賽后，平均每場比賽的進(jìn)球數(shù)。其中底層代碼是手工代碼和Q學(xué)習(xí)代碼的基礎(chǔ)，手工代碼和Q學(xué)習(xí)代碼都是在其上經(jīng)過修改而成的，UVA 優(yōu)秀代碼是國內(nèi)一支以UVA 為底層的RoboCup2010全國賽8 強(qiáng)之一的球隊(duì)代碼。從表1 中可以看出，Q學(xué)習(xí)代碼相對于底層代碼和手工代碼，無論對手是UVA 優(yōu)秀代碼還是底層代碼，進(jìn)攻實(shí)力都大大增強(qiáng)，符合實(shí)驗(yàn)的初始設(shè)計(jì)目標(biāo)。

表1 實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

5 結(jié)束語

本文將Q學(xué)習(xí)算法應(yīng)用到RoboCup 前場進(jìn)攻動作決策中，通過大量周期的訓(xùn)練學(xué)習(xí)，使得Agent 能夠進(jìn)行自主動作決策，進(jìn)而加強(qiáng)Agent 的進(jìn)攻能力。通過觀察實(shí)驗(yàn)之后的統(tǒng)計(jì)結(jié)果，表明將Q學(xué)習(xí)應(yīng)用于Agent 的動作決策之中取得了一定的效果。然而不足之處也是很明顯的，如環(huán)境狀態(tài)描述過于簡單粗糙，并沒有細(xì)致地描述出球場上的實(shí)時狀態(tài)。將此方法應(yīng)用于安徽大學(xué)最新版本的DreamWing仿真2D 球隊(duì)代碼中，通過進(jìn)行多場實(shí)際的對抗性比賽，發(fā)現(xiàn)球隊(duì)進(jìn)攻能力取得了明顯的提高，符合本文的設(shè)計(jì)目標(biāo)。

[1] Akiyama H，Shimora H.HELIOS2010 team description[C]//Proceedings of the Robocup 2010 Conference，2010.

[2] 馬勇，李龍澍，李學(xué)俊.基于Q學(xué)習(xí)的Agent 智能防守策略研究與應(yīng)用[J].計(jì)算機(jī)技算與發(fā)展，2008，18（12）.

[3] 周勇，劉峰.基于改進(jìn)的Q學(xué)習(xí)的RoboCup 傳球策略研究[J].計(jì)算機(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.