基于PSO-HJ算法的多無人機協(xié)同航跡規(guī)劃方法

單文昭，崔乃剛，黃 蓓，王小剛，白瑜亮

（1.中國運載火箭技術研究院，北京 100076；2.哈爾濱工業(yè)大學 航天學院，哈爾濱 150001）

多無人機協(xié)同航跡規(guī)劃是任務規(guī)劃系統(tǒng)中的關鍵部分[1]。多無人機協(xié)同任務包括目標協(xié)同定位、目標協(xié)同攻擊和目標效能協(xié)同評估等。其中，多個無人機同時到達目標區(qū)域是目前協(xié)同攻擊問題的主要研究方向[2]。

航跡規(guī)劃是一類復雜優(yōu)化問題，國內外學者提出很多算法。常用算法可大致分為兩類，一類基于圖的算法包括Voronoi圖、A*搜索算法、D*搜索算法等[3]。另一類基于群體智能優(yōu)化算法包括遺傳算法、粒子群算法、差分進化算法等[4]。這類智能算法簡單且計算效率高。其中，粒子群算法（Particle Swarm Optimization，PSO）不需要變異操作，比其他進化算法更易實現(xiàn)，但PSO存在局部搜索能力差的缺陷[5]。文獻[6]通過引入收縮因子和學習因子到PSO中，改善二維航跡規(guī)劃算法收斂速度。文獻[7]通過將種群的繁殖機制引入PSO，提升算法全局搜索能力。文獻[8]設計了異步變化的學習因子，提高了算法全局搜索能力。本文引入Hooke-Jeeves（HJ）搜索算法到PSO中，提出一種粒子群優(yōu)化和HJ搜索算法相組合的PSO-HJ算法，豐富粒子搜索行為并改善粒子局部搜索能力。同時，對評價粒子優(yōu)劣的方法做出改進，充分考慮不滿足約束的粒子，避免由于過度舍棄而遠離可行解。

多無人機協(xié)同航跡規(guī)劃問題需要考慮的約束增多且模型更加復雜，對求解效率和速度要求更高[10]。目前，文獻常用集中式求解框架解決多機協(xié)同問題，集中式求解框架相對簡單且獲得解的精度高。文獻中這類方法考慮無人機數(shù)量較少或環(huán)境過于簡單，如果無人機數(shù)量增加，計算維數(shù)將擴大，求解速度變慢，算法不適用于動態(tài)變化的場景。而且，真實場景中無人機可能存在通信受限情況，集中求解方法需要掌握信息過多，難以實際應用。針對這些問題，本文提出一種多無人機協(xié)同航跡規(guī)劃方法的框架，先分別求解單機航跡規(guī)劃問題再求解多機協(xié)同問題，將求解總體代價最小的問題轉化為求取最小的協(xié)同時間。一個復雜的高維優(yōu)化問題分解成一個計算量小的低維問題，提高計算效率。另外，傳遞協(xié)同變量編隊預計到達時間ETA（estimate time arrival，ETA），節(jié)省傳輸時間和空間，更具有可實現(xiàn)性[11]。

1 無人機航跡規(guī)劃問題建模

1.1 環(huán)境建模

無人機任務環(huán)境中威脅包括雷達、防空火炮、防空導彈等。一旦無人機穿越威脅區(qū)，無人機存在被擊落的可能。本文將威脅區(qū)定義為圓柱體，威脅區(qū)為T=（xT,yT,hT,rT）。威脅中心坐標為（xT,yT），威脅區(qū)水平投影半徑為rT，威脅區(qū)高度為hT。地形包括山丘和平原，因此設計地形函數(shù)為z=fT（x,y）。地形示意圖如圖1。

圖1 地形示意圖 Fig.1 Topographic map

1.2 航跡代價函數(shù)

本文航跡代價函數(shù)包括威脅代價、航程代價、高度代價、撞地概率代價函數(shù)。

1.2.1 威脅代價函數(shù)

威脅代價是無人機全程飛行中穿越威脅區(qū)的可能性。按圖2所示，在第i個航跡段wiwi+1取k個點，記Pi=（pi,1,pi,2,pi,3…pi,k）。威脅代價按照式(1)計算。

其中，n為航跡段個數(shù)，m為威脅源個數(shù)。lTi是第i段航跡被威脅區(qū)覆蓋的長度。fTAj（pi,q）是pi,q點受到第j個威脅的影響程度，按照公式(2)計算。

其中dj是航跡段上當前節(jié)點到第j個威脅源中心的距離。

圖2 威脅代價計算示意圖Fig.2 Schematic of threat cost calculation

1.2.2 航程代價函數(shù)

航程是無人機從起始點到指定目標點需要飛過的空間距離。通過縮短航程，既能降低無人機危險系數(shù)，也能節(jié)省燃油。航程代價函數(shù)為：

其中l(wèi)i是第i個航跡段長度。

1.2.3 高度代價函數(shù)

低空飛行能降低無人機被敵方雷達發(fā)現(xiàn)的概率。所以，要求無人機在滿足地形最小離地高度條件下，以盡可能低的高度飛行，利用地形實現(xiàn)隱蔽。為表達簡潔，用fT表示fT（xi,yi），高度代價函數(shù)為：

其中，N是無人機航跡上取點的個數(shù)，（xi,yi,zi）是無人機當前位置坐標，fT(xi,yi)是航跡曲線上任意一個航跡點（xi,yi）對應的地形高度，Hmin是無人機允許最低飛行高度。

1.2.4 撞地概率代價函數(shù)

撞地代價函數(shù)是航跡曲線穿過地形的航跡點總數(shù)。

綜上所述，無人機航跡代價函數(shù)如式(1)

其中，ω1～ω4是評價指標的權重系數(shù)，且滿足。根據不同的無人機任務，權重系數(shù)不同。評價指標越重要，對應的權重系數(shù)越大。

1.3 約束條件

1.3.1 最短航程約束

無人機調整飛行姿態(tài)前，第i個航跡段li需滿足大于最短直飛距離lmin。該約束表示為：

1.3.2 最長航程約束

無人機攜帶燃料有限，存在最長航程限制。設lmax是允許的最長航程。該約束表示為：

1.3.3 最大水平拐彎角約束

無人機性能限制其只能在有限的拐彎角內轉彎。設φmax為最大允許拐彎角，記ai=（xi-xi-1,yi-yi-1）T是第i段航跡水平投影。該約束表示為：

1.3.4 最大爬升角或俯沖角約束

無人機爬升或俯沖最大高度受到自身機動性能的影響。設θmax是允許最大爬升角或俯沖角，該約束表示為：

1.3.5 最低飛行高度約束

無人機飛行過低會增加地面碰撞概率，該約束為：

2 單無人機航跡規(guī)劃的PSO-HJ算法

2.1 基本粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）由Eberhart和Kennedy于1995年提出，PSO算法是采用群體智能思想的全局優(yōu)化算法，借鑒模仿魚群和鳥群的集體行為，利用粒子間之間合作和競爭達到計算最優(yōu)解的目的[12]。每個粒子都代表一個解，在D維搜索空間中，第i個粒子位置向量為xi=（xi1,xi2…xiD），第i個粒子速度向量為vi=（vi1,vi2…viD），經過t+1次迭代后，粒子xi歷史最佳位置為，種群全局最佳位置。粒子速度和位置更新公式為：

其中，w是慣性權重系數(shù)，c1和c2分別是粒子的學習因子和加速因子，r1和r2是（0,1）之間的隨機數(shù)且服從均勻分布，M是種群規(guī)模，D是粒子的維數(shù)，tmax是粒子的最大迭代次數(shù)。速度和位置有最大速度和最大位置限制。

圖3 粒子群算法原理圖Fig.3 Schematic of particle swarm optimization

2.2 約束處理機制

無人機航跡規(guī)劃問題可轉化為如下非線性規(guī)劃問題。

其中，J是適應度值。f（x）是適應度評價函數(shù)，具體參考式(6)，g（x）是不等式約束，l是不等式約束的個數(shù)，h（x）是等式約束，p是等式約束的個數(shù)。這里只考慮不等式約束。為處理約束，引入約束違反度函數(shù)fv（x）：

傳統(tǒng)評價粒子的方法不考慮違背約束的粒子。本文對評價粒子優(yōu)劣的方法做出改進，避免由于過度舍棄而遠離可行解?；诒容^準則提出新的粒子評價機制為：

（1）當粒子xi和粒子xj都滿足約束時，如果f（xi）＜f（xj），則xi個體為優(yōu)，否則xj個體為優(yōu)。

（2）當粒子xi和粒子xj都不滿足約束時，如果fv(xi)＜fv（xj），則xi個體為優(yōu)，否則xj個體為優(yōu)。

（3）當粒子xi滿足約束，粒子xj不滿足約束時，如果fv（xj）＜εv且f（xj）＜f(xi)，則xj個體為優(yōu)，否則xi個體為優(yōu)。εv是要求的精度指標。

2.3 單無人機航跡規(guī)劃的PSO-HJ算法

粒子群算法的慣性權重越大全局搜索能力越強，反之，慣性權重越小，局部搜索能力越強。與傳統(tǒng)PSO算法不同，本文慣性權重不是固定值，慣性權重線性下降公式為：

其中，根據經驗wmax= 0.95，wmin= 0.4，ω是慣性權重，ωmax是最大權重，ωmin是最小權重 ，t是粒子的當前迭代次數(shù)[13]。

在PSO算法搜索過程中，粒子速度可能會超出最大速度限制，此時速度更新公式為：

粒子位置可能會超出解空間的邊界，此時位置更新公式為：

其中，v是粒子當前速度，xU是粒子位置的邊界值上限，xL是粒子位置的邊界值下限。

HJ算法是一種無需梯度計算的直接搜索算法。HJ算法先探索下降的最有利的方向，然后沿著這個方向加快搜索速度，可以迅速獲得局部最優(yōu)解。粒子群算法是隨機搜索算法，所以局部搜索能力較差，PSO和HJ混合能豐富優(yōu)化過程的搜索行為，有利于收斂到最優(yōu)解。改進的混合算法稱為PSO-HJ算法。PSO-HJ算法步驟可以描述為：

（1）初始化：確定種群規(guī)模M、粒子維數(shù)D、最大迭代次數(shù)tmax。初始化粒子速度、位置和PSO參數(shù)。

（2）根據式（14）計算粒子的適應度值，根據新的粒子評價機制，得到粒子歷史最佳位置pbest和粒子全局最佳位置gbest。

（3）更新粒子速度和位置，并更新粒子歷史最佳位置pbest和粒子全局最佳位置gbest。

（4）如果粒子下一代適應度值大于粒子當代適應度值，進入到第（6），否則進入第（5）。

（5）選擇前百分之二十的粒子引入HJ算法 ：將PSO算法的解賦予HJ算法作為初始值，利用HJ算法更新PSO的解。然后進入到第（6）。

（6）對于超出邊界的粒子按照公式更新其速度和位置，保證速度和位置滿足要求。

（7）判斷是否滿足結束條件：達到設定的最大迭代次數(shù)或達到精度要求。如果滿足，停止迭代，輸出最優(yōu)解。否則，回到第（2）。算法流程圖如圖4所示。

圖4 PSO-HJ算法流程圖Fig.4 Flow chart of PSO-HJ algorithm

3 多無人機協(xié)同航跡規(guī)劃方法

3.1 多無人機協(xié)同航跡規(guī)劃方法框架

本文協(xié)同航跡規(guī)劃的任務是多無人機協(xié)同攻擊目標，要求編隊同時到達時間最短。定義協(xié)同變量為編隊預計到達時間（estimate time arrival，ETA）。多無人機協(xié)同航跡規(guī)劃問題可以通過層次分解法，轉化為先求解單機航跡規(guī)劃問題再求解多機協(xié)同問題。多機協(xié)同規(guī)劃算法的框架包括三個層次，每個層次之間互相傳遞信息，框架如圖5所示。

圖5 多無人機協(xié)同航跡規(guī)劃方法框架Fig.5 Framework of multi-UAV cooperative track planning method

（1）第一層是多無人機任務要求層。任務為多無人機協(xié)同攻擊目標，要求多無人機同時到達目標。

（2）第二層是多無人機集中計算層。集中計算層為中央單元，包括領機或者地面指揮站等，利用時間協(xié)同航跡規(guī)劃算法計算編隊到達時間和無人機速度。

（3）第三層是單無人機航跡規(guī)劃層。利用PSO-HJ算法求解最優(yōu)航跡和備選航跡信息，作為多無人機集中計算層的輸入信息。

3.2 多無人機時間協(xié)同航跡規(guī)劃算法描述

假設第i架無人機速度變化范圍為。其中，是第i架無人機的最小飛行速度，是第i架無人的最大飛行速度。因為航跡規(guī)劃空域里無人機速度變化較小，理想假設無人機勻速飛行。根據前文航跡規(guī)劃方法獲取無人機航跡組信息，包括最優(yōu)航跡和多條備選的次優(yōu)航跡。那么可知第i架無人機如果按照最優(yōu)航跡飛行，該無人機預計到達時間范圍Stime,i為：

其中，i= 1,2…s，s是無人機的數(shù)量。Lgi是第i架無人機最優(yōu)航跡長度。同理可計算無人機選擇其他備選航跡的預計到達時間范圍。

無人機編隊需要實現(xiàn)最短時間同時到達，協(xié)同變量ETA的計算公式為

協(xié)同變量ETA是所有無人機預計到達時間集合交集的最小值。若編隊預計到達時間ETA無解，則取預計到達時間Stime,i最短的無人機的次優(yōu)航跡Lci替換其當前航跡Li，重新計算該無人機預計到達時間Stime,i。如果仍無解，重復以上步驟直至協(xié)同變量ETA有解。求解得到編隊到達時間Tf后，可分配第i架無人機速度為Vi=LfiTf，Lfi是滿足時間協(xié)同的無人機航跡。具體無人機協(xié)同航跡規(guī)劃算法流程如圖6所示。

圖6 多無人機時間協(xié)同航跡規(guī)劃算法流程Fig.6 Flow chart of multi-UAV time cooperative flight path planning algorithm

多無人機時間協(xié)同航跡規(guī)劃算法可以描述為：

（1）根據式（1）到式（18）同時計算每架無人機的最優(yōu)航跡和備選的次優(yōu)航跡組。

（2）將（1）計算得到的結果作為協(xié)同規(guī)劃層的輸入，根據式（19）計算每架無人機到達時間范圍Stime,i。如果ETA無解，進入（3）。否則，進入到（4）。

（3）選擇預計到達時間最短的無人機次優(yōu)航跡Lci替換該無人機當前航跡Li，進入到（2）。

（4）根據式（20）計算協(xié)同變量ETA。

（5）由Vi=LfiTf計算每架無人機飛行速度Vi。

（6）分配速度Vi和協(xié)同航跡Lfi至第i架無人機。

4 仿真分析

4.1 仿真初始條件

仿真實驗環(huán)境為 Dell PC，Core E5800 CPU(3.2GHz)，4G內存。無人機的任務區(qū)域是30km×30 km×30 km的立方體。3D地形內有很多山和平原，威脅的覆蓋以圓柱體表示。本文設計仿真場景包括5個威脅。設定初始種群規(guī)模M= 100，粒子維數(shù)D= 21，最大迭代次數(shù)tmax=200，最大權重ωmax= 0.95，最小權重ωmin= 0.4。最大拐彎角φmax= 60°，最大爬升角θmax= 60°，最低飛行高度Hmin= 20m 。

4.2 仿真結果

仿真算例1：

為驗證PSO-HJ算法的多無人機時間協(xié)同三維航跡規(guī)劃方法的可行性，仿真結果如圖7-8所示。

圖7 基于PSO-HJ算法的單無人機航跡結果Fig.7 Single UAV path planning results based on PSO-HJ algorithm

圖8 多無人機時間協(xié)同航跡結果Fig.8 Multiple UAV time cooperative path planning results

仿真結果表明，算法可行性得到驗證。從圖7看出，無人機規(guī)劃航跡避開威脅區(qū)，以盡量低高度飛行并較好的跟隨地形。從圖8可以看出，本文提出的方法實現(xiàn)多架無人機同時到達目標。

仿真算例2：

為驗證PSO-HJ航跡規(guī)劃算法的效率，與傳統(tǒng)PSO和量子粒子群（QPSO）航跡規(guī)劃算法比較。算法效率的評價指標包括直線率系數(shù)和最優(yōu)適應度值。本文定義了航跡規(guī)劃算法的評價指標直線率系數(shù)SLR，直線率系數(shù)決定了航跡整體長度與最短直線距離接近的程度。直線率系數(shù)越高代表航跡規(guī)劃算法性能越好。直線率系數(shù)，SG代表從無人機出發(fā)點到目標點的直線距離，luav是無人機規(guī)劃后的航跡長度。仿真結果如圖9- 10所示。PSO、QPSO和PSO-HJ算法計算20次后算法評價指標結果如表1所示。

圖9 PSO、QPSO和PSO-HJ算法的航跡比較結果Fig.9 Path planning results comparison of PSO,QPSO and PSO-HJ algorithms

仿真結果表明，PSO-HJ算法比PSO算法和QPSO算法收斂速度更快。圖9可以看出，PSO-HJ算法生成的航跡更短，而且地形跟隨效果更好，PSO生成的航跡選擇爬過高山，而PSO-HJ算法選擇較低的高度飛行。從圖10可以看出，PSO-HJ算法最優(yōu)適應值更低。從表1可以看出，PSO-HJ算法的航跡代價和航跡長度都低于PSO和QPSO算法。PSO-HJ算法的精度比QPSO算法精度提高了20.85%，比PSO算法精度提高了58.14%，說明PSO-HJ算法得到的解的質量更高，PSO-HJ算法的局部搜索能力更好。

圖10 三種算法的最優(yōu)適應度值和SLR曲線圖Fig.10 The optimal fitness value and SLR curve of the three algorithms

表1 航跡規(guī)劃效果的算法比較Tab.1 Algorithm comparison of flight path planning effect

5 結 論

本文分析和設計了無人機航跡代價函數(shù)，結合無人機動力學特性設計了約束條件，建立了單無人機三維航跡規(guī)劃數(shù)學模型。

為處理復雜優(yōu)化問題，設計了基于PSO-HJ算法的無人機的三維航跡規(guī)劃方法。提出了新的粒子評價機制，并對表現(xiàn)差的粒子引入HJ算法，來改善化算法的效率。

設計多無人機協(xié)同航跡規(guī)劃方法框架，基于PSO-HJ算法求解備選航跡，通過多無人機集中航跡規(guī)劃層協(xié)調編隊到達時間實現(xiàn)協(xié)同航跡規(guī)劃。

仿真結果表明，本文提出的算法實現(xiàn)了多架無人機同時到達目標區(qū)域，證明了算法可行性；與PSO算法和QPSO算法相比，具有更快的計算速度和收斂精度。