多基地多目標無人機協同任務規劃算法研究*

潘楠，劉海石，陳啟用，顏禮賢，郭曉玨

(1.昆明理工大學a.民航與航空學院;b.材料科學與工程學院，云南 昆明 650500;2.昆明智淵測控科技有限公司，云南 昆明 650500)

0 引言

無人飛行器(unmanned aerial vehicle,UAV) 是一種以自身程序或人在回路控制的不載人飛行器。現代戰爭中，無人機需對多個目標進行攻擊，同時也面臨著多個威脅源的威脅，而單機的作戰能力有限，因此未來軍事斗爭中，更多的將是機群協同對地目標的攻擊[1]。任務規劃是多無人機協同作戰任務技術中的重要組成部分，在軍事領域，UAV任務規劃的主要目的是依據戰場環境信息，綜合考慮UAV的性能，到達時間、油耗、威脅等約束條件[2]，為每個UAV規劃出一條或多條從基地到目標最優或滿意的航路，使UAV的生存概率和作戰效能達到最佳。多無人機協同作戰任務規劃分為任務分配和航跡規劃2部分，在任務規劃的過程中，由于UAV自身的動力特點以及所執行任務的協同性，給解決多目標多基地UAV任務規劃問題帶來很大的困難，對此，國內外開展了大量的研究。

在UAV協同任務規劃技術的相關研究中，無論是航跡優化還是任務分配，智能優化算法都必不可少[3-5]。Voronoi圖是由若干個圍繞障礙物的共邊多邊形產生的連接圖[6]。文獻[7]利用Voronoi圖以及粒子群(particle swarm optimization,PSO)算法對單基地單目標進行路徑規劃，沒有考慮多基地多目標。文獻[8]利用Voronoi圖及快速擴展隨機樹算法進行航跡規劃，并基于博弈策略來選擇最優航跡。文獻[9]提出一種周期性快速搜索遺傳算法(periodic fast search genetic algorithm,PFSGA) 與人工勢場法(artificial potential field,APF) 的聯合算法，作多基地多無人機任務規劃時對航跡沒有做圓滑處理，沒有考慮到UAV的物理限制。文獻[10]提出了基于動態權值的A*算法，并利用其進行航跡搜索，取得了一定的效果。文獻[11]提出的任務規劃模型中一機攻打多個目標，加大了任務難度，一旦發生意外，便不能很好地完成任務，而且該方法也不能滿足現代戰爭中的同時性。文獻[12]中對于飛行空間不作限制，沒有考慮到UAV的航路距離約束。Dijkstra算法確定了賦權網絡中從某點到所有其他節點的具有最小權的路徑[13]。

目前，大多數研究中，沒有針對多基地、多目標、多無人機，這對算法的實際應用造成了困難。文獻[14]分別對兩目標和三目標決策運用多目標優化算法得到了所需結果,目標太少，不能很好體現多目標的復雜性。文獻[15]提出利用小生境克隆選擇算法為無人機生成滿足要求的航路，有效解決了多機航跡規劃問題，但是沒有進一步進行任務分配。

文獻[16]針對傳統粒子群優化算法收斂速度慢的問題，改進了粒子群算法，從而得到最優偵察任務方案。雖然以上研究均針對無人機航跡規劃問題以及任務分配問題進行了算法的改進，并驗證了所提算法的逼近性，但是沒有驗證算法的均勻性，也沒有完成航跡規劃與任務分配的耦合。

本文針對多基地、多目標、多UAV協同任務規劃問題復雜且耦合的特點，在較為完善的約束條件下提出了一種基于模擬退火粒子群算法的規劃方法，先用Voronoi圖和Dijkstra算法進行第1重優化找到基地到目標之間的最優化航路，然后再用基于模擬退火的粒子群算法進行再優化，找到一種滿意的任務分配方式，通過反饋回來的各UAV的航線長度并根據各UAV的速度，進而控制各UAV起飛時間，從而完成航跡規劃與任務分配的耦合，達到協同作戰目的。最后仿真結果表明，文中所提算法具有較好的逼近性以及均勻性，符合軍事上多無人機執行對地多目標攻擊任務的工程應用。

1 問題描述

1.1 問題描述

針對多基地、多目標、多無人機在對地攻擊背景下協同任務規劃問題，考慮到目標位置以及固定障礙物區域已知，因此，對地攻擊任務的關鍵在于如何保證各UAV航跡的距離最短、威脅代價最小，即整體航跡的最優，以及各目標向各基地派出的無人機數量。

1.2 任務場景

某作戰部隊有4個基地，分別在不同的區域，各基地分別有6架某型號無人機。某次攻打任務有7個敵方目標群，經偵察得到戰場上敵方探測雷達威脅以及禁飛區域、每個目標群的火力情況以及面積，經綜合評估攻打任務目標所需該型號無人機的數量如表1所示。其中每次任務所有無人機可不完全出動，并要求4 h內完成攻打任務。

表1 攻擊任務評估結果

2 任務規劃模型

2.1 模型假設

(1)為了簡化模型故將UAV設為質點，不考慮各UAV之間的距離過短產生碰撞。

(2)為了方便數字地圖模型的建立，把山體建筑物等禁飛區域簡化為圓形。

(3)將飛行空間由三維轉化為二維，故各目標群中心位置，基地位置，固定障礙物以及雷達位置如圖1示。

(4)在考慮飛機機動性能時僅考慮最大作戰半徑約束、最小轉彎半徑約束、最大(最小)速度約束。

(5)如果各飛機航線重合，將采用線性編隊。

圖1 任務場景示意圖

2.2 模型建立

2.2.1 航路代價建模

符號描述如表2所示。

表2 符號描述

由于將作戰空間簡化為二維空間，故cij為節點j-1 和節點j之間的距離。

(1)

ci則為第i條路線上各小段的求和。當第i條路線有m段時：

(2)

當UAV具有相同雷達反射截面時，其反射雷達回波的強度與到達雷達距離的4次方成反比。為了簡化計算，實際上通常取某一段上的幾個點進行加權平均。為了讓威脅代價更加貼近于真實值，這里取5個點進行威脅代價計算，如圖2所示。計算結果為

(3)

式中：l為第i條航跡上，節點j-1和節點j之間的距離，即l=cij；dij1,dij2,…,dij5分別為在某航跡段上所取的5個點到雷達威脅源的距離。

(4)

圖2 計算威脅代價取點示意圖

由于威脅代價和燃油代價數量級的不同，因而利用線性函數歸一化方法對代價函數中的指標進行歸一化處理。

(5)

(6)

故目標函數為

(7)

式中：ω1為燃油代價的權重；ω2為威脅代價的權重。

2.2.2 約束條件

(1) 最大作戰半徑約束，該約束限制了航路的長度。

L≤Lmax，

(8)

Lmax=300 km.

(9)

(2) 最小轉彎半徑約束，限制生成的航路轉彎半徑必須大于UAV最小轉彎半徑，該約束條件取決于UAV的性能。

K≤Kmax，

(10)

Kmax=50 km.

(11)

(3) 最大、最小速度約束，限制飛機飛行的最長最短時間。

vmin≤v≤vmax，

(12)

vmin=25 km/h，vmax=150 km/h.

(13)

3 算法描述

3.1 基于Voronoi圖法的航跡規劃

(1) 初始化雷達坐標、禁飛區域、基地中心坐標、目標中心位置以及各代價權重。

(2) 根據禁飛區域和雷達坐標生成威脅點。

(3) 根據威脅源的分布情況，用Voronoi圖法快速初始化航路，各威脅源連線的中垂線對應了Voronoi圖的各邊，形成初始航路選擇圖，此初始航路選擇圖中邊上的各點距離威脅源最遠，如圖3所示。

(4) 進行航路的再規劃：刪去超出飛行區域，以及在禁飛區域內的節點，產生安全路徑。

(5) 生成代價矩陣：Voronoi圖上每相鄰的兩節點的距離和所有雷達對該段航路的威脅程度構成代價矩陣。

(6) 用Dijkstra算法快速搜索各基地到各目標的最小代價航路。

(7) 用貝塞爾曲線對最小代價航路進行平滑處理。

圖3 初始航路選擇圖

3.2 標準粒子群算法

在PSO算法中，在可行解空間中初始化一群粒子，每個粒子都代表問題的一個潛在最優解，每個粒子都有自己的位置、速度、適應度值，其中由適應度函數計算得到適應度值，其值好壞表示其代表粒子的優劣。粒子在解空間中運動，粒子的速度決定了粒子移動的方向和距離，速度隨自身以及其他粒子的移動經驗進行動態調整，實現個體在可解空間中找到自己的最好位置，稱為個體極值Pbest。粒子群中所有粒子搜索到的適應度的最優值稱為群體極值Gbest。各粒子經過不斷的迭代過程找到最優解。算法運行過程中，為了防止粒子的盲目搜索，一般建議將其位置和速度限制在一定的區間[-Xmax,Xmax],[-vmax,vmax]。

3.3 模擬退火算法

Metropolis等于1953年提出了模擬退火(simulated annealing,SA)算法。首先對固體物質高溫加熱，然后慢慢冷卻，由高能向低能轉變的降溫過程成為退火。模擬退火算法，在迭代過程中和粒子群算法用更好的值來代替原來的位置不同，在SA算法中，是以概率接受新狀態，所以模擬退火算法可以跳出局部最優。

3.4 基于模擬退火的粒子群算法優化多目標多基地無人機協同任務分配

算法流程圖如圖4所示。

圖4 算法流程圖

算法具體步驟：

(1) 初始化參數，設置每個目標被摧毀至少需要的無人機數量、粒子群數量、最大迭代次數、學習因子、慣性因子。

(2) 更新粒子群的個體極值和全局極值。

(3) 根據基本粒子群更新公式，更新粒子群中各粒子的速度和位置；基本粒子群速度更新公式為

vid=w·vid+c1r1(pid-xid)+c2r2(pgd-xid).

(14)

由于任務分配進行的是整數離散粒子群優化，每個粒子的位置表示基地派往目標的無人機數量，所以粒子群位置更新公式為

xid=xid+[vid].

(15)

(4) 計算更新后各粒子的適應度值，記為fi，位置記為xi。

(5) 隨機擾動產生新的粒子群x_newi，計算其適應度值為f_newi。

(7) 降溫并判斷當前是否達到最低溫度，如果達到退火結束，如果沒有返回步驟(5)繼續優化。

(8) 判斷當前是否達到最大迭代次數，如果達到，優化結束并輸出結果，如果沒有，返回步驟(2)繼續優化。

4 仿真算例

為了驗證本文中基于模擬退火粒子群算法UAV任務規劃的有效性，對圖1所示的具有3個禁飛區域、10個威脅源的戰場環境利用Matlab R2017a進行任務規劃仿真。

采用Voronoi圖并進行航路再規劃之后得到的可飛行路徑結果如圖5所示。在此基礎上，利用Dijkstra算法以及貝塞爾曲線獲得最小代價路徑并對最小代價路徑進行平滑處理，得到最優路徑，如圖6所示。

圖5 基于Voronoi圖的可飛行路徑

圖6 最優路徑

當得到最優路徑之后，采用基于模擬退火的粒子群算法進行任務分配，得到從各基地到各目標出動的UAV數量如表3所示，從各基地到各目標的航跡長度如表4所示。

表3 從各基地到各目標出動的UAV的數量

表4 從各基地到各目標的航跡長度

采用基本PSO算法、SA算法以及SA-PSO算法一次運行過程中進行對比得到的仿真曲線如圖7所示。3個算法30次運行過過程中得到的最優解、最差解以及平均值如表5所示，平均值的仿真曲線如圖8所示。

從圖7中可以看出，在相同進化次數和粒子群各參數相同的前提下，本文方法得到的代價函數值遠低于基本PSO算法。基本PSO算法得到的目標函數的最小值為76.34，標準SA算法得到的目標函數最小值為92.74，而本文方法得到的目標函數的最小值為63.06。從圖7，8可以看出，本文所提算法，無論是收斂速度還是收斂精度均要優于PSO算法和SA算法。從表5中可以看出，在3個算法運行30次的過程中，從最優解、最差解以及平均值3個指標中任一指標來看，本文所提算法的結果均為最優。因此可以得出結論，本文所提算法在解決多基地、多目標、多無人機任務規劃這類大規模優化問題時，具有較快的收斂速度以及較高的收斂精度，SA-PSO算法具有較強的穩健性、均勻性。

圖7 代價函數值隨時間變化曲線

指標算法PSOSASA-PSO最優解56.41479.42856.351最差解94.80996.30666.528平均值76.01689.33262.689

5 結束語

本文在以攻擊任務為背景的情況下，通過對多基地、多目標、多UAV任務規劃進行分析，根據威脅點及障礙物分布情況，獲得基于Voronoi圖的可行路徑，然后采用Dijkstra算法以及貝塞爾曲線對航跡進行優化以及平滑處理，得到最優航路，之后根據最優航路并利用基于模擬退火的粒子群算法進行任務分配。文中所述方法能夠保證各UAV組成的整體以總燃油代價最小，總威脅代價最小的情況下完成任務，與其他方法相比提高了基本粒子群全局搜索能力，加快了優化的速度，提高了收斂精度。但仍存在一些不足之處，比如對UAV的物理限制不夠完善，將作戰空間簡化為二維空間。下一步的工作是討論如何在三維空間內，采用文中的基于模擬退火的粒子群算法面對突發威脅時的任務規劃。