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

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

0 引言

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

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

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

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

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

1 問題描述

1.1 問題描述

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

1.2 任務場景

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

表1 攻擊任務評估結果

2 任務規(guī)劃模型

2.1 模型假設

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

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

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

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

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

圖1 任務場景示意圖

2.2 模型建立

2.2.1 航路代價建模

符號描述如表2所示。

表2 符號描述

由于將作戰(zhàn)空間簡化為二維空間，故cij為節(jié)點j-1 和節(jié)點j之間的距離。

(1)

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

(2)

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

(3)

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

(4)

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

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

(5)

(6)

故目標函數(shù)為

(7)

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

2.2.2 約束條件

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

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圖法的航跡規(guī)劃

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

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

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

(4) 進行航路的再規(guī)劃：刪去超出飛行區(qū)域，以及在禁飛區(qū)域內的節(jié)點，產(chǎn)生安全路徑。

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

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

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

圖3 初始航路選擇圖

3.2 標準粒子群算法

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

3.3 模擬退火算法

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

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

算法流程圖如圖4所示。

圖4 算法流程圖

算法具體步驟：

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

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

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

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

(14)

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

xid=xid+[vid].

(15)

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

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

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

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

4 仿真算例

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

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

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

圖6 最優(yōu)路徑

當?shù)玫阶顑?yōu)路徑之后，采用基于模擬退火的粒子群算法進行任務分配，得到從各基地到各目標出動的UAV數(shù)量如表3所示，從各基地到各目標的航跡長度如表4所示。

表3 從各基地到各目標出動的UAV的數(shù)量

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

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

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

圖7 代價函數(shù)值隨時間變化曲線

指標算法PSOSASA-PSO最優(yōu)解56.41479.42856.351最差解94.80996.30666.528平均值76.01689.33262.689

5 結束語

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