改進(jìn)布谷鳥(niǎo)搜索算法的無(wú)人機(jī)三維航路規(guī)劃

曾簫瀟

摘? ?要：針對(duì)無(wú)人機(jī)三維航路規(guī)劃問(wèn)題，結(jié)合差分進(jìn)化算法，提出了一種改進(jìn)布谷鳥(niǎo)搜索算法進(jìn)行無(wú)人機(jī)航路規(guī)劃。對(duì)無(wú)人機(jī)飛行的三維真實(shí)環(huán)境進(jìn)行建模，將其分為城市樓宇環(huán)境和山峰環(huán)境。對(duì)不同的地形環(huán)境采用不同的編碼方式，將航路最短距離和規(guī)避威脅作為評(píng)價(jià)函數(shù)。仿真實(shí)驗(yàn)表明，改進(jìn)后的布谷鳥(niǎo)搜索算法能夠?qū)ふ叶鄺l切實(shí)可行的三維航路且魯棒性較好，是一種行之有效的航路規(guī)劃算法。

關(guān)鍵詞：無(wú)人機(jī);三維;布谷鳥(niǎo)搜索算法;差分進(jìn)化算法

中圖分類(lèi)號(hào)：TP39? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Three Dimensional Path Planning for Unmanned Aerial

Vehicles Using Improved Cuckoo Search Algorithm

ZENG Xiao-xiao

（Guangxi Science﹠Technology Normal University，Laibin，Guangxi 546199，China）

Abstract：Aiming at the problems of three dimensional path planning for unmanned aerial vehicles （UAV），combining the differential evolution algorithm，this paper proposes a path planning method of UAV using improved cuckoo search algorithm. Establishing model for threat in UAV flight real environment，it is divided into urban building environment and mountain environment. Different coding methods are adopted for different terrain environments. the objective function was shortest distance and avoiding the threaten. Two simulation result shows that the improved cuckoo search algorithm can find many feasible three-dimensional route and be of stability. So it is an effective and feasible path planning algorithm.

Key words：UAV;three dimensional;cuckoo search algorithm;differential evolution algorithm

研究無(wú)人機(jī)路徑規(guī)劃是無(wú)人機(jī)飛行和控制的關(guān)鍵技術(shù)之一。在確定無(wú)人機(jī)飛行任務(wù)之前，首當(dāng)其沖的問(wèn)題是對(duì)其進(jìn)行航路規(guī)劃，考慮飛行環(huán)境和任務(wù)需求等約束條件下，為其規(guī)劃出一條或多條最佳航路。近年來(lái)，多種智能方法被提出來(lái)處理無(wú)人機(jī)三維航路規(guī)劃問(wèn)題，例如遺傳算法[1]、粒子群算法[2]、蟻群算法[3-4]、狼群覓食搜索算法[5]、螢火蟲(chóng)算法[6]、中心力優(yōu)化算法[7]、流水避石原理[8]及其他一些改進(jìn)算法等[9]，這些算法在一定程度上解決了無(wú)人機(jī)的三維航路規(guī)劃。針對(duì)不同的地形模型采用不同的編碼方式，提出一種改進(jìn)布谷鳥(niǎo)搜索算法求解無(wú)人機(jī)三維航路規(guī)劃問(wèn)題。

1? ?航路規(guī)劃問(wèn)題

無(wú)人機(jī)三維航路規(guī)劃問(wèn)題可描述為在一個(gè)指定的三維空間中飛行，該空間包括地形威脅、敵情威脅以及無(wú)人機(jī)自身的約束條件，求解從起點(diǎn)至終點(diǎn)滿(mǎn)足某些性能指標(biāo)的最優(yōu)運(yùn)動(dòng)航路。這些性能指標(biāo)包括耗油最少且能自動(dòng)規(guī)避地形威脅和敵情威脅，使得規(guī)劃出來(lái)的航路盡可能短和安全。

在規(guī)劃航路時(shí)，需要建立合適的數(shù)字地形信息，建立兩種數(shù)字地圖，一種是建立城市樓宇數(shù)字地圖，另一種建立山峰數(shù)字地圖。

1.1? ?城市樓宇數(shù)字地圖

假設(shè)航行的電子地圖是600 m×600 m×100 m，起點(diǎn)（0，200，0），終點(diǎn)（600，550，30），為了簡(jiǎn)單起見(jiàn)，各種形狀的樓宇均近似為圓柱體。樓宇的位置分布坐標(biāo)（x，y，z，r） 如下所示：（75，75，20，71），（230，380，60，85），（70，200，40，57），（375，305，40， 71），（400，200，30，40），（550，400，50，30），（500， 500，40，40），（100，450，50，50）。其中（x，y，z）表示三維坐標(biāo)系中的坐標(biāo)，r表示圓柱體的半徑。得到的模擬地圖如圖1所示。

1.2? ?山峰數(shù)字地圖

假設(shè)無(wú)人機(jī)需要執(zhí)行低空飛行任務(wù)，采用Matlab自帶的peaks函數(shù)模擬山峰地形，航行的電子地圖是600 m×600 m×1000 m，無(wú)人機(jī)的起點(diǎn)坐標(biāo)為（0，0，0），終點(diǎn)坐標(biāo)為（600，600，40），在飛行過(guò)程中遇到的威脅坐標(biāo)（x，y，z，r） = （500，150，200， 50）。其中（x，y，z）表示三維坐標(biāo)系中的坐標(biāo)，r表示威脅的半徑。得到的模擬地圖如圖2所示。

1.3? ?航路編碼

航路編碼決定算法的可行性與效率，簡(jiǎn)便的航路編碼有利于代碼的實(shí)現(xiàn)和計(jì)算效率，在三維空間中，航路編碼直接采用三維直角坐標(biāo)編碼。對(duì)于城市樓宇數(shù)字地圖而言，對(duì)x軸進(jìn)行n等分得到等長(zhǎng)的L1，L2，……，Ln，無(wú)人機(jī)的航線(xiàn)y值必經(jīng)過(guò)L1，L2，……，Ln上的點(diǎn)，現(xiàn)橫坐標(biāo)已固定，縱坐標(biāo)在200到550之間變化，z軸的取值在20到30之間變化。于是解編碼表示為（1）式，航路的編碼表示為（2）式，

x = y1，y2，…，ynz1，z2，…，zn? ? ?（1）

path = 200，y1，y2，…，yn，55020，z1，z2，…，zn，30? ? ? ?（2）

對(duì)于山峰數(shù)字地圖將其進(jìn)行水平投影，同樣對(duì)x軸進(jìn)行n等分得到等長(zhǎng)的L1，L2，……，Ln，無(wú)人機(jī)的航線(xiàn)y值必經(jīng)過(guò)L1，L2，……，Ln上的點(diǎn)，現(xiàn)橫坐標(biāo)已固定，縱坐標(biāo)在0到600之間變化，于是解編碼可表示為（3）式，航路的編碼表示為（4）式。

x = {y1，y2，…，yn}? ? ? （3）

path = {0，y1，y2，…，yn，600}? ? ?（4）

采用該編碼的方法會(huì)隨著控制點(diǎn)個(gè)數(shù)增多航線(xiàn)更平滑，當(dāng)然計(jì)算難度和時(shí)間也相應(yīng)增加。

1.4? ?航路性能評(píng)價(jià)

在規(guī)劃航路時(shí)，要計(jì)算每條航路的性能指標(biāo)，它主要包括耗油代價(jià)和威脅代價(jià)，耗油代價(jià)與路徑成正比，航路的目標(biāo)就是使得總代價(jià)最小，采用公式（5）式來(lái)評(píng)價(jià)航路性能[10]：

min J = ■[k1 wti + k2 wfi ]? ? ? （5）

式中的J為航路總指標(biāo)，n為航路點(diǎn)的數(shù)目，wti為第i段航路的耗油代價(jià)，它與航程Li成正比;k1 ，k2 為權(quán)重系數(shù)，可以根據(jù)無(wú)人機(jī)的要求做出傾向性選擇;wfi為第i段航路的威脅代價(jià)，每一個(gè)航路點(diǎn)的威脅代價(jià)表達(dá)式為：

wfi = ρ/di min? ? ?（6）

其中ρ表示規(guī)避威脅的系數(shù)，ρ越大，無(wú)人機(jī)越安全。di min表示航路點(diǎn)離所有威脅的最小距離，若飛機(jī)進(jìn)入禁飛區(qū)，wfi則取為無(wú)窮大。將（6）代入（5）式后得到的目標(biāo)函數(shù)：

min J = ■[k1 Li + k2? ρ/di min]? ? ? （7）

2? ?算法實(shí)現(xiàn)

2.1? ?基本布谷鳥(niǎo)搜索算法和差分進(jìn)化算法

2009年，英國(guó)劍橋大學(xué)學(xué)者 YANG Xin-she和DEB Suash對(duì)布谷鳥(niǎo)的寄生育雛行為進(jìn)行模擬，提出了一種新興的啟發(fā)式搜索算法，即Cuckoo Search Algorithm（CS）[11]。該算法通過(guò)Levy飛行生成隨機(jī)數(shù)和一定概率的棄巢來(lái)更新種群，而不是簡(jiǎn)單的隨機(jī)游走，研究表明該算法較其他智能算法更為有效。由于這種算法只有一個(gè)迭代表達(dá)式，代碼編寫(xiě)簡(jiǎn)單、高效且易于實(shí)現(xiàn)，近年來(lái)在各個(gè)領(lǐng)域得到了廣泛應(yīng)用[12]。布谷鳥(niǎo)尋窩產(chǎn)卵的迭代公式如下：

x（t+1）i? ? ? ?= x（t）i? + ？墜 ？茌 L（λ），i = 1，2，…，n? ? （8）

（8）式中x（t）i 表示第i個(gè)鳥(niǎo)巢在第t代的值，？茌表示點(diǎn)乘，？墜表示步長(zhǎng)，L（λ）為L(zhǎng)evy飛行隨機(jī)搜索的路徑，并且符合Levy分布L ～ u = t-λ，（1<λ≤3）。將（8）式細(xì)化以后得到（9）式：

x（t+1）i? ? ? ?= x（t）i? + ？墜.*step（t） .*（x ti - best（t） ）? ? （9）

i = 1，2，…，n，式中step（t） 表示第t代由Levy飛行產(chǎn)生的步長(zhǎng)，best（t） 是第t代最好解。

差分進(jìn)化算法是1995年Storn和Price首次提出，主要用于求解一些實(shí)數(shù)優(yōu)化問(wèn)題。由于其結(jié)構(gòu)簡(jiǎn)單，收斂速度快等優(yōu)點(diǎn)得到廣泛應(yīng)用。該算法與遺傳算法非常類(lèi)似，整個(gè)進(jìn)化過(guò)程包括變異操作、交叉操作和選擇操作。

變異操作：在每一次迭代過(guò)程中其變異過(guò)程是通過(guò)在種群中選擇3個(gè)不同的個(gè)體，通過(guò)（9）式產(chǎn)生新的個(gè)體

Vi，G+1 = Xr3，G + F × （Xr1，G - Xr2，G）? ? ? ?（10）

其中，i = 1，…，NP;r1，r2，r3∈（1，…，NP），r1≠r2≠r3≠i，F(xiàn)∈[0，1]）。

NP為種群數(shù)目，F(xiàn)控制變異的概率。

交叉操作：新個(gè)體Vi，G+1與當(dāng)前個(gè)體Vi，G通過(guò)（11）式交叉操作形成個(gè)體。

Vj，i，G+1 = Vj，i，G+1 if randj ≤ CR or j = kxj，i，G? ? ? otherwise? ? （11）

j = 1，2，…，n，k = 1，2，…，NP，CR∈[0，1]之間的交叉率，rand為[0，1]之間的隨機(jī)數(shù)。

選擇操作：經(jīng)過(guò)變異和交叉生成的個(gè)體Ui，G和目標(biāo)個(gè)體Xi，G通過(guò)（11）式更新種群。

Xi，G+1 = Ui，G+1 if f （Ui，G+1 ≤ f （Xi，G））Xi，G? ? ? otherwise? ? （12）

2.2? ?改進(jìn)CS算法

基本的布谷鳥(niǎo)搜索算法完全由Levy飛行和一定概率的棄巢來(lái)更新種群，種群中的個(gè)體并沒(méi)有進(jìn)行信息交互，針對(duì)布谷鳥(niǎo)搜索算法的不足，結(jié)合差分進(jìn)化算法的變異、交叉和選擇操作，提出如下改進(jìn)的布谷鳥(niǎo)搜索算法，即Improved Cuckoo Search（ICS）算法，整個(gè)算法的流程如下：

1：在[Xmin，Xmax]范圍內(nèi)初始化鳥(niǎo)巢nest，計(jì)算出fitness，[ fmin，k] = min（fitness），bestnest=nest（k，：）。

2：在終止條件滿(mǎn)足以前進(jìn)行如下循環(huán)：

2.1：根據(jù)式（8）更新位置得到new_nest，更新位置后需要進(jìn)行越界處理，以防new_nesti各維上的值超出[Xmin，Xmax]范圍，對(duì)每一個(gè)new_nesti計(jì)算適應(yīng)度值fitness′，若fitness′ fitness，則用new_nesti替換nesti，再計(jì)算[fnew，k]=min（fitness），best=nest（k，：）。

2.2根據(jù)式（9-11）對(duì)任意一個(gè)nesti進(jìn)行變異、交叉和選擇操作得到new_nesti，并做越界處理，然后對(duì)new_nesti計(jì)算適應(yīng)度值fitness′，若fitness′ fitness，則用new_nesti替換nesti，再計(jì)算[fnew，k]=min（fitness），best=nest（k，：）。

2.3：若fnew≤fmin，則fmin替換fnew，best替換bestnest。

3：結(jié)束。

3? ?仿真實(shí)例與分析

為了驗(yàn)證所提出算法的性能，進(jìn)行2個(gè)實(shí)驗(yàn)均運(yùn)行在處理器為Celeron（R）雙核CPU T3200，2.90GHZ 、內(nèi)存為4G的PC上，以Matlab編寫(xiě)代碼。參數(shù)設(shè)置為：種群規(guī)模30，總迭代次數(shù)為2000;權(quán)重系數(shù)k1 = 0.4，k2 = 0.6，棄巢率Pa = 0.25，變異率F = 0.6，交叉率CR = 0.8，規(guī)避系數(shù)ρ = 30。

實(shí)驗(yàn)一：

假設(shè)無(wú)人機(jī)的飛行區(qū)域如圖1所示，利用該算法搜索到的三維航路如圖3所示。由圖3可知求解的三維航路能自動(dòng)規(guī)避建筑物且有多條可行、較光滑的航路。

實(shí)驗(yàn)二：

使用（x，y，z） = peaks（25）函數(shù)取z的絕對(duì)值得到圖2的山峰數(shù)字地圖。相當(dāng)于給x軸和y軸進(jìn)行24等分，為了實(shí)現(xiàn)地面跟隨，將山峰數(shù)字地圖進(jìn)行水平投影，使用式（4）的航路編碼方式求得可行的航路，由于采用的是浮點(diǎn)編碼，求出的航路需要進(jìn)一步處理，首先計(jì)算航路點(diǎn)離哪一個(gè)網(wǎng)格線(xiàn)最近即得到y(tǒng)軸值即行row，然后再根據(jù)row，column（即x軸橫坐標(biāo)的刻度）值求出z（row，column）矩陣對(duì)應(yīng)的高度值，然后在矩陣z高度值的基礎(chǔ)上實(shí)現(xiàn)整體抬高h(yuǎn)，即可得到的三維航路如圖4、圖5所示（分別從不同的角度得到的航路示意圖）。從圖4和圖5可知該算法能自動(dòng)規(guī)避地形威脅和敵情威脅，并且盡可能利用地形環(huán)境作掩護(hù)進(jìn)行低空飛行和地面跟隨。通過(guò)兩個(gè)實(shí)驗(yàn)表明本文的方法能夠完成真實(shí)地形環(huán)境下無(wú)人機(jī)航路規(guī)劃任務(wù)。

4? ?結(jié)? ?論

研究了無(wú)人機(jī)在三維環(huán)境中的航路規(guī)劃問(wèn)題。通過(guò)對(duì)無(wú)人機(jī)在真實(shí)飛行環(huán)境中所受的威脅進(jìn)行城市樓宇和山峰地形數(shù)字建模，把數(shù)字地圖網(wǎng)格化，將三維問(wèn)題轉(zhuǎn)化為二維問(wèn)題和一維問(wèn)題。考慮單個(gè)算法求解時(shí)的局限性，結(jié)合差分進(jìn)化算法的優(yōu)勢(shì)，提出一種改進(jìn)布谷鳥(niǎo)搜索算法并應(yīng)用于無(wú)人機(jī)三維航路規(guī)劃，由仿真實(shí)驗(yàn)可知該航路規(guī)劃方法的有效性和可行性。

參考文獻(xiàn)

[1]? ? 李楠，劉明，鄧人博，等. 基于改進(jìn)遺傳算法的無(wú)人機(jī)三維航路規(guī)劃[J]. 計(jì)算機(jī)仿真，2017，34（12）：22- 25.

[2]? ? 周鑫，李新洪，王謙. 基于威脅建模的PSO在UAV3維航路規(guī)劃中的應(yīng)用[J]. 兵工自動(dòng)化，2017，36（4）：73 - 80.

[3]? ? 陳謀，肖健，姜長(zhǎng)生. 基于改進(jìn)蟻群算法的無(wú)人機(jī)三維航路規(guī)劃[J]. 吉林大學(xué)學(xué)報(bào)（工學(xué)版），2008，38（4）：992 - 995.

[4]? ? 于濤.基于改進(jìn)蟻群算法的三維無(wú)人機(jī)路徑規(guī)劃的研究與實(shí)現(xiàn)[D]. 重慶大學(xué)，2017.

[5]? ? CHEN Yong-bo，MEI Yue-song，YU Jian-qiao.Three dimensional unmanned aerial vehicle path planning using modified wolf pack search algorithm[J]. Neuro Computing 2017，266 （6）：445-457.

[6]? ? UTKARSH G，SHUBHAM V，ANSHUL J.Three dimensional path planning for UAVs in dynamic environment using glow-worm swarm optimization[J]. Procedia Computer Science 2018，133（11）：230-239.

[7]? ? CHEN Yong-bo，YU Jian-qiao，MEI Song-yue. modified central force optimization （MCFO） algorithm for 3D UAV path planning[J].Neuro Computing 2016，171 （5） ：878-888.

[8]? ? 王宏倫，姚鵬，梁宵，等. 基于流水避石原理的無(wú)人機(jī)三維航路規(guī)劃[J]. 電光與控制，2015，22（10）：1-6.

[9]? ? 席慶彪，李康，劉慧霞. 振動(dòng)遺傳算法在無(wú)人機(jī)三維航路規(guī)劃的算法研究[J]. 火力與指揮控制.2014，39（10）：1708-1713.

[10]? 魚(yú)佳欣，周春來(lái)，劉東平. 改進(jìn)遺傳算法的無(wú)人機(jī)航路規(guī)劃與仿真[J]. 計(jì)算機(jī)仿真，2013，30（12）：17-20.

[11]? YANG X S，DEB S. Cuckoo search via Levy flights [C] // Proceedings of World Congress on Nature & Biologically Inspired Computing，India：IEEE Publications，2009，5（9）：210-214.

[12]? 鄭洪清，鄧舒婷，謝聰. 布谷鳥(niǎo)搜索算法在人群疏散中的應(yīng)用研究[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí).2018，48（14）：165-170.