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

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

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

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

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

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

1 Voronoi圖劃分方法設計

1.1 傳統(tǒng)Voronoi圖原理

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

集群中無人機數(shù)量為6 架時構(gòu)成的Voronoi 圖如圖1 所示。

圖1 Voronoi圖

目標任務區(qū)域的抽象Voronoi 圖主要性質(zhì)為：

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

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

1.2 Guaranteed Voronoi圖原理

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

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

圖2 Guaranteed Voronoi圖

2 區(qū)域覆蓋方法設計

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

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

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

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

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

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

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

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

3 仿真結(jié)果與分析

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

表1 集群無人機初始位置

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

圖3 集群最終劃分位置

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

圖4 覆蓋質(zhì)量目標比變化圖

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

圖5 集群運行最終位置

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

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

圖7 覆蓋質(zhì)量目標比變化圖

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

4 結(jié)論

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