面向Ad-Hoc協作的局部觀測重建方法*

陳皓,楊立昆,尹奇躍,黃凱奇,3?

(1 中國科學院自動化研究所智能系統與工程研究中心, 北京 100190; 2 中國科學院大學人工智能學院, 北京 100049;3 中國科學院腦科學與智能技術卓越創新中心, 上海 200031) (2022年3月2日收稿; 2022年4月1日收修改稿)

在現實生活中,多智能體系統(multi-agent System, MAS)無處不在,比如電力分配網絡[1]、自動駕駛車輛[2]、傳感器網絡[3]等。強化學習是處理這些多智能體問題的常用方法。然而相比單智能體強化學習,多智能體強化學習面臨著環境非平穩、信用分配、Ad-Hoc協作等獨特的挑戰。

為應對上述挑戰,多智能體強化學習(multi-agent reinforcement learning, MARL)在近年來取得了以中心化訓練分布式執行(centralized training with decentralized execution, CTDE)框架[4-5]為代表的一系列突破性進展[6-12]。在CTDE訓練范式中,智能體在中心化訓練階段可以使用全局信息,在分布式執行階段只能依賴局部觀測信息進行決策,也就是滿足了部分可觀測的限制。在CTDE框架下,以QMIX[8]為代表的價值函數分解方法通過信用分配網絡把每個智能體的本地Q值組合成全局Q值,更好地評價每個智能體的貢獻,實現了更好的合作,在很多極具挑戰性的任務上取得了良好效果。

然而在很多實際的應用場景中,智能體需要在測試時與從未見過的隊友進行協作,比如不同種類、數量的隊友。這被稱為Ad-Hoc協作問題[13]。在CTDE框架下,現有的基于信用分配的方法往往不能利用由于不同隊友設定帶來的變化的輸入信息,從而導致算法無法在Ad-Hoc協作場景下取得較好的性能。

針對上述問題, 本文提出一種面向Ad-Hoc協作的局部觀測重建算法,首先把智能體的局部觀測信息分解為3個部分,然后利用注意力機制處理長度變化的輸入信息,使得算法對數量變化的智能體輸入不敏感,最后利用采樣網絡實現局部觀測抽象,使得算法認識到并充分利用不同局面中的高維狀態表征。最終實現了對每個智能體的局部觀測信息的重建,使得算法可以在Ad-Hoc協作場景下進行零樣本泛化。本文在星際爭霸微操環境(StarCraft multi-agent challenge, SMAC)[14]和Ad-Hoc協作場景上對算法性能進行了驗證, 實驗結果表明,在1c3s5z等簡單地圖,5m_vs_6m等困難地圖,極度困難地圖MMM2,以及Ad-Hoc協作場景上,算法取得了超越現有代表性算法的性能,學到了更好的協作策略。

本文貢獻包括如下兩方面內容：1)提出一種面向Ad-Hoc協作的局部觀測重建算法,通過注意力機制和采樣網絡對局部觀測進行重建,使得算法認識到并充分利用不同局面中的高維狀態表征,有效提升了算法在Ad-Hoc協作場景下的零樣本泛化能力;2)在星際爭霸微操環境和Ad-Hoc協作場景上與代表性算法的性能進行對比與分析,并進行消融實驗,驗證了算法的有效性。

1 問題定義與相關工作

1.1 問題定義

1.2 多智能體深度強化學習

深度強化學習在近幾年取得了很大的進展[16-17],其中DQN算法[18-19]是一個具有代表性的成果。這些單智能體強化學習算法的突破,也激勵著研究者們將深度強化學習應用在多智能體領域中[20-22]。一個顯而易見的想法是將單智能體算法直接遷移至多智能體問題上,但這種直接的遷移并沒有收獲良好的效果[23]。原因在于,在多智能體的設定下,智能體的決策環境不滿足馬爾科夫性質。即各個智能體的策略都在不斷變化,導致單個智能體在決策過程中觀測到的環境在不斷變化。這種問題被稱為環境非平穩問題。正是該問題使得單智能體強化學習算法在多智能體問題中失去了理論保證。除了環境非平穩問題,在多智能體強化學習領域中還存在著諸多具有挑戰性的問題,比如部分可觀測問題、信用分配問題、狀態-動作空間指數爆炸問題等。在多智能體領域中,學者們提出了諸多方法以應對上述問題,其中具有代表性的是行為分析[24-27]、學習通信[28-32]、學習合作[33-34]、對手建模[35-37]4類方法。這些方法有效地促進了多智能體深度強化學習的發展。

1.3 中心化訓練分布式執行

在強化學習中,動作-值函數的優異程度很大程度上決定整個算法的效果。在多智能體系統中,學習最優的動作-值函數也是一個重要的問題。當智能體數目較少時,完全中心化的算法一般具有較好的性能,然而隨著智能體數目的增多,完全中心化是算法引起了狀態-動作空間指數爆炸的問題。而完全去中心化的算法,比如獨立Q學習算法(independent Q learning, IQL)[23],雖然可以解決上述問題,但是將其他智能體建模成環境的方法卻導致了環境非平穩的問題,從而難以獲得較好的性能。

綜上所述,完全中心化和完全去中心化都不能得到良好的效果,所以學者們提出了中心化訓練分布式執行框架,如圖1所示。在CTDE框架的訓練過程中,算法可以獲取所有智能體的動作-觀測歷史τ和全局狀態s,而在測試過程中,每個智能體只根據自己的動作-觀測歷史τi來進行決策。這種方法緩解了環境非平穩和狀態-動作空間指數爆炸的問題并在多智能體深度強化學習中得到了廣泛應用[6-9],并成為目前學界使用的主流框架。

圖1 中心化訓練分布式執行框架下多智能體與環境交互Fig.1 Multi-agent interaction with environment under CTDE framework

1.4 基于值分解的信用分配方法

基于值分解的方法是實現智能體之間信用分配的一種常用方法,也是多智能體深度強化學習研究中的一個熱點。

在基于值分解的方法中,最優的聯合動作等于最優個體動作的集合,是個體-全局最優條件(individual-global-max, IGM)[9]中定義的最優的個體動作和最優的聯合動作之間應該滿足的關系。使用符合IGM條件的基于值分解的方法可以使算法較快收斂并取得更好的性能。其中,IGM條件可以表示為

(1)

VDN算法[7]假設聯合動作值函數Qtot(τ,u)是每個智能體的動作值函數Qi(τi,ui)的簡單加和,通過如下所示的加性約束滿足了IGM條件。

(2)

QMIX算法假設聯合動作值函數Qtot(τ,u)滿足單調性約束,進而滿足IGM條件。因此實現了對聯合動作-值函數的分解. 具體限制條件如下所示

(3)

QMIX中的單調性約束是指隨著某個智能體的Qi(τi,ui)增大,Qtot(τ,u)也隨之會增大,反之亦然。同時為了使值分解網絡具有單調性以滿足IGM條件,QMIX限制了值分解網絡的權重非負。

QTRAN算法[9]把原有的聯合動作-值函數轉化為新的可分解的聯合動作-值函數以實現更廣泛的值分解。QTRAN算法移除了VDN算法和QMIX算法中的結構化約束,并使轉化前后的聯合動作-值函數具有相同的最優動作。上述過程同樣帶來了算法復雜度增加的問題,使得算法整體性能略有降低。

1.5 Ad-Hoc協作

Ad-Hoc協作是多智能體領域中一個極具挑戰性的研究問題,近年來獲得了學界大量的關注[38-40]。在Ad-Hoc協作問題中,智能體需要學會如何跟變化的隊友合作,包括種類上和數量上的變化等。也就是說,在訓練和測試的時候,智能體會面對完全不同,甚至從未見過的隊友設置,并且需要在這種情況下取得較好的性能。前人的方法或者有很強的先驗知識假設[41-42],或者使用硬編碼的規則進行合作[43-44],都具有很多限制,從而無法泛化到更一般的Ad-Hoc協作場景。本文提出的算法可以實現在Ad-Hoc協作場景下的零樣本泛化,在從未見過的隊友設置上取得較好的效果。

2 面向Ad-Hoc協作的局部觀測重建算法

本節詳細介紹面向Ad-Hoc協作的局部觀測重建算法LOBRE(local observation reconstruction for Ad-Hoc cooperation)。傳統的信用分配算法只能接受固定長度的輸入數據,無法適應數量變化的隊友。同時,傳統的信用分配算法沒有針對Ad-Hoc協作問題重建智能體的局部觀測,導致無法充分利用局部觀測信息,從而無法取得很好的Ad-Hoc協作能力。為解決該問題,本文提出的LOBRE算法通過局部觀測重建網絡對智能體接收到的局部觀測進行重構,從而實現了在Ad-Hoc協作場景下的零樣本泛化。

2.1 局部觀測重建網絡

為實現在Ad-Hoc協作場景下的零樣本泛化,對智能體的局部觀測網絡進行重建,一方面可以適應數量變化的隊友,另一方面使得算法認識到并充分利用不同局面中的高維狀態表征,有利于提升算法在Ad-Hoc協作場景下的性能。

LOBRE算法的網絡結構如圖2所示,在中心化訓練的過程中,LOBRE算法首先接收智能體的局部觀測信息作為智能體決策網絡的輸入,輸出每個智能體的Q值。然后通過信用分配網絡處理每個智能體的Q值進而得到Qtot(τ,u)。智能體決策網絡由局部觀測重建網絡、門控循環單元(gated recurrent unit, GRU)和線性層組成。

圖2 LOBRE算法的網絡結構Fig.2 Network structure of LOBRE algorithm

局部觀測重建網絡的具體網絡結構如圖3所示,在局部觀測重建網絡中,智能體的局部觀測首先被分為3個部分,分別為：該智能體自己的特征Oown、與智能體數目有關的特征Ovar和與智能體數目無關的特征Oinv。然后,本文使用縮放點積注意力處理該智能體自己的特征Oown和與智能體數目有關的特征Ovar,如下式所示

圖3 局部觀測重建網絡的結構Fig.3 The structure of local observation reconstruction network

(4)

其中：Q,K,V分別對應Oown,Ovar,Ovar。

然后,使用采樣網絡處理縮放點積注意力的輸出信息,以及與智能體數目無關的特征Oinv,下一節將詳細介紹關于采樣網絡的結構設計。最后,把從采樣網絡中輸出的2個信息矩陣拼接起來得到經過重建的局部觀測信息Orecon,并將其作為局部觀測重建網絡的輸出。該輸出Orecon會作為重建后的局部觀測信息輸入到智能體后續的決策網絡中用于智能體的決策。

2.2 采樣網絡

本節詳細介紹局部觀測重建網絡中的采樣網絡。LOBRE算法通過采樣網絡實現了局部觀測抽象,使得算法認識到并充分利用不同局面中的高維狀態表征。局部觀測重建網絡包含2個采樣網絡,結構相同,本文以圖3右側的采樣網絡為例進行闡述。如圖3所示,采樣網絡首先通過編碼器f把輸入信息Oinv編碼為均值μ和方差σ,如下式所示：

(μ,σ)=f(Oinv).

(5)

之后利用該均值和方差構建多維高斯分布N(μ,σ)。進而從中采樣得到輸出信息

Oout～N(μ,σ).

(6)

由于均值μ和方差σ都是通過編碼器f得到的,因此該多維高斯分布N(μ,σ)是可以被學習的。同時, 為保證從該多維高斯分布中采樣的過程是可以被神經網絡學習的,在對該多維高斯分布進行采樣的過程中采用了重參數化技巧。

由于LOBRE算法沒有改變信用分配網絡的結構,由式(3)可知,LOBRE算法仍然滿足IGM條件,也就是說最優的聯合動作等于最優個體動作的集合。為了證明加入的2個采樣網絡的有效性,在實驗部分進行了驗證,證明加入采樣網絡之后再進行拼接得到經過重建的局部觀測信息Orecon相比直接拼接得到Orecon效果更好。

2.3 總體優化目標

本文算法框架的總體優化目標是DQN算法中的時序差分誤差(TD-error),如下式所示：

(7)

(8)

其中：b是從經驗回放池中采樣得到的一個批次樣本的數量,θ是網絡的參數,θ-是目標網絡的參數,目標網絡參數θ-通過周期性地拷貝θ進行更新。更新周期為200個時間步。

LOBRE算法使用中心化訓練分布式執行框架進行端到端訓練從而對上述總體優化目標進行優化。在中心化訓練階段,網絡參數共享,同時信用分配網絡可以獲取全局狀態信息s和聯合動作-觀測歷史τ。在分布式執行階段,智能體不能使用信用分配網絡,只能使用本地的動作-觀測歷史τi進行決策。

3 實驗設計與結果分析

3.1 實驗環境設置

本文所采用的算法性能測試環境是星際微操環境。星際微操環境是一個標準的用于檢驗多智能體決策能力的復雜環境,是當今驗證多智能體算法性能的一個重要環境。它具有狀態-動作空間大、部分可觀測、環境非平穩等特點,復雜性強,挑戰性高,是學術界常用的算法驗證環境。圖4展示了在地圖MMM2上的對戰畫面。

圖4 地圖MMM2的對戰畫面Fig.4 Combat scenario of map MMM2

微操是指對每個智能體分別進行控制以達到擊敗對手的目的。隨著智能體數目的增多,這種控制形式即可以被建模為多智能體問題。具體在星際微操環境中,智能體動作空間是離散的,具體包括4方向移動、攻擊目標、停止和不執行任何動作。其中,不執行任何動作單獨適用于陣亡的智能體。星際微操環境禁用了星際爭霸原有的移動-攻擊指令,徹底分離了移動和攻擊指令,使得智能體必須在每個時間步都進行動作決策,增加了決策的復雜度。

每個智能體都有自身的局部觀測,其觀測范圍局限于以之為中心的圓形范圍內,并且無法得到觀測范圍以外的信息。具體地說,智能體的觀測可以得到智能體當前位置、智能體之間的相對位置和觀測范圍內智能體的血量和護甲這3類信息。全局觀測信息由各智能體的局部觀測信息結合得到。為保證智能體在觀測到敵人后需要移動一段距離才可以進行攻擊,每個智能體的觀測范圍都被設置為9,攻擊范圍都被設置為6。

智能體在每個時間步都會接收到環境返回的全局獎勵。全局獎勵具體獎勵設置為：在對敵方智能體造成的傷害的基礎上減去我方智能體受到的傷害的一半,每殺死一個對手都會將10點獎勵額外給予智能體, 贏得游戲會將當前團隊剩余生命值的總和外加200點的獎勵給予智能體。

算法運行過程中,每隔2 000個時間步運行20局對戰作為測試,并統計當前時間點上的勝率,最終繪制勝率-時間步的曲線圖。本文使用的是基于星際爭霸SC2.4.10(B75689)游戲版本的SMAC環境。在Ad-Hoc協作場景的實驗中,使用一張地圖訓練算法,使用另一張地圖測試算法性能,比如5 m-5 ma表示在5 m地圖上進行訓練,在5 ma地圖上進行測試。

在算法訓練和測試的過程中使用了多種星際爭霸微操環境的地圖,包括從簡單、困難、到極度困難不同難度的地圖,以及同構、異構、對稱、非對稱多種設置的地圖,具體如表1所示。其中,狂熱者、跳蟲是近戰單位;掠奪者、海軍陸戰隊員、巨像、追獵者是遠程單位;醫療運輸機無法進行攻擊,但是具有治療友方單位的能力。

表1 本文使用的地圖Table 1 Maps used in this paper

在上述每張星際爭霸微操地圖上都使用5個不同的隨機種子運行200萬個時間步進行實驗并畫出算法的測試勝率-時間步曲線圖,同時用陰影表示25%～75%分位數的結果。所使用的顯卡為NVIDIA TITAN RTX GPU 24G。

3.2 基線算法和超參數設置

本文的基線算法為基于值分解的多智能體信用分配算法VDN、QMIX、QTRAN以及獨立Q學習算法IQL,如表2所示。上述算法均使用星際爭霸微操環境SMAC內置的代碼。同時,為了在智能體數量變化的測試環境下運行上述基線算法,使用注意力機制模型增強上述基線算法,從而使得上述基線算法可以接收數量變化的智能體輸入信息。為保證對比實驗的公平,使用SMAC環境提供的原始參數運行實驗。

表2 本文使用的算法Table 2 Algorithms used in this paper

使用QMIX算法的信用分配網絡,具體參數設置與QMIX相同。在智能體決策網絡中,使用具有64維隱藏狀態的門控循環單元,同時該門控循環單元的尾端連接了1個線性層。通過ε-貪心算法實現對智能體動作的探索。在訓練過程中,對超參數ε進行線性退火, 在5萬個時間步內從1逐步減少到0.05, 并在訓練結束前保持不變。本文所有的神經網絡都使用RMSprop優化器進行優化,學習率設置為5×10-4。智能體之間進行參數共享,所有的神經網絡均進行了隨機初始化并進行端到端訓練。

3.3 實驗結果

將LOBRE算法與IQL、VDN、QMIX、QTRAN算法在星際爭霸微操環境和Ad-Hoc協作場景下進行對比。其中,5m_vs_6m-6m_vs_6m地圖表示在5m_vs_6m地圖上進行訓練,在6m_vs_6m地圖上進行測試,也就是說在測試時增加了我方智能體的數目。3s2z-2s3z地圖表示在3s2z地圖上進行訓練,在2s3z地圖上進行測試,也就是說在測試時同時改變了不同種類的我方智能體的數目。5m-5ma地圖表示在5m地圖上進行訓練,在5ma地圖上進行測試。5ma-5m地圖表示在5 ma地圖上進行訓練,在5 m地圖上進行測試。上述2個地圖是在測試時改變了我方智能體的種類。

在本文所涉及到的地圖中,1c3s5z、2s3z是簡單地圖;5m_vs_6m是困難地圖,需要訓練更長時間才能有較好效果;MMM2是極度困難地圖,需要學到集火等某些特定的微操技巧才有可能取得對局的勝利。5m_vs_6m-6m_vs_6m地圖由于在測試的時候新增了隊友,因此相對容易;5m-5ma地圖由于在測試的時候更換了智能體的種類,因此相對復雜。

從圖5和圖6所示的實驗結果中可以發現,LOBRE算法在上述地圖上都取得了超過現有代表性算法的性能。其中,在簡單地圖上LOBRE算法性能略有提升,在復雜地圖上性能提升更加明顯,比如在5m_vs_6m地圖、MMM2地圖上。這可能是因為針對局部觀測的抽象和重建更有利于算法對于復雜策略的學習。同時,LOBRE算法在Ad-Hoc協作場景下取得了較大提升,這是因為LOBRE算法通過對局部觀測進行重建,使得算法可以有效利用不同局面中的高維狀態表征,適應變化的隊友,從而提升了算法在Ad-Hoc協作場景下的零樣本泛化能力。

圖5 LOBRE算法在SMAC上的實驗結果Fig.5 Experimental results of LOBRE algorithm on SMAC

圖6 LOBRE算法在Ad-Hoc協作場景的實驗結果Fig.6 Experimental results of LOBRE algorithm on Ad-Hoc cooperation scenarios

本文在Ad-Hoc協作場景5m_vs_6m-6m_vs_6m和3s2z-2s3z上進行消融實驗,如圖6所示。通過LOBRE算法和QMIX_Attn算法的性能對比可知,采樣網絡的加入提升了算法性能。通過LOBRE算法和QMIX算法的性能對比可知,局部觀測重建網絡的加入提升了算法的性能。

4 總結與展望

本文提出一種面向Ad-Hoc協作的局部觀測重建算法——LOBRE算法。該算法通過局部觀測重建網絡對智能體接收到的局部觀測進行重構,通過采樣網絡實現了局部觀測抽象,使得算法認識到并充分利用不同局面中的高維狀態表征,從而實現在Ad-Hoc協作場景下的零樣本泛化。對比實驗結果表明,LOBRE算法在星際爭霸微操環境和Ad-Hoc協作場景下均取得超過現有代表性算法的性能,證明了LOBRE算法的有效性。未來值得進一步探索的問題包括如何更有效地利用局部觀測增強算法的零樣本泛化能力,以及如何更好地對局部觀測進行抽象從而得到高維狀態表征等。