基于優(yōu)先經驗回放的多智能體協同算法

黃子蓉，甯彥淞，王 莉

(太原理工大學 大數據學院，山西 晉中 030600)

協作是多智能體系統的核心，智能體間通過協調配合可提高團隊協作效率且獲得更高的利益。深度強化學習結合了深度學習自學習、自適應的能力和強化學習感知試錯能力，在多智能體協同中取得了階段性成果，如星際爭霸Ⅱ[1]、交通樞紐任務[2]、飛機編隊[3]等。但基于深度強化學習的多智能體協同算法仍然存在經驗數據回放、可擴展性和合作性能等諸多方面的挑戰(zhàn)。

On-policy強化學習算法中，智能體與環(huán)境交互一次獲得的經驗元組(st,at,rt,st+1)僅利用一次便被拋棄。為了重復利用歷史經驗數據，DQN(Deep Q-Networks)算法中引入經驗回放緩存機制[4-5]，將歷史數據存入經驗回放緩存池中，極大地提高了經驗利用率。但先前的工作采取隨機采樣方式回放經驗或僅采樣近期經驗數據，忽略了經驗數據的優(yōu)先級，這可能造成成功經驗很快被遺忘或成功經驗較少的問題。SCHAUL et al[6]研究者提出的PER(prioritized experience replay)算法對經驗數據進行優(yōu)先級評估和排序，在采樣時選取優(yōu)先級較高的經驗進行模型訓練。該算法使重要經驗被回放的概率增大，增加了模型采樣效率和學習效率。但這種算法僅關注單智能體環(huán)境，隨著科技的發(fā)展，人們不再僅滿足于用深度強化學習算法控制單智能體，基于深度強化學習的多智能體協同研究逐步進入人們視野。如何在多智能體環(huán)境中有效利用歷史經驗且提高采樣效率和合作性能成為關鍵研究挑戰(zhàn)。

多智能體合作環(huán)境中，集中訓練分散執(zhí)行的框架已被證明是處理智能體間合作的有效范式。訓練階段，集中訓練的框架允許每個智能體的評判網絡使用其他智能體的狀態(tài)和動作信息，幫助智能體更好地合作。執(zhí)行階段，分散執(zhí)行的框架使智能體僅依賴它自身的觀測進行決策。這一范式解決了多智能體環(huán)境非平穩(wěn)問題。當面對連續(xù)型環(huán)境時，MADDPG(multi-agent deep deterministic policy gradient)算法[7]成為提升智能體間合作性能的代表性方法。MADDPG算法遵循集中訓練分散執(zhí)行框架， 每個智能體有自己獨立的Critic網絡和Actor網絡，Critic網絡以所有智能體的觀測和動作為輸入，解決了多智能體環(huán)境非平穩(wěn)性問題。但當環(huán)境中智能體數量增多時，狀態(tài)動作空間的大小呈指數型增長，造成可擴展性差的問題。且MADDPG算法僅選取近期經驗進行回放，使之前的經驗被遺忘，經驗利用率低。MAAC算法[8]嘗試解決上述問題。首先，MAAC算法學習帶有注意力機制的Critic網絡，注意力機制使智能體動態(tài)地選取周邊信息，改善了智能體在復雜環(huán)境中的合作性能。同時，模型的輸入維度隨智能體的增長呈線性增長趨勢，而非之前工作中的二次增長，一定程度上解決了可擴展性差的問題。其次，MAAC算法采用隨機采樣的方式進行經驗回放，利用了歷史經驗，但該算法仍忽略了歷史經驗的重要程度。本文擴展了MAAC算法，提出一種基于優(yōu)先經驗回放的多智能體協同算法(prioritized experience replayfor multi-agent cooperation，PEMAC)。

該算法的主要貢獻為：

1) 在多智能體系統中，算法基于TD誤差求出每條經驗數據的優(yōu)先級，每次采樣均采取優(yōu)先級較高的經驗數據更新網絡。PEMAC算法提升了訓練數據的質量，從而提升了模型收斂速度和智能體的合作性能。

2) PEMAC算法使用了基于注意力機制的Critic網絡學習智能體間的合作，使智能體動態(tài)地選取周邊信息，一定程度上實現多智能體系統的可擴展性。算法適用于合作、競爭和合作競爭混合的環(huán)境。

1 相關工作

深度強化學習已有很長的發(fā)展歷史。其中，幾個關鍵的研究點為：智能體如何使用歷史經驗提高經驗利用率；智能體如何提高合作性能；面對智能體數量較多的環(huán)境時模型的可擴展性等。

針對智能體經驗利用率問題，MNIH et al[5]提出的DQN算法引入經驗回放緩存機制，將經驗元組存入經驗回放緩存池中，極大地提高了經驗利用率。但其對所有數據均勻采樣，忽略了經驗數據的重要程度。SCHAUL et al[6]提出的PER算法對經驗數據進行優(yōu)先級評估和排序，采樣時選取優(yōu)先級較高的經驗進行模型訓練，使高優(yōu)先級的經驗被回放的概率增大，增加了模型采樣效率和學習效率。HOU et al[9]學者將PER算法引入DDPG(deep deterministic policy gradient)算法中，進一步提高了DDPG算法中經驗回放機制的效率，從而加速訓練過程。SHEN et al[10]將TD誤差的分布進行分段，然后根據更新后的TD誤差對經驗進行分類，實現相似經驗的交換機制，改變經驗池中的經驗的生命周期。這一算法降低了經驗池大小，節(jié)約了系統內存。BU et al[11]提出DPSR算法為經驗元組中的舊狀態(tài)選擇新動作，計算新的TD誤差，將原始緩存池中TD誤差值最小經驗元組替換，解決了模型無法選擇TD誤差較小的經驗元組的問題。

針對多智能體合作問題，集中訓練分散執(zhí)行的框架已被證明是處理智能體間合作的一個有效范式。集中訓練階段，智能體的評判網絡輸入所有智能體的狀態(tài)和動作，分散執(zhí)行階段智能體僅依賴它自身觀測和策略網絡進行決策，評判網絡失效。這一框架中，VDN[12]和QMIX[13]算法學習聯合的動作值函數，然后將其分解為智能體自身的值函數，達成智能體間有效的合作。但這些方法僅適用于合作環(huán)境，且很難處理大的動作空間的游戲場景，尤其是具有連續(xù)動作空間的場景。COMA[14]和CoRe[15]算法使用反事實基線方法推斷每個智能體對團隊利益的貢獻，從而達成智能體間合作。每個智能體的反事實基線是通過比較智能體的聯合動作值函數和將其他智能體的動作固定后只改變當前智能體的動作獲得的動作值函數得出的。然而這些方法必須為每個智能體所有給定動作都計算一條基線。當智能體數量增多或智能體的動作空間較大時，這些方法將更難訓練。且上述方法僅從環(huán)境中獲得聯合獎勵，對純合作環(huán)境適用，但對于競爭和合作競爭共存的環(huán)境不適用。

MADDPG算法同樣遵循集中訓練分散執(zhí)行的框架，該算法中每個智能體都有自身的Actor網絡和Critic網絡，所以適用于合作、競爭和合作競爭共存的環(huán)境。但MADDPG算法僅選取近期經驗進行回放，使之前的經驗被遺忘，經驗利用率低，且模型無法通過經驗學習一個智能體間的顯式通信，模型的可擴展性較差。MD-MADDPG算法[16]通過引入存儲設備，端到端的學習智能體間的顯式通信協議，提高智能體的合作性能。SMARL算法[17]提出一種基于Seq2eq序列多智能體強化學習算法，該算法將智能體策略網絡分解為動作網絡和目標網絡兩部分，可以適應智能體規(guī)模動態(tài)變化的環(huán)境。BiC-DDPG算法[18]使用雙向RNN結構實現信息通信。當智能體合作時，算法采用了一種映射方法將連續(xù)的聯合動作空間輸出映射到離散的聯合動作空間，解決智能體在大型聯合動作空間上的決策問題。但大多數環(huán)境中通信信道、通信協議是不可用的或通信帶寬受限制，使智能體間可進行交流的信息變少。MAAC算法擴展了MADDPG算法，學習帶有注意力機制的Critic網絡，降低模型輸入維度，一定程度上解決了可擴展性差的問題。且該算法采用隨機采樣的方式進行經驗回放，利用了歷史經驗，但該算法仍忽略了歷史經驗的重要程度。本文基于MAAC算法提出一種基于優(yōu)先經驗回放的多智能體協同算法PEMAC.PEMAC算法為每條經驗元組計算優(yōu)先級，并基于這一優(yōu)先級選取歷史經驗，訓練Critic網絡和Actor網絡。

2 基于優(yōu)先經驗回放的多智能體協同算法

現實世界中，智能體往往通過不斷試錯，從錯誤經驗中學習知識，從而實現某一目標。如人類在學會走路之前經過了無數次摔跤。受這一思想的啟發(fā)，本文提出了PEMAC算法。該算法利用TD誤差評估經驗元組的優(yōu)先級，然后選取優(yōu)先級大的經驗訓練Actor網絡和Critic網絡。同時考慮到智能體和環(huán)境交互時會選擇性地關注周邊智能體中的一些重要信息，這樣智能體能更好地做出決策。PEMAC算法在Critic網絡部分引入多頭自注意力機制，動態(tài)地選擇其要關注智能體的哪些信息，從而提高多智能體在復雜環(huán)境中的交互性能，網絡框架如圖1所示。

圖1 PEMAC算法框架圖Fig.1 Architecture of PEMAC

具體地，在經驗存儲和采樣階段，先初始化所有智能體在t時刻的狀態(tài)，將狀態(tài)作為智能體的局部觀測o，o=s=(s1,t,…,sn,t)，用參數θ={θ1,…,θn}初始化策略網絡，策略網絡生成策略集π={π1,…,πn}，然后智能體根據局部觀測和策略集做出t時刻的決策a，a=(a1,t,…,an,t)，智能體在狀態(tài)s，執(zhí)行動作a，與環(huán)境交互獲得了獎勵r，r=(r1,t,…,rn,t)，且智能體轉移到t+1時刻狀態(tài)s′=(s1,t+1,…,sn,t+1).之后將每個智能體的游戲軌跡四元組(si,t,ai,t,ri,t,si,t+1)和經驗優(yōu)先級Pi,t存入經驗回放緩存區(qū)～U(D).其中經驗優(yōu)先級Pi,t初始時刻均賦值為最大概率1.最后本文從U(D)中選取Pi,t值最大的一個批次的經驗作為模型訓練數據集。

在模型訓練階段，每個智能體將自己t時刻的狀態(tài)和動作輸入各自評判網絡的全連接編碼器中，智能體i的編碼信息為ei,t，ei,t=gi(si,t,ai,t).gi為一層的MLP編碼器。然后對智能體的編碼信息進行多頭自注意力選取，選取后的信息為(x1,t,…,xn,t).其中，

xi,t=∑j≠iαjvj=∑j≠iαjh(Vej,t).

(1)

式中：V為一個共享的線性變換矩陣，h為非線性函數(本文選取ReLU函數)，注意力權重αj為智能體i的信息編碼ei,t與線性變換矩陣Wq相乘后得到的鍵碼與鄰居智能體j的鍵碼求相似度得到，即：

(2)

接著將智能體i的編碼信息ei和其他智能體經過注意力選取后的信息xi,t輸入到一個兩層的全連接網絡fi中，進而得出智能體i的動作值函數Qi，即:

(3)

(4)

(5)

其中α是在獎勵值部分加入最大熵后的超參，遵循SAC算法模型。然后可通過TD誤差更新智能體i在t時刻的經驗元組的采樣概率Pi,t，具體地：

(6)

pi=|LQi(ψ)|+ε.

(7)

其中指數σ決定使用多少優(yōu)先級，當σ=0時為均勻采樣。參數μ和β是結合貪婪優(yōu)選算法和隨機選擇的優(yōu)點，保證經驗元組的更新概率是單調的，同時也保證了所有經驗元組以較高的概率更新經驗回放緩存池，而低優(yōu)先級的經驗元組也可以一定概率更新緩存池。ε為正數，防止TD誤差逼近0時，經驗元組的采樣概率逼近于0.此時策略網絡的更新變?yōu)椋?/p>

(8)

上述策略網絡更新中，PEMAC算法用反事實機制方法解決信度分配問題，即排除其他智能體對當前智能體期望收益的影響。b(o,ai)是反事實基線，為：

(9)

3 實驗

獎勵(reward)是強化學習中一個重要的評估指標，它指導智能體優(yōu)化策略且反映了強化學習中任務的完成程度。 為了驗證算法的有效性，本章以獎勵作為評價指標，分別基于合作尋寶[7]和漫游者-發(fā)射塔[8]兩種環(huán)境進行了實驗驗證。合作尋寶和漫游者-發(fā)射塔環(huán)境是完全合作的環(huán)境，本文控制環(huán)境中所有的智能體。

3.1 實驗環(huán)境

合作尋寶環(huán)境中，我方智能體必須在有限的步長內協調它們的行為盡可能收集到所有寶藏。如圖2(a)所示，粉色的大圓代表我方智能體，其他顏色的小圓代表寶藏。我方智能體能觀察到其他智能體和寶藏的相應位置。將智能體到寶藏的相對位置作為智能體的獎勵。這就意味著，我方智能體必須盡可能地尋找與自己距離最近的寶藏，同時避免與其他智能體到達相同的寶藏處。另外，智能體占據一定的物理空間，當智能體間相互碰撞時會受到一定程度的懲罰。

圖2 實驗環(huán)境Fig.2 Experimental environment

漫游者-發(fā)射塔環(huán)境中總共有2N個智能體，N個為漫游者，N個為發(fā)射塔。另外環(huán)境中設有N+1個隨機地標。如圖2(b)所示，灰色智能體為發(fā)射塔，大圓表示漫游者，小圓表示隨機地標。每次迭代中，漫游者和塔隨機配對。漫游者無法探知周邊環(huán)境和目標地標位置，其必須依賴于發(fā)射塔的通信。而發(fā)射塔可以定位漫游者的位置以及它們的目標地標。

3.2 實驗設置

對于合作尋寶環(huán)境來說，為驗證算法在智能體數量較多的環(huán)境中模型仍適用，本文分別設置了3個合作的智能體和4個合作的智能體。環(huán)境中目標地標寶藏的數量與智能體數量一致，即分別選取了3個寶藏和4個寶藏。各個智能體計算它距離各個寶藏的相對距離，然后智能體以距離它最近的寶藏與當前智能體的相對距離的負值作為獎勵。但當智能體間互相碰撞時，智能體得到-1的懲罰。

對于漫游者-發(fā)射塔環(huán)境，本文設置了2個漫游者，2個發(fā)射塔，3個目標地標。漫游者以其與目標地標距離的負值作為獎勵，發(fā)射塔以與其配對的漫游者距離目標地表的距離的負值作為獎勵。但當智能體間互相碰撞時，智能體得到-1的懲罰。

另外，本文選取當前運行的進程數+當前運行次數×1 000作為隨機種子初始化環(huán)境。每輪游戲設置了25個步長。為證明算法有效性，本文中每種算法都在所有環(huán)境中獨立運行了5次，獎勵選取5次運行的平均結果。

3.3 實驗結果

為驗證PEMAC算法的有效性，本章選取MADDPG算法、MD-MADDPG算法和MAAC算法作為基線模型進行對比試驗。表1顯示了當模型收斂時，所有環(huán)境中智能體所在團隊5次運行結果的平均獎勵。表中所示結果為未經過平滑的平均獎勵和浮動范圍。圖3顯示了3個智能體的合作尋寶環(huán)境中，每種算法獲得獎勵的變化趨勢，圖4顯示了4個智能體的合作尋寶環(huán)境中獎勵的變化趨勢，圖5顯示了漫游者-發(fā)射塔環(huán)境中獎勵的變化趨勢。所有圖均為經過smooth函數平滑后的獎勵變化趨勢圖。

表1 模型收斂后合作尋寶和漫游者-發(fā)射塔環(huán)境中的平均獎勵Table 1 Average reward per episode after model converging in the cooperative treasure hunt and the rover-tower environments

表1和圖3的結果表明，在合作尋寶環(huán)境中，當智能體數量為3時，智能體在局部觀測情況下，PEMAC算法的性能優(yōu)于MADDPG算法8.7%，優(yōu)于MD-MADDPG算法5.2%，優(yōu)于MAAC算法2.9%.表1和圖4的結果表明，當智能體數量為4時，PEMAC算法的性能優(yōu)于MADDPG算法8.4%，優(yōu)于MD-MADDPG算法3.5%，優(yōu)于MAAC算法1.6%.

圖3 合作尋寶環(huán)境中智能體數量為3時獎勵的變化趨勢Fig.3 Change trend of rewards when the number of agents is three in the cooperative treasure hunt environment

圖4 合作尋寶環(huán)境中智能體數量為4時獎勵的變化趨勢Fig.4 Change trend of rewards when the number of agents is four in the cooperative treasure hunt environment

表1和圖5的結果表明，在漫游者-發(fā)射塔環(huán)境中，智能體在局部觀測情況下，PEMAC算法的性能是MADDPG算法的118.09倍，是MD-MADDPG算法的204.11倍，比MAAC算法的性能高3.7%.也證明當環(huán)境較為復雜時，注意力機制可以使智能體有選擇地關注周邊信息，從而提升合作性能。

圖5 漫游者-發(fā)射塔環(huán)境中的獎勵變化趨勢Fig.5 Change trend of rewards in the rover-tower environment

由上可知，PEMAC算法整體性能均高于MADDPG算法、MD-MADDPG算法和MAAC算法。引入優(yōu)先經驗回放，使重要經驗被回放的概率增大，學習更有效。智能體可從大量失敗經驗中更有效地學習到隱藏的成功經驗，從而提升算法性能。且由圖3、圖4和圖5可知，PEMAC算法的收斂速度比其他算法的收斂速度快。算法收斂速度由智能體獲得相同獎勵所需要的運行次數和模型趨于穩(wěn)定所運行的迭代步決定。另外，由表1和圖中的浮動范圍可知，當模型收斂后，智能體使用PEMAC算法獲得的獎勵在平均獎勵附近波動范圍比MAAC算法波動范圍小，因而PEMAC算法可以提高MAAC算法的穩(wěn)定性。

為了更細粒度地顯示注意力機制如何工作，本文對漫游者-發(fā)射塔環(huán)境中漫游者對所有發(fā)射塔的注意力權重進行了可視化分析。如圖6所示，流浪者1對與其匹配的發(fā)射塔1的關注度高于對發(fā)射塔2的關注度。流浪者2對發(fā)射塔2的關注度高于發(fā)射塔1。經過分析可知漫游者在無法探知周邊情況時，學會了關注與其配對的塔，并與塔進行通信，從而提高智能體收益。

圖6 漫游者對發(fā)射塔的注意力權重Fig.6 Attention weights over all tower for a rover in rover-tower environment

4 結束語

本文提出基于優(yōu)先經驗回放的多智能體協同算法PEMAC.該算法通過使用優(yōu)先經驗回放機制，從失敗經驗中學習隱藏成功經驗，提升了模型性能，加快了收斂速度和模型穩(wěn)定性。同時使用注意力機制使智能體可以選擇性的關注周邊信息，進一步提升了模型性能。最后本文基于合作尋寶和流浪者-發(fā)射塔環(huán)境對算法性能進行對比驗證，實驗結果表明PEMAC算法具有較優(yōu)的合作性能。

本文雖對智能體數量增多時模型性能進行了實驗驗證，但環(huán)境規(guī)模仍受限。接下來計劃擴展多智能體環(huán)境規(guī)模和環(huán)境復雜度，將PEMAC算法推廣到更復雜的環(huán)境中。