基于遗传算法的无人机三维航迹规划研究

何光勤

摘要：近年来，随着无人机在各个领域的广泛应用，无人机的航迹规划问题成为研究的热点，本文通过分析地形条件以及无人机自身性能对航迹规划的影响，研究无人机三维规划问题。在数字地图预处理的基础上，对基准地形以及障碍区域进行建模，建立等效的环境数字地图，并采用样条插值法对地形进行平滑处理，降低搜索空间。在此基础上建立带有惩罚函数的评价目标，使用遗传算法完成了无人机的三维航迹规划。实验结果表明：遗传算法不仅能够完成无人机的规划任务，生成短而平滑的路径，而且能够获得很好的收敛效果，为各种实际任务提供技术支持。

Abstract： In recent years， with the wide application of Unmanned Aerial Vehicles（UAVs）， flight path planning for UAVs has become a hot research topic. This paper studies the three-dimensional planning for UAVs by considering the terrain conditions and the influence of UAV's performance on the planning. Based on the preprocessing of the digital map， the reference terrain and the obstacle area are modeled， an equivalent environmental digital map is built， and smoothed by the spline interpolation method， which reduces the search space. Moreover， the evaluation target with a penalty function is set and the genetic algorithm was applied to complete the 3D flight path planning for UAVs. The experimental results show that the genetic algorithm can not only complete the planning task for drones， generate a short and smooth path， but also obtain good convergence and provide technical support for various practical missions.

關键词： 无人机;环境建模;路径规划;遗传算法

0  引言

无人机航迹规划是无人机应用的关键技术之一，它的主要功能是依靠无人机系统自身性能，在脱离人工干预的情况下，根据特定的环境条件，自动搜寻出一条从起始点到目标点的最优路径，使得无人机能够安全高效的完成特定任务[1]。无人机路径规划是NP难问题，如何对其进行更好的规划极具挑战。为此，各国学者针对此问题做了大量的研究工作。在二维路径规划方面，文献[2-3]应用改进的A*算法对搜索空间进行求解，有效的解决了搜索空间大及搜索复杂度高的问题;文献[4]对蚁群算法进行研究，提出了适用于无人机航路规划的优化算法，兼顾最小探测概率以及最短路，生成一条可接受的无人机飞行路径;文献[5]对传统的快速扩展随机树（RRT）算法进行改进，采用改进算法（RRT*算法）对无人机路径进行规划，获得了更好的航迹代价值;文献[6]在传统人工势场法的基础上选取适当的增益系数，解决了目标不可达问题，最终优化出圆滑的最优路径。文献[7]提出了一种基于Voronoi图的航路规划方法，并结合蚁群算法对无人机航路进行规划，提升了无人机在多威胁情况下的航路规划效率。尽管在二维路径规划方面已经有了较为成熟的研究成果，但是上述方法忽略了无人机的三维机动能力以及三维搜索空间的复杂度，难以满足实际需求，故许多学者开始对无人机三维路径规划进行研究。文献[8]引入虚拟地形以消除大量搜索空间，将三维空间降至二维，随后采用改进的A*算法生成无人机航迹;文献[9]通过对搜索区域进行网格离散化提出了一种新的无人机三维路径规划方法，此法可以在满足多目标约束的条件下生成较为理想的无人机路径;文献[10]提出基于蚁群优化算法的无人机路径规划算法获得了无人机三维路径;文献[11]应用粒子群算法和遗传算法变异算子的思想来改进原始的中心力优化（CFO）算法，提出了一种采用改进的中心力优化（MCFO）对无人机进行路径规划，生成了有效的无人机路径。尽管三维路径规划已经有了长足的进展，但是相较于二维路径规划，三维路径规划考虑了高度限制及地形约束，搜索空间激增，问题的复杂度也呈指数增长。在求解过程中容易遇到陷入局部最优解以及收敛速度慢，甚至无法收敛的问题。

因此，针对无人机三维路径规划问题，本文提出了一种适合无人机三维实地飞行的路径规划方法。该方法在满足无人机自身性能约束条件下，对数字地图进行预处理，完成网格划分，并在此基础上，使用遗传算法对无人机三维航迹进行规划，最终得到无人机飞行的最优三维路径。

1  数字地图的预处理

对数字地图进行预处理不仅可以获得虚拟的客观环境，为无人机的路径规划提供实际的仿真模拟条件，而且可以验证规划算法的实用性。地形数据的预处理主要包括数字地图的获取、地形信息截取、高程信息提取以及生成经纬高坐标序列4个阶段。

根据任务地区的经纬度信息在google earth上进行定位，对该区域范围进行锁定，进行地形数据采集，随后利用google earth 高程信息商业软件获取所需高程信息，并最终导出经度、纬度以及高度的坐标信息，以文本形式储存。

2  无人机航迹规划建模

2.1 建立环境模型

2.1.1 基准地形建模

无人机三维航迹规划问题与任务区域的真实地理环境息息相关。针对任务区域的地形环境进行建模时不仅要考虑明显的山体特征，还要对地形起伏的基准地形进行考量。由于地形信息的准确度与精细度是影响航路规划质量的关键，故本文采取文献[12]中的地形模拟函数对真实地形进行建模：

2.1.2  障碍区域建模

针对障碍区域建模，本研究对较高的自然山体采用山峰模型[13]，具体的数学表达式如下：

其中， z2（x，y）表示每个投影到平面的点坐标（x，y）的高程值，hi表示第i座山的高度，（xi，yi）是第i座山峰的中心坐标，xsi和ysi分别是山峰沿x轴和y轴上的坡度，值越大坡度越大。

由于实际地形起伏较为复杂，考虑到飞机性能以及计算方便，本研究采用三次样条插值法对实际地形进行平滑处理。具体处理方式如下：

假定x0，xn是两个端点，要在两点之间插入n-1個点，需构造形如式（3）的样条函数s（x），且s（x）满足插值条件式（4）和式（5）。

2.1.3 等效数字地图

针对任务区三维空间，本研究利用上述方法分别对基准地形以及障碍区域进行建模，并将其转换为计算机可以处理的数据类型，然后将地形高程信息与障碍区域高程信息进行融合，建立等效的环境数字地图，如图1所示。具体的融合模型如下：

2.2 约束条件

2.2.1 航迹长度

无人机航迹由一系列导航点{xi，yi，zi | i=1，2，…，n}组成，其中（xi，yi，zi）表示第i个导航点的三维坐标取值，（xi，yi，zi）表示起点，（xn，yn，zn）表示终点，基于此，无人机路径长度值为：当然无人机路径长度L越短越好。

2.2.2 最低飞行高度

最低飞行高度是指垂直方向上无人机距离障碍物的最小距离。在低空空域进行飞行时，飞行高度h必须满足h？叟hmin才能保证无人机不会碰撞，其中hmin为最低飞行高度。

2.2.3 最大偏航角

无人机的最大偏航角是指无人机在航路飞行过程中允许的最大转弯角，其值的大小取决于无人机自身性能以及物理条件。假设相邻节点坐标分别为（x1，y1，z1）和（x2，y2，z2），最大偏航角为αmax，则满足：

2.2.4 最大俯仰角

无人机的最大俯仰角是指无人机在爬升以及下降过程中机身纵轴能够与水平方向达到的最大角度，其值完全取决于无人机纵向性能约束。假设相邻节点坐标分别为 （x1，y1，z1）和（x2，y2，z2），最大俯仰角为βmax，则满足：

2.3 航迹评价函数

无人机的三维路径规划既要保证飞行任务的顺利实施，还要满足无人机的机动性能限制。综合考虑无人机的航路长度、最低飞行高度、最大偏航角以及最大俯仰角等的限制，生成一条最短航路。

同时，在无人机路径规划过程中，需要考虑避障问题，本研究采用惩罚函数法对不满足避障要求的导航点进行惩罚，评价函数F定义如下：

其中，pf为惩罚系数，取值为正数，I（xi，yi，zi）为示性函数，当点（xn，yn，zn）满足避障要求时，I（xi，yi，zi）为0;当点（xn，yn，zn）不满足避障要求时，I（xi，yi，zi）为1。

3  遗传算法

遗传算法（Genetic Algorithm，GA）是模仿生物进化机制而演变的现代仿生学方法，它是一种随机全局搜索优化算法。通过种群初始化、染色体的选择、交叉、变异等操作获取问题最优解[14]。具体操作步骤如下：

3.1 染色体编码

在染色体编码中常用二进制和实数编码两种方式，本研究采用实数编码方式对染色体进行编码操作，通过unifrnd命令生成0到1之间的随机数，编码长度与决策变量个数相同。此种编码方式精度高，有利于多维空间的搜索。

3.2 个体适应度

个体适应度函数反映了种群染色体的质量，其值大小直接决定了个体能否进入下一代的概率，因此非常关键。考虑到本文的评价函数是求解无人机的最短路径，故选取评价函数的倒数作为个体适应度函数，二者的关系如下：

3.3 选择

本算法采用轮盘赌与精英保留策略相结合的方法对个体进行选择，根据个体适应度值进行排序，对排在前1/3的个体采取精英保留策略，其它个体采用轮盘赌选择，个体被选中的概率为

其中， N为种群个数，Zi为种群适应度值。此种选择策略既保留了种群最优个体，同时也保证了种群多样性。

3.4 交叉

考虑到编码方式为整数编码，故本算法采用整数交叉法如式（13）对染色体进行交叉操作，产生新的染色体。

3.5 变异

以一定的概率对染色体进行变异操作，增强算法局部搜索能力的同时，保证了种群多样性。本研究选用单点高斯变异的方法[15]对个体进行变异操作，即在满足均值为μ，方差为σ2的正态分布里随机生成一个数来代替原有基因值。具体方法如下：

4  仿真实验

实验中，算法均采用matlab2016a编程实现，运行环境为：win10 专业版、Inter（R）Xeon（R） W-2133 CPU @ 3.6GHz 处理器，64G内存，64位操作系统。

相关参数的设置如下：起始坐标为（25，90，64），目标点坐标为（40，30，2），最大偏航角αmax=60°，最大俯仰角βmax=30°、最低飞行高hmin=60m。在遗传算法中，种群数量N=50，最大迭代次数I=300，交叉变异概率分别为Pc=0.7，  Pm=0.3。

Matlab仿真结果如图2-图4所示，图2为三维空间航迹规划图，图3为二维空间航迹规划图，图4为评价函数迭代曲线。

5  总结

针对无人机的三维航迹规划问题，本文通过对数字地图预处理，将地形高程信息与障碍区域高程信息进行融合，根据飞行器的性能指标，给出了地图平滑处理手段，在此基础上设计带有惩罚的代价函数，采用传统遗传算法对三维地形下的无人机航迹进行航迹规划，根据仿真结果得出以下结论：

①对实际地形进行平滑处理，可以极大的减小搜索空间，减小算法复杂度;

②遗传算法具有很好的收敛效果，可以生成短而平滑的航迹，从而高效完成无人机的飞行任务;

③数字地图的预处理需要借助google earth等软件协助完成，因此本文提到的算法仅能满足离线规划任务需求。

本文的研究重点是无人机静态的三维航迹规划问题，在建模时仅将地形障碍以及无人机自身性能作为约束条件，并未考虑实际飞行任务中的气象条件以及通信条件，在后期工作中将结合实际任务区域的气象条件以及通信条件等，对无人机的三维动态航迹规划问题进行研究，以期为无人机的完成飞行任务提供更好的技术支持。

参考文献：

[1]史红玉，刘淑芬.基于Voronoi图的无人机航路改进规划[J].吉林大学学报，2018，56（4）：945-952.

[2]Szczerba R J， Galkowski P， Glicktein I S， et al. Robust algorithm for real-time route planning[J]. IEEE Transactions on Aerospace and Electronic Systems， 2000， 36（3）： 869-878.

[3]马立.基于改进 A～*算法的无人机动态航迹规划[J].现代导航，2018，9（1）：60-64.

[4]白俊强，柳长安.基于蚁群算法的无人机航路规划[J].飞行力学，2005， 23（2）：9-12.

[5] Alejo D ， Cobano J A ， Heredia G ， et al. Efficient Trajectory Planning for WSN Data Collection with Multiple UAVs[J]. Studies in Computational Intelligence， 2015， 604：53-75.

[6]张建英，刘暾.基于人工势场法的移动机器人最优路径规划[J].航空学报：2007，28：183-188.

[7]王壮，刘聪锋，蔡啸.一种基于Voronoi图的航路规划方法[J].船舶电子对抗：2017，40（4）：76-80.

[8]Qi Z ， Shao Z ， Ping Y S ， et al. An Improved Heuristic Algorithm for UAV Path Planning in 3D Environment[C]// International Conference on Intelligent Human-machine Systems & Cybernetics. IEEE， 2010.

[9]Babel L . Three-dimensional Route Planning for Unmanned Aerial Vehicles in a Risk Environment[J]. Journal of Intelligent & Robotic Systems， 2013， 71（2）：255-269.

[10]Zhang C ， Zhen Z ， Wang D ， et al. UAV Path Planning Method Based on Ant Colony Optimization[C]// Chinese Control & Decision Conference. 2010.

[11]Chen Y ， Yu J ， Mei Y ， et al. Modified central force optimization （MCFO） algorithm for 3D UAV path planning[J]. Neurocomputing， 2016， 171（C）：878-888.

[12]賈广芝.基于遗传算法和稀疏A*算法的无人机三维航迹规划研究[D].南京：南京邮电大学，2017.

[13]马云红，张恒，齐乐融.基于改进 A*算法的三维无人机路径规划[J/OL].电光与控制http：//kns.cnki.net/kcms/detail/41.1227.tn.20190624.1645.016.html.

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

[15]王宁，魏利胜.一种基于 GA 的新型生物地理学优化算法研究[J/OL].系统仿真学报.http：//kns.cnki.net/kcms/detail/11.3092.v.20190531.1702.025.html.