基于混合Q學(xué)習(xí)的多Agent系統(tǒng)

陳玉明，張廣明，趙英凱

（南京工業(yè)大學(xué) 自動(dòng)化與電氣工程學(xué)院，南京 210009）

0 引言

強(qiáng)化學(xué)習(xí)允許多Agent能夠在沒有關(guān)于任務(wù)和環(huán)境的先驗(yàn)知識的條件下，只有通過不斷與變化的環(huán)境進(jìn)行“試錯(cuò)式”交互，并從環(huán)境中獲取強(qiáng)化信號來學(xué)習(xí)一種從狀態(tài)到動(dòng)作的映射,以便能獲取最大的獎(jiǎng)賞,并且它所做出的合理的策略將被得到加強(qiáng)。在多Agent系統(tǒng)中，對學(xué)習(xí)Agent而言，當(dāng)前的環(huán)境狀態(tài)可以通過自身執(zhí)行的動(dòng)作來改變，但由于同時(shí)其他Agent也在進(jìn)行學(xué)習(xí)，它們執(zhí)行動(dòng)作也在改變環(huán)境狀態(tài)。此外，多Agent強(qiáng)化學(xué)習(xí)從環(huán)境中獲得的強(qiáng)化信號是基于多Agent系統(tǒng)，而不是基于獨(dú)立的學(xué)習(xí)個(gè)體。在多Agent強(qiáng)化學(xué)習(xí)中，所有學(xué)習(xí)Agent的狀態(tài)變量構(gòu)成聯(lián)合狀態(tài)，它們執(zhí)行的動(dòng)作構(gòu)成聯(lián)合動(dòng)作，每個(gè)Agent學(xué)習(xí)各自的策略。所有Agent的聯(lián)合動(dòng)作作用于環(huán)境并使環(huán)境狀態(tài)發(fā)生改變，同時(shí)得到回報(bào)?；貓?bào)根據(jù)某種信度分配策略分配給每個(gè)獨(dú)立的Agent，以完成各自的強(qiáng)化學(xué)習(xí) 。本文提出了基于Agent獨(dú)立學(xué)習(xí)的情形下，多Agent通過協(xié)作的混合Q學(xué)習(xí)算法，多Agent根據(jù)環(huán)境情況，進(jìn)行聯(lián)合動(dòng)作學(xué)習(xí)，提高了整體的學(xué)習(xí)性能；通過神經(jīng)網(wǎng)絡(luò)的泛化和存儲能力，優(yōu)化學(xué)習(xí)狀態(tài)，提高學(xué)習(xí)效率。

1 多智能體聯(lián)合強(qiáng)化學(xué)習(xí)

在多Agent系統(tǒng)中，Agent不但表現(xiàn)為個(gè)體的行為，應(yīng)該依照自己的規(guī)則行動(dòng)，更重要的是它所應(yīng)當(dāng)表現(xiàn)出來的社會行為。多個(gè)Agent共同完成任務(wù)，可能會比單個(gè)Agent完成更有效率,或者是完成單個(gè)Agent所不能獨(dú)立完成的任務(wù)。因此在Agent做出行動(dòng)的決策之前，了解其它Agent的可能決策是相當(dāng)?shù)赜杏?。由于每個(gè)Agent的動(dòng)作都會帶來環(huán)境狀態(tài)的變化。Agent成為了環(huán)境動(dòng)態(tài)的一個(gè)因素，環(huán)境變化很難用一個(gè)MDP來表示。因此Agent在多Agent的環(huán)境中做出決策的過程，是一個(gè)通過推測其它Agent而綜合做出決策的過程，把它稱為推測決策過程。Agent的決策過程分作三步：第一步是根據(jù)對等原理推測其他Agent的過程；第二步是選擇自己的最優(yōu)動(dòng)作的過程；第三步是更新學(xué)習(xí)的過程 。

本節(jié)將研究基于Multi-Agent的聯(lián)合Q學(xué)習(xí)方法，其中Multi-Agent強(qiáng)化學(xué)習(xí)的Q函數(shù)依賴于所有Agent執(zhí)行的動(dòng)作效果總和。定義學(xué)習(xí)目標(biāo)為學(xué)習(xí)策略π，，S為有限狀態(tài)集，A為Agent動(dòng)作集合。時(shí)刻t在狀態(tài)st下，Agent選擇動(dòng)作的概率分布表示為π={P1,P2,...,Pi}，策略π={π1,π2,...,πn}，從狀態(tài)st開始，按策略了獲得的期望累計(jì)折扣回報(bào)為[4]：

其中，0≤γ＜1為折扣因子，反映了對當(dāng)前回報(bào)與未來回報(bào)的取舍，rt指每次獲得的有界回報(bào)，由于是在非確定馬爾可夫環(huán)境下進(jìn)行學(xué)習(xí)，累計(jì)回報(bào)加上期望運(yùn)算，最佳策略是使(1)式獲得最大值的策略，其中Agent執(zhí)行聯(lián)合動(dòng)作其后繼狀態(tài)為s'。Multi-Agent強(qiáng)化學(xué)習(xí)的Q函數(shù)依賴于所有Agent執(zhí)行的聯(lián)合動(dòng)作，對于強(qiáng)化學(xué)習(xí)算法改進(jìn)為：

at是動(dòng)態(tài)學(xué)習(xí)率。用表示學(xué)習(xí)Agent的最佳策略，用Tn表示n個(gè)Agent聯(lián)合狀態(tài)轉(zhuǎn)移函數(shù)其中Agent聯(lián)合環(huán)境狀態(tài)自身狀態(tài)為，將(4)式變?yōu)椋?/p>

強(qiáng)化學(xué)習(xí)過程如下：

1）初始化所有的Q-表

2）通過輸入和知識庫系統(tǒng)判斷當(dāng)前的聯(lián)合狀態(tài)

3）推測聯(lián)合動(dòng)作

4）選擇一個(gè)使群體最優(yōu)行為

5）Agent實(shí)現(xiàn)行為 ，然后當(dāng)環(huán)境的狀態(tài)從 遷移到 , Agent將得到一個(gè)獎(jiǎng)賞值

6）更新Q-表的值

7）進(jìn)行到下一個(gè)時(shí)刻

2 Multi-Agent基于神經(jīng)網(wǎng)絡(luò)的聯(lián)合強(qiáng)化學(xué)習(xí)

傳統(tǒng)的強(qiáng)化學(xué)習(xí)算法，如Q學(xué)習(xí)算法利用表格來表示Q(s,a)函數(shù)，但當(dāng)狀態(tài)集合S、系統(tǒng)動(dòng)作集合A較大時(shí)，但該方法需要占用大量的內(nèi)存空間，而且也不具有泛化能力。將強(qiáng)化學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)相結(jié)合，主要是利用神經(jīng)網(wǎng)絡(luò)的強(qiáng)大存儲能力和函數(shù)估計(jì)能力。一般來說，神經(jīng)網(wǎng)絡(luò)在系統(tǒng)中的工作方式 是：接收外界環(huán)境的完全或不完全狀態(tài)描述，作為神經(jīng)網(wǎng)絡(luò)的輸入，并通過神經(jīng)網(wǎng)絡(luò)進(jìn)行計(jì)算，輸出強(qiáng)化學(xué)習(xí)系統(tǒng)所需的Q值，網(wǎng)絡(luò)的輸入對應(yīng)描述環(huán)境的狀態(tài)。采用神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)Q學(xué)習(xí)克服了傳統(tǒng)Q學(xué)習(xí)存在的問題，采用這種方式在較大程度上發(fā)揮這兩種技術(shù)各自特有的優(yōu)勢[6]。本文提出了基于神經(jīng)網(wǎng)絡(luò)的Q學(xué)習(xí)，即用神經(jīng)網(wǎng)絡(luò)來逼近Q函數(shù)，從而可以克服圖表存儲Q值所存在的缺陷,提高了混合算法的學(xué)習(xí)速率，應(yīng)用一個(gè)3層的BP神經(jīng)網(wǎng)絡(luò)，BP算法是由兩部分組成：信息的正向傳遞與誤差的反向傳播。BP網(wǎng)絡(luò)隱層的輸入為狀態(tài)矢量S=(s1,s2,...sn)，網(wǎng)絡(luò)的輸出為每一狀態(tài)下可選動(dòng)作的Q-值，即。

式中可?。?/p>

由式(4)可知，每次執(zhí)行一個(gè)動(dòng)作后的Q值會更新，其Q值的變化為：

而ΔQ可以看作是BP網(wǎng)絡(luò)輸出層的誤差，隱層與輸入層的權(quán)值q更新公式如下：

利用BP算法的誤差反向傳播就可以調(diào)整權(quán)值保存調(diào)整后的Q值，從而實(shí)現(xiàn)Q值的學(xué)習(xí)[7]。其框圖如圖1所示。

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

圖1 基于Multi-Agent的混合Q學(xué)習(xí)算法實(shí)現(xiàn)結(jié)構(gòu)圖

為了能驗(yàn)證Multi-Agent混合強(qiáng)化學(xué)習(xí)的有效性和功能的正確性，利用hunters-prey模型，設(shè)計(jì)仿真實(shí)驗(yàn)如下：1）用實(shí)驗(yàn)空間為20 *20格的類似棋盤的平面，一個(gè)prey和四個(gè)Hunter速度相同，均為全局視覺，每次行動(dòng)一格有5種可能:原地不動(dòng)、上、下、左、右移動(dòng)一格，初始位置隨機(jī)生成；2）環(huán)境無邊界，如果圍捕的步數(shù)超過100步，則認(rèn)為圍捕失敗；3）4個(gè)Hunter在prey臨近上下左右四個(gè)方格中，認(rèn)為圍捕成功；4）prey的逃跑策略是:向離自身最近的 的反方向逃跑， 移向prey所在格時(shí)會被隨機(jī)傳送的棋盤中的一個(gè)空格中作為懲罰，如果兩個(gè)捕食者同時(shí)移向同一個(gè)格子也會收到懲罰。實(shí)驗(yàn)初始態(tài)模型如圖2-1所示，圖2-2是成功圍捕的狀態(tài)圖。

圖2-1 Hunters-prey模型初始狀態(tài)圖

圖2-2 Hunters-prey模型成功圍捕圖

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

設(shè)定學(xué)習(xí)結(jié)束條件為學(xué)習(xí)次數(shù)到達(dá)10000次，利用3種學(xué)習(xí)agent進(jìn)行實(shí)驗(yàn)，即Multi-Agent Independence Q-Learning（MIQ）、Multi-Agent Coordination Q-Learning（MCQ）和Multi-Agent Coordination Q-Learning at Neural Network（MCQNN） ，其中， MIQ采用的是MAS中agent采用單獨(dú)Q學(xué)習(xí)算法；即Q-學(xué)習(xí); MCQ采用的是MAS中采用聯(lián)合Q學(xué)習(xí)算法； MCQNN采用的是本文所提出的基于神經(jīng)網(wǎng)絡(luò)的聯(lián)合Q學(xué)習(xí)算法，實(shí)驗(yàn)結(jié)果如表1所示，每種情況都運(yùn)行1000次，計(jì)算實(shí)現(xiàn)圍捕的成功率.

表 1 圍捕的成功率比較

由結(jié)果可以看出，MAS都采用單獨(dú)Q學(xué)習(xí)算法時(shí)，實(shí)現(xiàn)成功率為23%，這是單Agent不對其他Agent建模的原因所致; 使用聯(lián)合Q學(xué)習(xí)算法時(shí),實(shí)現(xiàn)成功率為77%，較第一種情況有了很大的提高，Multi-Agent采用了協(xié)作學(xué)習(xí)，對于全局控制遠(yuǎn)遠(yuǎn)好于單獨(dú)Q學(xué)習(xí)，而第三種基于NN的聯(lián)合Q學(xué)習(xí)在效果上，比聯(lián)合Q學(xué)習(xí)又得到了一定的提升。

圖3是三種不同Q-學(xué)習(xí)算法學(xué)習(xí)的策略成功抓取prey時(shí)間的結(jié)果圖。從圖中可以看到，在 周期中CAQNN算法和MCQ算法相比于MIQ算法都顯示出了更快的學(xué)習(xí)速度，結(jié)合圖4中所示的實(shí)驗(yàn)結(jié)果，出現(xiàn)這種現(xiàn)象是因?yàn)镸CQNN算法使用神經(jīng)網(wǎng)絡(luò)替代了狀態(tài)—?jiǎng)幼鲗Φ谋砀袼阉?，而MCQ算法其需要考察的狀態(tài)一動(dòng)作對遠(yuǎn)遠(yuǎn)少于MIQ算法。同樣在這次實(shí)驗(yàn)中也注意到其后不久MIQ算法的效能急劇減退并且始終存在著劇烈的振蕩，而最后的結(jié)果也無法收斂到較好的值，其原因是MIQ算法沒有考慮其他智能體的動(dòng)作，無法與別的智能體交互的同時(shí)導(dǎo)致環(huán)境的不穩(wěn)定而無法收斂?？疾斓?周期時(shí)，MCQ算法的學(xué)習(xí)結(jié)果與到MCQNN的學(xué)習(xí)算法效果還有一定差距。由此可見，MCQNN學(xué)習(xí)算法擁有良好的學(xué)習(xí)效能，一般情況下也可以找到達(dá)成學(xué)習(xí)目標(biāo)解。

圖3 三種算法策略的成功抓捕Prey的時(shí)間

4 結(jié)論

本文使用的多智能體神經(jīng)網(wǎng)絡(luò)聯(lián)合Q學(xué)習(xí)算法，結(jié)合了聯(lián)合Q學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)的特點(diǎn)，既考慮到了智能體的交互學(xué)習(xí)，同時(shí)通過神經(jīng)網(wǎng)絡(luò)的泛化能力替代了傳統(tǒng)的Q學(xué)習(xí)表格法。減少了搜索表格的時(shí)間和節(jié)省了大量的內(nèi)存空間，在提高學(xué)習(xí)速率的同時(shí)，又取得了較好的學(xué)習(xí)效能，也解決了由于“維數(shù)災(zāi)難”帶來的Q值表示所引起的內(nèi)存開銷問題。

[1] 高陽,陳世福,陸鑫.強(qiáng)化學(xué)習(xí)研究綜述[J].自動(dòng)化學(xué)報(bào),2004,30(1):86-100.

[2] Bevan Jarvis,Dennis Jarvis,Lakhmi Jain.TEAMS IN MULTIAGENT SYSTEMS[J].Intelligent Information Processing III,2006:1-10.

[3] 唐文彬,朱淼良.基于強(qiáng)化學(xué)習(xí)的多Agent系統(tǒng)[J].計(jì)算機(jī)科學(xué),2003,30(4):16-18.

[4] 郭銳,吳敏,彭軍,等.一種新的多智能體Q學(xué)習(xí)算法[J].自動(dòng)化學(xué)報(bào),2007,33(4):365-372.

[5] Suton R S.Learning to predict by the methods of temporal differences[J].Machine Learning,1988,(3):9-44.

[6] 張彥鐸,閔鋒.基于人工神經(jīng)網(wǎng)絡(luò)在機(jī)器人足球中的應(yīng)用[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2004,36(7):859-861.

[7] Jim Duggan. Equation-based policy optimization for agentoriented system dynamics models[J].System Dynamics Review Volume,2008,24(1):98-118.

[8] 蘇治寶,陸標(biāo)聯(lián),童亮.一種多智能體協(xié)作圍捕策略[J].北京理工大學(xué)學(xué)報(bào),2004,24(5):403-406.