基于改进的RRT车辆路径规划

户望力

基于改进的RRT车辆路径规划

户望力

（长安大学 汽车学院，陕西 西安 710000）

文章针对基础RRT算法的不足即搜索的盲目性与复杂条件下较差的适应性，对基础RRT算法进行改进，通过对扩展节点的条件进行约束，使得车辆进行路径规划时更加具有方向性，能够实现对物体的绕行，以快速地寻找出可行的路径。最后通过MATLAB进行仿真，验证了改进算法在简单条件与复杂条件（狭小通道）下路径规划的有效性。

路径规划；RRT算法；智能驾驶

前言

近年来，随着人们对机器学习与深度学习的深入研究，人工智能进入了快速的发展阶段，再加上5G网络的兴起，深度机器学习更是如鱼得水，已经渗透到了各种行业之中。对于汽车的研究，更是向着智能驾驶的方向发展。从研究的进展来看，对于智能驾驶的研究大多数企业均已进入了L3阶段，甚至有些汽车企业已经进入L4阶段的研究。而对于智能汽车的研究，其车辆路径规划是高级智能汽车的必经之路。目前，对于车辆路径规划具有很多的方法，常见的算法有：Astar、Dstar、RRT、Hybrid Astar等。对于不同的算法都有其优缺点。总体而言，无论哪种算法其最重要的问题就是算法的实时性与精确性这两者的平衡。一般而言，两者是呈现负相关的关系，即要想使算法具有较高的精度就必须牺牲相应的时间。好在随着5G网络及芯片的快速发展，研发人员研制出了针对不同的处理数据的CPU、GPU，使得对数据的处理能力得到了快速的提高。

车辆路径规划包含全局路径规划和局部路径规划，亦称静态规划、动态规划。是指车辆在运行的环境中，按照一定的规则，从目标位置寻找一条可行路径达到目标位置且不与静态或动态的障碍物发生碰撞[1]。对于静态的路径规划相对简单，车辆通过传感器设备或者智能网联获取车辆周围的环境信息，然后通过地图搜索，寻找出可行路径。而动态路径规划由于周围环境是时刻变化的，需要实时更新获取周围环境信息，对于算法的实时性要求较高。

RRT（Rapidly-Exploring Random Tree）快速扩展随机树是一种基于采样的规划算法，由Steven.M.LaValle提出。其优点是不必对周围环境进行建模，而是具有方向性的向目标点进行采样检测，从而绕过障碍物达到目标点，系统的复杂性小，所以该方法适合解决高维度空间和复杂约束的机器人路径规划问题[2]。但是该算法也具有一定的缺陷：（1）由于采样的盲目性，所以搜索的效率低；（2）寻求的路径一般不是最优路径。（3）对于一些复杂的环境（狭窄的通道），RRT算法很难寻找出路径[3]。

图1 RRT的发展历程

经过几十年的发展，RRT的缺点得到了很大的改善。图1为RRT算法的发展历程，针对其不同的缺点，RRT发展出了不同的变体，其中RRT-connect/B-RRT通过采用两颗快速扩展随机树（从起始点与目标点同时开始）搜索空间，每次选取支点较少的随机树进行扩展，直至两颗随机树相连完成搜索，使得搜索的性能有了显著的提高；RRT*算法主要针对的是路径优化问题，它能快速地找出初始路径，随着采样点的增加，不断地进行优化直到程序终止，所以RRT*的缺点就是对运算时间要求较高。B-RRT*相对于B-RRT的区别在于前者能够在扩展采样节点的同时能够对父节点进行重选，通过对比将最短路径的节点作为待选父节点，从而实现了对搜索路径的优化。

本文通过对RRT算法进行改进，根据障碍物的位置对扩展节点进行有目的的采样，实现对障碍物的绕行，已实现对路径的快速规划，且在某些复杂的环境下（狭小通道），改进的RRT依旧具有较为明显的优势。最后通过MATLAB仿真分析，来验证该算法的有效性。

1 RRT算法介绍

1.1 RRT算法基本原理

RRT算法基本原理如图2所示：以起始点qinit作为树的根节点，然后在自由空间中以设定的概率prand随机选取采样点qrand，或者以概率pgoal选取目标点qgoal作为采样点，选取距离采样点qrand最近的父节点qnear作为随机树的扩展对象，然后按照设定的步长ρ在qnear至qrand方向产生下一个待选父节点qnew，判断候选节点qnew是否满足条件（是否在障碍物内，是否超出规划区域等），若满足条件，将节点qnew加入到父节点之中，按照此方式继续扩展随机树直至达到目标点qgoal，或者达到最大迭代次数[4]。

图2 RRT算法路径规划过程

1.2 改进的RRT算法

有别于基础的RRT算法，本文在此基础上，对RRT算法父节点进行有目的的选取。其目的在于实现障碍物的绕行，然后直接到达目标点位置。其思想是根据人的寻路逻辑进行设计，如图3所示，行人在目的地已知的条件下，要想达到目的地，必须要绕过河流，即目的地方向内的障碍物，然后才能达到目的地，而对目的地方向以外的障碍物不会给予考虑。根据此原理，本文对RRT算法进行改进，设计了主动绕行路径上障碍物的方法，从而能够快速达到目的地。该方法能够减少基础RRT算法的盲目性，并且对一些特殊的环境也具有很好的适用性，图4为改进的RRT算法的工作流程图。

图3 行人寻路图

图4 改进的RRT工作流程图

1.3 障碍物绕行决策方法

随机树在沿着目标点的方向前进时，如果检测到前方具有障碍物，树的节点会根据障碍物的形状进行自动绕行，其方法采用试探法，在探索方向上分别向左和右侧偏离一个角的δ，若仍然具有障碍物，则继续偏离角度δ，直到产生新的节点qnew1与qnew2。为了增加搜索的速度，本文根据节点下降的梯度对qnear进行有目的的选取。其执行的示意图如图5所示。绿点qinit为数根节点，黄色点q2为树的分叉点，qgoal为目标点。

图5 障碍物绕行原理图

2 MATLAB算法仿真验证

2.1 运行环境

表1 仿真环境

2.2 仿真结果分析

为了验证提出的改进的RRT算法的有效性，运用MATLAB分别对基础的RRT算法和改进的RRT算法进行仿真。图6-9为两种算法的一种仿真结果。在30次的仿真结果中，基础RRT算法的平均仿真时长为8.34秒，改进的RRT算法平均仿真时长为3.77秒。从仿真结果可以看出，改进的RRT算法减少了对目标的盲目探索，对简单环境下的路径规划具有很好的适用性。

图6 基础RRT仿真图

图7 基础RRT仿真路径

图8 改进RRT仿真图

图9 改进RRT仿真路径

为了验证改进RRT在狭小通道的有效性，本文设置了如图10-13所示的仿真环境，在30次的仿真结果中，基础RRT算法失败次数为3次，改进RRT算法的失败次数为0。从仿真结果可以看出，在复杂的环境下（狭小通道），改进的RRT依旧具有较为明显的优势。

图10 基础RRT仿真图

图11 基础RRT仿真路径

图12 改进RRT仿真图

图13 改进RRT仿真路径

3 总结

本文通过对基础RRT算法的改进，优化了基础算法路径搜索的随机性，且在复杂环境下也具有较好的适用性，使得算法的性能得到了较大的提高。但是对于情况较为复杂的环境，如障碍物过多的条件下，使得搜索的路径较长，所以对于接下来的研究，将会注重对搜索结果的优化之上。

[1] 黄淑彤.浅论车辆路径规划的算法[J].中国科技纵横,2019,003 (000):32-34.

[2] 施杨洋,杨家富,布升强,朱林峰.基于RRT改进的智能车辆路径规划算法[J].计算技术与自动化,2019,38(04):81-86.

[3] 刘晓倩,张辉,王英健.基于改进RRT的路径规划算法[J].自动化技术与应用,2019(5):96-100.

[4] 刘恩海,高文斌,孔瑞平,等.改进的RRT路径规划算法[J].计算机工程与设计,2019,40(8):2253-2258.

Based on Improved RRT Vehicle Path Planning

Hu Wangli

( School of Automobile, Chang’ an University, Shaanxi Xi’an 710000 )

In this paper, aiming at the shortcomings of the basic RRT algorithm under complex conditions, the blindness of the search and poor adaptability, to improve the basic RRT algorithm, based on the extension node constraint conditions, the vehicle for path planning more directional, can achieve the object around, to quickly find out the feasible path.At last, MATLAB is used for simulation to verify the effectiveness of the improved algorithm under simple and complex conditions (narrow channels).

Path planning; RRT algorithm; Intelligent driving

10.16638/j.cnki.1671-7988.2021.06.014

U462

A

1671-7988(2021)06-45-03

U495

A

1671-7988(2021)06-45-03

户望力，硕士研究生，就读于长安大学汽车学院交通运输工程专业，研究方向：载运工具运用工程。