曾簫瀟

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

關鍵詞：無人機;三維;布谷鳥搜索算法;差分進化算法

中圖分類號：TP39? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：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

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

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

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

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

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

假設航行的電子地圖是600 m×600 m×100 m，起點（0，200，0），終點（600，550，30），為了簡單起見，各種形狀的樓宇均近似為圓柱體。樓宇的位置分布坐標（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）表示三維坐標系中的坐標，r表示圓柱體的半徑。得到的模擬地圖如圖1所示。

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

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

1.3? ?航路編碼

航路編碼決定算法的可行性與效率，簡便的航路編碼有利于代碼的實現(xiàn)和計算效率，在三維空間中，航路編碼直接采用三維直角坐標編碼。對于城市樓宇數(shù)字地圖而言，對x軸進行n等分得到等長的L1，L2，……，Ln，無人機的航線y值必經(jīng)過L1，L2，……，Ln上的點，現(xiàn)橫坐標已固定，縱坐標在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）

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

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

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

采用該編碼的方法會隨著控制點個數(shù)增多航線更平滑，當然計算難度和時間也相應增加。

1.4? ?航路性能評價

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

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

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

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

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

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

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

2.1? ?基本布谷鳥搜索算法和差分進化算法

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

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

（8）式中x（t）i 表示第i個鳥巢在第t代的值，？茌表示點乘，？墜表示步長，L（λ）為Levy飛行隨機搜索的路徑，并且符合Levy分布L ～ u = t-λ，（1<λ≤3）。將（8）式細化以后得到（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)生的步長，best（t） 是第t代最好解。

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

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

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)控制變異的概率。

交叉操作：新個體Vi，G+1與當前個體Vi，G通過（11）式交叉操作形成個體。

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]之間的隨機數(shù)。

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

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

2.2? ?改進CS算法

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

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

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

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

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

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

3：結束。

3? ?仿真實例與分析

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

實驗一：

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

實驗二：

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

4? ?結? ?論

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

參考文獻

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

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

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

[4]? ? 于濤.基于改進蟻群算法的三維無人機路徑規(guī)劃的研究與實現(xiàn)[D]. 重慶大學，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]? ? 王宏倫，姚鵬，梁宵，等. 基于流水避石原理的無人機三維航路規(guī)劃[J]. 電光與控制，2015，22（10）：1-6.

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

[10]? 魚佳欣，周春來，劉東平. 改進遺傳算法的無人機航路規(guī)劃與仿真[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]? 鄭洪清，鄧舒婷，謝聰. 布谷鳥搜索算法在人群疏散中的應用研究[J]. 數(shù)學的實踐與認識.2018，48（14）：165-170.