王慶海，姚冬艷，劉廣瑞

(鄭州大學 機械工程學院，鄭州　450001)

0　引言

無人機航跡規(guī)劃是根據(jù)所處地形、威脅等環(huán)境因素下，根據(jù)無人機自身綜合性能快速由起點到目標點規(guī)劃出一條最優(yōu)或較優(yōu)航跡[1]。無人機航跡規(guī)劃對于提高無人機作業(yè)效率和實戰(zhàn)能力具有重要意義。國內(nèi)外許多學者對無人機航跡規(guī)劃進行了大量研究。文獻[2]提出一種基于平衡演化策略的改進人工蜂群算法的二維航跡規(guī)劃方法，通過利用標志向量控制算法探索精度和改進偵查蜂的產(chǎn)生策略兩種方式促進了全局搜索和局部搜索的平衡，但該方法僅局限于無人機二維航跡規(guī)劃，不能解決三維航跡規(guī)劃問題。文獻[3]提出一種基于人工勢場法的三維航跡規(guī)劃方法，通過在目標點和威脅處定義虛擬力函數(shù)，實現(xiàn)無人機避障完成航跡規(guī)劃，但該方法存在局部極小問題，當威脅較多時，易導致無人機航跡規(guī)劃進入“死胡同”，無法得到到達目標點的航跡。文獻[4-6]根據(jù)變化的環(huán)境信息實現(xiàn)動態(tài)航跡規(guī)劃，但由于動態(tài)環(huán)境信息數(shù)據(jù)量較大，實時航跡規(guī)劃并未取得較理想的結(jié)果。文獻[7]引入差分進化思想對蝙蝠算法進行改進，改進后的蝙蝠算法在無人機三維航跡規(guī)劃中取得了較好的優(yōu)化效果，但求解無人機三維航跡規(guī)劃問題時，收斂速度較慢，易陷入局部最優(yōu)，導致算法規(guī)劃效率較低。

目前，專家學者對無人機二維航跡規(guī)劃做了充分的研究工作，而三維航跡規(guī)劃還有值得深入研究和改進的地方[8]。面對動態(tài)威脅，本文所提算法可使無人機根據(jù)實時采集的環(huán)境信息進行動態(tài)規(guī)劃，0.1s內(nèi)就能規(guī)劃出當前所處環(huán)境的較優(yōu)航跡。針對蜜源初始化方式、選擇策略、判定準則等問題，本文通過對人工蜂群算法進行適當?shù)母倪M，使之更適應無人機三維航跡規(guī)劃，通過仿真實驗結(jié)果表明，本文改進人工蜂群算法在三維航跡規(guī)劃中較傳統(tǒng)人工蜂群算法具有更高的優(yōu)化效率。

1　無人機三維航跡規(guī)劃數(shù)學模型

1.1　環(huán)境建模

無人機航跡規(guī)劃環(huán)境為三維空間，由起點到終點分布有若干威脅，本文中威脅用包括其自身的最小外接球表示，本文航跡規(guī)劃目標為在躲避所有威脅的情況下由起點到終點規(guī)劃一條最優(yōu)或次最優(yōu)可行航跡。

在無人機航跡規(guī)劃范圍內(nèi)建立空間直角坐標系O-xyz，如圖1所示，其中S(O)表示無人機的起點，T為目標點。將原直角坐標系轉(zhuǎn)化為柱坐標系，把線段ST進行(D+1)等分，過每個等分節(jié)點做直線ST的垂面Sk，在每個垂面上取一個點Pk，取垂面Sk與z軸的交點為極點，則點Pk在垂面Sk的極坐標為(Rk,φk)，則航跡可以通過D個點的坐標組成的2D維向量(R1,φ2, …,Rk,φk, …,RD,φD)表示，無人機三維航跡規(guī)劃問題被轉(zhuǎn)化為2D維函數(shù)優(yōu)化問題。

1.2　約束條件

無人機搜索范圍為以線段ST為軸，半徑為最大搜索半徑Rmax的圓柱空間，為保證所規(guī)劃航跡的可行性和規(guī)劃效率，對航跡規(guī)劃進行一定的條件約束[9]，具體如下：

(1)無人機在每次轉(zhuǎn)向前須保持直飛，直飛長度根據(jù)無人機的機動性能和導航性能決定。如圖1所示，須保證線段ST的等分間隔(即最小航跡段)大于該長度。

(2)考慮無人機執(zhí)行任務過程中時間限制，所規(guī)劃航跡長度約束為：

(1)

(3)為提高多無人機編隊作業(yè)過程的安全性，無人機的轉(zhuǎn)向角度約束為：

(2)

圖1　無人機航跡規(guī)劃環(huán)境模型

1.3　目標函數(shù)

無人機航跡規(guī)劃過程主要考慮威脅代價fi、耗油代價li和轉(zhuǎn)向代價αi，目標函數(shù)如式(3)所示:

(3)

其中，X=(R1,φ2, …,Rk,φk, …,RD,φD)，且Rk∈(0,Rmax)，φk∈(0, 2π)，k1,k2,k3為對應的代價權(quán)重系數(shù)。本文假設無人機勻速飛行，故無人機耗油代價fi與航跡總長度成正比。轉(zhuǎn)向代價αi計算公式如式(4)所示。如圖2所示，航跡中第i+1段航跡威脅由該段航跡中三個樣本點的威脅均值表示[10]，通過式(5)計算。

(4)

其中，k>1，θj為第j個節(jié)點轉(zhuǎn)向角度，φ為最大轉(zhuǎn)向角度。

(5)

其中，Nt為總的威脅個數(shù)，li為第i段航跡的長度，無人機航跡中點x受第j個威脅的影響代價如式(6)。

(6)

其中，Kj為第j個威脅對無人機威脅強度等級，Rj為第j個威脅的半徑，dxj為第x個點到第j個威脅中心的距離，a為大于1的系數(shù)。

圖2　航跡段威脅計算

2　人工蜂群算法的改進

2.1　初始化蜜源

通過生成一個2D×NP矩陣產(chǎn)生NP個蜜源(每一個行向量代表一條航跡)，傳統(tǒng)ABC算法未能考慮航跡點之間的關(guān)聯(lián)性，優(yōu)化效果較差，為提高初始化蜜源的可行性，提高航跡規(guī)劃算法收斂速度，改進人工蜂群算法中航跡各個跡點的極坐標值為在前一個跡點基礎上按照搜索步長在可行區(qū)間內(nèi)隨機選取，其中，第i個蜜源位置通過式(7)表示：

Xi=(R1,φ1,…,Rk,φk,…,RD,φD,)

(7)

(8)

其中，0≤Rik≤Rmax，0≤φik≤2π，Ri1=RiD=0,φi1=φiD=0, 1≤i≤Np，2≤k≤(D-1)，rand為-1～1的隨機數(shù)，step1和step2分別為半徑搜索步長和角度搜索步長。

2.2　選擇機制

傳統(tǒng)ABC算法通過目標函數(shù)值決定的蜜源適應度比例來判定所要跟隨的采蜜蜂，該方法雖然提高了算法收斂速度，但是容易導致蜂群向適應度值較高的蜜源聚攏，使得算法陷入局部最優(yōu)。本文采用動態(tài)評價選擇策略[11]取代傳統(tǒng)選擇機制，通過采蜜蜂動態(tài)變化狀況決定被跟隨的概率，極大地提高了蜂群多樣性，保證收斂速度的情況下提高了算法的魯棒性。

動態(tài)評價指標為id1(i)和id2(i)。蜜源i被優(yōu)化時id2(i)按式(10)計算，id1(i)為0；蜜源i未被優(yōu)化時id1(i)按式(9)計算，id2(i)為0。動態(tài)評價函數(shù)為式(11)。

(9)

(10)

(11)

其中，id1(i) 為蜜源i被優(yōu)化連續(xù)不變的次數(shù)，id2(i)為蜜源i被優(yōu)化連續(xù)變化次數(shù)，Limit為算法限制參數(shù)。

通過動態(tài)評價函數(shù)計算蜜源個體得分，采蜜蜂被選擇概率計算公式見式(12)，通過Pi計算累計第i個采蜜蜂被選擇概率，將生成的0～1的隨機數(shù)與各累計選擇概率匹配，決定觀察蜂選擇哪個采蜜蜂。

(12)

2.3　鄰域搜索

(13)

2.4　Metropolis準則

在航跡尋優(yōu)過程中，由于尋優(yōu)域較寬，傳統(tǒng)ABC算法全局尋優(yōu)性能劣化，尋優(yōu)前期收斂較快，而后期卻收斂變慢。為提高算法收斂速度和精度，比較完更新前后蜜源后，本文引入Metropolis準則[12]對新舊蜜源進行進一步判定。當前航跡向新航跡轉(zhuǎn)化概率表達如式(14)。通過改進，算法尋優(yōu)初期對較差航跡具有較高接受概率，使算法不易陷入局部最優(yōu)；算法尋優(yōu)后期對較差航跡具有較小接受概率，蜜蜂可在較優(yōu)航跡附近進行細致搜索。

(14)

其中，o代表舊航跡，n代表新航跡，下降函數(shù)T(t)=T(t-1)·σ，退火系數(shù)σ一般取0.8。

2.5　程序流程設計

基于改進人工蜂群算法(IABC)的無人機三維航跡規(guī)劃算法流程圖如圖3所示。

圖3　IABC算法流程圖

3　算例分析

為對本文所提算法的可行性和優(yōu)化效率進行分析，本文在Inter(R) Core(TM) i3-2130 CPU，3.4 GHz，Matlab R2014a環(huán)境下進行仿真分析。人工蜂群算法參數(shù)：蜜蜂總數(shù)為NP=60，采蜜蜂總數(shù)為NP/2，算法限制參數(shù)Limit=5, 最大迭代次數(shù)為maxCycle=100，跡點個數(shù)為10。威脅個數(shù)為6，具體參數(shù)見表1。

本文分別用ABC算法和IABC算法進行了20次航跡規(guī)劃仿真實驗，取20次實驗中最優(yōu)航跡見圖4；取20次實驗中相同迭代次數(shù)的蜂群中最優(yōu)目標函數(shù)值求均值得到100個點，擬合出目標函數(shù)最優(yōu)值收斂曲線對比圖見圖5；取20次實驗中相同迭代次數(shù)的所有蜂群目標函數(shù)值均值求均值得到100個點，擬合出目標函數(shù)均值收斂曲線對比圖6；兩種算法20次實驗結(jié)果數(shù)據(jù)分析對比如表2所示。

表1　威脅信息

表2　優(yōu)化結(jié)果數(shù)據(jù)

圖4　規(guī)劃航跡對比圖

圖5　目標函數(shù)最優(yōu)值收斂曲線對比圖

圖6　目標函數(shù)均值收斂曲線對比圖

通過仿真實驗，改進ABC算法耗時均值雖然高了13.7%，但是平均收斂代數(shù)提高了79.1%，收斂值方差提高了90.1%，收斂均值提高了8.3%。改進ABC算法在無人機航跡規(guī)劃的收斂速度、收斂精度和魯棒性較傳統(tǒng)ABC算法都有較大幅度的提升。

4　結(jié)論

本文提出了無人機三維航跡規(guī)劃的數(shù)學模型，采用改進人工蜂群算法進行航跡尋優(yōu)，通過改進航跡初始化方式提高了初始化航跡可行性；引入動態(tài)選擇機制保證了蜂群的多樣性；引入Metropolis準則對新舊蜜源進行接受判定避免了算法陷入局部最優(yōu)；改進鄰域搜索方式，提高了搜索的精度和算法收斂速度。通過以上改進方式對算法的全局探索能力和局部開發(fā)性能進行較好的權(quán)衡，提高了算法綜合性能。通過仿真實驗證實本文算法較傳統(tǒng)ABC算法在無人機航跡規(guī)劃效率有較大幅度提升，本文所提算法對于高空無人機作戰(zhàn)航跡規(guī)劃具有較好的借鑒意義。

[參考文獻]

[1] 沈林成,陳璟,王楠.飛行器任務規(guī)劃技術(shù)綜述[J]. 航空學報,2014,35(3):593-606.

[2] LI Bai, GONG Li-gang, YANG Wen-lun. An improved artificial bee colony algorithm based on balance-evolution strategy for unmanned combat aerial vehicle path planning [J]. Scientific World Journal,2014(1):95-104.

[3] 方旭,劉金琨.四旋翼無人機三維航跡規(guī)劃及跟蹤控制[J].控制理論與應用,2015,32(8):1120-1128.

[4] WU Jian, ZHANG Dong-hao, PEI Deng-hong. Autonomous route planning for UAV when threats are uncertain[C]. Proceedings of 2014 IEEE Chinese Guidance, Navigation and Control Conference, Yantai, China, 2014.

[5] ROBERGE V, TARBOUCHI M, LABONTE G. Comparison of parallel genetic algorithm and particle swarm optimization for real time UAV path planning[J]. IEEE Transactions on Industrial Informatics, 2013,9(1):132-141.

[6] CHEN Xia, LIU Dong, TANG Ting. Path planning for UCAV in dynamic and uncertain environment based on focused D* algorithm[C]. 2011 Fourth International Symposium on Computational Intelligence and Design, Hangzhou, China, 2011.

[7] WANG Gai-ge, CHU H, MIRJALILI S. Three dimensional path planning for UCAV using an improved bat algorithm[J]. Aerospace Science and Technology, 2016,49:231-238.

[8] 禹建麗,程思雅,孫增圻,等.一種移動機器人三維路徑規(guī)劃優(yōu)化算法[J].中南大學學報：自然科學版,2009,40(2):471-477.

[9] 徐流沙,吳梅,袁志敏.改進人工蜂群算法的無人機航跡規(guī)劃研究[J].火力與指揮控制,2015,40(1):62-66.

[10] XU Chun-fang, DUAN Hai-bin, LIU Fang. Chaotic artificial bee colony approach to uninhabited combat air vehicle (UCAV) path planning[J]. Aerospace Science and Technology, 2013,14(8):535-541.

[11] 徐向平,魯海燕,程畢蕓.基于動態(tài)評價選擇策略的改進人工蜂群算法[J].計算機應用,2015,35(7):1969-1974.

[12] MIAO Hui, TIAN Yu-chu. Dynamic robot path planning using an enhanced simulated annealing approach[J]. Applied Mathematics and Computation, 2013,222:420-437.

(編輯李秀敏)