一種面向無人機區域協同覆蓋的感知任務分配方法

宋偉中 王行業 王 寧

1(黃河科技學院信息工程學院 河南 鄭州 450000) 2(華北水利水電大學信息工程學院 河南 鄭州 450000)

0 引 言

智能無人機目標搜索在很大程度上取決于無人機對區域環境的協同覆蓋和感知[1-2]，將無人機集群搜索的問題轉化為目標區域協同最優覆蓋問題，具有空間與功能上的分布性、任務執行的并行性及容錯性，可以有效地對危險區域進行目標搜索和定位。感知任務的合理分配是影響多無人機區域協同覆蓋的一個重要因素[3]，也是多無人機自主協同控制的重要研究方向[4]。

面向無人機區域協同覆蓋的感知任務分配方法，主要分為集中式任務分配和分布式任務分配[5]。其中，集中式任務分配方法通過中心系統控制無人機之間的通信和數據傳輸，針對任務需求和任務約束，確定無人機之間的任務序列，從而建立調度模型進行優化求解，包括整數規劃模型[6]、人工蟻群算法[7]、進化算法[8]；與集中式任務分配方法相比，分布式任務分配方法以去中心化的方式平衡任務分配的交互，能夠實現對任務態勢的快速優化組合及高效的同步共享，如基于合同網[9]方法，通過“招標-投標-中標”的市場拍賣機制實現無人機任務的委派和遷移，使系統以較低的代價和較高的質量完成區域協同覆蓋任務。考慮目標區域的動態變化和不確定性，以及無人機的局部觀測性，很多研究在動態實時環境下引入柵格化[11]的劃分方法對區域覆蓋，從而使無人機根據相同的柵格區域分配目標控制任務，實現代價最小的區域覆蓋。但柵格化的劃分使目標數據太大，導致無人機在大量的無關結果中篩選信息，計算開銷較大；交互式動態圖[12]和基于多agent[13]的任務分配方法可以求解空間狀態的目標搜索問題，在無先驗信息環境下實現區域協同覆蓋，但該方法受限于知識表達和推理的局部性，不能夠感知任務特征與目標區域的內部差異，使任務分配不能保證每次都計算出最優解；群智感知[14]任務分配系統尋求利益最大化的眾包任務競爭與激勵模式，可以為無人機區域協同覆蓋提供一種漸進式的任務分發服務，但其需要綁定多樣化的移動設備，且隨著任務的動態程度加大，需要選擇更多感知設備參與者調度無人機對區域協同覆蓋的任務，對于無人機針對異構設備的數據采集過于頻繁且要求較高，應用實現較為困難。

本文針對任務需求的差異，提出一種面向區域協同覆蓋的任務分配方法。考慮無人機局部觀測性和環境不確定性，該方法在構建分布式馬爾可夫覆蓋框架模型的基礎上，利用目標線路集和任務擴散調度序列集對目標區域進行差異化計算，提出基于強化學習的感知任務差異化分配方法，實現動態目標區域的最優覆蓋策略；采用MATLAB仿真平臺驗證本文方法的有效性。

1 問題描述及結構框架

1.1 環境描述

(1) 無人機屬性及飛行參數。無人機在一定區域W×W內飛行，集群控制系統對目標進行搜索覆蓋，并受到包括環境障礙、碰撞規避、電磁干擾和威脅入侵等干擾因素的約束和影響。設無人機集群系統為基于四旋翼無人機的同構群體，每臺無人機都架構了相同的傳感器和觀測系統，數量為NU臺，計算無人機的飛行參數，令其在固定高度下通過加速器直接測量機體坐標下的水平移動速度為VU，最大偏角度為φmax，有效探測距離為L。

(2) 動態目標搜索任務描述。設有NT個動態目標和Nd個干擾區域，如圖1所示。分別用三角形表示動態目標，用圓形表示干擾因素，目標以VT的速度向任意方向移動，所有的目標信息在搜索任務前均未知，無人機系統的任務是搜索這些目標并保證無人機不進入干擾因素，利用目標線路實現對目標區域的穩定覆蓋。

圖1 任務搜索區域

1.2 任務分配控制框架

針對在線實時環境下區域協同覆蓋的需求和目標信息的流向特點，將任務分配控制框架分為操作平臺、區域覆蓋和任務分配三個模塊，如圖2所示。

圖2 感知任務分配控制框架

操作平臺為用戶提供數據基礎服務和可視化操作界面，包括ArcGIS數據服務和信息系統界面，通過分布式通信組網聯通實時在線的多臺無人機系統。

區域覆蓋模塊包括區域差異劃分、分布式馬爾可夫覆蓋模型和任務擴散調度，當獲取區域覆蓋需求后，首先根據任務關聯比重將擬覆蓋區域進行差異劃分，然后構建分布式馬爾可夫覆蓋模型在劃分的區域中選擇覆蓋線路，為任務的擴散調度提供數據交互的模型。

任務分配模塊在實現差異化分配計算的基礎上，提出強化學習的方法，利用選擇目標線路集和擴散調度任務序列，從而找到一個策略使無人機達到最大的獎勵回報信號，實現區域的最優協同覆蓋。

2 目標區域覆蓋模型

2.1 目標區域差異劃分

(1)

然后，根據Voronoi圖和任務關聯比重對目標區域進行差異劃分，計算式如下：

(2)

2.2 分布式馬爾可夫覆蓋模型

無人機實時在線感知已差異劃分的目標區域，針對局部不確定態勢環境下，對于任務分配而言根據差異劃分的區域線路選擇判斷區域覆蓋的程度，利用文獻[17]所提出的分布式馬爾可夫覆蓋模型推測并優化最佳的個體路線集合和群體行為，可以解決對區域覆蓋的任務分配。

定義1分布式馬爾可夫覆蓋模型。對于一臺無人機Ui在子區域Ω而言，將目標區域覆蓋構建為一個分布式馬爾可夫模型：

M={Ui,Si,R(Ui),{Ai},{δi},Pi,Reword,X0}

(3)

式中:Ui表示無人機集合，Ui={U1,U2,…,UN}；Si為無人機狀態空間；R(Ui)表示無人機訪問某一子區域Ωi的線路集合；{Ai}表示為動作空間集合，以水平移動速度VU在任意方向飛行；{δi}表示無人機Ui可觀測的目標集合。δi(t)={regi(t),posi(t),0≤i≤1}，表示t時刻第i臺無人機Ui的局部可觀測目標區域信息regi(t)和位置信息posi(t)，regi(t)表示對當前區域內觀測信息的集合info={infoconvered,infounconver,Ci}，infoconvered表示已被覆蓋的子區域集合，infounconver表示未被覆蓋的子區域集合，Ci為滿足干擾因素條件的集合。無人機在可觀測范圍內可以根據區域劃分判定目標所在位置。

Reword計算了無人機Ui在當前狀態Si下經過某個動作Ai到達狀態Si+1的回報值，在覆蓋線路選擇時使用無人機獲得了不同的回報值，從而保證對目標區域的覆蓋。

X0為初始信念狀態，無人機通過初始信念狀態和初始函數獲取當前狀態向量，指導無人機的行為動作。

2.3 任務擴散調度

由于任務信息轉發所需的近距離接觸時間是不可忽略的，需要對任務信息在節點間的擴散復制時間進行定量分析。對于任務信息q而言，在傳感器傳輸方式下轉發所需的時間為Ttrans(q)，在數據的擴散分配過程中，對已攜帶任務信息的無人機，需要尋找交互時間滿足數據轉發時間的節點對象進行擴散。為了對節點間的交互時間進行描述，本文定義可調度序列對無人機區域覆蓋的任務分配進行描述。

基于分布式馬爾可夫覆蓋模型，描述兩臺無人機之間關于某一任務數據所存在的空閑時間對，記為TP。首先將發送任務數據的發送方無人機稱為出節點，接收方稱為入節點。針對從出節點U1發送的任務數據q，若出節點U1和入節點U2在時刻Tmin之后存在關于[Ts,Te]的空閑時間對，其中Ts為數據傳輸的起始時刻且Ts≥Tmin，而Te為Ts與Ttrans(q)之和，則稱為兩者存在時刻Tmin之后關于數據q的可調度序列，記為:

TP=({δi},U1,U2,[Ts,Te],Reword)

(4)

式中:Reword表示當前狀態下覆蓋線路的回報值，用于標記任務數據q的擴散可調度結果。如圖3所示，無人機U1和U2在某一區域內的停留時間為[T0,T5]和[T0,T6]，其中灰色橫段表示無人機的忙碌時段，即攜帶的數據正在任務調度中，時段[T1,T2]和[T3,T4]為兩臺無人機的空閑時間對，如果U1攜帶的數據信息需要向U2擴散，且所需的擴散時間段[Ts,Te]∈[T1,T2]或[T3,T4]∈[Ts,Te]，則U1和U2之間為關于數據q的可調度序列。

圖3 任務擴散調度示意圖

3 多無人機任務差異化分配方法

3.1 任務差異化分配

區域劃分根據特定的任務需求和相關事務的物理位置對整個感知區域作了平面劃分，計算無人機對每個子區域的任務關聯比重和最優劃分，為任務信息的差異化提供依據，而區域覆蓋和任務擴散調度是實現差異化分配的重要部分。這是由于一方面區域覆蓋用于選定直接分配的路線，另一方面任務擴散調度用于觸發無人機之間任務信息的調度和動作方案。因此，首先通過分布式馬爾可夫模型選擇合適的無人機線路集合R(Ui)，以及用式(2)計算無人機對子區域內的關聯比重J，并以J為目標進行覆蓋線路選擇。目標線路集合RΩ與任務關聯比重之間的差異值為：

(5)

式中：G(r′,Ωi)表示當前無人機Ui線路是否覆蓋子區域Ωi，如果覆蓋則值為1，未覆蓋則為0。在計算線路選擇時通過貪婪方式不斷地計算E，從而對具有差異性的目標線路集合進行選擇。

3.2 基于強化學習分配方法

選擇目標線路集后，為使可擴散調度序列集在任務之間達到最優分配，在分布式馬爾可夫覆蓋模型的基礎上，引入強化學習方法[18]在任務區域未知的前提下，通過與環境交互來獲取行動狀態信息并評價反饋覆蓋效果，利用不斷選擇目標線路和擴散調度任務序列，逐步改進覆蓋策略。而求解任務差異分配的目的是找到一個策略使無人機達到最大的獎勵回報信號，通過狀態值函數尋找最優策略，最優策略對應的狀態-聯合動作函數(Si,Ai)為最優值函數，記為Q*。在分布式馬爾可夫覆蓋模型作用下，t時刻無人機Ui在狀態Si下執行Ai行為的值函數為：

(6)

算法步驟具體如下：

輸入：輸入覆蓋需求向量K；任務調度需求向量W；子區域無人機線路R(Ui)；分布式馬爾可夫覆蓋模型DMCM。

輸出：最佳覆蓋策略函數值Q*。

1. 獲取DMCM中獲取無人機的子區域線路R(Ui)，觀測信息{δi}；

2. 根據式(5)計算每一條線路r(r∈R(Ui))加入目標線路集合RΩ，并計算與任務關聯之間的差異值E；

4. 重復步驟2和步驟3，直到線路被選擇完畢；

7. 從可調度序列集TP中選擇距離Ω′最近的k個無人機加入到子區域的擴散調度序列集TPi中，并驅動無人機的狀態轉移；

8. 以一臺無人機的策略開始，計算下一臺無人機的值函數，根據式(6)計算狀態值函數尋找最優策略Q*；

9. 重復步驟6-步驟8；

10. 輸出最佳覆蓋策略函數值Q*。

4 實驗分析

4.1 實驗數據

本文所開展的實驗背景為智能旅游系統的定位設計，采用真實的旅游景點數據背景進行仿真，將全局環境區域限定為W×W=1 000 km×1 000 km，由Voronoi圖分解為600個子區域，每個子區域設有中心位置節點，四臺同構四旋翼無人機飛行速度為40 m/s，最大的偏角度為60°，有效觀測距離為50 m，仿真實驗采用MATLAB R2014b軟件平臺編寫，采樣周期為5 s。通過目標覆蓋任務分配的控制結果分析以及與粒子優化方法和多鏈接合同方法進行比較分析說明本文方法的有效性。

4.2 任務分配控制分析

初始階段無人機對目標和環境區域信息未知，四臺無人機以任意的初始位置飛行于任務區域，對擬定目標1至目標8進行探測，如圖4所示。當機載傳感器接收到任務信號時，四臺無人機向任意位置移動覆蓋目標區域。由圖4(a)可知，四臺無人機以覆蓋需求向量K和任務調度需求向量對目標線路選擇，并通過強化學習的方法尋找了一個合理的覆蓋策略，而這些都是基于在本文方法初始階段對目標區域的差異化劃分，使無人機在每次覆蓋線路選擇時根據需求的差異性進行飛行；由圖4(b)可知，當兩臺無人機對目標區域覆蓋重復的情況下，通過擴散調度序列集使無人機在分布式馬爾可夫覆蓋模型的作用下轉移當前無人機的狀態，驅動任意一臺無人機變更目標路線動作，并在強化學習策略驅動下尋求最佳路線；由圖4(c)可知，在目標隨機移動情景下，無人機通過分布式馬爾可夫覆蓋模型，可以有效地轉移無人機現有狀態，對目標線路進行選擇，并通過強化學習方法得出全局最優策略；由圖4(d)可知，在出現干擾因素情況下，無人機通過可觀測集合的分析可以有效避開干擾區域，同時將干擾區域內的目標進行線路選擇，從而實現對目標區域的覆蓋。

(a) 任務擴散調度控制 (b) 目標重復覆蓋控制

(c) 隨機移動目標覆蓋 (d) 隨機移動目標覆蓋圖4 目標區域覆蓋任務分配控制

4.3 線路代價分析

對于任務的不斷擴散調度，使無人機目標線路選擇在差異化的學習過程中不斷迭代更新，采用任務線路代價[4]進一步說明本文方法在目標區域集群覆蓋的性能。圖5所示為4臺無人機的任務區域覆蓋線路代價變化曲線，在迭代至25次時代價值達到收斂水平，說明覆蓋結果的任務擴散調度方差計算值較小，同時說明了每臺無人機在經過多次任務調度和學習后，目標線路的選擇和區域覆蓋策略趨于最優。這是由于在Voronoi不規則圖的基礎上對任務需求進行了區域的差異劃分，強化了目標任務的依賴關系和擴散調度的時序關聯，并在強化學習Q值函數中找到了一個最優函數使任務合理分配，最終能夠在較少迭代次數中實現對目標區域的全局覆蓋。

圖5 目標任務線路代價變化曲線

4.4 性能比較

為綜合驗證本文方法對于區域覆蓋時任務分配的有效性，與現有的其他方法如人工蟻群方法、基于合同網方法和多agent方法進行性能比較，從目標函數適應和平均區域覆蓋率兩種指標衡量不同方法下的任務分配效果[4]。其中，目標函數適應指標描述了在任務分配過程中無人機對區域目標信息的不確定程度，表示為多無人機的信息熵的代數平均值；平均區域覆蓋率指標描述了多無人機在一定任務時間內所覆蓋區域占整個區域的面積比重。不同方法下四臺無人機協同覆蓋的目標函數適應和區域覆蓋率隨時間變化的結果如圖6所示。

(a) 目標函數適應比較

(b) 平均區域覆蓋率比較圖6 四種任務分配方法對區域協同覆蓋的性能比較結果

由圖6(a)可知，本文方法在每代最優值會出現微小的波動，有利于算法跳出局部最優解區域，并在第16次迭代時收斂速度趨于穩定且適應值為1.0左右。這種現象主要受益于基于強化學習的差異化算法，該算法的最優策略解使得無人機的根據任務需求的狀態轉移性更強，同時差異化的區域劃分也觸發了無人機對目標區域覆蓋需求的適應值，保證了算法收斂穩定。而人工蟻群方法在第25代時才逐步收斂穩定，收斂速度較慢；基于合同網方法的適應函數雖然與本文方法相近，可以解決任務分配的局部優化問題，但隨著迭代次數的增加陷入了不穩定狀態；多agent方法在后期存在較不穩定狀態。

由圖6(b)可知，隨著時間的變化，當仿真結束時，人工蟻群方法的覆蓋率為82.5%，基于合同網方法的覆蓋率為86.6%，多agent方法的覆蓋率為87.9%，本文方法的覆蓋率為92.3%。由此可知本文方法在區域覆蓋效率方面要優于其他方法，這是由于該方法在初始時對每個區域進行了差異劃分，體現了分布式馬爾可夫模型控制無人機飛行狀態的優勢，從而提高了區域協同覆蓋效率。

5 結 語

本文針對目標區域需求覆蓋問題，提出一種面向目標區域覆蓋的任務分配控制方法。在基于區域差異化任務關聯比重的基礎上，構建了分布式馬爾可夫覆蓋模型，提出任務差異化分配的強化學習方法，實現了動態目標區域的最優覆蓋策略。本文方法可以使任意兩臺無人機之間合理地分配任務，而且通過差異化學習方法使目標線路代價和目標適應函數收斂穩定，對于在旅游景點等復雜環境或人群密集中的危險目標搜索定位具有重要意義。然而，對于大規模問題，本文方法不能保證每次迭代都可以覆蓋到最優解，下一步工作將使任務數量增加到一定程度，解決陷入局部最優的情況，并結合語義搜索的方法進一步提高覆蓋的準確率。