概率路图

概率路图，通常简称 PRM，是一张可重复使用的“安全位置道路网”：机器人只建一次，之后却能反复在上面行驶。可以类比一座城市的道路地图——只需测绘和绘制一次，之后任何司机都能在上面规划任意两个地址之间的行程。PRM 为机器人做的也是同一件事：在较慢的第一阶段，它在“机器人所有可能动作”所构成的空间里随机撒下许多姿态，只保留不发生碰撞的那些，再把附近的安全姿态用短连线连起来，而这些连线同样会被检查为无碰撞。最终得到的是一张图——由一个个点（安全姿态）和连接它们的边（安全动作）组成——它刻画出了自由空间里可通行的形状。

这张路图一旦建好，回应一次规划请求就很快了。要从某个起始姿态走到某个目标姿态，规划器只需把它们各自连到路图上最近的点，然后在这张网络上跑一次普通的图搜索（比如迪杰斯特拉算法或 A*）来找出一条路线。由于采样和碰撞检查这些费时的工作已经在前期一次做完，之后每一次新的查询都很便宜——这正是为什么 PRM 被称为“多查询”规划器：地图建一次，却能为许多不同的起点—目标对反复复用。

它的价值，恰恰体现在世界保持静止、而机器人必须在其中往返许多趟的时候——比如一只整天从固定料箱里取件的机械臂，或是一台在不变的楼宇里巡逻的移动机器人。它的缺点正是这份长处的反面：一旦障碍物移动了，路图上的某些边可能就不再无碰撞，其中很大一部分就必须重建。对于在变化或未知空间里做一次性规划而言，像快速扩展随机树那样“一次成型”的方法，通常更为合适。