復雜環境下的多無人機協同巡邏航路規劃

李友松，喬福超

（1.東海艦隊司令部，浙江寧波315122；2.海軍航空工程學院研究生管理大隊，山東煙臺264001）

隨著武器裝備的革新和戰場構成的日益復雜，無人機所擔負的任務種類越來越多，其功能也日益綜合。如今，集偵查打擊能力于一體的無人作戰飛機已逐漸投入應用，利用多架UCAV協同執行戰場巡邏任務（包括偵查與打擊任務）也受到了越來越多的關注。

目前，針對多UCAV 協同巡邏航路規劃的研究取得了一些成果[1-4]。文獻[1]設計了一種滿足UCAV 機動限制和適應數據通訊延遲的協同路徑決策算法，使用搜索回報函數引導UCAV對未知環境進行搜索，仿真結果表明該方法能夠有效提高協同搜索的效率，但其僅以搜索效率為目標，而未對UCAV的空間分布進行優化。文獻[2]提出了兼顧搜索效率和打擊效率的多UCAV協同航路原則，使用搜索回報函數和加權平均距離，加強了對高關注度區域的巡邏力度，改善了UCAV 的空間分布。此外，一些窮舉覆蓋航路規劃模型，如Zamboni搜索方法已經得到了發展應用，較好地保證了航路的最優性[3-4]，然而該方法缺乏靈活性，如在設計某地區的森林火情偵查路線時，不能對該區域的湖泊和其他無林帶進行規避，在載油有限和時間緊張下，將影響到對其他更有價值區域的偵查活動。

本文在現有研究的基礎上，采用文獻[2]中的多UCAV 協同巡邏模型，對復雜環境下的多UCAV 協同巡邏進行了研究。

1 復雜環境下的協同巡邏

1.1 復雜環境

復雜環境是指目標空間分布不均，目標分布隨時間不斷變化，且存在一定的飛行障礙（如禁飛區）的環境。UCAV在復雜環境下的搜索航路應充分考慮目標出現概率、飛行器活動范圍限制等因素，加大對目標出現概率高的區域的搜索力度，避開無價值區域，從而提高UCAV的搜索效率。為實現該目的，應對復雜環境進行區域劃分。例如，為提高火情偵查飛機的工作效率，其搜索環境應根據植被易燃程度、林木稀疏程度、干燥程度等因素劃分為關注程度不等的小區域；又如，UCAV 在爭議海域執行巡邏任務時，應根據目標出現的頻率和飛行限制將該海域劃分為一般關注區、重點關注區、禁飛區等區域。

基于上述分析，考慮根據先驗信息，將復雜環境劃分為一般關注區域、重點關注區域、已知區域和禁飛區域。UCAV 主要針對未知區域展開搜索，并對重點未知區域給予更高的搜索頻率。同時，UCAV 應當盡量避免對已知區域進行搜索，并完全避開禁飛區域。圖1為某海區的區域劃分示意圖。

圖1 某海區的區域劃分示意圖Fig.1 Schematic diagram of a sea area's division

1.2 協同巡邏

UCAV的協同巡邏是一種兼顧搜索和打擊的作戰形式。例如，在近海作戰中，UCAV執行對水面目標的偵查和打擊任務：當未發現目標時，UCAV在整個作戰區域搜索目標；當發現目標并需對其進行打擊時，UCAV 應能及時飛至交戰地點并實施打擊，作戰完成后再轉為執行搜索任務。

綜上所述，UCAV 在復雜環境下的協同巡邏航路應當同時兼顧搜索效率和打擊效率，即應滿足以下原則：

1）搜索路徑應覆蓋盡量多的未知區域，并盡可能避開已知區域，完全避開禁飛區域。

2）根據未知區域的關注度，對關注度高的區域給予更高的搜索頻率。

3）UCAV 的空間分布應利于打擊盡量多的目標。即在巡邏過程中的多數時間里，UCAV 的空間分布能夠使之較快地到達戰場區域內的任意一點。此外，當戰場環境中的區域具有不同的關注度時，UCAV 應對關注度高的區域具有更短的打擊距離。

2 協同巡邏航路規劃模型

2.1 環境模型

將作戰區域以等距網格劃分。每一網格(i,j)被賦予一變量V(i,j)以表示UCAV 對該網格的關注程度。V(i,j) 取值越大，則網格(i,j) 被關注的程度越高，若UCAV 對網格(i,j)內的目標完全不關心，則V(i,j)=0。此外，為使UCAV 能夠對禁飛區實行完全的規避，可將禁飛區內網格的關注度設置為絕對值極大的負值。以圖1 所示的區域劃分為例，空間中各網格的關注度賦值為：

式（1）中：A為已知區域；B為重要未知區域；C為一般未知區域；D為禁飛區域；Negative_Value ＜0 ，High_Value ＞Low_Value ＞0。

2.2 UCAV運動模型

假定UCAV 以勻速運動，UCAV 的運動數學模型如下：

式（2）中：xt、yt為無人機在t時刻的坐標；v為無人機的飛行速度；v˙為加速度；ΔT為單位時間；θt為無人機在t時刻的航向角；θ˙t為無人機在t時刻相對t-ΔT時刻的航向角改變量；u為最大轉彎角限制參數。

2.3 UCAV航路

將連續的時間離散為時間序列{t|t=k?ΔT,k=1,2,…}。以任務開始時刻為零時刻，以固定的時長ΔT為一個時間單位。第n架無人作戰飛機Un(n=1,2,…,N)的航路可表示為向量：

式（3）中：xn、yn為UCAV 的起點坐標；θn,t為Un在t時刻所選擇的航向，相鄰2次轉向的時間間隔為ΔT。

θmax為ΔT內UCAV 物理操縱性能所限制的最大轉彎角[5]。UCAV的航路如圖2所示。

圖2 UCAV的航路Fig.2 Route of UCAV

2.4 搜索模型

UCAV 使用雷達對目標進行探測，其在某時刻的探測面積用雷達所覆蓋的網格數表示。假設UCAV的雷達探測半徑為2 個網格寬度，則一架UCAV 在某時刻能探測到12 個網格。令P(i,j,t)表示UCAV 在t時刻對網格(i,j)的覆蓋情況，若在t時刻至少有一架UCAV 的雷達能覆蓋到網格(i,j)，則P(i,j,t)=1。若此時所有UCAV 的雷達都無法覆蓋到網格(i,j) ，則P(i,j,t)=0。如圖3 所示，白色網格是被UCAV 雷達覆蓋的區域，灰色網格為未被覆蓋的區域。

令K(i,j,t)表示UCAV在t時刻對網格(i,j)內目標分布的不確定度，且滿足K(i,j,t)∈[0,1]。K(i,j,t)值越大，表示UCAV 對該區域的不確定度越高，當K(i,j,t)=1時，表示UCAV在t時刻完全不知道網格(i,j)內的目標分布情況。在搜索過程中，若網格(i,j)在t時刻被UCAV 探測到，則其下一時刻的不確定度K(i,j,t+1)變為0；若(i,j)沒被探測到，也根據該區域的關注度V(i,j)，其下一時刻的不確定度K(i,j,t+1)應當有適量的增加，即：

式中，Q＞0 為每ΔT時間網格(i,j)的不確定度的增量。

由式（4）可以看出，關注度越高的區域，其在單位時間內的不確定度的增量越高，由此便可以引導UCAV以更高的頻率對其進行搜索。

以搜索回報值來描述巡邏航路的搜索效率。多架UCAV 在整個飛行過程中探測到的所有網格的不確定度的加和，即為該航路的搜索回報值為

2.5 加權平均距離

UCAV的空間分布應利于打擊盡量多的目標。即在巡邏過程中的多數時間里，UCAV 的空間分布能夠使之較快地到達戰場區域內的任意一點。此外，當戰場環境中的區域具有不同的關注度時，UCAV 應對關注度高的區域具有更短的打擊距離。

圖4為3架UCAV 在某一時刻的空間分布圖。圖4 a）中，UCAV在戰場區域內分布得較為分散，對于需要UCAV 打擊的點a、b、c、d，其與UCAV 之間的最短距離都比較短，尤其對于重點區域內的點d，其與UCAV之間的距離更短；在圖4 b）中，UCAV分布得較為集中，當a點需要打擊時，UCAV就無法及時趕到。

圖4 某時刻無人機的空間分布Fig.4 Distribution of UCAV in a moment

以加權平均距離來描述巡邏航路的打擊效率。令d(i,j,t,n)表示網格(i,j)在t時刻與無人作戰飛機Un之間的距離，則表示網格(i,j)在t時刻與距其最近的UCAV之間的距離。令：

式（7）、（8）中：d(t)為t時刻所有網格與距其最近的UCAV 之間距離的加權總和，每一距離的權值為相應點的關注度；D值即為加權平均距離，D值越小，UCAV的打擊效率越高。

2.6 目標函數

根據協同巡邏航路原則，航路應同時兼顧搜索效率和打擊效率，即既具有較大的搜索回報值，又具有較小的加權平均距離。設計目標函數：

式中，α、β(α＜0,β＞0)是權重。因戰場環境、任務性質、指揮員性格的差異，其權重還需要做適當的調整。

3 航路規劃仿真

3.1 粒子群算法

粒子群優化算法將優化問題的每一個潛在解表示為搜索空間中的一個粒子，通過調整粒子的位置和移動速度實現問題的尋優[6-7]。

假設在一個D維的目標搜索空間中，有n個粒子組成一個群落X=(X1,X2,…,Xn)，其中第i個粒子表示為一個D維的向量Xi=(xi1,xi2,…,xiD)，代表第i個粒子在D維的搜索空間中的位置，亦代表問題的一個潛在解。根據目標函數即可計算出每個粒子位置Xi對應的適應度值。第i個粒子的速度為Vi=(vi1,vi2,…,viD)，其個體極值為Pi=(pi1,pi2,…,piD)，粒子群的群體極值為G=(g1,g2,…,gD)。在每次迭代過程中，粒子通過個體極值和群體極值更新自身的速度和位置，即

式（10）中：ω為慣性權重；k為當前迭代次數；Vi為粒子速度；c1和c2是非負常數，稱為加速因子；r1和r2是分布于[0,1]區間的隨機數。為防止粒子的盲目搜索，一般將粒子的位置和速度限制在一定的區間[-Xmax,Xmax]、[-Vmax,Vmax]。

利用粒子群算法解決一般優化問題的流程圖如圖5所示。

圖5 粒子群算法流程Fig.5 Process of Particle swarm algorithm

3.2 仿真分析

使用粒子群算法對多UCAV 協同巡邏航路規劃進行仿真。以單個粒子表示N架UCAV的航路，其粒子結構如圖6所示。

圖6 多UCAV航路的粒子結構Fig.6 Particle structure of multi UCAV route

其中，xi和yi分別為UCAVi的航路起點的網格坐標，θi,t為UCAVi在為t時刻的偏轉角，且θi,t∈[1,M]，M為UCAV 偏轉角的離散數量。與固定起點的N架UCAV 的航路相對應，其粒子的搜索空間是(T+1)×N維的空間。

仿真中，將戰場環境設置為20×15的網格區域，并設置1 個重點未知區域、1 個已知區域和1 個禁飛區域，其關注度分別設為2、0、0；剩余未劃分的區域為一般未知區域，其關注度設為1。3架UCAV從不同基地起飛開始執行巡邏任務，其起點坐標分別為（4,1），（8,1），（12,1），UCAV的最大拐彎角為90°，雷達探測半徑為1個網格寬度，每單位時間ΔT前進距離也為1個網格寬度。粒子群算法的各參數取值為：加速因子c1和c2均設為2；r1和r2取[0,1]區間內的隨機數；慣性權重ω隨迭代次數的增加由0.9 線性變化至0.4，迭代次數設為1 000 次。

圖7 的航路是多UCAV 分區域搜索的常規航路，是目前應用較為普遍的非協同搜索航路。在分區域搜索時，各UCAV 之間無協同，每架UCAV 在其搜索區域內按照最大搜索效率進行覆蓋式搜索。圖8是仿真得到的3 架UCAV 的協同巡邏航路，航路點為25。分別計算圖7、圖8 中2 種航路的搜索回報值、搜索覆蓋率、加權平均距離，計算結果如圖9所示。對比圖9中協同巡邏航路與非協同航路的參數。雖然協同航路的搜索覆蓋率（47%）不及非協同航路（51%），但在空間分布方面，協同航路的加權平均距離（3.01）遠小于非協同巡邏航路的加權平均距離（3.78），因而前者具有更高的打擊效率。協同航路的搜索回報值（9.67）高于非協同航路的搜索回報值（8.51），這是因為協同航路對關注度高的區域提高了搜索頻率。

圖7 25航路點的非協同搜索航路Fig.7 Non cooperative search route with 25 points

圖8 25航路點的協同巡邏航路Fig.8 Cooperative patrol route with 25 points

圖9 航路參數對比Fig.9 Comparison of route parameter

為說明協同巡邏航路規劃算法所生成的航路具有更好的打擊效率，將UCAV飛行距離設置為15個航路點，起點坐標分別設為（2,1），（2,10），（15,7），得到的航路如圖10 所示?？梢钥闯觯瑥膖=1 時刻到t=15 時刻，3架UCAV在同一時刻的空間分布都較為分散，與區域內多數網格點之間的距離較短，尤其對于重點區域內的網格點具有更短的距離，因而具有較好的打擊效率。圖11 是航路點為50 的協同巡邏航路，該航路基本覆蓋了區域內所有點，且在重點區域內較為密集，在一般區域內較為稀疏，達到了預期的加強對高關注度區域的巡邏的目的。

圖10 15個航路點的協同巡邏航路Fig.10 Cooperative patrol route with 15 points

圖11 50個航路點的協同巡邏航路Fig.11 Cooperative patrol route with 50 points

4 結束語

多UCAV 在復雜環境下的協同巡邏航路規劃算法通過對未知區域、已知區域、禁飛區域設置不同的關注度，并使用搜索回報函數和加權平均距離對UCAV進行引導，加強了對高關注度區域的巡邏力度，改善了UCAV 的空間分布，與文獻[2]的結果相比，本文中UCAV完全避開了禁飛區，并減少了對已知區域的搜索。仿真結果顯示，在上述20×15的網格內，1個重點未知區域、1 個已知區域和1 個禁飛區域，3 架UCAV 的條件下，協同航路的搜索回報值比非協同航路提高了13.6%，加權平均距離僅為非協同航路的79.6%。UCAV 的協同航路和空間分布既加強了對高關注度區域的巡邏力度，又利于對目標進行快速打擊。因此，在復雜環境下，本文的多UCAV 協同巡邏航比一般非協同航路具有更好的搜索效率和打擊效率。

[1] 吳文超，黃長強，宋磊.不確定環境下的多無人機協同搜索航路規劃[J].兵工學報，2011，32（11）：1337-1342.

WU WENCHAO，HUANG CHANGQIANG，SONG LEI.Cooperative search and path planning of multi-unmanned air vevehicles in uncertain environment[J]. Acta Armamentarii，2011，32（11）：1337-1342.（in Chinese）

[2] 喬福超，王昌金.按關注度分布的多無人機協同巡邏航路規劃[C]//海洋發展與指揮控制會議.煙臺，2013：144-147.

QIAO FUCHAO，WANG CHANGJIN. Cooperative patrol and path planning of multi-UCAVs according to degree of concern[C]//Ocean Development and Command Control Cconference. Yantai，2013：144-147.（in Chinese）

[3] CHANDLER P，PACHTER M，RASMUSSEN S. Hierarchical control for autonomous teams[C]//Proceedings of AIAA Guidance，Navigation，and Control Conference and Exhibit. Montreal：American Institute of Aeronautics and Astronautics，2001：632-642.

[4] SVENNEBRING J，KOENIG S. Building terrain-covering ant robots：a feasibility study[J].Autonomous Robots，2004：16（3）：313-332.

[5] 黃長強，翁興偉，王勇.多無人機協同作戰技術[M].北京：國防工業出版社，2012：41-53.

HUANG CHANGQIANG，WENG XINGWEI，WANG YONG. Cooperative combat technology for multi-UAVS[M]. Beijing：National Defense Industry Press，2012：41-53.（in Chinese）

[6] 汲萬峰，姜禮平，朱建沖.基于機動目標威脅和粒子群算法的航路規劃[J].電光與控制，2010，17（11）：5-8.

JI WANFENG，JIANG LIPING，ZHU JIANCHONG.Route planning based on mobile threat and particle swarm optim ization[J]. Electronics Optics and Control，2010，17（11）：5-8.（in Chinese）

[7] 王磊，施榮華.基于粒子群算法的無人機航路規劃與建模仿真[J].計算機仿真，2011，28（4）：74-77.

WANG LEI，SHI RONGHUA. Application of particle swan optimization algorithm to path planning of unmanned aerial vehicle[J]. Computer Simulation，2011，28（4）：74-77.（in Chinese）

[8] 丁偉鋒，嚴建鋼，葉文.不同作戰任務條件下的UCAV航路規劃問題建模[J].海軍航空工程學院學報，2012，27（1）：115-119.

DING WEIFENG，YAN JIANGANG，YE WEN. Research on the UCAV path planning model in different combat mission condition[J]. Journal of Naval Aeronautical and Astronautical University，2012，27（1）：115-119.（in Chinese）

[9] CHOSET H.Coverage for robotics：a survey of recent results[J]. Annals of Mathematics and Artificial Intelligence，2001，31：113-126.

[10]劉鋼，老松楊，侯綠林，等.知識引導的智能優化算法在航路規劃中的應用[J].湖南大學學報，2013，40（1）：103-108.

LIU GANG，LAO SONGYANG，HOU LVLIN，et al.Application of knowledge-conducting intelligent optimization algorithms to path planning[J].Journal of Hunan University，2013，40（1）：103-108.（in Chinese）

[11]劉科，周繼強，郭小和.基于改進粒子群算法的無人機路徑規劃研究[J].中北大學學報，2013，34（4）：441-447.

LIU KE，ZHOU JIQIANG，GUO XIAOHE. Path planning research for unmanned air vehicle based on improved particle swarm algorithm[J].Journal of North University of China，2013，34（4）：441-447.（in Chinese）

[12]杜繼永，張鳳鳴，毛紅保，等.多UAV協同搜索的博弈論模型及快速求解方法[J].上海交通大學學報，2013，47（4）：667-673.

DU JIYONG，ZHANG FENGMING，MAO HONGBAO，et al. Game theory based Multi-UAV cooperative searching model and fast solution approach[J]. Journal of Shanghai Jiaotong University，2013，47（4）：667-673.（in Chinese）

[13]李帆，郝博，萬聰梅，等.基于混合粒子群優化算法的多彈協同航跡規劃[J].飛行力學，2013，31（1）：93-96.

LI FAN，HAO BO，WAN CONGMEI，et al.Multi-missile cooperative route planning based on hybrid particle swarm optimization[J]. Flight Dynamics，2013，31（1）：93-96.（in Chinese）