基于改进RRT算法的无人车路径规划研究

关键词：RRT算法；目标偏置策略；障碍物膨胀策略；启发式贪心思想；三次B样条曲线

0 引言

近些年来，随着科技的进步，汽车无人驾驶技术得到了迅速发展。新一代智能汽车研究已成为产业革命的重要方向[1]。无人驾驶汽车具有提高道路安全性、减少交通事故和拥堵、降低交通成本、提高出行舒适度、满足特定出行需求、节能环保等优点，为人类出行带来更加安全、高效、便捷和环保的体验。因此，对无人驾驶汽车领域的研究变得越发重要，引起了众多科研人员的广泛关注。

路径规划是无人车智能驾驶技术中的关键技术之一。为了使无人车根据预定地图到达指定目的地，需要在地图上进行路径规划，并采用合适的路径规划算法。常见的全局路径规划算法包括Dijkstra算法[2]、A*算法[3]、蚁群算法[4]、RRT 算法[5] 等。其中，RRT（Rapidly-exploring Random Tree） 算法是一种基于树结构的随机采样路径规划算法。它通过不断随机采样状态空间中的点，并将其连接到树上已有节点的方式，逐步生成一棵覆盖整个状态空间的树。RRT算法具有简单易实现、适应性强等优点。然而，其缺点也较为明显，对RRT算法的缺点，尽管国内外学者对其进行了多种改进，以提升其在不同场景下的表现，但仍存在一些共性问题。

文献[5]采用双向改进RRT算法并结合人工势场法，解决了RRT算法在随机性和计算量较大的问题，从而提高了算法的寻优精度和路径规划速度。文献[6] 将目标导向策略引入RRT，以解决路径规划中随机性较大、容易陷入停滞状态的问题，通过增加目标点的采样概率，加快了路径规划的收敛速度，提高了效率。文献[7]将人工势场法与RRT结合，利用环境信息引导随机树向目标点生长，避免陷入局部最优。尽管这一方法改善了路径生成过程，但由于选用的地图过于简单，缺乏代表性，其效果在复杂环境中可能有限。文献[8]将改进的RRT与动态窗口法相结合，以防止陷入局部最优并实现动态避障，并融合人工势场法来调整扩展方向，提高了算法的搜索效率和路径质量。然而，最终生成的路径依然不够平滑，不适合实际应用中的移动机器人行驶。文献[9]提出通过计算从起点到终点的方向向量，并将其作为引导向量，使随机树的生长方向更加朝向目标点，减少了节点扩展的随机性，提高了搜索效率。然而，随机树扩展时仍容易陷入障碍物包围圈，导致路径规划失败。

针对RRT算法搜索效率不高、生成路径不平滑等缺点，本文提出了一种改进的RRT算法。具体优化过程如下：首先，加入目标偏置策略和障碍物膨胀策略，以减小RRT算法扩展的随机性，在提升搜索效率的同时，保证规划路径的安全和稳定性。其次，引入贪心算法思想，剔除规划路径中的冗余节点，使生成的路径更加简短和高效。最后，使用三次B样条曲线对生成的路径进行平滑处理，使规划出的路径更有利于无人车的行驶。

1 传统RRT 算法

RRT算法具有简单、高效、无须预处理和适用于非线性约束等优点，因此被广泛应用于无人驾驶领域。RRT算法的核心思想是通过在搜索空间中随机采样，逐步扩展树结构，从而找到从起点Sinit到目标点Sgoal的路径，其扩展方式如图1所示。

算法的主要步骤包括：

（1） 初始化：创建一棵树 T，树的根节点为起点Sinit。

（2） 随机采样：在搜索空间中随机生成一个点Srand。

（3） 找到最近节点：在树 T 中找到离 Srand 最近的节点 Snear。

（4） 扩展新节点：从 Snear 沿着 Srand的方向，以固定步长 A生成新节点 Snew。

（5） 碰撞检测：检查从 Snear 到 Snew 的路径是否与障碍物发生碰撞。如果没有碰撞，则将 Snew 添加到树T 中。

（6） 检查是否到达目标：如果 Snew 到目标点的距离小于预设的阈值，则认为找到了路径。

（7） 重复：重复上述步骤，直到找到路径或者达到最大迭代次数。

2 改进RRT 路径规划算法

2.1 障碍物虚拟膨胀策略

传统的RRT算法在规划路径时，路径可能会紧贴障碍物的边缘，这对于实际应用中的无人车来说并不理想。无人车具有一定的宽度，如果按照传统RRT算法规划出的路径行驶，容易发生碰撞或剐蹭。为了更符合无人车的实际运动要求，我们需要改进RRT算法，使其在规划路径时能够考虑无人车的宽度，从而提高车辆在行驶过程中的安全性。

为此，本文提出了一种障碍物虚拟膨胀策略。在进行延伸节点的碰撞检测时，将延伸节点与障碍物的虚拟半径进行比较。当延伸点与障碍物圆心之间的距离小于虚拟半径时，则认为发生碰撞，剔除该延伸节点。图2为障碍物虚拟膨胀示意图，其中rt为真实半径，rv为虚拟半径。

2.2 目标偏置策略

传统RRT算法的搜索效率低下，搜索时间过长。然而，目标偏置策略可以有效降低算法搜索的随机性，减少对不必要空间的搜索，从而极大提高算法的搜索效率，节省大量搜索时间。因此，在RRT算法中融入目标偏置策略进行随机采样是一种有效的选择。加入目标偏置策略后，随机点的生成方式如式（1） 所示。

式中设定了两个概率值Pg和Ptarget。其中，Pg为按照均匀概率分布随机生成的概率值，范围在0到1之间。Ptarget 为事先设定好的阈值，通常是一个较小的值。在每次迭代中，笔者随机生成一个Pg，当Pg小于Ptarget时，选择目标点Sgoal为采样点；否则，则在整个地图范围内随机生成一个采样点。

2.3 结合启发式贪心思想剔除冗余节点

在通过前面两种策略对RRT算法进行改进之后，规划出的路径仍然存在许多冗余路径。为此，本文结合启发式贪心思想，对路径中的冗余节点进行剔除，使生成的路径更加简短，从而有利于无人车高效行驶。冗余节点去除策略的具体步骤如下：

1） 将起点设置为起始索引，将路径中的最后一个点设置为终点索引，并记录检测次数为节点数量减1。

2） 从终点向起点遍历路径中的每个节点。对于每个节点，检查其与父节点之间的路径是否与障碍物虚拟相交。如果相交，则将终点索引减1，并继续向上检测父节点；如果不相交，则将该节点添加到最优路径中，并更新起始索引和检测次数。

3） 一旦找到一条最优路径段（即不与障碍物虚拟相交的路径段），将其添加到最优路径中。在找到最优路径段之后，将该节点作为新的起始节点，从该节点向上重新检测父节点的路径段。

4） 当检测次数为0 时，表示已经遍历完所有节点，最优路径生成完成。

在完成启发式贪心思想优化后，最终得到的最优路径将不再包含不必要的节点。冗余节点剔除策略的具体实现如图3所示。

其中，虚线代表去除冗余节点后的优化路径。

2.4 采用三次B 样条曲线平滑路径

在结合启发式贪心思想去除冗余节点之后，生成的路径虽然与原始RRT算法相比平滑了很多，但仍存在曲率不连续的问题，这会影响无人车行驶的流畅性和稳定性。为了提高无人车行驶的平顺性，需要对得到的折线路径进行平滑处理。B样条曲线是一种广泛应用于路径平滑的方法，具有几何不变性和凹凸性等优点。为使规划路径具有较好的连续性，使用B样条曲线对路径进行平滑处理。k阶 B样条曲线的方程式如式（2） 所示：

公式中：ei ，i=0，1，2，3…n 是B样条曲线的控制顶点，也就是路径中的节点；Li，k（z）是第i 个k 次B样条基函数，由一个称为节点向量的参数序列U={ p0 ，...，p } m所确定。根据这些节点向量的不同分布形式，可以将B样条曲线划分为均匀B样条曲线、 准均匀 B 样条曲线和非均匀 B 样条曲线。其中，准均匀B样条曲线保留了贝塞尔曲线在两个端点处的性质，样条曲线在端点处的切线为两个端点的连线，更适合应用于折线路径的光滑处理。基函数确定了B样条曲线的连续性和相应的次数，其递推公式为：

由递推公式可以看出，高次的B样条基函数是用低次的B样条基函数的线性组合来表示的，所有的Li，k（z）均为两个（k-1） 次B 样条基函数Li，k-1（z）和Li+1，k-1（z）的线性组合。

综合分析车辆的运动学模型和行驶环境，同时结合算法的运算复杂度，笔者选用三次准均匀B样条曲线对路径进行平滑处理，从而可以得到一条曲率连续的平滑路径。拟合三次B样条曲线段的示意图如图4 所示：

2.5 改进RRT 路径规划算法流程

将前文提到的几种改进策略全部融入传统RRT 算法之后，绘制出完整的改进RRT算法流程图。本文改进RRT算法的流程图如图5所示。

3 实验仿真验证

为验证改进RRT算法的有效性和适应性，本实验在MATLAB R2023仿真平台上进行。在二维环境下，每种算法分别进行50 次实验，并取平均值将改进RRT算法与传统RRT算法进行对比。起点设置为 [0，0]，终点为[10， 10]，步长ρ 为 0.5，阈值设置为 0.1，最大迭代次数设置为 5 000。传统RRT算法及其改进算法在地图中的路径仿真结果如图6至图10所示。

从图中可以看出，相较于传统RRT算法，加入改进点1之后，规划的路径更远离障碍物，提高了无人车行驶的安全性。同时，在加入改进点1和2之后，RRT 算法的探索空间明显减少，从而提高了搜索效率。进一步地，加入改进点1、2和3后，路径中的冗余节点显著减少，路径变得更加流畅。最终，笔者使用三次B 样条曲线对路径进行了平滑处理。

传统RRT算法与本文最终改进算法的仿真结果如表1所示。从表1中可以明显看出，在扩展节点数大幅减少的情况下，平均时间减少了78.1%，路径长度减少了18.6%。

4 结束语

本文主要针对传统RRT算法在路径规划过程中存在的收敛速度慢、搜索随机性高、冗余节点过多以及路径安全性较差等问题进行了优化处理。改进算法首先对障碍物采取虚拟膨胀，使得在随机树的生成过程中更加远离障碍物，从而生成的路径更加安全可靠。其次，采用目标偏置策略，减小搜索范围，提高搜索效率。再次，结合启发式贪心思想，对路径上的冗余节点进行剔除，消除路径中过大的转弯角，减少路径长度。最后，采用三次B样条曲线对生成的路径进行平滑处理，降低路径曲率的突变性，增加车辆的平稳性。

通过在MATLAB进行仿真验证，结果表明改进后的RRT算法具有较高的可行性和有效性，对无人车的路径规划具有一定的参考价值。未来，笔者将继续深入研究全局路径规划，期望将该算法优化得更加完善，同时对局部路径规划算法进行优化。随后，将优化后的局部路径规划算法与改进的RRT算法结合起来，通过一系列实验验证和分析，以进一步验证这种融合算法在实际场景中进行路径规划的有效性。