基于RRT算法的无人驾驶车辆路径规划方法研究

刘 芙，陈宏明

(1.淮阴商业学校实训处，江苏 淮安 223003)

(2.淮阴工学院应用技术学院，江苏 淮安 223003)

汽车保有量增加一方面易导致交通更加拥堵，另一方面导致交通事故频发。所有的交通事故中高达90%以上的事故都是由驾驶员驾驶不规范导致的，因此加大对无人驾驶车辆的研发，避免不规范的驾驶以减少交通事故的发生就变得至关重要。无人驾驶车辆路径规划是无人驾驶车辆研发的核心，其任务是规划一条从起始点到目标点的可行驶路径[1]。无人驾驶车辆在行驶的过程中必须满足车辆的可行性约束条件，做到不和静态、动态障碍物碰撞，车辆在不同的驾驶场景下保持良好的性能，具有良好的环境适应性。本文对快速扩展随机树(RRT)算法进行研究，并对其进行改进，将RRT算法应用于无人驾驶车辆的路径规划中，为无人驾驶车辆路径规划提供了一种新的方法。

1 无人驾驶车辆路径规划技术

1.1 无人驾驶车辆路径规划定义

无人驾驶车辆路径规划就是已知无人驾驶车辆的起始位置、目标位置、车辆的姿态、障碍物的分布，在此基础上规划出不与环境障碍物碰撞、满足车辆运动学约束的路径。本文主要讨论基于二维平面的无人驾驶车辆路径规划问题。定义无人驾驶车辆的状态为q，q=[x,y,θ]，其中，x为车辆质心横坐标位置，y为车辆质心纵坐标位置，θ为车身的横摆角。无人驾驶车辆从起始位置到目标位置所有状态构成的状态空间为C，车辆的初始状态为qi，车辆的目标状态为qg，整个二维平面的状态空间为Ω，障碍物的状态空间为Qo，不和障碍物碰撞的无人驾驶车辆状态空间为Qf，则：

(1)

无人驾驶车辆路径规划问题就是在Qf中去寻找车辆初始状态qi到车辆目标状态qg的关系，即：

C[qi,qg]∈Qf

(2)

同时，无人驾驶车辆路径规划的每一个状态必须满足车辆的可行性约束条件。

1.2 无人驾驶车辆运动学建模

无人驾驶车辆在车速比较低时可以通过自行车模型来进行车辆的运动学建模，所建立的无人驾驶车辆运动学模型如图1所示[2]。其中，(Xr，Yr)为无人驾驶车辆后轴轴心的坐标，(Xf，Yf)为无人驾驶车辆前轴轴心的坐标，φ为无人驾驶车辆车身横摆角，δf为无人驾驶车辆前轮偏角，vr为无人驾驶车辆后轴轴心的速度，vf为无人驾驶车辆前轴轴心的速度，l为无人驾驶车辆的轴距，R为无人驾驶车辆后轮的转弯半径。

图1 无人驾驶车辆运动学模型

由运动学关系可知：

(3)

不考虑无人驾驶车辆在运动过程中的侧滑，那么：

(4)

根据无人驾驶车辆前轮和后轮的几何关系可知：

(5)

联立式(3)～(5)，可得无人驾驶车辆的横摆角速度ω为：

(6)

由理论力学和数学知识可知：

(7)

在对无人驾驶车辆路径规划的过程中必须对无人驾驶车辆的最小转弯半径进行限制，即所规划路径的曲率要小于曲率的最大值，曲率k的计算公式为：

(8)

1.3 无人驾驶车辆路径规划标准

无人驾驶车辆路径规划的核心是规划一条满足车辆行驶安全、车辆运动学约束等硬要求，同时兼顾对环境的适应性、最优性、实时性、舒适性等软要求的路径。安全性就是要确保车辆和环境中障碍物不发生碰撞，满足车辆运动学约束就是规划路径中弯道的曲率满足车辆最小转弯半径限制。环境的适应性就是规划的路径适应不同的环境路径，常常采用平均路径长度来衡量。最优性就是确保路径规划所需要的时间最短，所规划路径的平均长度最短等。不同的路径规划问题其最优性指标不同。实时性就是无人驾驶车辆可以快速对实时路况给予响应，往往用平均路径规划时间来衡量。舒适性是所规划路径要尽量平滑，其所规划路径中弯道的最大曲率要比较小。本文采用平均采样点数目、路径规划时间、平均路径长度和最大曲率4个指标来衡量无人驾驶车辆路径规划算法的优劣。

2 无人驾驶车辆路径规划的RRT算法研究

2.1 RRT算法

1998年，Lavalle首次提出了RRT算法。采用RRT算法进行无人驾驶车辆路径规划步骤如下[3]：

1)以无人驾驶车辆的起始状态qi为起始节点来初始化随机树T，同时在Qf空间中随机采样一个节点为qr。借助于距离评估函数对随机树T中的节点进行遍历，找出距离随机树T最近的节点qn。

2)从节点qn向节点qr前进单位步长，生成新的节点qnew。如果节点qn和节点qnew之间没有和障碍物发生碰撞，那么将其添加到随机树T中；反之，不对随机树T进行修改。

3)重复步骤2)，直到新的节点中包含有车辆的目标状态qg为止。通过回溯法就可以在随机树T中获得从起始状态qi到目标状态qg的规划路径。

无人驾驶车辆路径规划的RRT算法流程图如图2所示。

图2 无人驾驶车辆路径规划RRT算法流程图

通过对RRT算法的分析可知，采用RRT算法虽然可以在各种复杂环境下进行无人驾驶车辆的路径规划，但是该算法是一种随机搜索算法，存在一定的不足。例如同样的环境每次规划的路径却不相同，即可重复性较差；寻找最优路径的能力较差。另外由于需要在整个Qf区域内采点来随机寻找最近的节点，计算量较大，导致路径规划的计算时间增加。

2.2 RRT算法改进

2.2.1RRT算法改进思路

针对RRT算法的不足，对RRT算法进行改进。在对随机树的节点进行拓展时以一定概率选择目标点作为采样点的策略，加快在随机树中拓展到目标节点qg的速度；采用新的碰撞检测算法来快速检测新的节点和新的边是否与环境中的障碍物发生了碰撞，以确保所规划的路径是安全的[4]；针对算法中所产生的折线段进行剪枝处理，在很大程度上使生成的规划路径长度大大缩短，使车辆由起始位置到目标位置的不必要转向大大减少，以确保无人驾驶车辆路径的舒适性。另外，为了提高无人驾驶车辆路径规划的成功率，使路径规划的效率大大提升，可以采取无人驾驶车辆初始位置和目标位置双向拓展的办法。

2.2.2人工势场法的拓展域生成

人工势场法由Khatib提出，其将无人驾驶车辆的运动轨迹看作是在虚拟力场中的受力运动，环境中的障碍物对无人驾驶车辆产生排斥力，目的地对无人驾驶车辆产生吸引力，在排斥力和吸引力的共同作用下，无人驾驶车辆由起始点向目标点运动[5]。

常用的引力场函数为：

(9)

式中：Ua为吸引力；ζ1为引力尺度因子；ρ1为无人驾驶车辆当前所在节点和目标节点之间的距离。

常用的排斥力场函数为：

(10)

式中：Ur为排斥力；ζ2为排斥力尺度因子；ρ2为无人驾驶车辆当前所在节点与障碍物之间的距离；ρ0为环境中每一个障碍物的影响半径。

在排斥力和吸引力的共同作用下，无人驾驶车辆在环境中所受到的力U为吸引力Ua与排斥力Ur之和[6]，即：

U=Ua+Ur

(11)

2.2.3RRT算法和人工势场联合路径规划

采用RRT算法对无人驾驶车辆进行路径规划时，在整个环境空间中节点的选择具有很大的盲目性，这使得单纯利用RRT算法进行无人驾驶车辆的路径规划效率比较低，同时所得到的规划路线比较长，需要车辆进行多次转向操作，不能够满足车辆的行使舒适性和环境适应性要求。基于此，将人工势场引入其中，利用人工势场法来获得拓展域，这样可以在很大程度上提升RRT算法对无人驾驶车辆路径规划的效率。RRT和人工势场联合的无人驾驶车辆路径规划算法流程如图3所示。

图3 RRT和人工势场联合的车辆路径规划算法流程

3 无人驾驶车辆路径规划仿真分析

3.1 仿真试验

本文采用MATLAB搭建含障碍物的试验环境，采用仿真试验来对比RRT算法和RRT与人工势场联合算法在对无人驾驶车辆路径规划方面的性能。利用MATLAB软件构建500 m×500 m大小的正方形区域，在正方形区域内构建有3个障碍物，如图4中所示，其中黑色区域为障碍物所在区域。设定无人驾驶车辆的起始位置坐标为(10 m，10 m)，目标位置坐标为(490 m，490 m)。采用RRT算法对无人驾驶车辆进行路径规划，路径规划结果如图4(a)所示，图中长条线条为RRT算法规划的路径，分支线条为采用RRT算法生产的随机扩展树；采用RRT与人工势场联合算法对无人驾驶车辆进行路径规划，路径规划结果如图4(b)所示，图中灰色区域内的分支路径为RRT与人工势场联合算法规划的路径。

图4 两种算法路径规划结果

3.2 仿真结果对比分析

为了更好地对比RRT算法和RRT与人工势场联合算法在无人驾驶车辆路径规划方面的性能，对两种算法的平均采样节点数、路径规划时间、规划路径平均长度、规划路径最大曲率进行对比，结果见表1。

表1 两种算法结果对比

由表1可见， RRT与人工势场联合算法的平均采样节点数、路径规划时间均比RRT算法减少了约50%，平均路径长度缩短接近50%，所规划路径的最大曲率也只有RRT算法的约1/6。由此说明，采用RRT与人工势场联合算法对无人驾驶车辆进行路径规划，其性能要远远优于RRT算法，RRT与人工势场联合算法的效率更高，对实际的无人驾驶车辆路径规划更为有效。

4 结束语

车辆无人驾驶可以在很大程度上降低由于人工不规范驾驶造成的交通事故数量。本文对无人驾驶车辆路径规划问题进行了研究，在RRT算法的基础上提出了RRT与人工势场联合的无人驾驶车辆路径规划算法，仿真试验也验证了该算法可大大缩短规划路径的长度，减少无人驾驶车辆从起始点到目标点过程中许多不必要的转向，提高了规划路径的车辆舒适性。本文的研究对于无人驾驶车辆的路径规划具有一定的参考价值。