一種面向無人機群區域協同覆蓋的深度強化學習方法

姜 波，梁晨陽，梅 杰，馬廣富

哈爾濱工業大學(深圳)，深圳 518055

0 引 言

在火星探測任務中，火星車由于自身運動限制，無法獲得大面積火星地表信息，因此火星車通過攜帶小型無人機編隊來實現對地表的大范圍信息采集.無人機編隊UAV(unmanned aerial vehicles)具有靈活性、移動空間大等特點，其能夠在沒有固定基礎設施的情況下，提供救援、搜索和基礎服務覆蓋等服務.例如文獻[1]研究使用無人機編隊為指定區域提供無線通信服務；文獻[2]通過調整無人機編隊中每個無人機位置，在陌生環境下為目標點提供實時定位服務；文獻[3]使用無人機編隊，實現對特定區域中指定目標的搜索，文獻[4]通過改進的遺傳算法解決有障礙區域的無人機群多目標點路徑規劃問題.除此之外，無人機編隊還可以應用于未知環境探索[5]、區域監視[6]等領域.上述應用都利用了無人機編隊的可操作性、靈巧性和魯棒性.考慮到無人機的速度和姿態的實時調整、地面站到無人機視野的遮擋等復雜環境，使用地面站來控制每架無人機并不可靠.因此，亟需結合具體應用場景，發展一種完全自治、不需要地面站控制的的編隊算法.

考慮圖1的場景，在地外系統中，當地面車需要獲取某一片未知區域的信息時，就可以采用搭載相機的無人機群，這些無人機在目標區域上空散開.每架無人機通過自身機載傳感設備對一部分目標區域進行地面信息采集(比如地形、紋理等)，而所有無人機采集到的信息能夠覆蓋整個目標區域，完成信息采集后編隊可以通過離線或在線方式把信息數據發送給地面車輛.在上述場景下，編隊需要考慮幾個問題：一是由于每架無人機通信范圍有限，無人機群之間必須保持通信連接,以保證在距離較遠和有障礙物遮擋的情況下，整個無人機群能和地面保持通信連接[7]；二是無人機機載感知設備的覆蓋范圍有限，可以認為是一個各向同性的圓；三是在地外系統中無人機需要長時間工作，而無人機的能量來源于地面車的太陽能充電，在火星惡劣的沙塵暴環境下，“機遇號”[8]火星探測車上面的太陽能電池板產生電量僅僅能產生晴天的九分之一，因此無人機在工作期間要盡可能減少能量損耗.綜上，無人機在上述場景下，受到通信范圍約束、感知范圍約束和能量有限約束，考慮到每架無人機均是一個獨立的智能體，因此需要采用分布式的控制方法.本文的目標是通過設計無人機編隊的分布式控制方法，采集盡可能多的目標區域信息.這個問題主要有以下幾個難點：一是由于無人機數量有限，需要每架無人機找到最優位置，這樣才能采集到盡可能多的信息；二是由于無人機的移動需要消耗能量，需要衡量無人機移動和能量消耗之間的關系；三是無人機不能失去和其他無人機的通信.

圖1 無人機編隊對目標區域進行覆蓋采集信息Fig.1 UAV formation covers the target area and collects information

為解決上述問題，大量研究利用多智能體系統研究區域覆蓋問題[9].在文獻[10]中，作者提出一個框架，在這個框架中通過特定的執行參數和系統條件(即剩余能量、計算能力和特定車載傳感器提供的能力)，能夠對無人機進行編程和管理，以及協調無人機編隊行動.為提高智能體搜索目標的效率，在文獻[11]中把目標區域分割成若干個大小相同的單元格，并且提出一個統計框架來預測智能體應該在一個單元格中花費的時間量，以增加該單元格中的目標檢測置信度.在單元格被智能體覆蓋之后，擁有目標的概率會被更新.但是文中需要一個集中式的概率地圖來存儲每個單元格的概率.文獻[12]為解決異構智能體覆蓋問題，將這個問題分成了2層，上層是根據每個子編隊能力的不同，將目標區域劃分給每個子編隊，下層是根據子編隊中每個智能體的能力不同，將子區域劃分給每個智能體.2層的目標函數形式相同.上下2層分別使用不同的分割算法來分割目標區域，目的是為了發揮2種分割算法的優點.文獻[13]考慮的是1維的覆蓋問題，能夠推導出當多智能體系統滿足一定條件時，覆蓋效果能夠達到最好，即目標函數達到全局最優.因此，文章沒有對目標函數進行求導，而是在全局最優條件的基礎上設計負反饋控制律.此外，控制律的設計還考慮了圓上智能體順序的保持，不僅能夠保證智能體間避免碰撞，還能夠簡化收斂性分析.文獻[14]為找到最優的智能體配置方案，設計了一種“離線+在線”的方法.假設可使用的智能體數量固定，在離線階段通過貪心算法尋找所有可用智能體初始位置.離線的貪心算法的好處一是能夠提供智能體的初始位置，二是能夠克服局部最優限制，三是能夠提供一個目標函數下界.在線階段，通過梯度下降算法，一是去除多余的智能體，二是進一步調整智能體位置.通過仿真證明，整個算法總能夠使目標函數近乎達到全局最優解.文獻[15]為得到離散系統的梯度方向，僅需要對智能體覆蓋區域的邊界曲線進行積分，這樣做好處是減少計算量.此外，文中還設計了智能體移動條件，保證在控制律作用下，智能體的每次移動都能夠使目標函數增加.文獻[16]以控制質心和智能體實際坐標誤差為目標，通過控制律使得誤差呈指數衰減.在設計完梯度下降的控制律后，使用模糊邏輯和自適應方法，近似控制律中未知項，并且使用魯棒覆蓋準則減少自適應模糊系統近似誤差.文獻[17]的控制律設計不同于上述文獻，為解決Art Gallery完全覆蓋問題，在Max-Sum算法基礎上發展出CMGD算法，通過對未知探索區域的近似以及證明Utility Function可導，使得改進后的算法能夠使覆蓋區域沿著梯度方向變大，適用于離散和連續條件以及適用于智能體全向或扇形探測模型.此外，文章還設計智能體釋放策略，通過逐個釋放智能體，保證智能體的最大利用.

一些研究成果同樣考慮了多智能體系統的約束問題.文獻[18]為解決覆蓋中的通信連通約束，將約束轉換為一不等式約束.此外，在上述不等式約束下，系統容易陷入局部最小值，為解決這個問題，文章在目標函數中加入每個Voronoi圖質心到目標區域質心的距離.但是對目標函數如此改造，文中沒有給出具體說明或理論證明.文獻[19]同樣嘗試解決連通約束問題，不過文章在維持連通的同時，最大限度提高覆蓋范圍.文章將這個問題分解成2部分，一是尋找最小生成樹，這是維持連通的最小拓撲，二是在最小生成樹拓撲下，對CVT的名義控制律輸出加上一個Control Barrier Function約束，約束最終控制律輸出和名義控制律輸出夾角余弦大于零.這種做法不足的地方，一是需要對上述約束分布式化，二是需要智能體在線求解QP優化問題.文獻[20]不同于其他算法單純從圖論或者控制器輸出來達到連通性約束，而是考慮了路由維護需求，如果不滿足路由維護，就把控制律給出的下一時刻坐標點映射到最近的滿足路由維護的點上.

深度強化學習近年來同樣吸引了很多不同領域的學者研究.文獻[21]的作者開創性地引入一個強化學習框架，它使用DQN作為函數近似器，以及經驗回放和目標網絡2種新技術，以提高學習穩定性.還有其他學者提出許多擴展來解決DQN的限制.文獻[22]提出一種DDQN，將深度Q網絡和目標網絡解耦以避免高估.文獻[23]使用重要度采樣的方法，提高樣本的利用效率.文獻[24]提出一種分布式強化學習網絡，通過學習折扣回報的分類分布和噪聲網絡，得到更優的結果.在文獻[25]中，作者將上述2種方法以及其他4種方法組合在一個名為“彩虹”的模型中，具有更優異的性能.為解決連續動作空間的問題，文獻[26]提出一種基于確定性策略梯度的無模型算法，該算法可以在連續動作空間上運行.其他關于深度強化學習的工作包括文獻[27-28].雖然深度強化學習在一些實際的應用場景如游戲、機械臂控制[29]等方面有重要的應用，但它在多智能體系統控制上的適用性和有效性仍未得到有效解決.

多智能體強化學習算法是在單智能體強化學習基礎上發展出來的算法，解決群體與環境交互的決策和控制問題.MADDPG[30]算法是對DDPG算法的改進，其能夠解決復雜多智能體環境下的問題，MADDPG算法采用了集中式訓練分布式執行的方法，在一定程度上緩解了多智能體環境下的非穩態問題.MAPPO[31]算法基于全局狀態而不是智能體的局部觀測來學習一個策略和中心化的值函數，算法將原本在單智能體環境上表現突出的PPO[32]算法擴展到了多智能體環境上，通過采用一系列的技巧，包括廣義價值優勢估計、觀測值歸一化、層歸一化和梯度裁剪等，MAPPO算法在多智能體環境下表現出了良好的性能.VDN[33]算法主要解決智能體訓練過程中的獎勵信用分配問題，通過將團隊價值函數分解為單個智能體的價值函數之和，能夠有效解決“惰性”智能體的出現.而QMIX[34]算法則是將VDN算法中將各個智能體的價值函數簡單相加變為采用非線性組合的方式，并且在混合網絡中引入了全局信息，算法解決了智能體數量過多情況下的參數爆炸以及信用分配問題.

本文基于深度強化學習DRL(deep reinforcement learning)技術，提出一種分布式多無人機覆蓋控制算法.使用神經網絡控制無人機編隊的移動，通過定義適當的獎勵函數來實現指標的最大化(包括最大覆蓋面積、無人機群連通性保持和最小能源消耗).算法采用了參數共享機制，通過采用圖神經網絡DGN(deep graph network)作為模型隱藏層，模型不會受到因輸入的排列不同產生的影響.最后使用本文所提算法和其他2個基線方法進行了比較，結果表明本文所提算法優于其他2種算法.

本文其余部分組織如下.第1節定義系統模型并對問題進行建模.第2節詳細介紹本文所提出的算法.第3節介紹仿真實驗結果和分析.最后在第4節對本文進行總結.

1 無人機編隊覆蓋控制問題

本文考慮多約束下無人機編隊對2維區域的覆蓋問題.無人機編隊構成集合N{i=1,2,…,N},集合中每架無人機均能執行覆蓋任務，每架無人機的覆蓋范圍是一個半徑為Rsense的各向同性圓，并且無人機的飛行高度固定.我們假設每個時刻無人機能夠定位到自身的位置，并且能知道待覆蓋區域的形狀.

表1 變量名稱和含義Tab.1 Variable definitions

(1)

其中φ(q)是表示點重要程度的函數，在區域內每個點重要程度一致的情況下，φ(q)退化為常數1.

綜上，本文的目標是通過設計無人機編隊的分布式控制律，控制每架無人機到達合適位置，并且最大化覆蓋目標區域.無人機編隊要同時滿足以下要求：一是最大化目標區域的覆蓋面積；二是最小化能量損耗；三是保持無人機群的通信連通性.

2 基于強化學習的覆蓋控制策略

2.1 基本理論

強化學習可以概括為智能體通過與環境交互來學習策略.在t時刻，智能體獲得環境狀態值為st，根據自身行為策略π，采取下一步行為at，并且該行為產生的獎勵為rt.策略看作是一個從狀態到執行動作的概率映射，表示為π(at|st).智能體的目標是通過學習策略，從而在與環境交互時使得未來累計獎勵最大化，其數學表示為

(2)

其中T表示最后一個時隙，γ表示折扣因子，取值為0≤γ≤1，rt表示在時隙t時的獎勵.

基于值函數的強化學習方法關鍵在于對智能體動作價值函數的估計.假設在t時刻環境狀態值為st，智能體采取行為at，狀態-動作價值函數Q(st,at)滿足貝爾曼方程

(3)

隨著迭代次數j→∞，值函數會收斂到最優值Q*.在Q-learning方法的基礎上發展而來的DQN[28]方法，這種方法使用DNN作為函數估計，解決了狀態數量無窮的情況，通過最小化損失函數(4)進行訓練，損失函數表示為

(4)

(5)

文獻[36]提出的策略梯度方法可以應用于連續系統.令θπ表示行為策略參數，πθπ(at|st)表示在時刻t、狀態值st時，采取行為at的概率，ρπ表示在策略π下智能體的狀態分布函數.目標函數可以表述為最大化J(θ)=Es～ρπ,a～πθπ[R1].根據策略梯度[36]方法對策略參數θπ進行更新，關于參數θπ的梯度計算方式如下:

(6)

另外可根據“REINFORCE”[35]方法來獲取Q(st,at)的值.

在基于“ACTOR-CRITIC”框架的強化學習算法中，ACTOR指的是策略函數的近似值，CRITIC指的是價值函數的近似值.DDPG[26]是這種框架下的一個典型算法，并且ACTOR網絡從狀態到動作的映射是一個確定的值，這個映射通過μ表示.通過最小化損失函數(4)來對CRITIC網絡參數進行訓練.ACTOR網絡參數更新依照下式

(7)

DDPG也采用了TARGET網絡和經驗回放池提高訓練穩定性.由單智能體DDPG算法發展而來的多智能體強化學習算法MADDP[30]用來解決多個智能體的控制決策問題，每個智能體在訓練階段能夠獲取到全局的狀態信息，在一定程度上解決了多智能體環境的非穩態性.每個智能體需要維護一個CRITIC網絡的拷貝Qi.CRITIC網絡的參數更新按照損失函數(8)進行

(8)

(9)

2.2 基于強化學習的多智能體覆蓋控制算法

本文提出一種基于圖神經網絡和參數共享機制的多智能體強化學習無人機覆蓋控制算法.用來解決在MLP網絡中由于輸入排列不同而導致的輸出不同的問題.

(1)參數共享機制

相比較于MADDPG算法，我們維護一個所有智能體共享的CRITIC網絡來指導無人機進行訓練，即Q1=Q2=…QN=QG.

MADDPG算法中每個無人機維護一個ACTOR網絡，每個無人機還需額外維護一個CRITIC網絡.通過CRITIC網絡指導無人機對ACTOR網絡進行訓練，如圖2所示.

圖2 MADDPG示意圖Fig.2 MADDPG schematic

MADDPG算法的網絡參數將隨著智能體數量的增加而線性增加，CRITIC網絡參數的空間復雜度為O(N)，而采用共享機制的CRITIC網絡參數復雜度為O(1)，這減少了訓練參數的數量，提高了訓練的速度，如圖3所示.

圖3 基于參數共享的Q網絡Fig.3 Q network based on parameter sharing

(2)CRITIC網絡隱藏層設計

本文使用圖神經網絡[37]來作為CRITIC網絡的隱藏層.對于具有相同動力學模型，相同感知視野的無人機，在不同的時刻，當無人機群的全局狀態相同，但輸入到全局Q網絡的順序不同時，對于采用全連接層作為隱藏層的CRITIC網絡，2種情況下將作為不同的輸入處理，從而產生不同的價值函數，如圖4所示.

圖4 MLP網絡結構Fig.4 MLP network structure

圖4中4個智能體不同的顏色代表不同的觀測值，對于同質的智能體，2種情況下CRITIC獲得的全局狀態應該是一致的，但是神經網絡輸出了不同的價值函數.而采用圖神經網絡作為隱藏層，不會受到因輸入的排列而產生的影響.如圖5所示，輸入到神經網絡的無人機觀測值排列不相同，然而經過圖網絡處理后，得到了相同的輸出值.

圖5 圖神經網絡結構Fig.5 Graph neural network structure

采用圖神經網絡的CRITIC網絡，其前向傳播方式為

(10)

其中fGCN表示圖卷積層，fv是全連接層，fmax表示最大池化.zt=[otat]表示所有智能體的觀測向量和動作向量的拼接.輸入是從右往左傳播到輸出的，°代表網絡的連接.

(3)參數共享和圖神經網絡強化學習算法設計

(11)

根據如下的損失函數更新CRITIC網絡參數θQ.

(12)

(13)

最后更新ACTOR網絡和CRITIC網絡對應的TARGET網絡參數

(14)

TARGET網絡的更新采用軟更新的方式，參數τ表示目標網絡每次向評估網絡移動的距離百分比，采用這種方法，保證了訓練的穩定性.完整的訓練算法流程如表2所示.

表2 訓練算法步驟Tab.2 Training steps

(4)獎勵函數設計

關于獎勵函數的設計，我們需要考慮以下幾點.一是每個無人機自身覆蓋到的范圍的大小，另外是能量約束以及無人機之間的連通限制.根據以上要求，將獎勵函數設計為如下的3個部分

(15)

單個無人機的總的獎勵函數表示為3部分獎勵函數的加權之和.當調整系數a1較大時，表示地面無人車輛需要盡可能多地獲取區域的信息，無人機群應該盡可能多的實現對區域的覆蓋.取a2較大時，表示無人機群對于能量消耗敏感.取a3較大時，地面無人車希望無人機群能一直保持通信連通.通過在仿真中不斷對3個系數進行調整，可以達到一個我們預期的覆蓋效果.

3 仿真環境設計與結果分析

3.1 仿真場景與參數設計

本文假設在地外系統中，地面車輛可以攜帶3架無人機.地面車輛要求無人機群覆蓋的區域在實時發生變化.我們模擬地面車輛給無人機群下達的覆蓋區域指令從一個半徑為R的圓上隨機選取4個點得到，如圖6所示，取R=5 m，目標區域內每個點的重要程度是一致的取φ(q)=1.

圖6 覆蓋目標區域(藍色四邊形內)Fig.6 The target area to be covered (inside the blue quadrilateral)

取無人機參數：覆蓋半徑Rsense=2 m，通信半徑Rconnect=5 m，每次迭代無人機移動的單位步長為Δx=0.1 m.

CRITIC網絡輸入層后面接層圖神經網絡，圖網絡的輸出層采用平均池化并接一個全連接層.ACTOR網絡為4層的網絡結構，包含輸入層、2層的隱藏層和輸出層.輸出層輸出無人機下一時刻應該移動的方向.隱藏層激活函數使用RELU，輸出層激活函數使用TANH.網絡權重和偏置采用了正交初始化.在調整a1、a2和a3時，發現3個值都為1可以取得較好的覆蓋效果，其他參數如表3所示.

表3 訓練參數Tab.3 Training parameters

3.2 仿真結果

我們使用算法構建了模型并對模型進行了2次訓練，第1次訓練采用的Mini Batch大小為128.第2次訓練的Mini Batch大小為256.訓練結果如圖7～8所示.

圖7 訓練過程reward變化示意圖Fig.7 Schematic diagram of reward changes during training

圖8 訓練過程loss變化示意圖Fig.8 Schematic diagram of loss change during training

2次訓練選取不同的Mint Batch大小，從訓練過程中的loss變化曲線上看，batch大小為256的訓練曲線峰值loss要小于 batch 為128，這符合理論上batch越大，loss的下降方向越符合真實梯度的要求.2次訓練loss都先呈現上升趨勢，然后穩步下降.經過分析是因為剛開始訓練時在動作中加入了隨機噪聲W，智能體策略傾向于探索.值函數在每一次更新中都去擬合了智能體最新的策略對應的價值函數，值函數的更新快.隨著學習步數增加，學習率衰減，隨機噪聲的去除，智能體策略趨于穩定.reward在訓練過程中始終呈現上升趨勢，并且最終趨于穩定，說明智能體在訓練過程中不斷的優化自身策略，并最終獲得一個較好的策略.

訓練完成后，測試效果如圖9所示，其中的圓形代表每個無人機的覆蓋范圍.圖9中3種不同顏色的圓形分別代表3個不同的無人機的覆蓋范圍，初始階段隨機初始化無人機的位置并使它們保持連通狀態，當迭代次數為35的時候到達了覆蓋任務中期，圖9中的3個無人機始終和自己最近的鄰居保持連通，在迭代步數為70的時候，從圖9中可以看出無人機已經完成了對目標區域的近似最優覆蓋.

圖9 覆蓋控制算法效果圖Fig.9 Overlay control algorithm renderings

為測試算法在無人機群連通性保持方面的表現，我們通過10次對隨機目標區域的覆蓋來觀察無人機群的通信連通保持情況.無人機之間的最大通信距離隨著仿真步數變化的情況如圖10所示.圖中的紅色水平虛線是我們設計的通信連通范圍限制，當無人機之間的最大通信距離超過紅線時，表示無人機網絡中存在無人機和集群斷開鏈接.從圖中可以看出，在執行覆蓋任務的時候，除了初始階段設定隨機初始位置的時候最大通信距離超過了紅色虛線，在覆蓋過程中所有無人機的最大通信距離始終保持在紅色虛線以下，表明無人機群的通信網絡始終保持連通.覆蓋過程中對目標區域的覆蓋比率隨著步數更新的曲線如圖11所示.

圖10 無人機之間最大通信距離變化曲線Fig.10 The curves of max connection distance between UAVs

圖11 無人機對目標區域的覆蓋比率變化曲線Fig.11 The curves of coverage rate

算法平均在前20步內即完成了對目標區域的近似最優覆蓋，覆蓋比率呈現穩步上升趨勢最終趨于穩定.藍色曲線有一個上升再下降的過程，分析是因為無人機學習到的覆蓋策略在一些形狀比較特殊的目標區域下容易陷入局部最優.沒有達到百分百的覆蓋比率是因為我們假設覆蓋區域為圓形，在無人機數量受限情況下無法實現對區域的全面覆蓋.

3.3 算法比較

我們使用MADDPG和隨機策略2種算法和本文算法進行了比較，任務為覆蓋10個不同的目標區域，比較的指標為所有無人機對目標區域覆蓋的面積之和取平均值.所有無人機在每次覆蓋任務中最多迭代步數為80步.算法運行的環境和初始條件都相同，算法測試得到的曲線如圖12所示.

圖12 MADDPG、隨機策略和本文算法的比較Fig.12 Comparison of MADDPG,random strategy and proposed algorithm

藍色的曲線代表使用參數共享和圖神經網絡作為CRITIC網絡的策略.綠色曲線代表的是MADDPG算法.橙色曲線代表隨機策略，無人機在每個時刻隨機的往一個方向移動.從reward曲線上可以看出DGN算法隨著步數的增加reward呈現穩步上升趨勢，MADDPG算法reward呈現震蕩，而RANDAN策略表現最差，reward呈現下降趨勢.綜上分析，采用參數共享和圖神經網絡作為CRITIC網絡的的多智能體強化學習覆蓋控制算法能較好的完成給定的覆蓋任務.

4 結 論

地外系統中，尤其是在火星復雜的地表環境下，地面車輛需要獲取給定區域的地圖信息，無人機群需要在復雜的情況下實現對目標區域的覆蓋.本文提出一種基于多智能體強化學習的無人機覆蓋控制算法.相比較于傳統的無人機覆蓋控制算法，本文提出的算法在考慮通信連通性、能量損耗約束方面具有優勢.并且所有無人機分布式執行策略.相比較于MADDPG算法，本文提出的強化學習算法采用CRITIC參數共享機制，使用圖神經網絡解決了狀態輸入的排列不一致問題.仿真結果表明本文提出的多智能體深度強化學習算法，能讓無人機群有效決策實現對目標區域的覆蓋.下一步的工作計劃考慮無人機的動力學模型，將本文提出的神經網絡決策與底層的無人機控制相結合，使得算法更加貼近于真實模型.