四旋翼无人机航径规划遗传算法研究

王世凯，耿振野，刘智，黄丹丹，李艳山

（长春理工大学 电子信息工程学院，长春 130022）

航径规划的核心内容是根据所要到达的目标，在符合约束条件的情况下，设计出合理的飞行路线。对于四旋翼无人机来说，自主航路规划是必不可少的重要部分。特别是当队伍参加“英飞凌”杯全国高校无人机创新设计应用大赛以来，更明白航径规划的重要性。航径规划的目的，就是在规定的时间范围内，通过自身的运算，来得到最优或者次优的航线，从而能够有效地规避障碍物。而自动避障技术［1］是四旋翼无人机安全飞行的重要保证。飞行航径规划最终负责产生轨迹空间，四旋翼无人机在进行飞行任务时，需要根据地形、障碍物等信息，有效实时地做出判断，准确地计算出飞行航路，实现到达目标位置的飞行任务。目前，无人机航径规划算法主要有可行性方向算法、实时优化算法、A*搜索算法［2］、启发式搜索算法［3］、神经网络算法［4］、蚁群算法［5］等，这些方法能在一定程度上达到相应代价的航路规划功能。但是，大多数传统的方法都存在着很大的缺陷。例如，规划结果需要进一步优化后，才能实现四旋翼无人机的稳定飞行，不能保证实时性和安全性。针对传统的遗传算法［6］，本文对遗传算法做出改进，使其能够对四旋翼无人机进行最短的航路规划。本文提出了一种改进的遗传算法，可以更加有效地规划飞行航径。

传统的四旋翼无人机航径规划方法处理流程，一般情况下可以划分成两部分来得到完美实现。第一个部分是从整体的角度上分析，获取参考航径规划；第二个部分是从局部的角度分析，进行航径动态优化。结合无人机在飞行过程中所需要完成的目标、安全标准、持续时间等因素，经过综合考量，得到最佳的性能指标。在此基础上，利用航径规划算法，便能够获取最佳的参考航径。针对处理流程，本文做出了分析，在实际情况下，必须考虑到参考路径旁边的障碍物分布情况，还有无人机存在的约束条件，比如转动的角度、所处的位置、当前的速度等，它们都会对无人机的飞行状态造成影响。因此，需要对参考航径做出改良，通过优化处理，来得到最佳的飞行路线。在四旋翼无人机执行系统的控制下，平稳的向下一个目标运动，这具有很好的应用前景［7］。当四旋翼无人机起飞、悬停完毕后，开始自主飞行命令，通过设置的障碍物，加以传感器的信息补偿，及时调整飞行位置，无人机根据感知到的信息，融合改进遗传算法，从而确定最佳的飞行路线，来确定在漫游飞行过程中，合理的规避当前感知到的障碍物。

1 四旋翼无人机平台

本设计使用基于英飞凌XMC4700与N3飞控的Onboard SDK平台，并应用了英飞凌的多种传感器，实现对四旋翼无人机的控制。融合了动力、飞控、导航、相机、图传与数传等系统模块，飞行的高度能够达到50m以上，而且有着很强的负载能力，是一个比较稳定的飞行平台。可以支持多种类型传感器，能够在复杂环境下实时计算。四旋翼无人机管理平台如图1所示。

图1 四旋翼无人机管理平台

如图2，四旋翼无人机通过障碍物信息估算距离、高度及导航位置。通过改进遗传算法来计算出比例信息，得到已知尺度下的障碍物（高度、位置）信息的数据估计，再通过判断获取的障碍物信息对两者的距离估计信息进行筛选，以保证四旋翼无人机始终处于飞行安全位置。

图2 无人机探测障碍物

四旋翼无人机航径规划首先进行环境的规划，包括建立障碍物模拟模型和无人机参考坐标系，接着是巡航阶段的航迹表示，考虑到约束条件，需要使用目标函数，合理地规划算法，最后统计分析出最佳航径。总体框图如图3所示。

图3 航径规划总体框图

2 模型搭建

考虑到四旋翼无人机是从障碍物中寻找最短航径，本文将大小不同、不规则静态障碍物用圆形图标来表示，如图4所示环境模型。

图4 静态障碍物模拟模型

通过图4的静态障碍物模拟模型，本文给出了图5搭建的二维空间环境模型，四旋翼无人机被简化为质点，四旋翼无人机从起始位置(x(t),y(t))飞向目标位置(xs,ys)，定义四旋翼无人机的质心为转向点，α为四旋翼无人机的当前运动方向与质心到目标位置连线的夹角，L为四旋翼无人机到目标位置的距离。

图5 参考坐标系

根据图5结合数学知识，可以得到：

四旋翼无人机的运动学方程为：

其中，(x,y,θ)是四旋翼无人机的位姿，四旋翼无人机与目标距离的距离为L，Ld为距离目标位置的安全距离。记四旋翼无人机与目标位置的距离误差为L误=L-Ld，则四旋翼无人机的位姿误差极坐标方程为：

3 航迹表示

很多情况下，由于四旋翼无人机在起飞后将保持一定的高度进入巡航阶段［8］，飞行的过程中通常只需要关注其水平方向的轨迹，按照事先设定好的高度参数，利用平面几何的原理进行规划。周围的环境可能是未知的，四旋翼无人机只能通过搭载的传感器探测障碍物，所以无人机的航径规划问题应该考虑两个方面的问题：一个是单个静态障碍物航径规划问题，一个是多个障碍物航径规划问题。在图6中，给出单个障碍物的处理方法，A代表最初起飞的地方，B代表所要到达的地方，h代表巡航高度。当无人机飞行到h高度的时候，A与B中间的障碍物所存在的地方，用圆形图标来显示。当h改变的时候，A与B中间的障碍物存在的地方亦会随之改变。

图6 单个静态障碍物平面示意图

如图6所示，在初始位置A和目标位置B之间有1个静态障碍物。线段AB经过障碍区，需要做Aa，Ac，bB，dB切圆，还需要计算出线段Aa，Ac，bB，dB和弧线ab，cd的长度作为节点代价。对于单个障碍物问题选择用图中所展示的方法，同样地，多个静态障碍物处理方法相同。通过一系列运算，得到切点、切线以及圆弧的长度，并由此来获取下一个层次的节点与节点代价，如此依次类推。

四旋翼无人机规划一条最佳航径，不光要考虑周围的环境，处于环境中的障碍物，复杂的地形，还要考虑无人机的自身条件，即最小转弯半径、航径长度、爬升角等等。这里主要考虑解决最短航径长度问题。

4 改进遗传算法

航径规划应该在具有任意形状障碍物的连续空间中解决。利用五个定制的交叉和变异算子来改善初始航径，并根据上述目标生成最优解。为了评估所提出的算法的效率，检查了具有复杂度的平面环境，以在连续环境中找到航径长度，平滑度和安全性的最佳航径。该航径不受离散网格化环境中的网格的限制。本文考虑二维环境中的航径规划问题，其中充满了任意形状的静态障碍物，其与自由空间没有相互作用（正面或负面属性）。同时，本文把四旋翼无人机标记为点。飞行路线定义为航径或轨迹［9］。可以通过在二维环境中选择适当的飞行节点集来定义四旋翼无人机可以飞行的路径。因此，改进遗传算法为所有节点分配适当的潜在值。然后，四旋翼无人机确定起始位置和目标位置之间的所有可行航径。

本文提出了一种带有改进遗传算子的改进遗传算法，以确定定义的飞行坐标点，使四旋翼无人机在连续环境中找到最佳位置。改进遗传算法的主要特征是：具有可变长度染色体群，增加寻找最佳路径的灵活性；具有五个交叉算子和变异算子，能够找到飞行坐标点的最佳位置；改进遗传算法重复演变，一直到达到终止条件。在本文中，使用固定迭代次数作为终端条件。

图7是改进遗传算法航径规划过程。

图7 改进遗传算法航径规划过程

4.1 选择运算

选择算子随机或基于预定义的度量从总体中选择一些个体。在本文中，使用轮盘转轮选择（RWS）来选择交叉算子的亲本。每个个体的选择概率与其质量成反比关系。因此更好的个体有更多的机会被RWS选中。同时，秩的选择是被用于第i次迭代，其包括第(i-1)次迭代的群体和由遗传算子获得的新后代。

4.2 改进交叉算子

修改后的交叉算子结合了两个具有相同或不同数量的飞行坐标点，以产生新的后代，这在预定义的目标方面可能更好。第一个交叉算子通过计算两个亲本的平均值来找到一个新的后代：

其中，x1p，y1p和x2p，y2p是两个亲本的飞行坐标点的x和y坐标，xf，分别是个体的飞行坐标点。当两个亲本的飞行坐标点不相等时。首先，选择具有较小飞行坐标点的亲本Ps。然后，通过取Ps的每个飞行坐标点的平均值，以及另一个亲本最近的飞行坐标点来计算后代的飞行坐标点(xf,)。在第二个交叉算子中，两个亲本以随机方式组合以增加多样性并搜索整个自由空间：

其中，γ是[- 1,1]范围内随机数的向量。在两个亲本的飞行坐标点不相等的情况下，类似于第一交叉算子，将具有最小距离的飞行坐标点组合在一起。第一交叉算子可以用于生成更短更平滑的航径，第二交叉算子可以用于随机搜索环境，以避免过早收敛。

4.3 改进变异算子

变异算子可以增加群体多样性、搜索环境区域以及能够将一组飞行坐标点移动到特定方向上，这些对于增加航径平滑度和获得最短航径长度是非常有用的。第一个变异算子是一个算术变异算子，它在随机方向上改变预定数量飞行坐标点的位置。该算子对提高多样性和避免过早收敛有很大的帮助。第二个变异算子修改飞行坐标点的位置，以改善路径的长度和平滑度。该算子通过将其当前位置Pi和朝向两侧的飞行坐标点方向（Pi-1和Pi+1）进行积分来改进飞行坐标点的位置。

其中，δ和β是小的正系数。第二个变异算子产生的航径具有更高的平滑度和更短的长度。第三个变异算子将任意选择的飞行坐标点移向到目标位置。这三种变异算子的组合为改进遗传算法的探索和开发提供了支持。

4.4 选择删除运算算子

为了使算法性能稳定，在改进遗传算法中使用删除运算算子，这与初始航径中的飞行坐标点无关，与下一坐标点有关。删除运算算子删除航径的冗余飞行坐标点。首先，从群体中选择个体。然后删除运算算子有顺序地评估每个飞行坐标点。如果删除任何选定的飞行坐标点是有效的，那么就可以减少航径的长度。

5 仿真验证与分析

根据航径规划遗传算法的要求，经改进遗传算法计算可得优化后的最优飞行航迹。

（1）实验环境：Intel（R）Xeon（R）CPU，运行内存为 32GB的 Win7 64位工作站［10］，编程环境使用MATLAB R2014a。

（2）设定改进遗传算法控制参数：控制参数主要是种群大小、迭代次数、交叉概率以及变异概率。种群大小和迭代次数直接影响质量。因此，用未改进算法和改进遗传算法通过MATLAB仿真进行了比较，证明改进遗传算法对四旋翼无人机航径规划问题的有效性。

（3）实验结果及分析

首先使用未改进算法进行实验，通过设定障碍物数据，合理规划二维空间，描述起点位置［20，160］，目标位置［180，100］，进行图形标注后，描绘障碍物图形，得到不同的航径后，用图8中的实线描绘可行航径。

图8 未改进算法航径情况

图9 未改进算法迭代后航径长度情况

由图8可得最短航径，未改进算法种群数量设定为30，设定100次迭代次数，经过循环搜索和一系列航径长度的计算，不断更新全局最短航径，在其飞行空间中找到一条从起始位置到目标位置的，能避开静态障碍物的最短航径。由图9可知，当算法的迭代次数一定时，航径总长度达到最优，但是得到的曲线不是平滑的。这在实际应用中，会导致获得的航径长度误差较大，不利于无人机的续航。同时，不能保证无人机安全着陆［11］。

本实验中改进遗传算法的参数设定如下：种群个数设定为30，迭代次数设定为100。适应值归一化淘汰加速指数设定为2，交叉和变异概率分别设定为0.35和0.2。飞行空间由直角坐标系组成，如图10所示，实线是改进遗传算法经过计算得出的无人机最短航径，图11所示获得的航径长度情况曲线相对光滑，这可以更好地规划无人机的航道，提高了飞行效率，增加了续航时间，有很好的技术价值。

图10 改进遗传算法航径情况

图11 改进遗传算法迭代后航径长度情况

仿真结果表明，未改进算法适合求解，但是收敛速度较慢。迭代次数达到一定次数时，容易陷入局部最优。而改进遗传算法对搜索空间里面的大量解完成评估后，降低了陷入局部最优的机率，有利于整体最优。

表1 综合对比

通过表1综合对比，虽然两者的运行时间几乎相同，但是图9所示未改进算法获得的曲线经过62次迭代，最优目标函数值收敛，航径长度为199.1836，而图11所示改进遗传算法在经历了55次迭代已经收敛，62次迭代后已经最优，航径长度为171.3615，比未改进算法获得的航径更短，效率更高，曲线更平滑。相对来说，优于未改进算法，证明了改进后的算法对解决四旋翼无人机航径规划问题是高效的。

6 结论

采用一种复杂环境下四旋翼无人机的改进算法。保证在每个复杂环境中找到最佳（或接近最佳）航径。改进遗传算法修改从初始航径获得的飞行坐标点位置，以找到起始位置和目标位置之间的最佳路径。在算法中引入五个交叉算子和变异算子来改善飞行坐标点的位置。改进算法提高了时间效率，航径长度大大缩短，在静态障碍物环境中可以找到最优航径。