快速随机搜索树(RRT)

快速随机搜索树（Rapidly-exploring Random Tree，RRT） 是一种基于随机采样的路径规划算法，通过在空间中不断随机撒点并向外扩展一棵“树”，来搜索出一条从起点到终点的可行路径。

它和我们熟知的A算法是两种不同的思路。A需要把空间预先划分成网格，像在一张精确的地图上找路；而RRT更像一个探险家，在未知或复杂的地形中“边走边探”，尤其擅长处理高维度、带有运动学约束的复杂环境。

💡 工作流程：一棵树如何“生长”出来

你可以把RRT想象成在空间中种一棵树，这棵树会自己寻找出路：

播种：将起点设为树的“根”。
随机撒点：在规划空间中随机生成一个采样点。这个点可能是任何位置，甚至可能落在障碍物里。
找到最近的“枝干”：在现有的树上，找到一个距离这个随机点最近的节点。
向目标“生长”：从这个最近节点出发，朝着随机点的方向，生长出固定长度的一小段“树枝”，生成一个新的节点。需要注意的是，如果随机点直接落在障碍物上，这个点会被放弃；如果超出步长限制，则会在该方向上截取一段步长内的新点。
安全检测：检查新长出的这段“树枝”是否碰到了障碍物。如果没有，就把这个新节点添加到树上。
不断重复：循环进行步骤2-5，直到新长出的“树枝”抵达终点附近，那么从终点沿着“树枝”一路回溯到起点，就找到了一条可行路径。

这个过程的精髓在于，它通过随机探索的方式，能够快速地覆盖整个空间，尤其在障碍物复杂的场景中，比传统网格算法效率更高。

🚧 挑战与改进：RRT并非完美

尽管RRT在处理复杂问题上很有一套，但它也存在明显的“短板”：

路径不“丝滑”：由于是随机生长，RRT找到的路径通常由许多折线组成，不够平滑，车辆实际行驶时很难直接跟随。
不是最短路径：它倾向于“找到一条路”，而非“找到最短的路”。算法本身不保证路径是全局最优的。
规划效率不高：在复杂环境中，容易产生大量无效的搜索分支，导致计算量大，收敛速度慢。

因此，在自动驾驶的实际应用中，工程师们通常会对基础RRT算法做大量改进。例如，引入目标偏置策略引导树向目标点生长，采用双向RRT（从起点和终点同时生长两棵树）来加速搜索，或者与A*等算法融合，以及通过路径剪枝和平滑处理来优化最终路径质量。一个较新的研究案例表明，经过优化的RRT算法，在计算耗时和规划时间上可分别降低64%至78%。