基于无人机航路规划问题的RRT 算法综合改进

郭莹婷，林川

（中国电子科技集团公司第十五研究所，北京 100083）

近年来，随着信息技术和人工智能在军事领域的广泛应用[1-2]，战争形态向着无人化和智能化的方向演变[3-4]，多种无人机航路规划算法受到国内外学者的广泛关注[5]。

在航路规划算法中[6-7]，人工势场算法等虽然收敛速度较快，但易陷入局部最优，模拟退火算法搜索效率较低[8-9]，蚁群算法[10]和遗传算法等存在航路规划实时性差等问题，且这些算法都需要在任务空间中对障碍物进行建模，不适用于解决无人机在复杂战场环境中的航路规划问题。快速扩展随机树算法（Rapidly-Exploring Random Trees,RRT）[11-12]无需对地图进行建模，通过对状态空间中的点随机采样并进行碰撞检测，有效解决了复杂环境和高维空间中的路径规划问题。

该文基于无人机在复杂战场环境下生成飞行航路的军事背景，针对传统RRT 算法存在的不足[13]，提出了目标引导随机点扩展方法以及动态步长选择策略，提高了算法的效率并减少了航路节点数量。文中首先说明了研究问题以及传统RRT 算法的应用；其次从随机点选择和生长步长调整两方面改进算法步骤；最后通过仿真实验对比，验证了改进后算法的有效性。

1 问题描述

无人机执行作战任务的战场环境一般较为复杂，常常包含各种不同地形和障碍物，例如高地、河流、雷达探测、火力打击和电子干扰等。研究中，为了简化任务空间的建模过程以及减少加载地图时间，根据战场环境的基本要素，采用简化后的二维地图表示无人机作战区域，其中实心圆点（图左上方）表示无人机起点，五角星（图右下方）表示无人机任务目标打击点，矩形表示电磁干扰区域、敌空中拦截蜂群等障碍物，黑色圆形表示敌方雷达探测范围，三角表示敌高炮火力杀伤范围。文中实验环境二维地图如图1 所示，任务空间大小为10×10 km2的二维图。

图1 实验任务空间

该文将无人机执行任务空间中的所有障碍物内部、雷达探测范围和火力杀伤范围都视为需要避开的飞行禁区，空白处为可跨越的安全区域，则航路规划问题可以抽象为从起点到目标点的可飞行航路的最优求解问题，无人机按照该飞行航路执行作战任务时，保证不会进入飞行禁区。

2 RRT算法改进过程

2.1 传统RRT算法

传统RRT 算法将任务空间中的起点Ns作为根节点，通过从任务空间中的安全区域（空白区域）中使用随机采样的方式生成一个随机点Nr，通过遍历随机树上的现存节点，找到距离随机点Nn最近的节点Nc，然后以随机点Nr作为扩展方向，以固定生长步长为距离，以最近的节点Nc为父节点，生成一个新节点Nn。然后检查新节点Nn与其父节点Nc之间有无障碍物，若无障碍物，则将该新节点Nn加入到扩展随机树上作为子节点，若新节点Nn与其父节点Nc之间有障碍物，则重新生成随机点Nr，重复以上步骤。其节点扩展方法如图2 所示。当扩展随机树中子节点接近目标点Ng,并且两点之间的距离在设定领域范围之内，则停止扩展并从目标节点Ng进行回溯，直到起点Ns。然后返回一条从起点Ns到目标点Ng的无障碍飞行航路，算法结束。

图2 传统RRT算法节点扩展方法

RRT 算法的基本思想是像树一样快速扩张以探索安全区域，从而找到可行路径，搜索节点的随机性保证了算法的探索能力和搜索速度，使该算法不受任务复杂度与空间复杂度的影响。此外，由于其实现原理相对简单，且该算法能够满足许多通用情况下的路径规划需求，因此被大量应用于机器人路径规划、无人驾驶寻找路径等领域中。但是，正是由于其节点选择的随机性大，传统RRT 算法在构造随机树的过程中会产生大量冗余节点，当空间从二维扩展到三维时，求解过程所需要的存储空间呈线性上升，还会由于扩展过多无用节点造成搜索时间的增加。且由于其扩展过程中生长步长的固定，生成的路径灵活性较低，路径一般较为曲折，这可能会导致航路的延长。

因此，为了进一步优化RRT 算法，文献[14]提出了RRT*算法，通过最优准则重选父节点，提高了算法全局搜索的效率；文献[15]提出了双向RRT 算法，通过从初始点和目标点同时扩展随机树来加快搜索速度；文献[16]提出了DRT-RRT*算法，利用反向生长最优快速搜索随机树的实时采样重规划算法。

在该文算法应用环境中，无人机执行作战任务的战场环境已知，因此，文中拟综合改进传统RRT 算法，在保证其搜索随机性的同时，提高算法收敛速度，并尽可能提高其生成航路的平滑性。

2.2 引力场引导随机树生长

为了减少随机树生长过程中产生的冗余节点，优化求解过程存储空间，降低传统RRT 算法在搜索过程中的随机性，文中根据无人机作战任务环境涉及到的作战区域以及对抗要素，参考人工势场算法的目标导向作用，建立了引力场用来引导随机树节点向目标的生长，以此来减少RRT 算法航路搜索时间，加快算法收敛速度。

在传统RRT 算法的基础上，建立以目标为导向的引力场引导随机树的扩展，在随机树节点扩展时，对生长节点Nn(xn,yn)构造引力函数Fg，其公式如下：

其中，Nn(xn,yn)为生长节点在任务空间中的位置，xn和yn分别为其横坐标与纵坐标，Ng(xg,yg)为目标节点在任务空间中的位置，kg为引力常数，r(·)表示两个节点在任务空间中的欧氏距离。每一次节点的扩展生长除了由随机采样点Nr的方向与固定生长步长step_length 决定外，还受到目标点对该生长节点引力的作用，使得扩展节点在选择方向时，向着目标点的方向快速生长。需要注意的是，为了保持传统RRT 算法的随机性，当扩展节点越靠近目标，所受目标节点的引力就越小，这同时也是为了减少随机节点在朝向目标生长时陷入局部最优的可能性。

2.3 动态生长步长策略

传统RRT 算法生长步长固定，当选择步长较小时，生成无人机航路的时间较长，且由于生长节点过多且曲折，导致无人机在实际飞行过程中需要频繁调整航向，由于其本身的性能限制，无人机在实际飞行中可能无法达到完美契合规划路径的状态。因而从理论上来讲，固定生长步长越大，生成无人机航路的速度就越快。但是，当固定生长步长过大时，无人机遇到障碍物后需要花费更多的时间来避开，反而可能造成搜索速度的下降、航路的延长，且由于步长过大，生长节点在到达目标点附近时，可能会反复震荡，无法接近目标，这不符合无人机在实际环境中执行作战任务的通常规则[17-18]。

因此，该文提出了动态生长步长策略，该策略的基本思想是通过判断随机树上新节点与障碍物之间的距离动态确定生长步长，当节点生长过程中遇到障碍物时，根据无人机实际飞行中能够达到的最小转向距离确定新的步长；无人机绕过障碍物后，可以使步长适当增加，加快在安全区域中生成航路的速度，减少搜索时间。对于节点生长步长ρnode的调整如下：

其中，ρfixed为固定生长步长，ρmin是根据无人机性能设定的最小转向距离，Dnode是生长节点与最近障碍物之间的距离。当新的节点Nn与其父节点Nc之间有障碍物时，需要较为谨慎的避开障碍物，因此，根据ρmin小范围调整前进距离与方向使其灵活避开障碍物。绕过障碍物后，在安全区域按照固定生长步长大幅度调整前进距离。该动态生长步长选择策略不仅可以使无人机灵活避开障碍物，增加了算法生成航路的平滑性，也在一定程度上提高了航路生成速度。

2.4 算法流程设计

在综合考虑引力场引导随机树生长和动态生长步长策略后，算法的具体流程如下：

步骤1：初始化任务空间地图，生成起点Ns、目标点Ng，根据无人机性能确定ρmin，根据任务空间地图区域大小确定ρfixed，同时将生长步长ρnode设定为ρfixed，将起点Ns存入随机树节点列表node_list中。

步骤2：计算node_list 中新加入的节点Nn与目标节点Ng的距离r，当该距离大于生长步长ρnode时，进入步骤3，否则，确定为成功找到路径，从目标点Ng回溯节点直到起点Ns生成路径，结束程序并绘图。

步骤3：在任务空间中随机选取节点Nr，在节点列表node_list 中找到距离Nr最近的节点Nc，以Nc与随机节点Nr的连线作为扩展方向，以生长步长ρnode为距离，以最近的节点Nc为父节点，生成一个新节点Nn。

步骤4：判断新节点Nn与其父节点Nc之间有无障碍物，若有，确定生长步长ρnode为ρmin，然后返回步骤3，否则确定生长步长ρnode为ρfixed，执行步骤5。

步骤5：判断Nn的引力值，若Nn的引力值大于其父节点Nc的引力值，则返回步骤3，否则，将该新节点加入到node_list 中作为子节点，进入步骤2。

算法具体流程如图3 所示。

图3 综合改进算法流程图

3 实验结果对比分析

为了验证综合改进后的RRT 算法在上述无人机航路规划场景中的效果，该算法在Matlab R2016a 中进行仿真验证，实验计算机为联想笔记本电脑，处理器为Core(TM) i7-1065G7，频率为1.30 GHz，内存为16 GB。在仿真验证中，根据无人机飞行性能设定ρmin为0.2 km，根据任务空间地图区域大小以及障碍物确定ρfixed为0.5 km，起点Ns(0,0) km、目标点Ng(9.5,9.5)km。同时，考虑到RRT 算法的随机性，单次或者少数实验不能保证实验结果的准确性，因此，在相同场景下进行100 次规划航路实验，取运算结果平均值作为实验结果。

对传统RRT 算法、加入引力场引导随机树的RRT 算法、动态生长步长策略的RRT 算法、综合改进RRT 算法进行比较，四种算法在比较过程中应保持初始参数一致，图4（a）、（b）、（c）、（d）四幅图分别展示了四种算法在任务空间中扩展的随机树。从图4可以看出，加入引力场的算法在随机树扩展过程中更加具有目标性和方向性，其扩展出随机树的树枝相较于传统算法有明显的减少。这表明，引力场引导随机树可以有效地减少随机树分支、冗余节点的产生，而加入动态生长步长策略的算法生成的无人机航路相较于传统RRT 算法路径更加平滑，比较符合无人机在实际飞行过程中的状态。综合改进的RRT 算法集成了上述两种算法的优势，其扩展树相较于其他三种算法，不仅在搜索节点上具有目标性，扩展树分支较少，且形成的路径更加平滑。

图4 算法搜索路径对比图

表1 为传统RRT 算法、加入引力场引导随机树的RRT 算法、动态生长步长策略的RRT 算法以及综合改进的RRT 算法四种算法的实验仿真数据。从表中数据可以看出，传统RRT 算法在扩展过程中搜索的节点较多，航路较长，且产生航路的时间普遍偏长。由引力场引导的RRT 算法相较于传统RRT 算法在搜索时间上节省了63.4%，路径节点减少了6.7%，这表明，引力场引导随机树节点的生长能够有效缩短搜索航路的时间。加入动态生长步长策略的RRT 算法相较于传统RRT 算法在搜索时间上节省了80.1%，路径节点减少了57.3%，这表明动态调整生长步长可以明显减少路径节点的数量，并且加快算法收敛速率。综合改进的RRT 算法，较传统RRT 算法的优势更加明显，不仅在搜索时间上节省了86.5%，且路径节点减少幅度更大，为58.4%。

表1 算法仿真测试结果

实验数据充分证明，综合改进的RRT 算法，相较于传统RRT 算法，扩展节点数量少、收敛速度快、时间效率高、路径更平滑、避障更加灵活，在整体性能上优于传统RRT 算法，更加符合无人机实际飞行情况，有利于无人机在作战任务中更好地发挥性能。

4 结束语

该文提出了一种综合改进的RRT 算法，针对无人机在实际战场环境中执行作战任务的飞行航路生成问题展开研究。针对传统RRT 算法随机性强、生长步长固定等问题，将引力场引导随机树扩展和动态生长步长选择两种策略结合起来融入传统RRT 算法的改进中，既保证了RRT 算法具有一定的随机性，又使RRT 算法在收敛速度、搜索时间、计算效率与路径平滑度等方面拥有更优的性能。同时，有效利用了战场环境、无人机性能等已知条件，实现了无人机在任务空间中快速生成有效航路和避障的能力。最后，通过仿真实验结果验证了改进的RRT 算法具有更佳的效果。

在下一步的研究中，会将该算法扩展应用于战场环境更加复杂的实际地理空间中，同时考虑战场环境态势的动态变化，以及更为复杂的对抗要素，根据给定的模型初始参数动态生成自适应的无人机优选航路信息，进一步改进优化无人机作战航路规划算法。