基于改进遗传算法的无人机路径规划

黄书召，田军委，乔 路，王 沁，苏 宇

（1.西安工业大学电子信息工程学院，西安 710021；2.西安工业大学机电工程学院，西安 710021）

（*通信作者1945980733@qq.com）

0 引言

近年来，受益于轻型高分子材料的发现以及嵌入式、自动化、信号处理、无线通信等技术的发展与成熟，无人机（Unmanned Aerial Vehicle,UAV)在田间信息获取、农业植保、设施巡检、物流配送［1-2］等场景中广受青睐。在借助UAV进行田间信息获取时，所获取的信息可能很多，覆盖面积广。由于民用UAV 的续航时间短，这就导致不同的信息获取路线所耗费的作业时间相差甚远。因此，UAV 路径规划［3］是田间信息获取场景下的关键问题。

路径规划技术作为任务规划系统的核心部分之一，受到了广泛关注。在这一领域，国内外已经展开了大量的研究工作。文献［4］中针对传统A*（A Star）算法搜索路径效率低、路径存在许多冗余节点和转折点的问题，引入启发函数，得到了更优质的路径。文献［5］中为了实现全局路径搜索，对A*算法进行了深入的探讨并介绍了几种A*算法的扩展算法。快速搜索随机树（Rapidly-exploring Random Tree，RRT）算法和概率路线图（Probabilistic RoadMap，PRM）算法都是概率型算法：前者从起始位置开始，通过概率分布连续产生生成树，当树的节点到达目标位置时，算法停止［6］；后者通过对地图进行概率画点从而完成对地图节点的离散，之后连接所有可视线段，结合使用A*等搜索算法实现路径寻优［7］。当前对于RRT算法和PRM 算法的研究主要集中在解决narrow-passage 问题上，Kalisiak 等［8］提出了动态规划的RRT，Jiménez-Franco 等［9］提出了基于粒子滤波的RRT 来确保在不确定性地形中随机树的生长。上述算法在路径规划技术都有着不错的发展，但A*算法在复杂地形下计算效率过于低下，RRT和PRM 存在着narrow-passage 等问题，这使得上述算法都难以应用至真实的三维路径规划上；但上述算法由于具有在简单地形中搜索高效的特点，被广泛地应用于动态在线规划中［10］，而在离线规划中，智能算法相比以上算法有着更大的优势。

遗传算法（Genetic Algorithm，GA）［11］具有强大的全局搜索能力，特别是在复杂优化问题中的搜索能力，使得GA 广泛地应用于路径规划、任务分配等问题研究。目前对于GA 进行路径规划的几个研究重点在于：航迹的表示［12］、GA 算子的设计及改进等；研究人员期望通过研究这些重点来解决GA中的早熟和收敛速度等问题。文献［13］中针对传统GA 不适用于转弯情况较多的复杂地图，首先将RRT 算法用于栅格环境产生初始路径，接着提出一种新的插入算子，最后进行路径优化；文献［14］中提出将极坐标与笛卡尔坐标结合的方式来表示航迹，从而降低计算消耗；文献［15-16］中提出了一种多频变异和交叉的思想，用于解决GA 中的早熟问题，并提出对种群初始化进行预处理，从而加快收敛；文献［17］中将GA 与ACO相结合，提出了一种新的融合算法，重点对时序约束进行了考虑；文献［18］中利用染色体路径表示的GA，并使用部分映射交叉的另一种形式，提高了基于置换的GA 的效率。虽然针对GA 路径规划问题已经进行了诸多研究，但仍然存在以下几个不足：

1）不能最大限度保留优质基因；

2）进化过程中染色体长度固定，重复基因处理不当；

3）变异随机性大，不一定能产生最优基因。

本文针对上述问题，提出了混合无重串选择算子、非对称映射交叉、启发式多次变异三种算子，并且引入三次B样条曲线平滑算法解决了GA 在无人机路径规划中存在的问题。最后通过实验结果证明，改进后算法规划路径相较其他算法规划出的路径更优，具有很好的性能以及较强的适应性。

1 模型建立

1.1 环境模型

农田信息的快速全方位获取是实现水肥药高效管理和精准施用的前提和基础。为了获取田间信息，无人机被用于承担在某一特定区域实施信息获取任务。

无人机路径规划过程所需信息需要从地形模型中提取，良好的地形建模能有效提高路径规划效率。本文考虑原始地形、障碍区域等因素来进行环境建模。基准地形模型［19］为：

式中：x和y为模型投影在水平面上的点坐标；Z1为水平面点对应的高程值；a、b、c、d、e、f、g为常系数，控制数字地图中的基准地形起伏。

对于飞行环境中的较高的天然山体用指数函数来进行描述，数学模型可以表示为：

式中：()xi，yi是第i个山峰的中心坐标；hi为地形参数，控制高度；xsi和ysi分别是第i个山峰沿x轴和y轴方向的衰减量、控制坡度；n表示山峰总个数。环境模型如图1所示。

图1 环境模型Fig.1 Environment model

1.2 飞行路径表示

无人机的飞行路径是通过有序的点坐标进行表征的，各个相互接近的空间坐标点彼此使用三次B样条平滑曲线进行关联。假设这一组节点序列是{S，W1，W2，…，Wn-1，G}，此组节点序列由N+1 个节点构成；S和G分别代表了无人机的起点与终点；W1，W2，…，Wn-1是飞行过程中的各个节点；设定起飞点与终止点的三维表述是S=(x0，y0，z0)，G=(xn，yn，zn)；用Wi=(xi，yi，zi)(i=1，2，…，n-1)描述各个中间节点。

1.3 基于三次B样条曲线的路径平滑算法

为了保证航迹平滑可飞，减少算法计算时间，本文使用三次B 样条曲线对路径进行平滑，文献［20］中主要是通过添加控制点来有效规避障碍并生成平滑飞行航迹。

1.3.1 路径平滑基函数及控制点

给定空间顶点Pi(i=0，1，…，m+n)可以得到n次曲线段：

式中：Pi为第i个控制点对应的曲线方程，Fi，k(t)为k阶B 样条基函数。由于k值代表曲线的平滑程度，k值越大，曲线平滑程度越好，但计算复杂度也越大。为了兼顾平滑度和复杂度，本文选取k=3，得到三次B样条曲线基函数为：

将遗传算法得到的点集称为路径规划点M，假设M中有n+1 个有序空间位姿矢量Vi(i=0，1，…，n)，把相邻的k+1个位置矢量作为一组进行线性组合，就可以得到第i段相邻k+1个控制点的曲线公式为：

式中，Pi(x)为第i条B 样条曲线函数。当k=3 时，将式（4）代入式（6）得到曲线的矩阵形式为：

1.3.2 曲线差值

式（6）中的Vi-1，Vi，Vi+1，Vi+2是一组控制点，在无人机路径规划中，需要先知其所求路径上的型值点，型值点即无人机运动学逆问题求解求出来的点。如果对已知型值点路径规划，首先要求控制点，设P为型值点，得到以下条件：

式（7）中，有m+2 个未知数，但只有m个方程，因此添加全局路径点集首尾端点约束条件如下：

由给定边界条件可以唯一确定一组Vi-1，Vi，Vi+1，Vi+2，式（6）确定的B样条曲线表示为：

式（9）中，由Vi-1，Vi，Vi+1，Vi+2四个控制点控制，设控制点的坐标由(Xi，Yi，Zi)(i=1，2，…，n)表示，其中参数x均匀取0 到1 之间、间隔为0.01 的所有数，就可以得到第i段B 样条曲线。曲线任意点坐标(Xt，Yt，Zt)表示如下：

最后，令k=3，依据式（9）、（10）就可以得到三次B 样条曲线的连接点。为了降低计算复杂度，将重复连接点删除，然后连接剩下连接点就可以得到三次B样条曲线平滑效果图如图2所示。

图2 三次B样条曲线效果Fig.2 Effect of cubic B-spline curve

2 路径规划数学模型

无人机的路径规划有许多约束条件，这些约束限制了无人机的机动动作，导致寻找最优路径十分困难。本文路径规划研究考虑的约束条件和目标函数如下。

2.1 约束条件

约束条件的目的是保证规划出可飞路径，本文针对单无人机路径规划，因此，提出了地形和环境约束2个约束条件。

在完成信息获取任务时，为了避免发生碰撞，无人机飞行高度应始终高于地形高度，故地形约束条件建模为：

式中，Z2()xi，yi为地形函数，用于返回位置()xi，yi处的地形高度值。

在执行信息获取任务的过程中，为了规划出更好的路径，同时降低代价，规定无人机只能在指定区域内工作，环境约束条件模型为：

2.2 目标函数

对于可飞的路径，将无人机的航程、障碍物和边界约束综合考虑，能够归纳出飞行器的综合代价函数表达式如下：

式中：Vc表示航程代价；Tc表示地形代价；Ec表示边界代价。

航程代价Vc主要考虑无人机从起点到终点的飞行距离，与距离L成正比，如果总航迹由n个航点组成，那么航程总代价可以表示为：

地形代价Tc主要考虑无人机在完成信息获取任务过程中山峰的威胁，通过该代价约束，可以使无人机躲避工作过程中的障碍，表达式如下：

边界代价Ec主要考虑无人机在完成信息获取任务过程中，保证无人机工作在指定空间区域中，表达式如下：

3 改进遗传算法设计

对于田间信息获取任务，遗传算法若要规划出更好路径，在编码方式、适应度函数、遗传算子设计等方面必须更加符合实际，具体设计如下。

3.1 编码方式与初始化

由于本文采用三次B 样条曲线平滑路径以减少计算时间，因此个体编码采用实数直接编码，路径个体表示为从出发点到目标点的一系列中途点，可以用{S，W1，W2，…，Wn-1，G}进行表示，其中，S和G分别代表起点和终点，Wi代表路径的中途点。编码方式图如图3所示。

图3 编码方式Fig.3 Encoding mode

初始化采用工作区域内随机初始化方式，这种初始化方式简单，而且能保证产生的初始种群都在工作范围内，并且初始化染色体长度相等。

3.2 适应度函数

遗传算法利用种群中每个个体的适应度值来进行搜索，适应度函数的选取直接影响到算法的收敛速度以及能否找到最优解。本文是最小化问题，适应度函数是由目标函数变换而成，目标函数转换为适应度函数，通过式（17）可以得到：

本文方法不需要对个体进行解码，可以直观地反映解的优劣程度。

3.3 改进遗传操作

遗传操作分为选择、交叉、变异算子三个部分，是遗传算法的核心。本节对上述三种算子分别进行改进，期望得到更好的收敛效果。

3.3.1 混合无重串选择算子

为了避免算法出现早熟现象，同时保证更好的个体可以直接进入下一代种群，本文提出了一种混合无重串的选择算子，该算子是由两种选择方式按照一定比例组合产生，然后在此基础上进行没有重串的稳态繁殖。第一种方式是锦标赛选择，所占比例为α；第二种方式是轮盘赌选择，个体的入选概率与其适应度值成正比，所占比例为1-α。选择完成后，首先判断该个体与种群中现有个体是否重复，如果重复就舍弃。

3.3.2 非对称映射交叉算子

根据积木块假设［21］，在基本遗传算法中，定义距长的模式很容易受到破坏，这对进化模拟而言是十分不利的。为了克服这一缺点，同时提高算法的收敛效果，本文提出了非对称映射交叉算子，该算子在不影响模式定义距的情况下，使优良的种群得以增值。

设计上，首先设计截断和拼接交叉算子，以适应染色体长度的变化；在截断操作中，随机选择两个不同的父代染色体，然后随机产生两个交叉点位，在交叉点截断生成四个基因段；最后，对基因段进行组合生成两条子代染色体。截断和拼接操作如图4所示。

图4 染色体截断和拼接操作Fig.4 Chromosome truncation and splicing operations

第二步，完成截断和拼接操作后，消除子代染色体产生的重复基因。

由于本文规划环境较大，基因变化较小时，在地图中差别不大，因此，本文提出了一种重复基因定义的方法：当某个点基因都在这区间范围内变化时，视为重复基因，需要对其做相应的处理。相似区间的定义可以结合区间划分的思想。

假设D为搜索空间，[Smin，Smax]为n个区间长度变量取值范围，Smin=[S1_min，S2_min，…，Sn_min]为n个区间长度变量的最小集合，Smax=[S1_max，S2_max，…，Sn_max]为n个区间长度变量的最大集合，则划分为m个区间，需要m+1 个区间向量对[Smin，Smax]进行划分，则m个区间可通过式（18）得到：

其中，l代表两个区间长度的间隔，由式（19）确定。

重复基因确定之后，通过截断前映射和截断后顺序复制两种方法处理。

截断前映射是使截断点之前的重复基因不变，对截断点之后的重复基因用*表示，处理结果如图5（a）所示。

然后，通过截断点之前部分消除重复基因，例如：子代1中2→20，3→10，6→15，与子代1 中基因不重复，则选择此基因替代重复基因。按照此方法依次消除重复基因得到最终结果如图5（b）所示。截断后顺序复制是使截断点之后重复基因不变，对截断点之前重复基因用*表示，处理结果如图5（c）所示。最后，从父代2 中找出子代1 中没有的基因，并将其按顺序给子代*位置，得到最终结果如图5（d）所示。

图5 重复基因处理方法Fig.5 Duplicate gene treatment method

综上所述，截断前映射可以保证后代染色体不会有重复基因，保留父代优秀基因；截断后顺序复制扩大了染色体改变范围，增大了搜索空间。因此，考虑用两种方法来对重复基因进行处理。在进化初期，适应度值比较分散（i≤k*β，i表示当前迭代次数，k表示总迭代次数，β控制比例），采用截断前映射消除重复基因；进化后期个体适应度值趋于一致或趋于局部最优（i＞k*β），采用截断后顺序复制消除重复基因。

3.3.3 启发式多次变异算子

针对传统随机变异算子早熟问题，本文提出了一种启发式多次变异算子来探索未知区域，抑制早熟现象，即通过多次启发式变异，寻求其中代价值最低的个体进入下一代。该算子流程如下：

1）发生变异时，先检查其中途点Pi与Pi+2是否有障碍物或者有不在工作区域内的点。

2）如果有，对穿越障碍物的点，或者不在工作区域的点进行变异，之后返回步骤1），直到该路径是可行路径为止。

3）如果没有，对其中途点随机变异，并且将Pi记录到R中。

4）如果R不为空，则从R中随机选取一点进行删除；否则，随机选取路径中一点删除。

5）返回步骤1）进行多次变异（变异次数一般取3或4），最终寻求其中代价值最低的个体进入下一代。

4 算法仿真与结果分析

为了验证所提路径规划算法和有效性，利用Matlab 进行了仿真验证，本文的主要参数设置如表1所示。

表1 改进GA与ACO算法的主要参数Tab.1 Main parameters of improved GA and ACO algorithm

为了验证本文改进GA的合理性，对比了改进GA、传统遗传算法（GA）、蚁群优化（Ant Colony Optimization，ACO）算法的收敛速度和代价值。在Matlab 2016a（主机Intel i5-5200U，CPU@2.20 GHz，4 GB RAM，Windows 10 系统）上运行了10次，并统计了10 次实验算法的平均收敛速度、代价值和程序运行时间，最终结果如表2 所示。由表2 可知，改进GA 平均代价值为392，平均在第5 代收敛，而GA 和ACO 算法代价值和收敛速度明显要低。

图6 是这三种算法的规划结果，从中可以看出，改进GA的规划结果最优。这是因为改进GA 的染色体在进化过程中是变化的，更加符合实际，而启发式多次变异过程中扩大了随机搜索范围，保证了可行解的质量。

表2 改进GA与传统GA和ACO算法的代价值与收敛速度对比Tab.2 Comparison of cost value and convergence iterations between improved GA with traditional GA and ACO algorithm

4.1 启发式变异与随机变异对算法的影响

为了验证改进后变异算子和交叉算子的性能，表3 给出了不同变异和交叉算子的代价值对比结果。由于收敛后代价值基本不再变化，所以为了展示方便，本文值选取了前15 代数据进行展示。通过表3 可以看出，采用启发式多次变异在第2代开始收敛，而随机变异在第12代才收敛，使用启发式变异相比随机变异代价值减小了32%；采用非对称映射交叉在第5 代开始收敛，而模拟二进制交叉在第9 代才收敛，使用非对称映射交叉相比模拟二进制交叉代价值减小了50%。可见，本文所设计的交叉和变异算子可以获得更好的效果。这是因为启发式变异既保证了种群多样性，又使变异目标更加明确，避免种群陷入局部最优。

表3 不同变异算子和交叉算子的路径规划代价值对比单位：mTab.3 Cost value comparison of path planning with different mutation operators and crossover operators unit：m

图7对比不同交叉率和变异率对求解算法的影响，从图7实验结果可以看出，不同的交叉率和变异率对代价值和收敛速度都有一定的影响。当交叉率小于变异率时代价值为837，收敛速度为10；当变异率大于交叉率时代价值为422，收敛速度为3。这是因为在变异操作中变异率太高，算法退化为随机搜索，变异率太小不容易产生新的结构。交叉概率过大新个体产生速度越快，种群被破坏的可能性也越大；交叉概率太小又会导致算法停滞不前。经过多次实验发现，当交叉率为1/ChromoSize时效果最好，ChromoSize表示染色体大小。

此外，染色体大小的选择对路径规划结果也有很大影响，不同染色体大小规划结果对比如图8所示。

图6 GA、ACO算法与改进GA的路径规划结果Fig.6 Path planning results of GA，ACO algorithm and improved GA

图7 不同交叉率和变异率的路径规划代价值对比Fig.7 Cost value comparison of path planning with different crossover rates and mutation rates

图8 不同染色体大小的路径规划代价值对比Fig.8 Cost value comparison of path planning with different chromosome sizes

从图9实验结果可以看出，当染色体长度为12时，平均代价值为1 870；染色体长度为6 和9 时，代价值分别为11 400 和1 158。但是，通过图9 可以看出，染色体长度为6 时，规划结果不可飞，不能保证每次都能规划出可飞路径；染色体长度为12 时，虽然规划的结果可飞，但是代价高，路径有冗余，计算复杂度增大。因此，选择适当的染色体大小对规划的最优结果是至关重要的。

4.2 不同环境对算法的影响

图10 展示了不同障碍物分布对无人机路径规划的影响，从图中可以看出，无论面对何种障碍物，该算法都可以规划出较好的路径。

图11 是算法在大尺寸地图上的表现，在不考虑无人机工作时间的情况下，仍能规划出很好的结果，表明该算法具有很强的适应性，面对不同的环境，可以完成信息获取任务。

图9 不同染色体长度的路径规划结果对比Fig.9 Path planning results comparison of different chromosome lengths

图10 不同障碍物分布对无人机路径规划的影响Fig.10 Influence of different obstacle distribution on UAV path planning

图11 算法在大尺寸地图上的规划结果Fig.11 Planning results of algorithm on large maps

5 结语

本文提出了改进遗传算法的路径规划方法。首先，为了模拟真实环境，考虑原始地形和障碍区域进行环境建模；其次，提出了混合无重串选择算子扩大了种群的分布范围，能在一定程度上避免算法过早收敛，在此基础上，还提出了非对称映射交叉算子和启发式多次变异算子，能加快收敛；然后，采用三次B 样条曲线对航迹平滑，保证最终航迹更平滑。通过Matlab 仿真表明，改进遗传算法得到的路径更优，并且得到选取变异率和交叉率的更好方法，能够解决三维环境下路径规划问题。由于无人机工作时间有限，无法长时间工作，后期将针对无人机长时间作业进行研究。