040｜RRT：让树朝还没探索过的地方生长

总览 · 目录 · 上一篇 · 下一篇

论文：Steven M. LaValle，Rapidly-Exploring Random Trees: A New Tool for Path Planning，1998，Iowa State University 技术报告。作者保存的四页原文。这篇短报告介绍原始 RRT；双树快速连接、重连优化等后续算法不属于它的原始实现。

先接住前作的问题

PRM先造路网再查询，单次任务常希望立即朝未知区域扩展。RRT用随机目标诱发Voronoi偏置。

五个前置概念

五个前置概念是：状态空间包含决定后续运动的变量；非完整约束限制瞬时可运动方向；前向积分从状态和输入预测未来；最近邻决定从哪里扩展；Voronoi 区域解释随机目标怎样转化为节点选择概率。

一、问题设定：一次规划怎样让树优先长向尚未覆盖的区域

要让一棵树覆盖自由空间，可以随机选择树上一个节点，再随机向某个方向伸出一小段。但树上节点大多集中在已经探索过的区域，这种做法容易反复在原地堆积。

问题定义：树长在状态空间，不一定只长在位置空间

设状态空间为 $X$，障碍或不允许状态集合为 $X_{obs}$，自由状态为 $X_{free}$。起点为 $x_{init}$，目标可以是区域 $X_{goal}$。对于纯几何问题，状态可取构型；对于动力学问题，状态通常还需要速度。

系统变化由

$$\dot x=f(x,u),\qquad u\in U$$

给出。每条树边对应一段合法控制及其状态演化，而不只是一条画在纸上的线段。汽车前轮朝前时不能任意侧移；含速度的系统也不能把终点位置对齐却忽略停车要求。

与 PRM 的区别需要结合原始动机理解。PRM 反复尝试连接已有样本，非完整约束下局部连接可能成为困难的控制问题。RRT 从一个已可达节点出发，选择一个输入推进短时间，因此不必每次精确到达随机样本。树始终保存从根到每个节点的可执行控制历史。

这不意味着所有 RRT 变体都比所有 PRM 更快。原文 p.3 明确把速度优势称作初步观察，并指出严格实验比较困难。两者的数据结构、查询用途、连接器和碰撞检测开销都不同。

二、随机采目标，再以最近邻短步扩展产生Voronoi偏置

方法：随机状态只是方向，不是必须到达的点

目标判定和返回路径是用于规划任务的补充表述；原文核心过程主要展示生成包含给定数量节点的树。连续空间中的随机样本不必恰好等于目标点，因此实际要明确目标区域、容差或额外连接条件。

输入选择可概括为

$$u^*\in\arg\min_{u\in U}\rho\bigl(\mathrm{Propagate}(x_{near},u,\Delta t),x_{rand}\bigr),$$

其中 $\rho$ 是状态距离，Propagate 是动力学推进。若控制集合有限可以枚举；若连续，则需离散或使用其他优化方式。原文提到数值积分可采用比欧拉更高阶的方法，说明控制输入与轨迹有效性需要一起考虑。

在无动力学的欧氏空间，常见教学特例是

$$x_{new}=x_{near}+\min(\eta,\|x_{rand}-x_{near}\|)\frac{x_{rand}-x_{near}}{\|x_{rand}-x_{near}\|}.$$

这只是在能沿任意方向移动的情形下，朝随机点走不超过 $\eta$ 的一步。将它直接用于只能前进转弯的汽车，会把问题中的运动约束抹掉。

原始 RRT 首要目标是找到满足约束的路径。最近邻和输入选择中的距离最小化，只是一次扩展的局部方向选择，不等于优化从起点到终点的总成本。

树边数量最少地保持所有节点与根连通，避免了为全图连通反复添边的部分开销；代价是每个节点只有既定父节点。即使后来发现另一条更短到达路线，原始算法也不会自动重选父节点。RRT* 的优化行为不能悄悄写进这里。

Voronoi 偏置：为什么外缘节点更容易被选中

给定树节点和距离 $\rho$，每个节点拥有一个 Voronoi 区域：区域内的随机点都以它为最近邻。若随机点均匀采样，某节点被选择的概率等于其 Voronoi 区域在采样域中所占的体积比例。

树内部节点互相挤占区域，边缘节点则常面向大片空白。于是边缘节点获得更多扩展机会，新节点又分割原来较大的区域，形成逐步覆盖过程。这里随机选的是整个空间中的目标，不是等概率选树节点。

但“被选中多”与“成功扩展多”也不同。一个节点可能面向障碍后的大区域，反复被抽中却无法通过碰撞检查。窄通道问题因此仍在：通道的有效入口可能概率很小，距离度量也可能把随机目标分配给无法朝该方向前进的节点。

这种偏置解释了探索机制，不证明有限预算内一定找到目标。原文 §3 讨论概率完备性与状态分布趋近等性质，但 §5 也指出显著理论分析仍待完成，特别是收敛速度与相对最优解质量的界。不能把后来的严格定理全部算到这份四页报告里。

Voronoi偏置可以直接数出来

在一维区间 $[0,10]$ 内，树节点为0、1、9，欧氏最近邻分界在0.5和5。均匀采样时，三节点被选中概率分别为0.05、0.45、0.50，而不是各三分之一。外缘节点9的大区域使它常获得扩展机会；加入节点10后，其区域会缩小，探索重点随树自动迁移。这是教学算例，解释偏置来源，不代表一维无障碍的速度能预测机械臂窄通道。

距离度量也参与算法：若状态包含角度与速度，直接混合“1弧度”和“1米/秒”会改变最近邻、进而改变探索概率。非完整系统还需从最近节点用合法输入前向传播，不能把 $q_{rand}-q_{near}$ 当成可执行动作。

PRM是构图采样的平行路线；RRT-Connect直接继承树扩展并增加双树贪心连接；RRT*加入重接以改变极限路径质量。四页原文第2–4页给出生成算法、初步性质与约束算例，作者的报告目录另列后续版本。原始RRT的快速覆盖现象与后来的渐近最优证明不能倒置合并。

随机目标先通过最近邻关系选择扩展节点，短控制推进再决定新状态是否可达。下面把位置、朝向与速度分开检查，避免把到达目标位置当完整动力学成功。

三、实现合法短控制推进，检查状态中的速度分量

原报告 p.2 的生成算法包括随机状态、最近邻、输入选择和新状态推进。可写成如下教学版：

输入：初始状态、动力学、允许控制、状态距离、步长、预算
T ← 只有根 xinit 的树
重复直到预算耗尽：
    xrand ← 从状态空间采样
    xnear ← T 中与 xrand 距离最近的节点
    在允许输入中选择 u，使短时推进结果接近 xrand
    用动力学积分得到 xnew 和完整短轨迹
    if 短轨迹全过程满足约束且没有碰撞：
        把 xnew 加入 T
        保存父节点、控制输入和连接轨迹
        if xnew 满足目标条件：回溯得到控制序列
返回当前树，或预算内未找到目标的状态

算例设置：短报告能支持多强的结论

原文没有提供这些算例的统一随机种子、重复次数、完整硬件预算与置信区间。不能把“作者成功应用到某维度”改成“该维度下普遍高成功率”。尤其是十二维状态空间与十二个机械自由度不是同一个概念：位置和速度一起计入状态，会使状态维数增加。

一个教学例子与五个前置概念

自构例子，未运行。 一维区间 $[0,10]$ 上只有节点 1、2、3，采用欧氏距离。节点 1 的 Voronoi 区间是 $[0,1.5]$，节点 2 是 $[1.5,2.5]$，节点 3 是 $[2.5,10]$。均匀采样下三者被选为最近邻的概率分别为 15%、10%、75%。等概率选节点则都为约 33.3%，无法同样偏向右侧尚未覆盖区域。

四、读短报告算例，分开探索形态与质量保证

读图：从左到右观察树如何把分支送往尚未覆盖的区域。图显示 Voronoi 偏置带来的空间扩张，不是在相同硬件和运行时间下统计得到的速度优势曲线。

原报告的树图与性能观察各能说明什么

四页报告中的树图主要说明探索机制；二维投影会隐藏速度等状态，无障碍路径长度观察也不是所有环境的近似比保证。

实验可以看覆盖速度、规划成功率、耗时、碰撞检测次数与解长度，但本文并没有完整报告这套现代指标。它的关键证据是算法结构、二维生长图、若干约束系统的可行轨迹，以及明确标为初步的质量观察。

五处证据与不能推出的结论

1．p.1 Fig. 1。 动力学车辆的 RRT 被投影到二维平面，展示从已有可达状态向外扩展的控制轨迹。投影只能帮助看形状，不能显示速度维的分布或证明每个投影交点都是可连接状态。

读图：粗线给出从树中取出的可行车辆轨迹；分枝是五维状态树的二维投影，不能把平面上的交点都当成可连接状态。

2．p.2 生成伪代码。 最近邻先于输入选择，新节点由输入推进产生，边保存控制信息。它支持“无需精确点到点连接器”的主要机制，不意味着完全不需要控制模型或积分器。

3．p.3 无障碍生长三联图。 树迅速向方形区域各方向扩展。相邻文字解释随机选节点扩展容易在已有区域堆积，而 RRT 的 Voronoi 区域偏置倾向未探索部分。这是机制比较，不是相同运行时间下的多次平均成绩。

4．p.3 路径质量观察。 作者报告二维凸空间的若干实验中，树路径长度与最优路径长度相差约 1.3–2.0 倍。这个范围属于所述模拟观察，不是任意地图和任意节点的近似比保证；文中也明确解离最优仍有距离。

5．p.4 四个约束示例与研究问题。 图片展示完整约束、限制转向和动力学场景的树与解；正文指出最近邻效率、距离度量、采样偏置和理论界仍待研究。它证明作者并未将这些工程与理论困难视为已经解决。

尚未内嵌：p.4 无编号示例组。缺的是同页完整四组受约束 RRT 运行结果，而非通用树结构示意。短报告的生长过程和模型对照已展示；再加入该组会重现其主要完整视觉例证集。没有同一随机运行数据，另跑示例不能冒充这些原结果。

五、检查距离设计、非完整约束和已有解不改进

贡献是一个极简而适应性强的探索框架：从可达状态向随机目标短步推进，利用最近邻自然形成空间覆盖偏置。它使动力学约束可以通过前向模拟进入规划，而不必先设计精确的两点边值求解器。

代价首先是距离。两个状态在位置上接近，可能速度相反，或由于转向限制很难互相到达。理想距离应反映可达代价，但精确计算这种距离本身可能接近原规划问题的难度。原文 p.3 已明确指出这一困难，因此实践中采用简单距离是一种折中。

其次是路径质量与时间。树可能很快找到一条曲折路径，但不能据此推断在同样时间内找得到短、平滑、易执行的路径。最近邻查询随着节点增长也变贵；过小步长需要更多节点，过大步长则容易跨过有效入口或在碰撞前反复失败。

最后是目标偏置。偶尔采样目标可以推动求解，但过强的目标偏置会重复朝阻挡方向尝试，损失探索优势。原文研究问题对此已有提醒。最有用的理解是“随机探索和任务引导要权衡”，而不是“朝目标采样越多越快”。

六、追问：改变最近邻距离而保持同一随机样本，会改变树的探索偏置吗？

七、让树更快会合，或持续改进旧路径

• 直接继承：RRT-Connect：让两棵搜索树主动相遇。用双向树与CONNECT操作加速可行路径会合。
• 直接继承：RRT*：让随机树在找到路径后继续变好。增加近邻选父与重连，研究已有路径质量如何随采样改进。

八、自测与参考答案

问题 1：RRT 是否以相同概率选择每个树节点扩展？

参考答案：不是。它采样目标，再选择最近邻。均匀目标采样下，节点的选择概率取决于其 Voronoi 区域体积。外缘节点通常拥有更大区域，所以探索偏置可以在没有显式“奖励未知区域”的情况下出现。

问题 2：汽车到达目标位置但速度很大，能否算动力学规划成功？

参考答案：取决于目标集合。如果任务要求停车，目标必须约束位置、朝向和速度等状态；仅二维位置接近不够。树中某条路径的平面投影看似到达终点，也可能没有满足完整终止条件。

问题 3：为什么原始 RRT 找到更多节点后，不一定不断改善已有解？

参考答案：生成机制只加入新的父子边，不主动重连旧节点或重新优化到达成本。更多节点提高探索覆盖，却不自动改变已选路径。要系统性改善成本，需要额外优化、重连或其他搜索设计，并为对应算法单独检查理论条件。