基于改進(jìn)人工蜂群算法的無(wú)人機(jī)三維航跡規(guī)劃

王慶海，姚冬艷，劉廣瑞

(鄭州大學(xué) 機(jī)械工程學(xué)院，鄭州　450001)

0　引言

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

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

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

1.1　環(huán)境建模

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

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

1.2　約束條件

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

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

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

(1)

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

(2)

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

1.3　目標(biāo)函數(shù)

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

(3)

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

(4)

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

(5)

其中，Nt為總的威脅個(gè)數(shù)，li為第i段航跡的長(zhǎng)度，無(wú)人機(jī)航跡中點(diǎn)x受第j個(gè)威脅的影響代價(jià)如式(6)。

(6)

其中，Kj為第j個(gè)威脅對(duì)無(wú)人機(jī)威脅強(qiáng)度等級(jí)，Rj為第j個(gè)威脅的半徑，dxj為第x個(gè)點(diǎn)到第j個(gè)威脅中心的距離，a為大于1的系數(shù)。

圖2　航跡段威脅計(jì)算

2　人工蜂群算法的改進(jìn)

2.1　初始化蜜源

通過(guò)生成一個(gè)2D×NP矩陣產(chǎn)生NP個(gè)蜜源(每一個(gè)行向量代表一條航跡)，傳統(tǒng)ABC算法未能考慮航跡點(diǎn)之間的關(guān)聯(lián)性，優(yōu)化效果較差，為提高初始化蜜源的可行性，提高航跡規(guī)劃算法收斂速度，改進(jìn)人工蜂群算法中航跡各個(gè)跡點(diǎn)的極坐標(biāo)值為在前一個(gè)跡點(diǎn)基礎(chǔ)上按照搜索步長(zhǎng)在可行區(qū)間內(nèi)隨機(jī)選取，其中，第i個(gè)蜜源位置通過(guò)式(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的隨機(jī)數(shù)，step1和step2分別為半徑搜索步長(zhǎng)和角度搜索步長(zhǎng)。

2.2　選擇機(jī)制

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

動(dòng)態(tài)評(píng)價(jià)指標(biāo)為id1(i)和id2(i)。蜜源i被優(yōu)化時(shí)id2(i)按式(10)計(jì)算，id1(i)為0；蜜源i未被優(yōu)化時(shí)id1(i)按式(9)計(jì)算，id2(i)為0。動(dòng)態(tài)評(píng)價(jià)函數(shù)為式(11)。

(9)

(10)

(11)

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

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

(12)

2.3　鄰域搜索

(13)

2.4　Metropolis準(zhǔn)則

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

(14)

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

2.5　程序流程設(shè)計(jì)

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

圖3　IABC算法流程圖

3　算例分析

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

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

表1　威脅信息

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

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

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

圖6　目標(biāo)函數(shù)均值收斂曲線對(duì)比圖

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

4　結(jié)論

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

[參考文獻(xiàn)]

[1] 沈林成,陳璟,王楠.飛行器任務(wù)規(guī)劃技術(shù)綜述[J]. 航空學(xué)報(bào),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] 方旭,劉金琨.四旋翼無(wú)人機(jī)三維航跡規(guī)劃及跟蹤控制[J].控制理論與應(yīng)用,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] 禹建麗,程思雅,孫增圻,等.一種移動(dòng)機(jī)器人三維路徑規(guī)劃優(yōu)化算法[J].中南大學(xué)學(xué)報(bào)：自然科學(xué)版,2009,40(2):471-477.

[9] 徐流沙,吳梅,袁志敏.改進(jìn)人工蜂群算法的無(wú)人機(jī)航跡規(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] 徐向平,魯海燕,程畢蕓.基于動(dòng)態(tài)評(píng)價(jià)選擇策略的改進(jìn)人工蜂群算法[J].計(jì)算機(jī)應(yīng)用,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.

(編輯李秀敏)