性能勢(shì)算法研究及在RoboCup中的應(yīng)用

楊宛璐，陳 瑋，黃浩暉，王廣濤

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣東 廣州510006）

0 引 言

強(qiáng)化學(xué)習(xí)（reinforcement learning）［1］是解決智能體尋優(yōu)路徑的有效手段，通過(guò)與環(huán)境不斷交互來(lái)改進(jìn)自身行為最終獲得最優(yōu)行為策略，在各個(gè)機(jī)器學(xué)習(xí)領(lǐng)域都有廣泛的應(yīng)用。強(qiáng)化學(xué)習(xí)分為兩種類型：折扣獎(jiǎng)賞強(qiáng)化學(xué)習(xí)和平均獎(jiǎng)賞強(qiáng)化學(xué)習(xí)。傳統(tǒng)的平均獎(jiǎng)賞類型強(qiáng)化學(xué)習(xí)更多考慮當(dāng)前動(dòng)作對(duì)未來(lái)的影響，適于解決不具有終結(jié)狀態(tài)或者具有循環(huán)特性的問(wèn)題，但其研究還處于一個(gè)初級(jí)階段。早期，Schwarz提出了一種平均獎(jiǎng)賞學(xué)習(xí)算法R－learning，采用值迭代的思想來(lái)獲得最優(yōu)策略，用于解決平均獎(jiǎng)賞的MDP問(wèn)題［2］；后來(lái)Tadepalli提出基于模型的H－learning［3］。這兩種算法都是基于值迭代，但是某個(gè)策略的平均獎(jiǎng)賞和的逼近過(guò)程并不是很穩(wěn)定，并且其對(duì)參數(shù)環(huán)境的敏感也是一大弊端。隨后，高陽(yáng)等人［4］將性能勢(shì)理論引入到強(qiáng)化學(xué)習(xí)技術(shù)中，得到一種新的平均獎(jiǎng)賞強(qiáng)化學(xué)習(xí)算法G－learning。該算法主要針對(duì)的是單鏈馬爾科夫過(guò)程，對(duì)于多智能體這種非馬爾科夫環(huán)境，直接使用的效果并不好。文獻(xiàn)［5］提出了一種在多鏈馬爾科夫狀態(tài)下，求取平均代價(jià)的方法；文獻(xiàn)［6］結(jié)合敏感性分析方法（sensitivity－based approach）［7］和優(yōu)化幾何方差方法（geometric variance reduction）［8］提出了基于性能勢(shì)的預(yù)估平均獎(jiǎng)賞方法。本文把改進(jìn)的G－learning引入到多智能體系統(tǒng)中，考慮其它馬爾科夫鏈對(duì)agent所產(chǎn)生的影響。算法選擇最優(yōu)的參照系，旨在加快其收斂速度，并成功應(yīng)用在Keepaway平臺(tái)上，降低了狀態(tài)空間的大小，從而達(dá)到了預(yù)期學(xué)習(xí)效果，加快了學(xué)習(xí)過(guò)程。

1 強(qiáng)化學(xué)習(xí)

在人工智能領(lǐng)域中，強(qiáng)化學(xué)習(xí)是一種重要的解決學(xué)習(xí)問(wèn)題的方法。在強(qiáng)化學(xué)習(xí)中，agent通過(guò)與環(huán)境的交互獲得知識(shí)，以此來(lái)改進(jìn)自身的行為。試錯(cuò)和回報(bào)是強(qiáng)化學(xué)習(xí)的兩個(gè)最顯著的特征，它主要是依靠環(huán)境對(duì)所采取行為的反饋信息來(lái)評(píng)價(jià)，并根據(jù)評(píng)價(jià)去指導(dǎo)以后的行為，使行為效果更佳，通過(guò)試探得到的較優(yōu)的行為策略來(lái)適應(yīng)環(huán)境。強(qiáng)化學(xué)習(xí)將環(huán)境映射到動(dòng)作形成策略，最終目標(biāo)是獲得使得長(zhǎng)期的積累的最大獎(jiǎng)賞大的策略。在強(qiáng)化學(xué)習(xí)中，存在兩種評(píng)價(jià)獎(jiǎng)賞值的標(biāo)準(zhǔn)，折扣累積獎(jiǎng)賞值式（1）和平均累積獎(jiǎng)賞值式（2）。近年，研究更多的是折扣累積獎(jiǎng)賞值，它注重的是近期的回報(bào)，表示當(dāng)前動(dòng)作對(duì)agent的影響，注重的是眼前的利益，符合大多數(shù)一般問(wèn)題的求解。然而，對(duì)于不具終結(jié)狀態(tài)或者具有循環(huán)特點(diǎn)的問(wèn)題，便顯得不適用。因此，對(duì)于注重長(zhǎng)遠(yuǎn)利益的問(wèn)題，需要更多地考慮當(dāng)前動(dòng)作的決策對(duì)未來(lái)環(huán)境的影響，平均獎(jiǎng)賞強(qiáng)化學(xué)習(xí)方法更適于解決這類問(wèn)題

1.1 平均獎(jiǎng)賞強(qiáng)化學(xué)習(xí)

R－learning是一種典型的無(wú)模型的平均獎(jiǎng)賞強(qiáng)化學(xué)習(xí)算法，它在學(xué)習(xí)的過(guò)程中環(huán)境模型是不可知的。R－learning由4個(gè)關(guān)鍵部分組成：策略函數(shù)、回報(bào)函數(shù)、值函數(shù)、環(huán)境模型。策略函數(shù)被定義成從觀察到的狀態(tài)到選擇的動(dòng)作的映射；回報(bào)函數(shù)可以看作是強(qiáng)化學(xué)習(xí)的目標(biāo)，在每一步學(xué)習(xí)過(guò)程中，回報(bào)函數(shù)估計(jì)智能體與環(huán)境之間的相互作用的效果，智能體的學(xué)習(xí)目標(biāo)是使的長(zhǎng)期積累獎(jiǎng)賞值最大化，換句話說(shuō)，回報(bào)的狀態(tài)到選擇的動(dòng)作的映射；回報(bào)函數(shù)可以看作是強(qiáng)化學(xué)習(xí)的目標(biāo)，在每一步學(xué)習(xí)過(guò)程中，回報(bào)函數(shù)估計(jì)智能體與環(huán)境之間的相互作用的效果，智能體的學(xué)習(xí)目標(biāo)是使的長(zhǎng)期積累獎(jiǎng)賞值最大化，換句話說(shuō)，回報(bào)函數(shù)可以確定哪些動(dòng)作會(huì)更適于現(xiàn)在的環(huán)境，哪些動(dòng)作被忽略掉；值函數(shù)用來(lái)估計(jì)這些被選擇動(dòng)作的獎(jiǎng)賞值；而環(huán)境模型是用來(lái)模擬智能體的學(xué)習(xí)環(huán)境。

但是在目前已有的一些平均獎(jiǎng)賞強(qiáng)化學(xué)習(xí)方法中，都采用采樣的方式逼近某個(gè)策略的平均獎(jiǎng)賞和，由于在逼近過(guò)程中并不穩(wěn)定，則導(dǎo)致已有學(xué)習(xí)算法不穩(wěn)定。高陽(yáng)等人將性能勢(shì)理論應(yīng)用到強(qiáng)化學(xué)習(xí)算法中，用相對(duì)參考狀態(tài)來(lái)替代平均獎(jiǎng)賞和，獲得一種新的平均獎(jiǎng)賞強(qiáng)化學(xué)習(xí)算法——G－learning學(xué)習(xí)算法。

1.2 性能勢(shì)以及基于性能勢(shì)的無(wú)折扣強(qiáng)化學(xué)習(xí)算法

假定有一個(gè)可重復(fù)且各態(tài)歷經(jīng)的Markov 鏈X ＝｛Xn：n≥0｝ 在有限狀態(tài)空間S＝1，2，…，M，其狀態(tài)轉(zhuǎn)移概率矩陣為P＝［p（i，j）］∈［0，1］（M×M），π＝π（1），…，π（M）表示狀態(tài)穩(wěn)定概率，f＝（f（1），f（2），…f（M））T表示各個(gè)狀態(tài)的獎(jiǎng)賞值，是一個(gè)M 維的全1矩陣。而π＝πp。平均性能可定義為式（6）

g＝（g1，g2，…，gn）T表示系統(tǒng)的性能勢(shì)，令g＝（Ip＋eπ）－1f，其中矩陣（I－p＋eπ）－1被定義為基礎(chǔ)矩陣。I表示單位矩陣，e＝（1，1，…，1）T，根據(jù)泰勒公式展開(kāi)成式（7）［9］

將性能勢(shì)和值迭代方法相結(jié)合，得到一種新的強(qiáng)化學(xué)習(xí)算法－G 學(xué)習(xí)，該算法選擇任意一個(gè)狀態(tài)作為參考狀態(tài)，采用值迭代的方法更新?tīng)顟B(tài)的性能勢(shì)，且算法的運(yùn)行只需要設(shè)定一個(gè)學(xué)習(xí)參數(shù)［10］。

根據(jù)性能勢(shì)的定義，選擇任意一個(gè)狀態(tài)作為其它狀態(tài)性能勢(shì)的參考標(biāo)準(zhǔn)。假定選擇狀態(tài)S0作為參考狀態(tài)，則sn狀態(tài)下的性能勢(shì)可表示為下式

定義在策略π下，狀態(tài)s相對(duì)參考狀態(tài)sk的性能勢(shì)

式（6）對(duì)于任意s∈S，a∈A 均成立。

性能勢(shì)的無(wú)折扣強(qiáng)化學(xué)習(xí)算法是一種在策略的G－學(xué)習(xí)算法，其算法描述如下所示：

算法1：在策略的G－學(xué)習(xí)算法

2 基于改進(jìn)的G－learning在RoboCup中的應(yīng)用

2.1 改進(jìn)的G－learning算法

在傳統(tǒng)的G－learning中，算法強(qiáng)調(diào)的是單個(gè)智能體在復(fù)雜環(huán)境中的學(xué)習(xí)過(guò)程，該算法并不能直接將G－learning應(yīng)用到多智能體系統(tǒng)中，所以有必要對(duì)原有的算法進(jìn)行改進(jìn)。改進(jìn)的思想是把算法應(yīng)用到多智能體環(huán)境中，考慮到其它智能體的勢(shì)函數(shù)對(duì)當(dāng)前智能體的影響；改進(jìn)的目的是當(dāng)智能體在選擇動(dòng)作的時(shí)候，能夠考慮到其它智能體的行為對(duì)其決策的影響。智能體在策略π下進(jìn)行學(xué)習(xí)，參照相對(duì)參考狀態(tài)g （s0）不斷改變G （s， a） 。設(shè)智能體共有k個(gè)，則γ＝［γ1，γ2，…γk］T表示k 個(gè)智能體學(xué)習(xí)的權(quán)值。則G可表示為式（10）

根據(jù)bellman最優(yōu)化定理，結(jié)合式（7）和式（8）的最優(yōu)策略為

由式（9）來(lái)確定智能體應(yīng)當(dāng)采取的下一個(gè)動(dòng)作，其中τ（s， a，s′） 為兩次狀態(tài)的停留時(shí)間。

2.2 仿真實(shí)驗(yàn)

機(jī)器人足球已經(jīng)被成功地作為國(guó)際化競(jìng)技的基礎(chǔ)和研究的一項(xiàng)挑戰(zhàn)，它是一個(gè)完全分布式的多主體域。但這里有隱藏狀態(tài)，每個(gè)智能體在任意給定的時(shí)刻里只能擁有部分世界觀。智能體還有噪音傳感器和執(zhí)行器，他們不能準(zhǔn)確的感知世界，同樣他們也不能完全影響世界。溝通的機(jī)會(huì)也是有限的，因此智能體必須實(shí)時(shí)地做出決定。這些特性決定了模擬機(jī)器人足球是一個(gè)現(xiàn)實(shí)的富有挑戰(zhàn)性的領(lǐng)域。

本文利用Keepaway－機(jī)器人足球的一個(gè)子任務(wù)進(jìn)行仿真實(shí)驗(yàn)，該平臺(tái)用于比較不同的機(jī)器學(xué)習(xí)方法。在Keepaway平臺(tái)中，其中一個(gè)球隊(duì)的keepers試圖保證控球在一個(gè)有限的區(qū)域內(nèi)，而另一個(gè)球隊(duì)的takers試圖從keepers中搶奪控球權(quán)，只有當(dāng)takers從keepers那搶奪到控球權(quán)或離開(kāi)了限定的區(qū)域，這個(gè)周期結(jié)束，下一個(gè)周期隨之開(kāi)始。

在RoboCup2D 仿真平臺(tái)中，每位agent都擁有各自的原子動(dòng)作，如kick，dash，turn等。而由于2D 仿真平臺(tái)要求的實(shí)時(shí)性比較高，在每個(gè)決策周期內(nèi)必須根據(jù)當(dāng)前狀態(tài)環(huán)境做出決策，因此假如每個(gè)學(xué)習(xí)步驟都以原子動(dòng)作作為學(xué)習(xí)對(duì)象，必然影響決策時(shí)間，因此本文引入SMDP概念，首先根據(jù)原子動(dòng)作建立宏動(dòng)作指令［11］：

HoldBall（）：保持持球，盡可能在距離對(duì)手較遠(yuǎn)的未知保持控球；

PassBall－：傳球，將球直接傳給keeper（k）；

GetOpen（）：跑位，移動(dòng)到距離對(duì)手有一定空間的未知，并根據(jù)當(dāng)前球的位置創(chuàng)造傳球的機(jī)會(huì)；

GoToBall（）：截取一個(gè)運(yùn)動(dòng)著的球或移動(dòng)到靜止的球；

BlockPass（k）：移動(dòng)到持球keeper和keeper（k）之間；

Shoot（）：在適當(dāng)?shù)那闆r下射門(mén)。

在學(xué)習(xí)過(guò)程中，場(chǎng)上的狀態(tài)描述我們主要考慮一下幾個(gè)方面：

ball＿pos（）：球的位置；

ball＿distto＿goal（）：球離球門(mén)的距離；

mate＿pos（）：該變量為一隊(duì)列，存儲(chǔ)隊(duì)友的位置信息；

opp＿pos（）：該變量為一隊(duì)列，存儲(chǔ)對(duì)方球員的位置信息；

球員的Keepaway的技能對(duì)于整個(gè)足球機(jī)器人比賽問(wèn)題的求解也是非常有用的。Keepaway可看成一個(gè)MDP過(guò)程，每個(gè)隊(duì)員只負(fù)責(zé)整個(gè)決策過(guò)程的一部分。每個(gè)隊(duì)員都是獨(dú)立地同時(shí)進(jìn)行學(xué)習(xí)。在本文的仿真實(shí)驗(yàn)中，選擇了如圖1所示的3個(gè)典型的前場(chǎng)進(jìn)攻場(chǎng)景，場(chǎng)景中防守方為agent2d底層，以這些場(chǎng)景開(kāi)始，直到出現(xiàn)進(jìn)球、球離開(kāi)限定區(qū)域或者場(chǎng)景執(zhí)行時(shí)間超時(shí)，終止當(dāng)前場(chǎng)景訓(xùn)練，選取新的場(chǎng)景并分別以3 個(gè)不同點(diǎn)（52.5，0.0）、（47.5，0.0）、（35.0，0.0）作為參考狀態(tài)對(duì)象分別運(yùn)用傳統(tǒng)R－learning和改進(jìn)的G－learning 進(jìn)行訓(xùn)練。在學(xué)習(xí)過(guò)程中，初始學(xué)習(xí)率默認(rèn)值為1，并按照進(jìn)行更新。每個(gè)場(chǎng)景限定執(zhí)行1500個(gè)仿真周期，按照服務(wù)器規(guī)定每個(gè)周期為100ms，每50個(gè)場(chǎng)景統(tǒng)計(jì)一次進(jìn)球數(shù)，進(jìn)球變化情況如圖2所示。

圖1 訓(xùn)練場(chǎng)景

從圖2可以看出，本文所采用的G－learning算法的訓(xùn)練效果明顯優(yōu)于R－learning。算法在學(xué)習(xí)過(guò)程中采用不同的參考狀態(tài)，發(fā)生頻率高的狀態(tài)（47.5，0.0）在650 個(gè)訓(xùn)練場(chǎng)景后開(kāi)始收斂，而R－learning則是在接近1000個(gè)訓(xùn)練場(chǎng)景后才開(kāi)始收斂。從進(jìn)球數(shù)看，應(yīng)用R－learning算法的整體進(jìn)球數(shù)低于G－learning算法的球隊(duì)進(jìn)球數(shù)，并且在收斂的初期仍有震蕩，從側(cè)面說(shuō)明了R－learning的敏感性。本文的算法收斂速度比R－learning快，整體算法穩(wěn)定。從訓(xùn)練結(jié)果看，本文的算法在收斂速度和收斂的穩(wěn)定性上均優(yōu)于傳統(tǒng)的R－learning。

圖2 運(yùn)行場(chǎng)景目數(shù)與進(jìn)球的關(guān)系

通過(guò)學(xué)習(xí)，把R－Learning與改進(jìn)后的G－Learning代碼應(yīng)用到廣東工業(yè)大學(xué)的仿真2D 球隊(duì)GDUT＿TiJi中，并分別與RoboCup2012世界賽的冠軍Helios、亞軍WrightEagle和agent2d底層進(jìn)行了100場(chǎng)比賽，結(jié)果見(jiàn)表1。

表1 仿真比賽統(tǒng)計(jì)結(jié)果（勝率）

3 結(jié)束語(yǔ)

針對(duì)在非確定性SMDP中的多智能體系統(tǒng)里，本文基于傳統(tǒng)的性勢(shì)能理論和平均強(qiáng)化學(xué)習(xí)提出了基于多智能系統(tǒng)的G－learning算法。該算法使用參考狀態(tài)的性勢(shì)能函數(shù)代替了R－learning中的平均獎(jiǎng)賞值，同時(shí)還考慮團(tuán)隊(duì)決策對(duì)智能體決策的影響，使智能體做出最有利于團(tuán)隊(duì)的決策。仿真實(shí)驗(yàn)表明，通過(guò)大量情景的學(xué)習(xí)，驗(yàn)證了改進(jìn)后Glearning算法的比傳統(tǒng)的R－learning效果更好，而且不同的參考狀態(tài)對(duì)G－learning的算法性能也會(huì)產(chǎn)生影響。從實(shí)驗(yàn)可以看出，選擇發(fā)生頻率高的狀態(tài)作為參考狀態(tài)，算法的收斂速度將會(huì)得到提高。運(yùn)用改進(jìn)后的G－learning后，廣東工業(yè)大學(xué)的仿真2D 球隊(duì)GDUT＿TiJi在比賽中的效果也得到了提高。從實(shí)驗(yàn)仿真結(jié)果上可以看出，該算法存在收斂時(shí)間長(zhǎng)、學(xué)習(xí)量大問(wèn)題，是進(jìn)一步研究的重點(diǎn)。

［1］Szepesvari C.Algorithms for reinforcement learning：Synthesis lectures on artificial intelligence and machine learning ［M］.San Rafael：Morgan＆Claypool Pulishers，2009：2－3.

［2］Chatterjee K，Majumadar R，Henzinge A T.Stochastic limitaverage games are in exptime［J］.International Journal in Game Theory，2007，37 （2）：219－234.

［3］Tadepalli P，D OK.Model－based average reward reinforcement learning ［J］.Artificial Intelligence，1998，100 （1－2）：177－224.

［4］GAO Yang，ZHOU Ruyi，WANG Hao，et al.Research on the average reward reinforcement learning ［J］.Chinese Journal of Computers，2007，30 （8）：1372－1378 （in Chinese）. ［高陽(yáng)，周如益，王皓，等.平均獎(jiǎng)賞強(qiáng)化學(xué)習(xí)算法研究 ［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30 （8）：1372－1378.］

［5］Sun T，Zhao Q，Luh P B.A rollout algorithm for multi chain Markov decision processes with average cost［J］.Positive Systems，2009，389：151－162.

［6］Yanjie L.An average reward performance potential estimation with geometric variance reduction ［C］／／31st Chinese Control Conference.IEEE，2012：2061－2065.

［7］Cao X R.Stochastic learning and optimization：A sensitivitybased approach ［J］.Annual Reviews in Control，2009，33（1）：11－24.

［8］Munos R.Geometric variance reduction in Markov chains：Application to value function and gradient estimation ［J］.Journal of Machine Learning Research，2006：413－427.

［9］CHEN Xuesong，YANG Yimin.Research on the reinforcement learning ［J］.Application Research of Computers，2010，27 （8）：2834－2838 （in Chinese）.［陳學(xué)松，楊宜民.強(qiáng)化學(xué)習(xí)研究綜述 ［J］.計(jì)算機(jī)應(yīng)用研究，2010，27 （8）：2834－2838.］

［10］ZHOU Ruyi，GAO Yang.A undiscounted reinforcement learning base on the performance potentials ［J］.Guangxi Normal University （Natural Science），2006，24 （4）：58－61（in Chinese）.［周如益，高陽(yáng).一種基于性能勢(shì)的無(wú)折扣強(qiáng)化學(xué)習(xí)算法 ［J］.廣西師范大學(xué)學(xué)報(bào) （自然科學(xué)版），2006，24 （4）：58－61.］

［11］ZUO Guoyu，ZHANG Hongwei，HAN Guangsheng.A reward function based on reinforcement learning of multi－agent［J］.Control Engineering，2009，16 （2）：239－242 （in Chinese）.［左國(guó)玉，張紅衛(wèi)，韓光勝.基于多智能體強(qiáng)化學(xué)習(xí)的新強(qiáng)化函數(shù)設(shè)計(jì) ［J］.控制工程，2009，16 （2）：239－242.］