基于混合Q學習的多Agent系統

陳玉明，張廣明，趙英凱

（南京工業大學 自動化與電氣工程學院，南京 210009）

0 引言

強化學習允許多Agent能夠在沒有關于任務和環境的先驗知識的條件下，只有通過不斷與變化的環境進行“試錯式”交互，并從環境中獲取強化信號來學習一種從狀態到動作的映射,以便能獲取最大的獎賞,并且它所做出的合理的策略將被得到加強。在多Agent系統中，對學習Agent而言，當前的環境狀態可以通過自身執行的動作來改變，但由于同時其他Agent也在進行學習，它們執行動作也在改變環境狀態。此外，多Agent強化學習從環境中獲得的強化信號是基于多Agent系統，而不是基于獨立的學習個體。在多Agent強化學習中，所有學習Agent的狀態變量構成聯合狀態，它們執行的動作構成聯合動作，每個Agent學習各自的策略。所有Agent的聯合動作作用于環境并使環境狀態發生改變，同時得到回報。回報根據某種信度分配策略分配給每個獨立的Agent，以完成各自的強化學習 。本文提出了基于Agent獨立學習的情形下，多Agent通過協作的混合Q學習算法，多Agent根據環境情況，進行聯合動作學習，提高了整體的學習性能；通過神經網絡的泛化和存儲能力，優化學習狀態，提高學習效率。

1 多智能體聯合強化學習

在多Agent系統中，Agent不但表現為個體的行為，應該依照自己的規則行動，更重要的是它所應當表現出來的社會行為。多個Agent共同完成任務，可能會比單個Agent完成更有效率,或者是完成單個Agent所不能獨立完成的任務。因此在Agent做出行動的決策之前，了解其它Agent的可能決策是相當地有用 。由于每個Agent的動作都會帶來環境狀態的變化。Agent成為了環境動態的一個因素，環境變化很難用一個MDP來表示。因此Agent在多Agent的環境中做出決策的過程，是一個通過推測其它Agent而綜合做出決策的過程，把它稱為推測決策過程。Agent的決策過程分作三步：第一步是根據對等原理推測其他Agent的過程；第二步是選擇自己的最優動作的過程；第三步是更新學習的過程 。

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

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

at是動態學習率。用表示學習Agent的最佳策略，用Tn表示n個Agent聯合狀態轉移函數其中Agent聯合環境狀態自身狀態為，將(4)式變為：

強化學習過程如下：

1）初始化所有的Q-表

2）通過輸入和知識庫系統判斷當前的聯合狀態

3）推測聯合動作

4）選擇一個使群體最優行為

5）Agent實現行為 ，然后當環境的狀態從 遷移到 , Agent將得到一個獎賞值

6）更新Q-表的值

7）進行到下一個時刻

2 Multi-Agent基于神經網絡的聯合強化學習

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

式中可取：

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

而ΔQ可以看作是BP網絡輸出層的誤差，隱層與輸入層的權值q更新公式如下：

利用BP算法的誤差反向傳播就可以調整權值保存調整后的Q值，從而實現Q值的學習[7]。其框圖如圖1所示。

3 實驗結果

3.1 實驗設計

圖1 基于Multi-Agent的混合Q學習算法實現結構圖

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

圖2-1 Hunters-prey模型初始狀態圖

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

3.2 實驗結果

設定學習結束條件為學習次數到達10000次，利用3種學習agent進行實驗，即Multi-Agent Independence Q-Learning（MIQ）、Multi-Agent Coordination Q-Learning（MCQ）和Multi-Agent Coordination Q-Learning at Neural Network（MCQNN） ，其中， MIQ采用的是MAS中agent采用單獨Q學習算法；即Q-學習; MCQ采用的是MAS中采用聯合Q學習算法； MCQNN采用的是本文所提出的基于神經網絡的聯合Q學習算法，實驗結果如表1所示，每種情況都運行1000次，計算實現圍捕的成功率.

表 1 圍捕的成功率比較

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

圖3是三種不同Q-學習算法學習的策略成功抓取prey時間的結果圖。從圖中可以看到，在 周期中CAQNN算法和MCQ算法相比于MIQ算法都顯示出了更快的學習速度，結合圖4中所示的實驗結果，出現這種現象是因為MCQNN算法使用神經網絡替代了狀態—動作對的表格搜索，而MCQ算法其需要考察的狀態一動作對遠遠少于MIQ算法。同樣在這次實驗中也注意到其后不久MIQ算法的效能急劇減退并且始終存在著劇烈的振蕩，而最后的結果也無法收斂到較好的值，其原因是MIQ算法沒有考慮其他智能體的動作，無法與別的智能體交互的同時導致環境的不穩定而無法收斂。考察到 周期時，MCQ算法的學習結果與到MCQNN的學習算法效果還有一定差距。由此可見，MCQNN學習算法擁有良好的學習效能，一般情況下也可以找到達成學習目標解。

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

4 結論

本文使用的多智能體神經網絡聯合Q學習算法，結合了聯合Q學習和神經網絡的特點，既考慮到了智能體的交互學習，同時通過神經網絡的泛化能力替代了傳統的Q學習表格法。減少了搜索表格的時間和節省了大量的內存空間，在提高學習速率的同時，又取得了較好的學習效能，也解決了由于“維數災難”帶來的Q值表示所引起的內存開銷問題。

[1] 高陽,陳世福,陸鑫.強化學習研究綜述[J].自動化學報,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] 唐文彬,朱淼良.基于強化學習的多Agent系統[J].計算機科學,2003,30(4):16-18.

[4] 郭銳,吳敏,彭軍,等.一種新的多智能體Q學習算法[J].自動化學報,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].哈爾濱工業大學學報,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] 蘇治寶,陸標聯,童亮.一種多智能體協作圍捕策略[J].北京理工大學學報,2004,24(5):403-406.