未知環境下無人機集群協同區域搜索算法

侯岳奇， 梁曉龍,*， 何呂龍， 劉流

(1. 空軍工程大學 國家空管防相撞技術重點實驗室, 西安 710051；2. 空軍工程大學 陜西省電子信息系統綜合集成重點實驗室, 西安 710051)

隨著高精度影像設備與技術的快速發展，攜帶照相設備的無人機(Unmanned Aerial Vehicle，UAV)在民用和軍事領域得到了廣泛應用，例如環境監測、戰場監視以及目標搜索等[1-2]。無人機集群通過無人機之間的協同合作，從而實現整體能力上的涌現，即系統涌現出的能力遠超系統內單架無人機能力的總和[3-4]。相比于單架無人機，利用多架無人機協同執行區域搜索任務得到了越來越廣泛的關注[5-6]。

針對協同搜索問題，諸多學者進行了深入的探索并取得豐碩的成果。離線規劃方法[7-9]將任務區域進行分割，設計各個子區域的覆蓋搜索航線，飛行航線固定。該方法的優勢在于能夠實現任務區域的全覆蓋，而在無人機故障、火力威脅等突發情況下該方法受限。文獻[5]使用笛卡兒柵格描述環境，賦予每個柵格一個值代表目標分布的不確定性，設計了搜索回報函數和禁飛區回避策略。在有先驗信息的情況下，該方法可以實現重點偵察和覆蓋搜索。文獻[10]在文獻[5]的基礎上，考慮通信約束，分析了不同通信約束對協同搜索效率的影響。在通信距離和角度有約束的情況下，該方法能夠較好地實現協同區域搜索。此類方法依賴先驗信息來建立概率地圖，然而在實際應用中，先驗信息的獲取和柵格量化是十分困難的。文獻[11]設計了基于信息素的網格回訪機制，引導無人機對目標存在概率較大的區域進行回訪搜索，使得無人機能夠盡早搜索到更多目標。上述方法[5,10-11]均假設無人機在相鄰柵格之間運動，這種“粗粒度”的運動模型雖然簡化了協同搜索決策的解空間，但卻在一定程度上降低了決策結果的精細程度。文獻[12-14]基于分布式模型預測控制框架，采用納什最優和粒子群優化相結合的算法，有效地降低了協同搜索決策問題的求解規模和通信負擔。雖然上述研究在一定程度上使多無人機具備了協同搜索的能力，但仍存在區域覆蓋率較低的問題。存在這一問題的原因在于：缺少專門的引導機制，來引導無人機向未覆蓋區域進行搜索。

在執行區域搜索任務時，無人機故障和環境中火力威脅等突發情況的影響是不容忽視的。考慮到傳統的離線規劃方法難以應對突發情況，本文提出了一種以覆蓋率為實時搜索獎勵的協同區域搜索算法，以改善一般在線規劃搜索方法覆蓋率不高的問題。

1 協同搜索問題建模

1.1 問題描述

多無人機協同搜索問題主要分為2類[15]：第1類是在環境信息已知的條件下，根據先驗信息對區域進行搜索，以盡快發現目標，或者對重點區域進行監控；第2類是在環境信息未知的條件下，對區域進行覆蓋。本文針對第2類問題展開研究。UAV集群攜帶通信設備和照相設備對特定任務區域展開搜索，區域內目標的位置分布未知，如圖1所示。

UAV按照實時規劃的航路對任務區域展開搜索，并通過通信組網模塊進行實時通信，為實時決策提供信息支撐，通信內容包括UAV狀態、環境信息和決策信息等。當某架UAV出現故障時，傳統的離線規劃方法難以適應性地完成搜索任務。相比而言，在線規劃方法魯棒性更強，在出現突發情況時，無人機集群能夠繼續保持協同，自組織地完成搜索任務。因此，本文主要研究如何建立一種高效的區域覆蓋在線規劃方法，確保UAV集群在盡可能短的時間內對區域進行覆蓋。

圖1 UAV集群協同搜索示意圖Fig.1 Schematic diagram of UAV swarm cooperative search

1.2 環境模型

設任務區域Ω為Lx×Ly的矩形區域，將區域按照固定間隔Δd柵格化為M×N個柵格，如圖2所示。

賦予每個柵格一個值μij(k)，用于描述截止到k時刻為止柵格(i,j)是否已被覆蓋。為簡化分析，做出如下假設：一旦柵格(i,j)處于UAV傳感器探測范圍內，則認為該柵格已被覆蓋，且柵格內的目標存在情況完全已知。柵格的狀態μij(k)表示為

(1)

式中：Ωc(k)為已覆蓋的柵格集合；Ωnc(k)為未覆蓋的柵格集合。任務區域Ω為Ωc(k)和Ωnc(k)的總和。構建覆蓋分布地圖(Coverage Distribution Map,CDM)來描述任務區域的覆蓋分布情況，用矩陣形式來表示覆蓋分布地圖，定義環境矩陣為

C(k)=[μij(k)]M×N

(2)

在搜索開始前，由于整個區域的環境信息完全未知，且需要對整個區域展開覆蓋搜索，因此每個柵格的值μij(0)=1；隨著搜索的進行，μij(k)實時變化，覆蓋分布地圖實時更新，并在UAV集群內共享，為UAV的實時決策提供環境信息。

圖2 任務區域柵格化Fig.2 Mission area rasterization

1.3 UAV模型

為簡化分析，假設UAV在任務區域上空等高度飛行，并將UAV視為二維空間中運動的質點，其運動方程為

(3)

式中：[xi(k),yi(k)]為UAV的位置；φi(k)=φi(k-1)+Δφi(k)，φi為航向角，Δφi∈[-φmax,φmax]為航向偏轉角，為決策輸入，φmax為受機動性能限制下的最大轉彎角；v0為平飛速度；Δt為時間步長。

將UAV集群視為一個控制系統，并將每架UAV視為一個子系統。k時刻，記子系統UAVi的狀態為pi(k)=(xi(k),yi(k),φi(k))。狀態方程為

pi(k+1)=f(pi(k),ui(k))

(4)

式中：ui(k)=Δφi(k)為子系統UAVi的輸入；f(·)為狀態轉移函數，由式(3)確定。

根據式(4)，建立子系統UAVi的預測模型為

i=1,2,…,n;j=1,2,…,H

(5)

式中：n為UAV架數；H為預測周期；pi(k+j|k)為基于k+j-1時刻UAVi狀態預測的k+j時刻的UAVi狀態，其值取決于狀態pi(k+j-1|k)和控制輸入ui(k+j-1|k)。

從k時刻起，給定H步預測控制輸入后，可以預測出未來H步以內UAV的航路，如圖3所示。通過優化預測控制輸入，來引導UAV盡可能向尚未被覆蓋的區域進行搜索，以獲得更高的區域覆蓋率。

圖3 H步預測航路圖Fig.3 H step route prediction

2 覆蓋分布地圖更新方法

覆蓋分布地圖描述了任務區域的覆蓋搜索情況，是UAV進行自主決策的重要依據。因此，如何快速更新覆蓋分布地圖，對在線實時決策具有重要意義。

覆蓋分布地圖的更新就是將傳感器探測范圍內覆蓋部分的相應柵格置為0。通過逐一判斷鄰近柵格到UAV之間的距離是否小于傳感器探測距離，并對覆蓋范圍內的柵格進行逐一賦值，可以實現覆蓋分布地圖的更新，但這種遍歷的方法運算量大、算法復雜度高，不利于實時更新。本文利用Hadamard積進行覆蓋分布地圖更新，操作簡單且易于實現，避免了遍歷判斷和逐一賦值，其流程如圖4所示。

圖4中探測矩陣和環境子矩陣的定義，以及對其進行Hadamard積的運算過程將在2.1節和 2.2節中詳細介紹。

圖4 覆蓋分布地圖更新流程Fig.4 Update process of coverage distribution map

2.1 探測矩陣

本文將傳感器探測范圍簡化為：UAV所處位置為中心，半徑為Rs的圓形區域。如圖5所示，正方形區域記為Ψ，將區域Ψ柵格化為Q×Q個柵格。

(6)

式中：Rs為傳感器探測半徑；「?為向上取整函數。

賦予每個柵格一個值ηpq，用于描述UAV傳感器能否探測到該柵格。若柵格(p,q)處于UAV傳感器探測范圍內，則令ηpq=0，反之，ηpq=1。ηpq表示為

(7)

式中：Ψc為傳感器可探測區域；Ψnc為不可探測區域。區域Ψ為Ψc和Ψnc的總和。

圖5 區域Ψ柵格化Fig.5 Region Ψ rasterization

以ηpq為元素建立探測矩陣D=[ηpq]Q×Q，表示UAV對鄰近柵格的覆蓋能力。

2.2 覆蓋分布地圖的更新

定義環境子矩陣C(mn)(k)：在環境矩陣C(k)中，以μmn(k)為中心元素，維度為Q×Q的子塊矩陣，稱為環境子矩陣。

(8)

(9)

當UAV處于柵格(m,n)內時，可近似認為UAV處于該柵格的中心。此時，環境子矩陣C(mn)(k)與探測矩陣D重合，且維度相等。對上述2個矩陣做Hadamard積

C(mn)(k+1)=C(mn)(k)°D=

(10)

式中:“°”為Hadamard積運算；p,q=1,2,…,Q。

假設傳感器的探測周期為Ts，以Ts為時間間隔將UAV從k到k+1時刻的直線運動離散為運動點跡。對每個離散點做上述運算，即可實現一個步長內覆蓋分布地圖的更新。

2.3 覆蓋分布地圖的信息融合

文獻[16]提出了一種地圖信息融合更新方法，該方法適用于通信理想的情況，在通信中斷或數據丟包的情況下，部分地圖信息無法融合更新，對搜索過程造成影響。因此，本文提出基于Hadamard積的地圖信息融合方法(見圖6)，能夠在一定程度上減小通信中斷或數據丟包對搜索過程的影響。

在協同搜索過程中，各UAV在本機進行覆蓋分布地圖更新，更新完畢后通過通信網絡廣播發送實現融合共享。k時刻，UAVi本地的覆蓋分布地圖對應的環境矩陣記為Ci(k)，并接收到其他UAV的廣播消息記為Cj≠i(k)。基于Hadamard積可實現各UAV覆蓋分布地圖的信息融合：

(11)

與文獻[16]方法相比，基于Hadamard積的地圖信息融合方法共享的探測信息為環境矩陣Ci(k)，是地圖的全局信息。假如k時刻數據丟包或通信中斷，當前時刻的探測信息會丟失，地圖信息無法更新。一旦k+x時刻通信恢復正常，環境矩陣Ci(k+x)中已包含了k到k+x時刻的歷史探測信息，經過基于Hadamard積的地圖信息融合方法更新后，丟失的歷史探測信息就得以恢復。雖然k到k+x時刻通信中斷會影響當前搜索決策，但是通信恢復后所有歷史信息得到恢復，k+x時刻之后的搜索過程不會受到影響。

圖6 基于Hadamard積的地圖信息融合示意圖Fig.6 Schematic diagram of map information fusion based on Hadamard product

3 獎勵函數與搜索算法

3.1 搜索獎勵函數

協同搜索的關鍵在于設計一個搜索獎勵函數，對每條預測航路進行評估[5]。獎勵的設定主要是一個步長內覆蓋率增量的大小，并依據邊界條件和轉彎角度設計懲罰函數。在搜索過程中，UAV基于當前狀態和覆蓋分布地圖，利用搜索獎勵函數對預測航路進行評估，并自主地選擇獎勵值最大的航路作為決策輸入。每架UAV使用搜索獎勵函數J選擇它的搜索航路：

J(pi(k),ui(k))=ω1γJC(k)+

ω2JT(k)+ω3JB(k)

(12)

式中：JC為覆蓋率增量；JT和JB分別為轉彎角度和邊界距離的懲罰函數；ω1、ω2和ω3為相應權重；γ為重要性因子，覆蓋率的重要性通過調整γ來體現，γ≥1。

k時刻的區域覆蓋率O(k)是已搜索區域Ωc(k)占任務區域Ω的面積比，即已搜索柵格數量與總柵格數量的比值：

(13)

k到k+1時刻的覆蓋率增量是指O(k+1)與O(k)的差值。實際意義為：k時刻，未搜索區域Ωnc(k)中，在k到k+1時刻內被搜索到的區域占任務區域Ω的面積比。覆蓋率獎勵函數為

JC(k)=O(k+1)-O(k)=

(14)

在執行任務過程中，若轉彎角度過大，導致耗油增大，影響續航時間。因此，設計一個懲罰函數，盡可能減少UAV轉彎角度過大引起的耗油代價。轉彎角度的懲罰函數JT可以表示為

(15)

在搜索過程中，距離邊界越近，傳感器覆蓋的有效區域越少，效率越低。借鑒虛擬勢函數的思想，設計一個懲罰函數，靠近邊界的UAV會受到邊界的虛擬“斥力”，距離邊界越近則“斥力”越大。因此，邊界距離的懲罰函數JB可以表示為

(16)

(17)

3.2 基于DMPC和DE的協同搜索算法

模型預測控制(Model Predictive Control，MPC)是一種利用控制系統模型和優化技術設計預測周期內系統最優控制輸入的方法，核心思想是滾動優化求解[17]。集中式MPC方法依賴中央節點進行決策，限制了系統規模的擴展和決策速度，在實際應用中有一定局限性[14,18]。考慮到UAV子系統之間不存在耦合性，即不同UAV的控制是相對獨立的，它們在系統的動態特性上并沒有關聯。為提高整個系統的抗毀性和決策速度，其控制結構可以采用分布式模型預測控制(Distributed Model Predictive Control，DMPC)方式[19]，如圖7所示。

MPCi決策流程分為3步。

步驟1預測

圖7 DMPC框架示意圖Fig.7 Schematic diagram of DMPC framework

圖8 MPCi決策流程Fig.8 Decision-making process of MPCi

在預測階段，每架UAV基于本地覆蓋地圖和自身狀態進行優化求解，而不考慮其他UAV的運動，即UAV之間不進行協同。根據式(17)，求解UAVi的H步預測控制輸入的優化模型可以描述為

(18)

步驟2通信

步驟3決策

(19)

搜索決策過程的算法偽代碼如下：

1 初始化任務參數

2 fork= 1 tokmax

9 將Ci(k)更新為Ci(k+1)

10 ifO(k+1) ≥ 設定閾值

11 break

12 end if

13 end for

控制輸入Ui(k)中包含H個未知變量，此優化問題是一個非線性優化問題。考慮到DE算法在求解優化問題，尤其是非線性優化問題中的優勢[20]，采用DE算法進行子系統本地優化求解，算法細節不再贅述。

4 仿真分析

為驗證本文方法的有效性，本節對其進行仿真驗證。仿真環境為I7-4960，主頻2.60 GHz，16 GB內存，基于MATLAB 2014a為平臺進行仿真實驗。

4.1 實 驗 1

設任務區域為8 km×8 km的矩形區域，每個柵格大小為20 m×20 m。執行搜索任務的4架UAV從不同位置進入搜索區域，其進入點坐標分別為(200,0) m，(2 200,0) m，(4 200,0) m，(6 200,0) m。UAV之間的通信均為理想條件。UAV平飛速度v0=30 m/s，傳感器探測半徑Rs=200 m，最大轉彎角φmax=60°，仿真步長Δt=10 s，預測步長H=3，ω1=0.9，ω2=0.05，ω3=0.05，γ=200。設定仿真環境條件：任務環境為無遮擋的平地區域，任務區域中存在分布未知的火力威脅，有一定幾率造成UAV設備故障。在仿真中加入突發情況來模擬這一環境條件：運行至20步長時，假定UAV1設備故障，停止執行任務；運行至100步長時，假定UAV3設備故障，停止執行任務。為體現本文算法的優勢，分別運用平行搜索、隨機搜索和本文算法進行對比仿真。仿真結果如圖9所示(圖中黑色區域為UAV傳感器未覆蓋的區域)。

圖9 3種搜索方法的仿真結果Fig.9 Simulation results of three search methods

如圖9(a)所示，在2架友機相繼發生故障的情況下，UAV2和UAV4只完成了各自預先分配的搜索任務，故障UAV未完成的搜索任務得不到繼續執行。如圖9(b)所示，隨機搜索方法作為一種無引導機制的在線規劃方法，在任務過程中多處存在UAV航跡交叉重疊的情況，搜索效率較低。如圖9(c)所示，在搜索初始階段，各UAV之間保持傳感器探測范圍盡可能不重疊，實現較高的覆蓋率增長。在2架友機相繼故障的情況下，UAV2和UAV4通過實時協同，保持原有的搜索策略，充分發揮各自的搜索能力，繼續完成搜索任務。總的來看，本文算法各UAV探測區域之間重疊部分較少，在出現突發情況時，能夠繼續完成搜索任務，體現了無人機集群在線協同的優勢。

為消除隨機因素的影響，在相同仿真條件下，針對本文算法和隨機搜索方法使用蒙特卡羅方法進行500次仿真，得到平均覆蓋率隨時間變化曲線如圖10所示。

圖10 3種搜索方法的覆蓋率變化曲線Fig.10 Coverage rate changing curve of three search methods

如圖10所示，平行搜索方法和本文算法覆蓋率高于隨機搜索方法。平行搜索方法的覆蓋率變化曲線呈折線狀：當某架UAV發生故障時，覆蓋率曲線的斜率隨之降低；當UAV到達邊界時，執行轉彎程序，覆蓋率斜率為零。在搜索初期，本文算法與平行搜索方法覆蓋率曲線斜率基本一致，體現了較高的搜索效率。當UAV2和UAV4完成各自的搜索任務后，平行搜索方法的覆蓋率保持不變。相比之下，本文算法在UAV1和UAV3發生故障后，仍能保持覆蓋率的穩定增長，最終任務結束時的覆蓋率遠高于平行搜索方法。

4.2 實 驗 2

針對本文算法在集群規模較大時的有效性進行驗證，采用10架無人機組成的無人機集群進行仿真。設任務區域為15 km×15 km的矩形區域，執行搜索任務的10架UAV的初始位置和航向由程序隨機產生，UAV故障隨機指定：設定UAV2、UAV3、UAV8、UAV9和UAV10分別于仿真步數為185、120、175、170和165時發生故障，其他仿真條件同實驗1。用本文算法進行仿真，仿真步數step為100和230時的仿真結果如圖11所示。

由圖11(a)可以看出，在搜索初期，10架UAV保持傳感器探測范圍盡可能不重疊，以獲得較高的覆蓋率增長。由圖11(b)可以看出，在搜索后期，由于未搜索區域被分割成多個不規則的形狀，UAV航路出現了部分交叉，但本文算法還是能夠引導UAV盡可能向未搜索區域移動。搜索過程中覆蓋率變化曲線如圖12所示。

如圖12所示，在搜索前期，覆蓋率增長速度較快，覆蓋率隨時間變化曲線的斜率保持穩定。到搜索后期，由于出現重復搜索的情況，覆蓋率增長放緩，斜率逐漸降低。當搜索時間到達38.33 min時，覆蓋率達到了90.13%，有效地對區域進行了覆蓋。仿真結果表明，在集群規模達到10 架的情況下，本文算法能夠較好地完成搜索任務。

圖11 本文算法仿真結果Fig.11 Simulation result of proposed algorithm

圖12 本文算法覆蓋率變化曲線Fig.12 Coverage rate changing curve of proposed algorithm

5 結 論

1) 本文算法在實驗仿真條件下能實現較高的區域覆蓋率，尤其是在出現突發情況時，覆蓋率遠高于平行搜索方法，體現了無人機集群在線協同的優勢。

2) 以覆蓋率作為實時搜索獎勵的引導機制，有利于引導UAV向未搜索區域運動，并協同各UAV之間探測區域重疊部分盡可能少，以實現更高的覆蓋率。

3) 利用Hadamard積可實現覆蓋分布地圖的快速更新，避免了遍歷判斷和逐一賦值，且操作簡單、運算速度快，為地圖信息實時更新提供了便捷。

4) 采用DMPC框架進行滾動優化求解，將長期的搜索獎勵考慮在內，并且可以提高系統的抗毀性和決策速度。

本文算法在通信理想的條件下實現了對任務區域的有效覆蓋搜索，但針對通信距離和角度約束的情況，尚需進行更加深入的后續研究。