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

吕 倩，孙宪坤，熊玉洁

（上海工程技术大学 电子电气工程学院，上海 201620）

0 引言

无人飞行器（unmanned aerial vehicle，UAV）的自主飞行与导航是1 个极具挑战性的任务[1]，该任务可分为环境信息感知、路径规划和飞行控制3 个阶段[2-3]。其中，路径规划阶段上承环境感知，下接飞行控制，起到重要作用。在无人机机载传感器准确探测周围环境信息并建立地图模型之后，规划算法根据环境感知结果开始规划从起点至终点的无碰撞轨迹。轨迹规划完成后，飞行控制系统根据规划结果指导无人机按线路飞行[4]。理想状态下，只要路径不接触障碍物，无人机就可以安全到达终点。但实际飞行任务中，传感器探测环境中的障碍物范围会有所偏差，控制系统指导无人机飞行时也会出现控制误差。既定路线距离障碍物越近，发生碰撞的可能性越大，所以本文采用使轨迹尽可能远离障碍物的思想来减少碰撞可能。同时，由于无人机机载电池的续航时间极其有限，要无人机从起点至终点的路程不能过长。通常，解决路径规划问题有人工势场法（artificial potential field method，APFM）、基于随机采样的方法、基于图搜索的规划方法、借鉴生物界进化规律的遗传算法（genetic algorithm，GA）等几类方法。

文献[5]中采用人工势场法，通过人工为飞行环境创造1 个包含斥力极与引力极的势场来完成路径规划任务。但若环境中某些位置的引力与斥力达到平衡就会陷入局部最优，导致无法完成规划任务。基于随机采样的路径规划方法有快速扩展随机树（rapidly-exploring random tree， RRT）[6]、在 RRT 的基础上加入了自起点与终点双向搜索引导策略的双向快速扩展随机树（rapidlyexploring random tree connect，RRTConnect）[7]、加入启发式策略及贪心思想的RRT*[8]等。这些变体在原始 RRT 的基础上加快了向终点的逼近速度。基于随机采样的算法理论上是可行的，但有时由于节点选择具有随机性，若进入环境死角会导致无法成功到达终点；即便到达终点，所得的路径也具有不稳定性，无法达到使无人机飞行路程较短以减少电池能量消耗的目的；同时，由于每阶段的路径与方向选择存在随机性，因此同样无法满足平滑易控制的条件。基于图搜索的算法，如迪杰斯特拉（Dijkstra）算法[9]，加入了启发式思想的A*算法[10]及各种变体，加入了修剪策略用于提高搜索速度的跳转点搜索算法（jump point search，JPS）[1,11]及其变体等。这些算法虽然通常情况可以到达终点，能满足飞行路程短的要求，但无法保证无人机在飞行过程中远离障碍物，增加了发生碰撞的可能；而且路径急转弯情况较多，不够平滑，造成飞行控制难度增加，同样无法保证飞行安全。

遗传算法是从生物进化思想得到启发而提出的优化算法。文献[12]提出的进化算法，可以有效地为给定障碍空间内的起始位置到目标位置规划出若干条可行路径，并采用改进的遗传算法解决静态环境下的多目标路径规划问题。文献[13]用遗传算法与蚁群算法2 种仿生物学算法解决灾后应急物资的路径规划问题，该研究适用于为可选择路线已存在的情况下规划最短路径问题。文献[14]在遗传算法的种群更新阶段，结合了模拟退火算法，令算法避免陷入局部最优，从而得出最短的援救路线。但这些方法都只是从得出最短路径的目的出发来规划路径，并未考虑机器人实际执行时，在环境感知与飞行控制阶段产生的误差对路线的要求。若规划路径距离障碍物过近，在这2 个阶段稍有偏差的情况下就会发生碰撞。无人机距障碍物越远，因感知与控制误差等因素导致的无人机与障碍物发生碰撞的概率也越小。本文通过规划，使无人机尽可能远离障碍物的路径，以达到保证无人机飞行安全的目的[15]，同时也要考虑飞行路程问题。所以在设计适应度函数时，通过为路程长度和路径点距障碍物距离设置权重来达到平衡2 者的目的。在此基础上，还加入精英个体保留策略，用于保证种群不会向更坏的方向繁衍；加入删除操作，以杜绝冗余路径节点的出现，以期有效缩短飞行路径长度。最后通过起始点全部在宽阔区域与起点位于狭窄的障碍物内部区域2 种场景的实验，与人工势场法、基于随机采样的RRT 算法、基于启发式图搜索的A*算法、原始遗传算法相比较。

1 模型建立

1.1 环境表示

假设无人机所处环境如图1 所示。四周的墙体表示环境边界，无人机飞行不能越过此范围。墙体内的中空柱体与圆锥可表示楼房等障碍物，飞行过程中要避免与之发生碰撞。

图1 无人机所处环境模型

在为无人机规划路径前，首先要对环境进行简化，将其转换为可进行信息处理的模型。由于3 维空间可表示为多个2 维平面的堆积，故本文针对 2 维环境进行处理。栅格法表示环境信息是常用的建模方式[3]，本文使用栅格表示2 维占用环境。模型表示如图2 所示。

图2 2 维环境栅格表示

以左下角为坐标原点建立直角坐标系，图2 中黑色部分为障碍物，白色部分为可供无人机自由飞行的无障碍区域，左下角标识位置为无人机当前位置，右上角标识位置为期望到达的终点。在从起点到终点的过程中，根据无人机机载传感器探测的范围，可分阶段为其规划路径。

1.2 遗传模型建立

进化算法是计算科学的重要领域，它使用生物进化的思想来解决计算问题。遗传算法是进化计算的最广泛的使用形式之一，可以在不断变化与复杂未知空间中寻找解决方案。本文采用遗传算法分阶段解决路径规划问题，其中，路径 PI可表示为

式中： p0表示起点； pn表示终点；下标i 表示路径节点的序号；pi表示整条路径中的第i 个路径节点；（ pi-1，pi）表示第i 段路径。

图3 为某条路径的示意图。在规划过程中，每条自起点至终点的无碰撞路径表示为1 个个体，每个个体中有1 条染色体，故每条路径也可称为1 条染色体。路径中的每个阶段（ pi， pi+1）表示为1 个基因。所有个体的集合即生成的所有从起点到终点无碰撞路径表示为种群。适应度函数的目的是将每个个体的属性量化，通过设计适应度函数来从种群中筛选出需要的个体。适应度越高的个体就越是精英个体。

图3 路径表示

2 算法介绍

本文主要采用遗传算法的思想为在复杂未知环境中的无人机规划路径，算法流程如图4 所示。

图4 算法流程

2.1 初始化种群

遗传算法的种群初始化阶段要求种群中个体具有随机性与多样性[3]，即在地图中随机生成自起点到终点的无碰撞路径。路径规划可分为全局规划和局部规划。全局路径规划是指周围环境信息已知，无人机只需要按照既定路径飞行。但现实中的环境是复杂可变的，无人机无法在飞行任务开始之前得到周围环境的先验信息，所以通常需要依靠无人机机载传感器探测到的环境信息的实时数据分阶段规划路径。

局部路径规划的种群初始化可分为2 个阶段，在第1 阶段，终点位于机载传感器最大感知范围之外，在无人机当前所处位置ip 无法知道终点位于何处，只能采用随机选择的方式来生成下1 阶段路径点 ip+1。当从 ip 到 ip+1的途中会经过障碍物时，则重新选择1 个点作为 ip+1。

在第2 阶段，当无人机此时位于 jp 点，假设此时终点位于传感器感知范围之内，由于要规划的是1 条距离较短的路径，所以此时可以为下1 个候选路径点pj+1限制范围，即

如此可令无人机更快地接近终点。但为保证初始种群的多样性与随机性，本文设定限制在该范围的个体占初始种群总数的50%，另外的50%依然采用随机选择的方式选取路径节点。

2.2 个体适应度函数

适应度函数用于将种群中每个个体的属性量化，不同的适应度函数在同1 种群中筛选出的精英个体也不同。本文要求为无人机规划出从起点到终点的无碰撞、路程短、平滑可行的路径。保证无人机的安全行驶为路径规划的第1 要义。考虑到无人机机载传感器对环境感知的误差，以及路径规划完成之后，飞行控制系统按照规划结果指导飞机实际飞行时可能出现的误差，若规划出的路径距障碍物过近则会增加碰撞概率，故要通过设计适应度函数选择出尽可能远离障碍物的轨迹，这样在飞行过程中发生碰撞的概率也会更小。同时也要考虑路程短的要求，适应度函数流程图如图5 所示。

图5 适应度函数流程

在有N个个体的种群中，Fitness（PI）为个体 PI的适应度函数，可表示为

式中：Length(PI)为路径 PI的总长度的函数；w1为第1 部分Length( PI)在整体中所占比重； NSample( PI)为路径 PI上的随机采样点个数函数；w2为第2 部分 NSample( PI)在整体中所占比重。

采样点个数函数 NSample( PI)可以表示为

式中δ 为正整数。

假设在路径 PI上随机选取的路径点为 pk，点 pk与距其最近障碍点 Obstacle的距离 dpk_Obs可表示为

若

则令

式中：θ 为大于无人机半径的定值； Number( PI)为在路径 PI上选择的采样点中 dpk_Obs＜θ 的点的数量。

适应度函数由路径 PI的长度与路径中距离障碍物过近的点的数量2 部分组成。函数值越大，则路径性能越差，函数值越小的个体越是种群中的精英个体。

2.3 交叉与变异

交叉与变异操作是为了产生更多的新个体，交叉与变异概率的大小影响了新个体产生的速度。发生交叉与变异的概率越大，产生新的个体的速度也越快。本文选择在种群中路径的交点处以一定的概率进行交叉操作以保证路径的连续性。

对于变异而言，本文采用随机变异的方法，即在地图的非障碍区域内随机选择某个路径点 Pi′用于替换原本的路径点 Pi。若替换之后的路径点 Pi′与 前 后点的 连 线即路 线（ Pi-1，Pi′）（ Pi，′ Pi+1）通过障碍物，则更换 Pi′为 Pi′，直到（ Pi-1，Pi′）( Pi′， Pi+1)中间无障碍物，针对路径点 Pi的变异完成。变异完成后，若变异得到的路径相较于变异前更优，及适应度函数值更小，则采用变异之后的路径，否则，采用原有路径。如此可保证变异朝着更优的方向进行，不会变异出更差的个体。

2.4 删除

本文采用文献[3]中增加的删除操作，目的是为了排除最优路径出现冗余路径点的情况，增加此步骤可以有效地缩短路径长度，防止节点冗余情况的发生。主要思想为：从终点开始遍历每个路径节点，若某节点 ip 可以与起点无障碍相连，则起点与节点 ip 中间的节点就是冗余节点，删除操作就是要删除这些冗余节点并重新计算路径的适应度函数。

2.5 精英个体选择与保留

遗传算法通过筛选出种群中优秀的子集用 于繁衍后代，遗传算法认为，越是优秀的个体繁衍出的后代也会越优秀，采用该思想仅使用每次选出的优秀个体集来繁衍后代，如此不断迭代即可令普通种群向精英种群进化，直到到达终止条件。

通过计算适应度函数，选取每代种群中的精英子种群，并选出当代种群中适应度函数值最小的个体Min(Fitness(IP ))，记IP 为最优路径POptimalpath，将其保留下来用于与下代种群中的最精英个体相比较，若后代精英个体的适应度函数小于 Fitness（POptimalpath），则更新最优路径，否则，依然保留上代最精英个体为POptimalpath，如此可以保证将适应度函数最低的个体保留下来。

3 实验

针对为无人机规划路径，保证无人机的飞行安全是首要目的。由于在环境感知与飞行控制过程中可能出现的误差，无人机离障碍物越远，那么因不可控误差因素导致的无人机与障碍物发生碰撞的概率也就越小。由于无人机机载电池的续航时间有限，要令无人机在短时间内到达指定目的地并且完成某种任务，则应使无人机飞行路程尽可能短；另外，为便于飞行控制系统根据路径规划结果指导飞行，应使路径尽可能平滑而易于控制。

本文设计实验为：在不同的起始点场景，对不同算法的规划结果进行比较：场景1 为起始点全部位于环境开阔的空旷地带；场景2 中，起点位于较狭窄区域，目的是模拟无人机位于中空障碍物内部起飞的路径规划情况。

3.1 不同算法规划结果比较

图6 为起始点都位于障碍物外部的开阔地带即场景1 的规划结果。图7 为起点位于左上角障碍物内部的狭窄地区即场景2 的规划结果。图6、图7 中的子图图6(a)、图6(b)、图6(c)、图7(a)、图7(b)及图7(c)分别为使用人工势场法、快速随机搜索树法、A*算法规划得出的结果。

图6 场景1 中3 种算法规划结果

图7 场景2 中3 种算法规划结果

3.1.1 人工势场法

APFM 是常见的路径规划方法，即人工为无人机运动的环境设置了1 个包含引力场和斥力场的虚拟力场，通过求合力的方法来控制运动。但若在某些位置的引力与斥力相同，则依靠规定的虚拟立场无法指导下一步路径节点的选择，也意味着规划失败。图6(a)与图7(a)为采用人工势场法分别为2 种不同的起始点位置规划路径的结果。实验表明该方法无论是在场景1 还是在场景2 中都未成功规划出从起点到终点的路径。

3.1.2 基于采样的路径规划算法

RRT 及其变体是典型的基于随机采样的路径规划算法，但随机算法规划出的路径具有不确定性，不能够保证成功率，在某些环境下会陷入死胡同，根本无法到达目的地。图6(b)与图7(b)为使用RRT 算法分别为2 种场景规划得出的路径。在2 种场景下，该方法虽然得出了从起点到达目标点的路径，但既不满足最短路程也不满足路径最优，距障碍物较远且蜿蜒曲折，如若无人机按此路径飞行既耗时耗能又极度不安全且难以控制。

3.1.3 基于图搜索的算法

基于图搜索的算法多种多样，如深度优先搜索，广度优先搜索、迪杰斯特拉算法、A*算法等，其中A*算法中加入了启发式策略，是可以得到最短路径的算法。图 6(c)与图7(c)为使用A*算法得出的路径。但A*算法有极大的局限性，不具备智能性，相同的地图使用A*算法得出的结果是唯一的，无法产生更多的路径来满足除路程最短之外的其他目的，如本文所需要的离障碍物足够远与平滑易控的需求。

3.2 原始遗传算法

图8、图9 为原始遗传算法的运行结果。图8 为场景1 情况下原始遗传算法的运行结果。在图8（a）中圈出的地方明显有1 段路程距离障碍物极近，若传感器在探测环境信息或者飞行控制方面稍有偏差，必将发生碰撞。在图8(b)中，路径明显过长，未达到飞行路程短的目的。在图8(c)中，出现了冗余路径点的情况，本文所加入的删除操作可以避 免该情况的发生。

图8 场景1 中原始遗传算法规划结果

图9 为场景2 情况下原始遗传算法的运行结果。在图9(a)中右下角障碍物附近出现路线距离障碍物较近的情况。图9(b)中在起点附近位置出现了冗余节点，同时规划路程过长，不利于节约机载电池耗电量。图9(c)中出现冗余路径点情况，加入删除操作就是为了避免此类情况的发生。

图9 场景2 中原始遗传算法规划结果

3.3 本文算法规划结果

图10、图11 为本文所用算法的规划结果，分别为场景1 与场景2 中本文所述算法运行的结果，起始点位置与3.1 节、3.2 节所列算法相同的。实验结果表明，此方法相较于图6(a)、图7(a)所示的人工势场法，可以完成路径规划的任务；与图6(b)、图7(b)所示的基于随机采样的RRT 算法相比，此方法可得出路程更短、离障碍物更远、更加平滑可控的路径；与图6(c)、图7(c)所示的基于图搜索的A*算法相比，此方法有更大的灵活性，可按照不同的需求规划不同路径，得出的路径更加光滑易控；相较于图10 所示的原始遗传算法，本方法在保证飞行安全（见图8(a)、图9(a)），保证路程较短（见图8(b)、图9(b)）与避免冗余节点(见图8(c)、图9(c))等方面有了明显提高。

图10 场景1 中本文算法规划结果

图11 场景2 中本文算法规划结果

4 结束语

随着机器人技术的快速发展与飞行控制技术的 日趋成熟，无人机在越来越多的领域中得到了广泛应用，路径规划是无人机自主飞行中的重要组成部分，规划出优质的路径是保证无人机在执行任务时，可以安全、快速到达终点的关键。因此，本文采用改进遗传算法的方法，通过规划出远离障碍物的平滑短距路径来保障无人机能够快速、安全地到达目的地。在无人机实际自主飞行与应用方面还需要考虑诸多因素，需要与环境感知与飞行控制等多个阶段密切配合才能够将该算法实际应用于无人机飞行中。