probabilistic roadmap（PRM） 算法是一类用于机器人路径规划的算法，最早在[1]中被提出，属于随机规划器的一种，其数据的主要形式为无向图（另一种 RRT 基于树）。[^2]将 PRM 算法分成了两个阶段：learning 阶段和 query 阶段。其中 learning 阶段主要在 configuration 空间（机械臂的话是 \(C\) 空间，移动机器人的话一般就是欧几里德空间，因为原文是在 \(C\) 空间中被提出的，所以这里就用 \(C\) 空间）中进行一定次数的采样（一般而言是均匀采样，后面为了解决一些狭小空间的问题进行了一些特殊的采样手段），并对采样点进行碰撞检测，再通过距离判断和碰撞检测将采样点进行连线，最终得到由有效采样点作为 vertex 而采样点之间的连线作为 edge（两点之间的距离很自然的作为 edge 的值）所形成的无向图 G =(V, E)。
PRM 算法的使用基于 3 个前提：
- 我们已经具备了碰撞检测的方法，无论是对 vertex 的检测还是对 edge 的检测。对于 vertex 的检测可能比较直观，而对于 edge，最简单的方式是在 edge 上插值得到很多个点，然后再像 vertex 一样进行碰撞检测
- 无论是在 \(C\) 空间还是欧几里德空间，我们有比较合理的方式计算采样点之间的距离
- 已经具备一个可以使用的无向图路径规划器，例如 [[A*算法]]。
PRM 算法的实现即是将上述 3 个前提工具进行组合使用，得到最终的结果。
learning 阶段
learning 阶段的目标是在 \(C_{free}\) 空间（即 \(C\) 空间中不会发生碰撞的空间）中得到一个无向图 G 。基本的实现方式如下：
- 将图的点和边置为空集
- 从 \(C_{free}\) 空间采样一个点（从 \(C\) 空间采样，直到找到一个不碰撞的点）
- 将点添加到图的点集合中，并尝试对新的点和图中原有的点进行连线。是否连线的标准为：1）不发生碰撞；2）在一定距离内。成功连线后，将连线添加到图的边集合中。
- 重复 2 与 3，直到采集到一定数量的点
query 阶段
learning 阶段得到无向图 G 后，query 阶段要利用 G 来找到一条路径连接起始点和目标点。首先要将起始点和目标点与 G 连接起来其方式与 learning 阶段添加 vertex 和 edge 的过程类似，之后，利用图规划器寻找一条路径：
- 尝试将起始点作为新的 vertex 连接到 G 中，如果无法连接则报错
- 尝试将目标点作为新的 vertex 连接到 G 中，如果无法连接则报错
- 使用图规划器在新的无向图中找到一条路径连接起始点与目标点
More Reading
Reference
Kavraki, L.E., P. Svestka, J.-C. Latombe, and M.H. Overmars. “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces.” IEEE Transactions on Robotics and Automation 12, no. 4 (August 1996): 566–80. https://doi.org/10.1109/70.508439. ↩︎