改进布谷鸟搜索算法的无人机三维航路规划

曾箫潇

摘   要：针对无人机三维航路规划问题，结合差分进化算法，提出了一种改进布谷鸟搜索算法进行无人机航路规划。对无人机飞行的三维真实环境进行建模，将其分为城市楼宇环境和山峰环境。对不同的地形环境采用不同的编码方式，将航路最短距离和规避威胁作为评价函数。仿真实验表明，改进后的布谷鸟搜索算法能够寻找多条切实可行的三维航路且鲁棒性较好，是一种行之有效的航路规划算法。

关键词：无人机;三维;布谷鸟搜索算法;差分进化算法

中图分类号：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

研究無人机路径规划是无人机飞行和控制的关键技术之一。在确定无人机飞行任务之前，首当其冲的问题是对其进行航路规划，考虑飞行环境和任务需求等约束条件下，为其规划出一条或多条最佳航路。近年来，多种智能方法被提出来处理无人机三维航路规划问题，例如遗传算法[1]、粒子群算法[2]、蚁群算法[3-4]、狼群觅食搜索算法[5]、萤火虫算法[6]、中心力优化算法[7]、流水避石原理[8]及其他一些改进算法等[9]，这些算法在一定程度上解决了无人机的三维航路规划。针对不同的地形模型采用不同的编码方式，提出一种改进布谷鸟搜索算法求解无人机三维航路规划问题。

1   航路规划问题

无人机三维航路规划问题可描述为在一个指定的三维空间中飞行，该空间包括地形威胁、敌情威胁以及无人机自身的约束条件，求解从起点至终点满足某些性能指标的最优运动航路。这些性能指标包括耗油最少且能自动规避地形威胁和敌情威胁，使得规划出来的航路尽可能短和安全。

在规划航路时，需要建立合适的数字地形信息，建立两种数字地图，一种是建立城市楼宇数字地图，另一种建立山峰数字地图。

1.1   城市楼宇数字地图

假设航行的电子地图是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   山峰数字地图

假设无人机需要执行低空飞行任务，采用Matlab自带的peaks函数模拟山峰地形，航行的电子地图是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   航路编码

航路编码决定算法的可行性与效率，简便的航路编码有利于代码的实现和计算效率，在三维空间中，航路编码直接采用三维直角坐标编码。对于城市楼宇数字地图而言，对x轴进行n等分得到等长的L1，L2，……，Ln，无人机的航线y值必经过L1，L2，……，Ln上的点，现横坐标已固定，纵坐标在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）

对于山峰数字地图将其进行水平投影，同样对x轴进行n等分得到等长的L1，L2，……，Ln，无人机的航线y值必经过L1，L2，……，Ln上的点，现横坐标已固定，纵坐标在0到600之间变化，于是解编码可表示为（3）式，航路的编码表示为（4）式。

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

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

采用该编码的方法会随着控制点个数增多航线更平滑，当然计算难度和时间也相应增加。

1.4   航路性能评价

在规划航路时，要计算每条航路的性能指标，它主要包括耗油代价和威胁代价，耗油代价与路径成正比，航路的目标就是使得总代价最小，采用公式（5）式来评价航路性能[10]：

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

式中的J为航路总指标，n为航路点的数目，wti为第i段航路的耗油代价，它与航程Li成正比;k1 ，k2 为权重系数，可以根据无人机的要求做出倾向性选择;wfi为第i段航路的威胁代价，每一个航路点的威胁代价表达式为：

wfi = ρ/di min     （6）

其中ρ表示规避威胁的系数，ρ越大，无人机越安全。di min表示航路点离所有威胁的最小距离，若飞机进入禁飞区，wfi则取为无穷大。将（6）代入（5）式后得到的目标函数：

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

2   算法实现

2.1   基本布谷鸟搜索算法和差分进化算法

2009年，英国剑桥大学学者 YANG Xin-she和DEB Suash对布谷鸟的寄生育雏行为进行模拟，提出了一种新兴的启发式搜索算法，即Cuckoo Search Algorithm（CS）[11]。该算法通过Levy飞行生成随机数和一定概率的弃巢来更新种群，而不是简单的随机游走，研究表明该算法较其他智能算法更为有效。由于这种算法只有一个迭代表达式，代码编写简单、高效且易于实现，近年来在各个领域得到了广泛应用[12]。布谷鸟寻窝产卵的迭代公式如下：

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飞行产生的步长，best（t） 是第t代最好解。

差分进化算法是1995年Storn和Price首次提出，主要用于求解一些实数优化问题。由于其结构简单，收敛速度快等优点得到广泛应用。该算法与遗传算法非常类似，整个进化过程包括变异操作、交叉操作和选择操作。

变异操作：在每一次迭代过程中其变异过程是通过在种群中选择3个不同的个体，通过（9）式产生新的个体

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

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

NP为种群数目，F控制变异的概率。

交叉操作：新个体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]之间的随机数。

选择操作：经过变异和交叉生成的个体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]范围内初始化鸟巢nest，计算出fitness，[ fmin，k] = min（fitness），bestnest=nest（k，：）。

2：在终止条件满足以前进行如下循环：

2.1：根据式（8）更新位置得到new_nest，更新位置后需要进行越界处理，以防new_nesti各维上的值超出[Xmin，Xmax]范围，对每一个new_nesti计算适应度值fitness′，若fitness′ fitness，则用new_nesti替换nesti，再计算[fnew，k]=min（fitness），best=nest（k，：）。

2.2根据式（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 、内存为4G的PC上，以Matlab编写代码。参数设置为：种群规模30，总迭代次数为2000;权重系数k1 = 0.4，k2 = 0.6，弃巢率Pa = 0.25，變异率F = 0.6，交叉率CR = 0.8，规避系数ρ = 30。

实验一：

假设无人机的飞行区域如图1所示，利用该算法搜索到的三维航路如图3所示。由图3可知求解的三维航路能自动规避建筑物且有多条可行、较光滑的航路。

实验二：

使用（x，y，z） = peaks（25）函数取z的绝对值得到图2的山峰数字地图。相当于给x轴和y轴进行24等分，为了实现地面跟随，将山峰数字地图进行水平投影，使用式（4）的航路编码方式求得可行的航路，由于采用的是浮点编码，求出的航路需要进一步处理，首先计算航路点离哪一个网格线最近即得到y轴值即行row，然后再根据row，column（即x轴横坐标的刻度）值求出z（row，column）矩阵对应的高度值，然后在矩阵z高度值的基础上实现整体抬高h，即可得到的三维航路如图4、图5所示（分别从不同的角度得到的航路示意图）。从图4和图5可知该算法能自动规避地形威胁和敌情威胁，并且尽可能利用地形环境作掩护进行低空飞行和地面跟随。通过两个实验表明本文的方法能够完成真实地形环境下无人机航路规划任务。

4   结   论

研究了无人机在三维环境中的航路规划问题。通过对无人机在真实飞行环境中所受的威胁进行城市楼宇和山峰地形数字建模，把数字地图网格化，将三维问题转化为二维问题和一维问题。考虑单个算法求解时的局限性，结合差分进化算法的优势，提出一种改进布谷鸟搜索算法并应用于无人机三维航路规划，由仿真实验可知该航路规划方法的有效性和可行性。

参考文献

[1]    李楠，刘明，邓人博，等. 基于改进遗传算法的无人机三维航路规划[J]. 计算机仿真，2017，34（12）：22- 25.

[2]    周鑫，李新洪，王谦. 基于威胁建模的PSO在UAV3维航路规划中的应用[J]. 兵工自动化，2017，36（4）：73 - 80.

[3]    陈谋，肖健，姜长生. 基于改进蚁群算法的无人机三维航路规划[J]. 吉林大学学报（工学版），2008，38（4）：992 - 995.

[4]    于涛.基于改进蚁群算法的三维无人机路径规划的研究与实现[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]    王宏伦，姚鹏，梁宵，等. 基于流水避石原理的无人机三维航路规划[J]. 电光与控制，2015，22（10）：1-6.

[9]    席庆彪，李康，刘慧霞. 振动遗传算法在无人机三维航路规划的算法研究[J]. 火力与指挥控制.2014，39（10）：1708-1713.

[10]  鱼佳欣，周春来，刘东平. 改进遗传算法的无人机航路规划与仿真[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]. 数学的实践与认识.2018，48（14）：165-170.