基于改進Voronoi 圖的集群無人機區域覆蓋方法

陳 捷，劉海穎，2，李志豪，謝遠龍

（1.南京航空航天大學航天學院，江蘇南京 210016；2.南京應用數學中心，江蘇南京 211135）

在當前智能體自主平臺處理信息能力以及傳感器等任務載荷限制的條件下，面對日益多樣化的任務要求和高度復雜的執行環境，智能體的應用方式逐漸趨向于集群協同作業[1-2]。在集群協同作業技術研究中，集群無人系統的區域覆蓋一直是研究的熱點問題，其指一定數量無人機在相互配合、協同合作中對目標區域進行全局覆蓋[3]。在對受災人員救援以及信號基站搭建等場景進行搜索覆蓋時，需要對目標任務區域進行劃分與分配。本質上，集群協同覆蓋區域分配問題是一種任務規劃問題[4]，需要在多種約束條件下，將目標任務根據權重值分配至集群內不同的無人機，其關鍵部分集中在數學模型的建立、集群控制律等輸入的動力學求解以及分區算法設計上[5-6]。

在無人機集群覆蓋任務研究中，一般可將覆蓋問題大致分為靜態覆蓋和掃描覆蓋兩種類型。在靜態覆蓋中，無人機集群的目標是收斂到期望狀態進而優化某些性能標準[7-8]；在掃描覆蓋中，集群內無人機因其性能指標隨時間而變化，位置也在不斷移動[9]。文中針對集群區域覆蓋任務規劃中定位系統測量不確定性進行研究，目前解決定位不確定性問題的一般方法有概率法[10]、安全軌跡規劃[11]以及Voronoi 圖法[12-14]。

文中主要討論的內容為如何實現集群無人機在規劃過程中對任務區域的全覆蓋，使其覆蓋評價指標達到最大；同時對傳統Voronoi 圖進行改進，設計合理分區算法對無人機責任偵察區域進行分配及規劃搜索路徑，在保證覆蓋質量的前提下實現對目標區域的快速搜索。

1 Voronoi圖劃分方法設計

1.1 傳統Voronoi圖原理

傳統Voronoi 圖應用于集群區域覆蓋問題時，無人機位置需要被精確定位[15-16]。目標區間能夠通過Voronoi 圖在集群內進行分配，每架無人機的責任區域（稱為Voronoi 單元）被定義為比集群中任何其他無人機更接近自身的空間區域：

集群中無人機數量為6 架時構成的Voronoi 圖如圖1 所示。

圖1 Voronoi圖

目標任務區域的抽象Voronoi 圖主要性質為：

其中，Int(·)表示集合論元的內部。

定義無人機i的Delaunary 鄰居，表示為Ni，它們是劃分網絡中Voronoi 單元與無人機i共享一條邊的無人機：

1.2 Guaranteed Voronoi圖原理

針對傳統Voronoi 應用于區域覆蓋算法的不足，在其基礎上引入無人機固有的位置不確定性，提出一種Guaranteed Voronoi(GV)圖劃分方法。在任務區域中定義一組不確定區域：

由于集群無人機的GV 圖劃分結果并不是對空間Ω的完全鑲嵌，因此中立區對應于未在網絡的任何節點上分配的空間的點集。圖2 所示為當集群內含有6 架無人機時的GV 圖。

圖2 Guaranteed Voronoi圖

2 區域覆蓋方法設計

將GV 圖劃分方法應用于集群無人機區域覆蓋問題，提高其最終集群覆蓋率。具體流程如下：

1）獲得無人機狀態信息，包括位置信息、高度信息、搭載視覺傳感器的水平量θi、縱向量hi以及視域角2δi。

2）建立無人機感知區域，考慮無人機內部GPS固有的不確定性，定義無人機保證感知區域為：

3）使用GV 圖將整個任務區域劃分為若干子區域，并分配至無人機集群，分配依據為無人機的保證感知區域以及空間權重系數。無人機i獲得責任區域后，計算其對應的覆蓋質量函數fi()· ：

其中，0 和1 分別對應視覺傳感器的最低和最高觀測質量。

4）根據計算所得fi()·，結合集群中每架無人機通過GV圖得到的重要性因子φ，計算覆蓋質量目標：

覆蓋質量目標H通過對任務區域內無人機視覺傳感器觀測質量與分配到的重要性因子積分得到，其能夠反映任務無人機集群對于任務區域的覆蓋程度。

5）設置集群控制律使得集群覆蓋質量目標單調增加，輸出無人機期望位置，將所得覆蓋質量目標與設定集群覆蓋質量目標H＇進行對比，判斷是否實現集群最大化覆蓋。

3 仿真結果與分析

利用Matlab 對集群無人機區域覆蓋方法進行仿真。在仿真實驗中，設置任務區域場景為凹形區域，目標區域中所有的位置點賦予同樣的重要性，集群覆蓋質量目標設置為H＇=8。設定集群無人機都存在定位不確定性，集群無人機初始位置如表1 所示。

表1 集群無人機初始位置

當集群覆蓋算法中不考慮視覺傳感器觀測質量，僅依靠GV 圖方法對集群無人機進行區域劃分時，集群最終劃分位置如圖3 所示。

圖3 集群最終劃分位置

集群無人機覆蓋質量目標比變化趨勢如圖4 所示，當無人機中沒有搭載視覺傳感器，僅依靠GV 圖方法對任務區域進行劃分時，集群覆蓋質量目標不能達到設定值。

圖4 覆蓋質量目標比變化圖

當集群覆蓋算法考慮視覺傳感器時，設置機載視覺傳感器縱向量限制為=30°，視錐角范圍設置為=15°,=35°,?i∈In，無人機高度范圍是zmin=0.3 m，zmax=2.3 m。區域覆蓋算法中對集群無人機的控制增益設置為：無人機水平與縱軸方向上Kx=0.25，Ky=0.25，Kz=0.25；視覺傳感器水平 量Kth=0.000 5，縱向量Kh=0.000 5，視錐角Kzoom=0.000 5，仿真步長為0.2 s。運行結果如圖5 所示，無人機感知區域以灰色填充，保證感知區域的邊界以虛線表示。

圖5 集群運行最終位置

圖6 和圖7 分別為集群無人機對任務區域的覆蓋率變化曲線以及覆蓋質量目標比變化曲線。對于凹形地圖，集群區域覆蓋任務規劃算法能夠使集群對任務區域的覆蓋率達到90.31%，同時覆蓋質量目標隨著仿真時間的推移單調增加，最終達到設定目標值。圖8 為集群無人機位置誤差變化圖，對于凹形任務環境中，集群無人機在三個維度上的誤差均小于0.1 m，且逐漸收斂到0。

圖6 集群運行覆蓋率變化圖

圖7 覆蓋質量目標比變化圖

圖8 集群無人機位置誤差變化圖

4 結論

針對集群無人機對任務區域的覆蓋問題，文中提出一種基于改進GV 圖的集群覆蓋方法。首先，對傳統Voronoi 圖進行改進，提出GV 圖方法，并對目標任務區域進行劃分；其次，建立無人機集群感知區域模型，利用GV 圖為集群內無人機分配責任子區域，根據視覺傳感器觀測質量以及分配的重要性因子計算對應的無人機覆蓋質量目標；最后，在覆蓋質量目標的約束下，將集群無人機引入局部最優配置，實現對任務區域的最大范圍覆蓋。通過仿真試驗表明，所提區域覆蓋方法能夠使無人機集群達到最優區域分布，并對目標區域有較高的覆蓋率。