強化學習的地–空異構多智能體協作覆蓋研究

張文旭，馬磊，賀薈霖，王曉東

近年來，多智能體覆蓋問題得到了越來越多的關注[1]，并作為多智能體協調控制的一個重要研究方向，有著重要的理論和應用價值，在服務保障、工業制造、軍事偵察、安全保衛、災后搜救、星球探索、資源勘察等方面都有著廣闊的應用前景[2]，其主要研究包括路徑規劃、動態避障、任務分配等方面[3-4]。

對于一個多智能體系統，智能體的異構特性可以更大地發揮多智能體的優勢，更好地完成協作任務[5]。目前，大多數的覆蓋研究都基于智能體為同構的假設前提，而異構多智能體與覆蓋問題的結合相對薄弱，比如，文獻[6]在一階動態異構覆蓋問題中，考慮不同的速度對應不同的控制輸入，設計了一種分布式覆蓋控制策略；文獻[7]研究了非凸環境下的覆蓋問題，提出了一種梯度環境分割算法；文獻[8]在異構無線傳感器網絡中研究了覆蓋與消耗的控制算法；文獻[9]介紹了一種基于加權Voronoi圖的異構機器人覆蓋框架，根據異構覆蓋代價進行加權，實現代價最小的覆蓋任務。針對異構多智能體的覆蓋問題，目前多智能體的異構性多體現在傳感器的異構上，即感知范圍的不同，少有研究從智能體運動方式的異構性上進行考慮。另一方面，無人機(unmanned aerial vehicle, UAV)和無人車(unmanned ground vehicle, UGV)的異構特性協作是多智能體的前沿性研究課題[10]，它們在速度、負載、通信、觀測能力等方面具有很強的互補性，二者協作可以有效拓寬應用范圍, 其應用價值受到了世界各國學者的廣泛關注[11]，現有的工作主要集中在路徑規劃、搜索定位、跟蹤追逃等方面，比如，文獻[12]提出了一種UAV和UGV的合作導航策略，利用UAV的大視野特性引導UGV避障；文獻[13]研究了多UAV和UGV的合作監控，通過二者的觀測數據融合完成對目標的偵查；文獻[14]基于UAV和UGV的合作框架研究了人群跟蹤的決策和監控。但是，針對UAV和UGV互補特性的協作覆蓋問題尚未得到研究。

本文提出了一種地–空異構多智能體的協作覆蓋模型，針對未知環境下的動態覆蓋問題，依靠UAV機動性能與觀測范圍的優勢，在覆蓋過程中對UGV的動作進行指導，同時考慮了智能體的觀測局部性和不確定性，基于分布式局部可觀測馬爾可夫(DEC-POMDPs)模型建立柵格地圖覆蓋環境，根據UAV和UGV的異構特性設計覆蓋場景，并利用多智能體強化學習算法完成對地圖的覆蓋。

1 問題描述

1.1 多智能體覆蓋問題

覆蓋問題大體上可分為靜態與動態覆蓋兩類，靜態覆蓋主要關注傳感器位置的優化，動態覆蓋則要求智能體群組遍歷區域內所有興趣點。動態覆蓋包含了導航與避障的研究內容，目的是利用移動機器人或固定傳感器，在物理接觸或傳感器感知范圍內遍歷目標環境區域，并盡可能地滿足時間短、重復路徑少和未遍歷區域小的優化目標[2]。

本文考慮帶有觀測不確定性的異構多智能體動態覆蓋問題，以柵格地圖為覆蓋環境，UGV作為覆蓋執行者，UAV則作為引導者。利用UAV觀測范圍廣和移動速度快的優勢對UGV的覆蓋行動進行指導，以擴大UGV的觀測視野和提高團隊對位置環境的獲取準確性，UGV不斷移動直到柵格被覆蓋到指定的程度。智能體的路徑以柵格序號進行表示，便于算法中地圖信息和智能體狀態的更新。

1.2 分布式馬爾可夫模型

分布式控制是多智能體系統的一個重要特性，由于智能體攜帶的傳感器存在精度誤差，且覆蓋環境復雜多變，智能體的局部觀測性和環境的不確定性將難以避免[12]。針對以上問題，考慮采用分布式局部可觀測馬爾可夫模型(DEC-POMDPs)[13]，其由一個八元組構成：

1.3 Q學習

文獻[14]提出了一類通過引入期望的延時回報，求解無完全信息的馬爾可夫決策過程的方法，稱為Q-學習(Q-learning)。Q-學習是一種與模型無關的基于瞬時策略的強化學習方法，通過對狀態–動作對的值函數進行估計，以求得最優策略。Q-學習算法的基本形式如下：

2 覆蓋問題設計

2.1 異構多智能體設計

對于異構多智能體系統，首先需要對單個智能體的特性進行分析。UGV能夠裝載大容量動力裝置和大型精密儀器，具備較高的數據處理運算能力，但移動速度慢，視野范圍小，在障礙物密集的區域，行動能力受到極大限制；相比之下，UAV具有較高的移動速度和空間靈活性，移動過程中不需要考慮地面復雜的障礙環境，然而它的實時運算能力、負載能力和電量荷載受到較大限制。

根據UGV和UAV的上述特性，在地–空異構多智能體覆蓋問題中，如圖1所示，UAV以五角星表示，定義UAV采取類似于攝像頭抽象環境掃描算法，在環境中的觀測范圍為一個掃描半徑為2個柵格的圓形區域，如虛線區域所示，其中12個陰影柵格為UAV的觀測，并據此獲得相關觀測矩陣。

圖1 UAV and UGV的異構觀測Fig. 1 The heterogeneous observation of UAV and UGV

UAV獲得的觀測信息不僅用于決策UAV的下一步移動動作，還需要向UGV提供額外的地圖環境信息。其次，考慮到UAV的速度異構特性，定義其移動速度為每步2個柵格，圖中箭頭表示智能體的移動方向。UGV以圓圈表示，不同于UAV具備廣闊的高空視野，UGV的觀測范圍較小，定義其觀測為前、后、左、右4個柵格，即周圍的陰影柵格，設定移動速度為每步1個柵格。UGV的優勢在于對環境信息的測量精度要高于UAV。

2.2 覆蓋場景設計

定義1 基于DEC-POMDPs的覆蓋環境需要體現出多智能體的異構性、分布式和不確定性，其組成類似于式(1)，可以抽象為一個 8元組結構，其中：

表1 觀測-狀態概率分布函數Table 1 The probability distribution function of observation-state

3 基于強化學習的覆蓋算法

3.1 異構多智能體學習決策

在覆蓋場景中，我們將UGV設定為任務執行者，負責訪問地圖上尚未被探索的柵格，而將UAV設定為作團隊中的督導者，通過通信向UGV提供更廣闊的視野信息，配合UGV建立更精確的信念狀態，實現更高效的覆蓋。

考慮到智能體的結構異構性和局部觀測性，假設UAV可以向觀測范圍內的UGV進行單向通信，并發送UAV的觀測信息，而UGV之間不能進行通信。UAV的強化學習一步策略更新的流程如圖2所示。

圖2 UAV強化學習一步策略更新流程Fig. 2 The one-step strategy update flow of reinforcement learning of UAV

UGV獲得的觀測能夠被分為兩類：1)根據智能體自身傳感器獲得的局部觀測信息；2)依賴通信行為獲得的UAV的觀測信息，則聯合觀測表示為?}，。

由于局部觀測性的存在，UGV不一定在所有時刻都能獲得UAV的觀測信息，本文用類似文獻[15]所提通訊受限的多智能體在線規劃算法的思想，將學習過程分為可以通信與不能通信兩種情況。在DEC-POMDPs 模型中嵌入多個局部可觀察馬爾可夫決策過程(partially observable Markov decision processes, POMDP)模型作為輔助學習單元，在POMDP模型中使用最大似然算法，如表1所示，并將局部狀態近似看作全局狀態。當執行策略更新時，依照觀測來源將觀測劃分為局部觀測和聯合觀測兩類，強化學習框架如圖3所示。

圖3 異構多智能體強化學習框架Fig. 3 The frame of reinforcement learning of heterogeneous multi-agent

3.2 基于強化學習的覆蓋算法

解決強化學習問題主要是找到一個策略使智能體團隊最終達到最大的獎勵信號。如果在所有狀態下，策略都大于或等于策略的期望回報值，那么稱這個策略為最優策略，記作。而最優策略對應的狀態–聯合動作對也有相同的最優值函數，記作。在POMDP模型下，智能體i 在狀態下執行行動獲得的Q值為

DEC-POMDPs與POMDP的唯一區別在于智能體的數量由單個變為多個，其Q-學習迭代表達式與POMDP類似，智能體的行動由單獨行動變為聯合行動：

4 仿真結果

圖4 多智能體覆蓋環境Fig. 4 The coverage environment of multi-agent

圖5 異構多智能體覆蓋完成步數Fig. 5 The coverage steps of heterogeneous multi-agent

執行1 000幕覆蓋實驗后的學習效果如圖5所示，可以看出隨著學習幕數的增加，經過700幕左右學習后，智能體團隊完成地圖覆蓋所需步數逐漸收斂到較穩定的值，其中虛線為覆蓋步數擬合曲線，圖中覆蓋步數存在的毛刺原因為智能體的觀測帶有不確定性，當觀測信息出現錯誤時，可能使智能體當前學習幕的覆蓋完成步數出現波動。圖中實線表示一個UAV和兩個UGV組成的異構多智能體團隊，虛線表示只有兩個UGV組成的團隊。從圖中可以看出，兩種智能體團隊對地圖的覆蓋成功率都隨著強化學習算法的迭代不斷得到提高。但是，在存在UAV的團隊中，因為UAV可以對UGV的覆蓋行動進行指導，所以在經過700幕左右學習時，團隊覆蓋成功率就開始趨于穩定，而只有UGV的團隊，需要900幕左右的學習才開始趨于穩定，因此體現出UAV與UGV協作覆蓋的優勢。

圖6 覆蓋試驗成功率Fig. 6 The success rate of coverage

最后，在地圖左上角設置了一個影響整體覆蓋效果的“陷阱”區域，用以進一步的驗證在強化學習過程中，UAV對UGV的引導效果。陷阱區域如圖4中虛線圈區域所示，為邊界與障礙物所夾的6個柵格，訪問此區域的回報，低于訪問其他空曠區域的回報。當覆蓋率達到95%時，認為本次覆蓋任務成功，但陷阱區域屬于不應該訪問的5%部分，每幕覆蓋實驗結束后，記錄陷阱區域被訪問的次數，每20個學習幕進行一次采樣。

圖7對比了UAV加入覆蓋任務時對陷阱區域的訪問效果，由圖中可以看出，兩種智能體團隊對陷阱區的訪問次數，都將隨著學習幕數的增加而逐漸減少，最終將不再訪問陷阱區，體現了強化學習算法對于覆蓋問題的有效性。但是，在只有兩個UGV組成的團隊進行覆蓋任務時，由于UGV的觀測范圍較小，團隊需要更多的學習幕數后，才能減少對陷阱區域的訪問。

圖7 陷阱區域訪問次數統計Fig. 7 The count of visits to the trap

5 結束語

本文探討了異構多智能體與動態覆蓋問題的結合，以UAV和UGV的異構協作任務為背景，提出了一種地–空異構多智能體協作覆蓋模型。根據UAV和UGV的異構特性，設計了UAV和UGV互補的覆蓋觀測方法，同時考慮到智能體觀測的局部性和不確定性，以DEC-POMDPs為模型建立覆蓋場景，并利用多智能體強化學習算法完成了對環境的覆蓋。進一步工作主要包括：1)在強化學習動作選擇中考慮UAV和UGA的動力學模型；2)在UAV與UGV的互補特性中考慮分布式系統的信息融合問題，以提高學習收斂速度。

[1]KANTAROS Y, ZAVLANOS M M. Distributed communication-aware coverage control by mobile sensor networks[J]. Automatica, 2016, 63: 209–220.

[2]蔡自興, 崔益安. 多機器人覆蓋技術研究進展[J]. 控制與決策, 2008, 23(5): 481–486, 491.CAI Zixing, CUI Yi’an. Survey of multi-robot coverage[J].Control and decision, 2008, 23(5): 481–486, 491.

[3]MAHBOUBI H, MOEZZI K, AGHDAM A G, et al. Distributed deployment algorithms for improved coverage in a network of wireless mobile sensors[J]. IEEE transactions on industrial informatics, 2014, 10(1): 163–174.

[4]TAO Dan, WU T Y. A survey on barrier coverage problem in directional sensor networks[J]. IEEE sensors journal,2015, 15(2): 876–885.

[5]TIAN Yuping, ZHANG Ya. High-order consensus of heterogeneous multi-agent systems with unknown communication delays[J]. Automatica, 2012, 48(6): 1205–1212.

[6]SONG Cheng, LIU Lu, FENG Gang, et al. Coverage control for heterogeneous mobile sensor networks on a circle[J].Automatica, 2016, 63: 349–358.

[7]KANTAROS Y, THANOU M, TZES A. Distributed coverage control for concave areas by a heterogeneous robotswarm with visibility sensing constraints[J]. Automatica,2015, 53: 195–207.

[8]WANG Xinbing, HAN Sihui, WU Yibo, et al. Coverage and energy consumption control in mobile heterogeneous wireless sensor networks[J]. IEEE transactions on automatic control, 2013, 58(4): 975–988.

[9]SHARIFI F, CHAMSEDDINE A, MAHBOUBI H, et al. A distributed deployment strategy for a network of cooperative autonomous vehicles[J]. IEEE transactions on control systems technology, 2015, 23(2): 737–745.

[10]CHEN Jie, ZHANG Xing, XIN Bin, et al. Coordination between unmanned aerial and ground vehicles: a taxonomy and optimization perspective[J]. IEEE transactions on cybernetics, 2016, 46(4): 959–972.

[11]ZHOU Yi, CHENG Nan, LU Ning, et al. Multi-UAV-aided networks: aerial-ground cooperative vehicular networking architecture[J]. IEEE vehicular technology magazine,2015, 10(4): 36–44.

[12]PAPACHRISTOS C, TZES A. The power-tethered UAVUGV team: a collaborative strategy for navigation in partially-mapped environments[C]//Proceedings of 22nd Mediterranean Conference of Control and Automation.Palermo, Italy, 2014: 1153–1158.

[13]GROCHOLSKY B, KELLER J, KUMAR V, et al. Cooperative air and ground surveillance[J]. IEEE robotics and automation magazine, 2006, 13(3): 16–25.

[14]KHALEGHI A M, XU Dong, WANG Zhenrui, et al. A DDDAMS-based planning and control framework for surveillance and crowd control via UAVs and UGVs[J]. Expert systems with applications, 2013, 40(18): 7168–7183.

[15]馬磊, 張文旭, 戴朝華. 多機器人系統強化學習研究綜述[J]. 西南交通大學學報, 2014, 49(6): 1032–1044.MA Lei, ZHANG Wenxu, DAI Chaohua. A review of developments in reinforcement learning for multi-robot systems[J]. Journal of southwest Jiaotong university, 2014,49(6): 1032–1044.

[16]PUTERMAN M L. Markov decision processes: discrete stochastic dynamic programming[M]. New York: John Wiley and Sons, 1994.

[17]WATKINS C J C H, DAYAN P. Q-learning[J]. Machine learning, 1992, 8(3/4): 279–292.

[18]WU Feng, ZILBERSTEIN S, CHEN Xiaoping. Online planning for multi-agent systems with bounded communication[J]. Artificial intelligence, 2011, 175(2): 487–511.