目录

01    为什么不先把所有可能路线都列出来？

02    RRT 怎么把一棵树“长”到终点？

03    明明在随机撒点，为什么反而能有效探索？

04    路找到了，为什么 RRT 还不够？

05    RRT* 多做了什么？核心是重新连边

06    RRT 和 RRT*，到底应该选哪一个？

07    真正部署到机器人，还需要补上什么？

08    写在最后

---

为了将算法知识真正转化为解决问题的能力，我们在《算法详解》专栏里，不只讲算法步骤，更关注它为什么这样设计、哪些条件下有效，以及放进机器人以后还要解决哪些问题。

在 Dijkstra 这样的图搜索算法中，我们通常先把地图表示成一张图，再寻找累计代价最小的路径。但如果机器人有很多关节，每个关节都可以连续转动，就很难预先列出所有可能的状态。这时，还能沿用逐个节点搜索的思路吗？

RRT（Rapidly-exploring Random Tree，快速探索随机树）提供了一种有点反直觉的答案：不用先把整张图搭好，直接在空间里随机选方向，让一棵树从起点不断长出去。

更有意思的是，这种方法首先解决的是“找到一条能走的路”，而不是“找到最短的路”。后来出现的 RRT*，正是为了进一步回答：路已经找到了，能不能继续把它改得更好？

01    为什么不先把所有可能路线都列出来？

先看一辆移动机器人在平面上的导航。只考虑平面位置时，我们可以把环境划成网格，再交给 Dijkstra 或 A* 搜索。但如果换成一只六自由度机械臂，问题就变了。

机械臂末端的空间位置只是结果，真正决定它是否碰到障碍物的，是六个关节此刻各自转到了什么角度。哪怕机械臂末端停在同一位置，肘部也可能绕到柜子外侧，或者直接撞上旁边的隔板。

因此规划时需要考虑的往往是关节组合构成的配置空间（Configuration Space），而不只是末端在三维空间中的位置。

如果每个关节粗略取 20 个候选角度，六个关节组合起来就已经有 6400 万种状态。这只是帮助理解规模的假设数字，并不是说机器人必须这样离散；问题在于，维度一高，逐一枚举的代价会迅速膨胀。

RRT 换了一个提问方式：与其把所有可能状态都列出来，再寻找路径，能不能只探索其中一部分，先找到一条可行的连接？

它并不是说网格搜索已经失效，而是针对连续、高维、甚至带运动约束的问题，提供另一种组织搜索的方法。

图1 | 对二维移动机器人，可以直观地在平面地图中找路；对多关节机械臂，规划变量往往是多个关节角的组合。维度增加后，预先枚举所有候选状态可能变得非常昂贵，采样规划因此有了用武之地。

02    RRT 怎么把一棵树“长”到终点？

先回到二维地图，假设机器人位于左下角，目标在右上角，中间有几块障碍物。我们让起点成为树根，随后不断重复四个动作。

第一步，随机采样（Sample）。在允许搜索的空间里随机选出一个点。它不一定是目标，也不一定马上能到达，只是告诉树：“这次试着往这个方向探索。”

第二步，寻找最近节点（Nearest）。在已经长出来的树上，找到离这个随机点最近的节点。注意这里的“近”，通常是按照规划空间中选定的距离度量计算，并不总是二维地图上的直线距离。

第三步，向采样方向扩展（Steer）。从最近节点朝随机点走一小段，而不是每次都直接跳到随机点。这样就能控制每一步扩展的尺度。在带运动约束的规划里，这一步还可能需要局部运动模型或控制输入来生成实际可行的运动。

第四步，检查碰撞（Collision Check）。只有当这段新运动没有穿过障碍物，才把新状态和对应的边加入树中；否则就放弃这次扩展，下一轮重新采样。

图2 | RRT 的一次扩展：算法从已有树上寻找靠近随机样本的节点，再朝采样方向生成新节点。只有当连接能够通过碰撞检测时，新的分支才会加入搜索树。

一次采样可能什么也没得到，但很多轮以后，树会逐渐伸向不同方向，绕开障碍物，探索此前没有到达的区域。只要某条分支成功连接到目标区域，就可以沿着父节点关系回溯，得到一条从起点到终点的路径。

下面这张动图能更直观地看到这个过程。树不是提前知道路线再沿着路线生长，而是不断尝试、碰壁、换方向，最后才可能碰到目标。

图3 | 一个二维障碍环境中的 RRT 生长示意。细线是已经探索出的树枝，粗线是首次找到目标后回溯得到的路径。每次运行受随机采样影响，搜索形状和首次找到的路径都可能不同。

03    明明在随机撒点，为什么反而能有效探索？

只看“随机采样”，RRT 似乎很随意。它真正有意思的地方，在于随机采样与最近节点扩展的组合，会自然鼓励树往尚未覆盖的区域生长。

试着想象，树已经把地图左半边探索得非常密集，右半边却只有几个稀疏的分支。如果下一个随机点落在右边大片空白区域，它通常会被分配给某个面向空白区域的树节点，再从那里长出新分支。

反过来，在已经很密集的地方，新随机点虽然也可能出现，但它们不会总让同一条旧分支不断占据优势。

这和一种叫作 Voronoi Bias 的性质有关：树上某个节点能够“吸引”多大范围内的随机样本，取决于它在空间中对应的最近邻区域。面向尚未探索区域的节点，往往拥有更大的影响范围，因此获得更多向外扩展的机会。RRT 原始工作也把这种探索偏置作为重要特点。

不过，“随机”不等于一定快，也不等于每次都能找到路。狭窄通道就是典型难题：门缝明明存在，但随机样本很难碰巧落到正确位置和方向上，扩展尝试可能反复失败。

在满足常见的可行性和采样条件时，RRT 还有一个重要性质叫作概率完备性：如果问题确实存在足够稳健的可行路径，随着采样次数增加，找到一条解的概率会趋近于 1。但它不保证固定时间内一定找到，更不保证找到的第一条就是最优路径。

实际实现常会增加一点目标偏置（Goal Bias），也就是偶尔直接拿终点当作采样目标，让搜索不要完全依赖运气。但目标偏置太强，又可能导致树反复向被障碍挡住的方向尝试，反而削弱探索能力。

所以 RRT 的优势不是“随机总比系统搜索快”，而是：在不必全面离散空间的情况下，用相对简单的规则，逐渐构造出一张只包含已探索状态的搜索树。

04    路找到了，为什么 RRT 还不够？

前面的 RRT 已经能找到一条可行路径，但它可能很难看：绕了远路、拐弯很多，甚至明明后来发现了更好的连接方式，最初那条路径仍然没有被主动改进。

原因不复杂。普通 RRT 主要关心的是把新节点接到哪一个已有节点上，才能继续探索。一旦接上，通常不会再反复检查：“如果把这条老树枝接到别的地方，会不会更短？”

因此，它更像是在问：有没有路？

但真正用于机器人执行时，我们又会关心：走这条路需要多长距离？会不会消耗更多时间和能量？经过的转弯是不是太激烈？

这就引出了 RRT*。这里的星号并不是说它每次都能直接找到最优解，而是说，它在保留随机扩展思想的同时，把持续改进路径代价纳入了搜索过程。

05    RRT* 多做了什么？核心是重新连边

RRT* 一样会采样、找附近节点、扩展和检查碰撞。但当一个新节点准备加入树中时，它不再满足于“连到离我最近的那个节点”。

首先，它会检查附近多个候选父节点：从起点经过哪个父节点到达新节点，累计代价更低，而且连接又是可行的？

这时的“最合适父节点”，未必是几何距离最近的。一个邻居虽然离新节点很近，但它自己可能已经绕了很大一圈，导致总路程反而更长。

找到更好的父节点以后，RRT* 还会多做一件事：Rewiring（重新连边）。

假设树上一个老节点原本需要绕路才能到达。现在新加入的节点提供了一条更便宜的连接，RRT* 就会检查：能否让这个老节点改从新节点接入？如果总成本下降，而且新连接无碰撞，就修改它的父节点；受影响的后代节点，其累计代价也要同步更新。

图4 | RRT 的 Rewiring 不是把整棵树推倒重来，而是局部调整父子关系。新节点加入后，某个旧节点若能通过它更便宜地连接到起点，算法便替换旧连线，并相应更新后续节点的累计代价。

这样一来，RRT* 不仅继续寻找新的空间，还会不断检查自己已经找到的连接是否存在改进空间。随着采样增加，树的结构可以逐步朝着更低的路径代价演化。

这里必须把一个容易被夸大的说法讲准确：RRT 具有渐近最优性，不等于有限时间内必然得到全局最优路径。 它的理论结论是在满足相应空间、采样、连接半径等条件时，随着采样数量趋于无穷，所找到的最优解代价以概率意义收敛到最优值。

换句话说，RRT* 的长处是“可以持续优化”，但实际运行总有时间预算，最后拿到的依然可能只是一条尚未达到最优的路径。

06    RRT 和 RRT*，到底应该选哪一个？

如果问题是“能不能尽快找到一条可行路径”，基础 RRT 的思路非常直接；如果找到第一条路后，还愿意继续投入计算来改进代价，RRT* 更符合需求。

但代价也很明确：RRT* 需要查询附近更多节点，比较不同父节点的累计成本，并对潜在新连线重复进行碰撞检测和 Rewiring。尤其在复杂空间里，最贵的步骤可能不是随机采样，而是一次次验证连接是否真的可行。

图5 | 同一障碍地图中的 RRT 与 RRT 教学仿真。左侧侧重找到一条可行路径；右侧允许新节点影响已有连接，并在搜索过程中持续保留更好的目标路径。图中路线只是特定随机种子和计算预算下的示例，不能据此概括所有任务的速度和性能。

也因此，算法选择不是简单的“RRT* 全面取代 RRT”。在实际软件库中，还能看到很多针对不同目标的变体。

例如 RRT-Connect 会尝试从起点和终点两侧分别生长树，并努力把它们连接起来，常用于强调可行解搜索的运动规划。Informed RRT* 则在找到初始解以后，将更多采样集中到可能继续改善当前路径的区域，以减少无效探索。

这些方法的不同设计，实际上都围绕同一个工程问题：有限计算预算应该优先用来发现新路径，还是改进已经发现的路径？

07    真正部署到机器人，还需要补上什么？

把 RRT 放到一张二维图里演示很容易，真正让机械臂或者车辆执行，难点却远不止“随机撒点”。

首先是状态空间。 对移动机器人，规划状态可能包括位置和朝向；对机械臂，可能是多个关节角；如果还要考虑速度和加速度，状态维度会更高。算法中的“距离最近”和“朝采样点扩展”都依赖状态表示，不能简单把所有变量当成二维坐标。

其次是碰撞检测。 新节点本身不在障碍物里，并不等于连接它的整条运动都安全。机械臂在两个合法关节姿态之间运动时，中途可能扫过障碍物；车辆在两个位置之间转弯时，车身也可能碰撞。所以工程实现必须检查连续运动或足够可靠的运动离散近似，并考虑机器人自身尺寸与安全余量。

第三是运动约束。 在二维图上直接画一条直线，不代表汽车能沿它开过去。车辆有最小转弯半径，机械臂有关节速度、加速度等限制。要处理这类约束，通常得设计真正符合运动学或动力学的局部扩展器，而不只是修改随机采样方式。

图6 | Dubins-RRT 的车辆路径规划仿真。与二维平面上的任意直线连边不同，树枝通过满足最小转弯半径约束的 Dubins 曲线连接，展示了如何在搜索过程中考虑车辆的前向行驶与转向约束。

最后是路径与执行之间的距离。 规划出若干连接点，不代表已经得到机器人可以稳定跟踪的轨迹。真实系统往往还需要路径平滑、时间参数化、速度规划和反馈控制。如果环境在执行过程中变化，还必须考虑重新规划或者动态避障。

因此，RRT 在机器人系统里的位置应该很清楚：它负责构造可行的状态连接；RRT* 在此基础上进一步优化定义好的代价。至于机器人能否安全、平顺地完成动作，仍要靠模型、碰撞检测、轨迹生成与底层控制共同保证。

08    写在最后

从 Dijkstra 到 RRT，看似都是“寻找一条路”，实际在解决两种不同的难题。

当世界已经被表示成有限图，Dijkstra 可以利用非负边权和累计代价，系统地找到最短路径。但在连续、高维的机器人配置空间里，事先枚举所有可能状态可能过于昂贵。RRT 的回答是：既然没必要把整个空间都列出来，不如在需要的时候随机探索，并让树一步步长出一条可行路径。

而 RRT* 又往前走了一步：找到路只是开始，已经建立的连接也可以随着新信息不断优化。 它不是凭空保证每次都最优，而是用更高的计算成本，换取持续改进的能力和相应的理论收敛性质。

这两种方法最值得记住的区别，并不是星号本身，而是规划目标的变化：先解决“有没有办法到达”，再考虑“在有限预算内，怎样到达得更好”。

参考资料

1. Steven M. LaValle, Rapidly-Exploring Random Trees: A New Tool for Path Planning, 1998. https://msl.cs.illinois.edu/~lavalle/papers/Lav98c.pdf

2. Sertac Karaman, Emilio Frazzoli, Sampling-based Algorithms for Optimal Motion Planning, IJRR, 2011. https://arxiv.org/abs/1105.1186

3. OMPL, RRTstar Class Reference. https://ompl.kavrakilab.org/classompl_1_1geometric_1_1RRTstar.html

4. PythonRobotics, Rapidly-Exploring Random Trees (RRT). https://atsushisakai.github.io/PythonRobotics/modules/5_path_planning/rrt/rrt.html

5. Steven M. LaValle, RRT Publications and Background. https://lavalle.pl/rrtpubs.html