基于RRT算法的无人机路径规划应用研究

任鹏博，董泽华

基于RRT算法的无人机路径规划应用研究

任鹏博，董泽华

（中国电子科技集团公司第二十研究所，西安 710068）

经典的路径规划算法大都需要在全局已知空间中对环境进行建模，包括人工势场法、遗传算法、启发式算法、仿生学算法等。由于需要预先构建环境，因此这些方法并不适合解决在高维度空间中的路径规划问题。基于快速扩展随机树（RRT）的路径规划方式其优势在于可以避免对全局环境的构建，通过对状态空间进行随机采样，检测碰撞点，能够有效地解决在平面及三维状态空间下的复杂路径规划问题。通过与人工势场法和A*算法进行比对，确定了RRT算法在复杂环境中解决无人机路径规划问题的优势，在对相关参数进行优化后该方法是概率完备且存在最优解的，同时在固定翼智能集群飞行编队控制及协同项目中应用。

无人机；路径规划；RRT算法

0 引言

无人机的航迹规划是在地形环境、外部威胁和机动性能三者综合约束条件下，规划出一条从任务起始点到目标点的最优飞行航线[1]。地形环境主要考虑飞行中不同海拔的山地因素；外部威胁主要考虑路径生成中的敌方导弹威胁、电磁干扰威胁、外部障碍威胁等；无人机的机动性能主要考虑无人机的飞行速度、最大航程、最大转弯角、最大爬升俯冲角、飞行高度等性能约束。当前全局路径规划中比较常规的算法包括人工势场法、启发算法的A*算法、仿生算法的蚁群算法，以及这些算法的优化改进算法，但这些路径规划算法都需要事先完成对空间内的障碍物等环境进行建模，不适合解决无人机在复杂环境中的全局路径预规划问题[2]。本文主要研究快速扩展随机树算法（Rapidly Exploring Random Tree，RRT）在固定翼智能集群飞行编队控制及协同项目中路径规划的应用与实现。

1 无人机全局路径规划算法研究

1.1 人工势场法

人工势场法的算法思想是受到电荷在电场中的运动特点的启发，将移动主体单位当做一个带电的电荷，其所处环境相当于一个复杂的电场[3]，其环境中的所有障碍物均带与移动单位相同的电荷，而目标点则为异种电荷，因此，移动单位与障碍物之间产生斥力，与目标点产生引力。这样，在障碍物与目标点的复杂合力作用下，对无人机的飞行路径进行规划。人工势场法的基本原理如图1所示，在已知无人机初始状态、目标位置以及障碍物位置的基础上，人工势场法产生一条安全平滑机动能耗小的飞行路线[4]。人工势场算法的流程图如图2所示。

图2 人工势场算法的流程图

通过将无人机所在的任务区间使用一定的势场函数进行设置，具体分为两部分，无人机与障碍物间的作用力用斥力势场函数表示，而与目标点之间的相互作用力则使用引力势场函数描述。

势场函数的具体表示如下，其中无人机与目标点之间产生的吸引力势场函数如式（1）所示：

另一方面，无人机对障碍物产生的斥力由斥力势场函数所产生，无人机与障碍物之间产生的排斥力势场函数如式（2）所示：

1.2 A*路径规划算法

在构建好的队列中，每个节点都会指向其前面的那个节点，目标节点将指向其前导节点，依此类推，直到某个节点的前导是开始节点。这样就得到了一条从初始点到达目标点的最短路径序列，A*算法流程如图3所示。

图3 A*路径规划算法流程图

1.3 RRT路径规划算法

相较于传统的路径规划算法，RRT算法具有无需事先对任务环境进行建模的优势，其本质是通过构建一棵随机搜索树对未知环境空间进行探索，将根节点设置为起始点，探索点的随机性保证了目标点探索的概率完备性，有利于在多维空间下的路径探索，可以解决具有非完整约束的路径规划问题[8]。RRT路径规划算法流程如图4所示，利用搜索策略进行设定区域内搜索，找到下一个待扩展的叶节点；然后利用步长策略作为判定条件实现随机树扩展生长，最后获得无人机初始点到达目标点的规划路径[9]。

RRT路径规划算法是一种在多维空间路径规划过程效率较高的方法，通常从状态空间中的一个初始点出发，初始点作为根节点，通过随机采样扩展的方式来增加叶子节点进而生成一个随机扩展树，当随机树中的叶子节点包含了目标点或进入目标区域，便可以在随机扩展树中至少找到一条从初始点到目标点的路径信息[10]。

图4 RRT路径规划算法流程图

图5 RRT的节点扩展过程示意图

1.4 路径规划算法分析

传统的路径规划算法受限于必须在静态环境中对周遭空间进行建模，其路径规划的效率受到状态空间大小的影响，主要是移动主体的动作空间，即无人机的自由度，其算法时间复杂度呈指数递增。因此，经典的路径规划算法不利于解决多自由度机器人的路径规划问题。基于RRT的方式可以省去以往的对状态空间的建模过程，并能同时解决高维空间下及多约束条件下的路径规划问题。结合多种路径规划算法的优缺点分析选择RRT算法作为固定翼无人机路径规划算法，并在固定翼智能集群飞行编队控制及协同项目中应用，常规路径规划算法优缺点如表1所示。

表1 路径规划算法优缺点对比

2 仿真验证与分析

为了验证RRT路径规划算法在无人机运动平台中路径规划的有效性，本文在Windows 10操作系统，Intel（R）Core（TM）i7-9700K CPU @ 3.6 GHz,内存16 GB实验环境中基于PyCharm 2021.1（Community Edition）编译工具实现RRT路径规划算法的仿真与分析。

2.1 二维任务空间仿真实验

图6 二维任务空间路径规划效果图

2.2 三维任务空间仿真实验

图7 三维任务空间路径规划效果图

3 结论

RRT算法的优势不仅体现在二维空间，高维空间中的路径搜索同样有效。RRT算法对整个区域空间进行更为充分的搜索，能够应对更为复杂的障碍物情况下路径规划问题。在仿真实验中可以发现，通过设置合适的随机概率使无人机能够在保持向目标点探索的基础上增加寻找到完整路径的概率，加强目标点导向性，设置适当的搜索步长则确保了无人机既可以从多障碍物中找到通路又可以减少规划迭代的次数。实验结果表明RRT算法不仅能够在高位空间中快速寻找到较优路径的能力，另一方面还可以保证规划路径的相对平滑，目前在RRT路径规划算法在固定翼智能集群飞行编队控制及协同项目中已应用并取得较好的效果。

[1] 成浩浩，杨森，齐晓慧. 基于改进RRT算法的四旋翼无人机航迹规划[J]. 计算机工程与设计，2018（12）：115-118.

[2] 张建英，赵志萍，刘暾. 基于人工势场法的机器人路径规划[J]. 哈尔滨工业大学学报，2006，38（8）：1306-1309.

[3] 文勇，张怀相，曾虹. 新型势场法的移动机器人避障研究[J]. 杭州电子科技大学学报，2009，29（1）：50-53.

[4] 卫珊，王凌，王斌锐. A*算法的改进及其在AGV路径规划中的应用[J]. 自动化仪表，2017（11）：246-251.

[5] 范伟伦，李薇，冯杭. 基于改进RRT算法的无人机实时航迹规划[J]. 舰船电子工程，2019（2）：333-337.

[6] 李洋，徐达，周诚. 基于自适应步长RRT的双机器人协同路径规划[J]. 农业机械学报，2019（3）：1016-1021.

[7] 刘晓倩，张辉，王英健. 基于改进RRT的路径规划算法[J]. 自动化技术与应用，2019（5）：454-459.

[8] 张艺巍，谭建豪，王耀南. 3维复杂山地环境下旋翼无人飞行器高时效航迹规划策略[J]. 机器人，2016，38（6）：727-737.

[9] 陈淼. 自转式无人旋翼机飞行控制技术研究[D]. 南京：南京航空航天大学，2012：56-61.

[10] 卢恩超，张邓斓，宁雅男，等. 改进人工势场法的机器人航迹规划[J]. 西北大学学报（自然科学版），2012，42（5）：735-738.

[11] 田晓亮. 无人机航迹规划方法研究[D]. 西安：西安电子科技大学，2014：28-29.

Research on UAV Path Planning Application Based on RRT Algorithm

REN Pengbo, DONG Zehua

Traditional global path planning algorithms include artificial potential field method, genetic algorithm, intelligent bionics algorithm, heuristic algorithm and so on. However, these methods all need to model obstacles in the known global space, and are not suitable for solving the planning problem of multi-degree-of-freedom robots in complex environments. The path planning algorithm based on rapidly exploring random tree, through the collision monitoring of sampling points in the state space, avoids the modeling of the global space, and can effectively solve the path planning problems of high-dimensional space and complex constraints. By comparing with the artificial potential field method and the A*algorithm, the advantages of the RRT algorithm in solving the UAV path planning problem in a complex environment is determined in the paper. After optimizing the relevant parameters, the method is probabilistic and has an optimal solution, and applied in the Fixed-wing intelligent cluster flight formation control and coordination project at the same time.

UAV; Path Planning; RRT Algorithm

V279

A

1674-7976-(2022)-01-062-05

2021-10-15。

任鹏博（1995.02—），陕西咸阳人，硕士研究生，主要研究方向为信号检测与信号处理。