035｜PRM：先把自由空间修成路网，再回答运动查询

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

论文：Lydia E. Kavraki、Petr Švestka、Jean-Claude Latombe、Mark H. Overmars，Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces，1996，IEEE Transactions on Robotics and Automation 12(4)：566–580。作者出版页 · 期刊原文。

先接住前作的问题

构型空间统一了碰撞描述，高维自由空间却难以显式建全。PRM先用采样路网积累连通性；RRT是面向查询增长树的平行路线，PRM*/RRT*再研究极限质量。

五个前置概念

理解该例子需要五个概念：构型空间把整台机器人的姿态作为一点；自由空间剔除碰撞姿态；局部规划器尝试连接两个给定点；连通分量表示图上已经可以互达的集合；摊销成本把一次预处理的支出分配到多次查询。

一、问题设定：高维构型空间怎样形成可复用的连通图

一台七关节机械臂即使只在平面内运动，它的构型也需要七个关节角描述。如果在每个角度上放置一百个格点，组合数就达到 $100^7$。困难不在工作空间看起来有多大，而在高维构型空间无法轻易穷举。

问题定义：图的顶点必须是一整个机器人姿态

设构型为 $q\in\mathcal C$，机器人与障碍物碰撞的集合为 $\mathcal C_{obs}$，自由空间为 $\mathcal C_{free}$。目标是求连续路径 $\tau:[0,1]\to\mathcal C_{free}$，使 $\tau(0)=q_s$、$\tau(1)=q_g$。

论文主要针对完整约束的几何规划设定：允许的运动可由局部构型路径表达。它不是直接求关节力矩，也没有把扭矩上限、接触动力学或汽车转弯约束自动包含进来。障碍物模型、机器人几何模型和碰撞检测器是输入条件。

两种老办法各有瓶颈。精确构造整个自由空间的几何分解，维度升高后代价很大；从某个起点出发的局部搜索容易被障碍结构困住，而且换一个查询可能又要做大量工作。PRM 选择只记录被采样与连接验证的部分拓扑，不显式描述所有障碍边界。

它特别适合环境与机器人几何不变、起终点经常改变的情形。若每次查询前家具都移动，旧边可能失效，维护图的代价就不能省略。这里所谓“无碰撞”也依赖实际几何和检测精度；错误的模型不会因为使用随机采样而自动修复。

二、采样自由构型，再用局部连接验证边

方法：采样、连接、扩展、查询

道路图 $G=(N,E)$ 的节点是无碰撞构型，边表示局部规划器已找到的可行路径。距离 $D(q_i,q_j)$ 用来选择值得尝试连接的候选点，但距离短并不等于能直连：机械臂中间运动仍可能扫过障碍。

原文 p.569 的构建步骤有一个容易被现代写法掩盖的细节：只尝试连接不同连通分量的节点。这样可以避免为已有连通关系重复投入碰撞检测，却也使图不以保留多条替代路线或逼近最短路径为主要目标。它不是后来具有渐近最优性讨论的 PRM*。

构建阶段倾向于覆盖较大的自由空间，扩展阶段则把计算投入连接困难的地方。原文 p.571 给出的一种权重使用节点局部连接的失败比例。若尝试次数为 $n(q)$、失败次数为 $f(q)$，先计算 $r_f(q)=f(q)/n(q)$，再在候选节点中归一化：

$$w(q)=\frac{r_f(q)}{\sum_{v\in N}r_f(v)}.$$

直觉是：频繁失败的节点可能靠近障碍或狭窄区域，值得从那里作进一步探索。但失败也可能是局部规划器太弱或邻居选择不合适，因此这只是启发式重要性分配，不是对真实通道概率的无偏估计。

扩展使用随机反弹运动，在遇到障碍后改变方向，尝试走出简单直线连接到不了的区域。确定性的廉价局部连接可以只存端点，之后重建路径；随机反弹得到的具体路线需要保留，不能假定再次调用会生成同一路径。这是 p.569 与 p.571 对内存和规划器行为的重要区分。

数学目标、机制与指标各是什么

该算法首先解决可行性，而非优化一个可微损失。几何目标是找到处于同一自由空间连通分量的起终点之间的路径；机制是随机离散表示加局部可行性验证；实验指标则包括建图时间、连接成功率和碰撞检测次数。

这三个层次不能混为一谈。道路图更大可能提高连接成功率，也可能让查询和存储变慢。图上找到的最短路径只对当前保留下来的边成立，不能据此称为连续自由空间的最短路径。路径平滑也只是进一步改善当前解，并不消除所有拓扑选择的限制。

为什么可能有效？大量自由空间具有相对开阔的区域，少量节点就能通过局部连接形成大的连通分量。真正困难的是小体积通道：均匀采样落进通道的概率低，而且沿通道连接也可能困难。扩展策略试图补偿这种不均衡。这里的解释是算法机制分析；它不等同于给任意有限样本预算提供成功保证。

狭窄通道为什么让有限预算突然失效

假设某条可行路径可由 $m$ 个具有正采样概率的局部区域覆盖，且相邻区域中的合适节点能被局部规划器连通。若每区单次命中概率至少 $p>0$，独立采样 $N$ 次后，漏掉至少一区的概率不超过 $m(1-p)^N$。这是教学用覆盖上界，省略了完整PRM证明里的几何和连接条件，不能对任意无净空路径使用。

例如 $m=10,p=0.01$ 时，$N=100$ 的上界大于1，几乎不给可靠信息；$N=1000$ 时约为0.000432。如果某通道区域只占 $10^{-6}$，相同预算远远不够。概率完备性的极限陈述，必须和正净空、采样支持及可用局部连接一起读。

作者摘要把学习和查询明确分成两阶段。因此重复查询的平均成本应写成 $T_{\rm build}/Q+T_{\rm query}$；其中 $Q$是查询次数，$T_{\rm build}$为一次建图时间，$T_{\rm query}$为单次查询时间；只报亚秒查询时间会隐藏建图预算。RRT是面向查询增长树的平行采样路线，RRT*则增加渐近最优性质所需的邻域与重接设计，不能把“用了随机点”视为同一保证。

道路图中的边必须经过局部碰撞验证，查询速度才有实际含义。下面把建图与查询开销一起算，随后再读论文多次查询的收益。

三、实现建图和查询，用成本摊销检验多次任务

输入：构型空间采样器、碰撞检测器、局部规划器、建图预算
N, E ← 空集
while 构建预算未耗尽:
    q ← 采样一个无碰撞构型
    候选 ← N 中距离 q 较近的一组节点
    将 q 加入 N
    按距离从近到远遍历候选 v:
        if q 与 v 不在同一连通分量:
            p ← 局部规划器(q, v)
            if p 全程无碰撞:
                加入边(q, v)，更新连通分量
按连接困难程度选择节点，做随机反弹扩展并连接其他分量

输入查询(qs, qg)
分别寻找 qs、qg 到道路图的可行连接
if 接入同一连通分量:
    搜索图路径，串接局部路径，必要时平滑
else:
    返回当前预算下未找到路径
输出：经过验证的几何路径，或未找到

这是教学压缩版，省略了查询随机反弹次数等参数。返回“未找到”不能解释成问题无解：狭窄通道可能存在，只是还没有被采到。

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

自构例子，未运行。 两间开阔房间之间只有一条很窄的门洞。分别在两个房间随机采到很多姿态，很快就会形成两个巨大连通分量；再多采同样容易的位置，可能仍没有过门路线。从门口附近失败较多的节点扩展，有机会进入门洞。若一百个起终点都分布在这两个房间，找到门洞后的路网很有价值；若只查询一次且环境马上变化，建图投资可能无法摊销。

四、读高维机构实验，连同预处理和碰撞成本报告

读图：表中把建图时间与成功比例并列，必须在相同场景及局部规划器下比较。查询很快并不抹去前期建图成本，随机多次运行的成功率也不是完备性证明。

实验怎样检验道路图是否有用

期刊印刷页与 PDF 文件页序不同；页跳转按文件页序，原文印刷页 578–579 的结果位于 PDF 第 13–14 页，不能直接把印刷页码写进跳转。

读图：C1至C8是不同查询构型，障碍布局相同；比较查询成功率时，应保留构型差异，不能仅用平均成功率代表所有窄通道。

作者有意识地避免一个偏差：若只测试与建图同分布的随机构型，很多点很容易接上图，结果会高估处理困难查询的能力。人工挑选困难点增加了实验的挑战性，不过它也使结果依赖这些特定场景，不能直接当成所有机器人任务的平均成功率。

碰撞检测次数是有用的计算量代理，但不同几何表示下每次检测的代价不同。论文为平面场景设计的实现与通用规划器，在预处理时间上相差很大；这个差异正说明算法名字相同，系统实现和模型复杂度仍会改变性能。

五处证据：结论应落在哪一层

1．p.569 构建算法。 比较节点之间的连通关系，只有连接不同分量才尝试添边。它支持“重点建设连通性”的解释，不支持把原算法描述成所有近邻边都保留的最优路网。

2．p.571 扩展机制。 连接失败比例和随机反弹把采样预算转向困难位置。它解释了论文如何处理均匀采样不足，但仅有机制本身不能证明每个狭窄通道都会被发现。

3．p.574 Fig. 2 与相邻实验文字。 七关节机器人和八个人工选定构型明确了高维的含义。重复生成 30 张图并连接同一批点，是对随机建图可靠性的检验；没有把机械臂执行误差纳入指标。

本页定位：图 2内嵌图。

4．Fig. 11 通用规划器结果。 两个所示场景在 2.5 秒学习预算下的成功率为 53.3% 与 50%，在 10 秒预算下都达到表中的 100%。它支持增加预算能够改善这些测试的连接表现；表中的有限次全成功，不等于任意查询必成功。

本页定位：图 11内嵌图。

5．Fig. 12 与结论。 更困难的 Fig. 2 场景使用通用规划器时，学习预算以分钟计：5 分钟时列出的 C1、C4、C7、C8 接入率分别为 80%、30%、30%、43.3%；25 分钟时这几列达到 100%。作者在结论也指出，若把预处理计入，一些单次查询中其他随机规划方法会更快。这限制了“查询很快”可以推出的整体效率结论。

读图：逐列看C1、C4、C7、C8的成功率，再对照学习成本；扩展路网可以改善困难构型，但额外预处理并非免费。

本页定位：图 2内嵌图。

上述数字都是对应表格的结果，不能把秒级简单场景与分钟级困难场景拼成同一条学习曲线。表中成功率衡量构型与图的连接表现，也不是一个带噪声机器人从起点走到终点的实测概率。

五、检查窄通道、有限图失败与路径质量

PRM 的持久贡献是把高维运动规划拆成可复用的采样表示与局部验证，并把规划难度转移到可以逐步增加预算的图构建过程。1996 年论文整合了作者此前的相关工作，因此不宜把所有道路图思想都说成在这一年突然出现。

它为少量查询付出的预处理代价可能不划算；为很多查询维护一张图则可能受益。这是工作负载的区别。另一个边界是窄通道和小连通分量：低体积区域可能长期缺少节点，扩展启发式也可能把时间花在实际上不能连接的边界附近。

局部规划器还决定了“边”是否有意义。关节空间直线适合某些完整约束机械臂，却未必满足汽车非完整约束。即使几何路径成立，高速执行仍需要时间参数化、动力学和控制约束检查。后者是本文分析，不是论文已经验证的实机能力。

六、追问：环境改变后，旧道路图的哪些信息还能安全复用？

七、从多次查询走向随机树与极限质量

• 平行路线：RRT：让树朝还没探索过的地方生长。面向一次任务增量生长探索树，改变预处理与查询的组织。
• 直接继承：RRT*：让随机树在找到路径后继续变好。研究连接规则与采样增多后的极限路径质量。

八、自测与参考答案

问题 1：一张 PRM 图里找不到起终点之间的路，能否宣布机器人无法通过？

参考答案：不能。图只记录有限采样和成功的局部连接。真实空间可能有一条很窄的通道尚未被采到，也可能已有合适节点但局部规划器没有连上。可以报告当前预算内失败，若要证明不可达，需要额外的完备性或几何论证。

问题 2：算法 A 建图花 100 秒，每次查询 0.1 秒；算法 B 不建图，每次查询 2 秒，何时 A 更划算？

参考答案：在这些自构且稳定的成本假设下，比较 $100+0.1n<2n$，得到 $n>100/1.9\approx52.63$，即至少 53 次查询。还要保证环境不变、查询成功标准相当，并计入图维护成本。只比较 0.1 秒与 2 秒会遗漏主要支出。

问题 3：为什么给道路图不断添加随机点，不一定让输出路径趋于全局最短？

参考答案：覆盖更多位置不等于保留优化所需的边。原算法关注连接不同分量，很多成环的替代路线不会加入；邻接规则、距离和后处理也没有自动构成连续空间最优性的证明。可行性、有限图最短路径和连续问题的渐近最优性是三个不同命题。