概率路线图

先在空间里随机撒点连成路网，再在路网上查起点到终点路径的规划算法。

概率路线图是一种基于采样的运动规划算法，一般认为由 Lydia Kavraki 等人在 1996 年的论文中提出。它分两个阶段：构建阶段在构型空间（机器人所有可能姿态组成的空间）里随机采样无碰撞的点，把相互间能直线连通、不撞障碍的近邻点连起来，形成一张图，即「路线图」；查询阶段把起点和终点接入这张图，再用 Dijkstra 或 A* 搜出路径。它的优点是路线图建一次可反复查询（多查询），适合环境基本不变、要频繁规划的场合；弱点是狭窄通道里很难采到点。它具有概率完备性：采样足够多时，只要路径存在，找到的概率趋近 1。与之相对，RRT 每次从起点现长一棵树，更适合单次查询。

例子工位上固定的机械臂，事先在关节空间建好一张 PRM 路线图；之后每换一组取放目标，只需把新的起点和终点接入路网搜索，不必从头规划。

也叫

概率路图法、概率路线图法、PRM 规划器

相关

快速扩展随机树、基于采样的规划、概率完备性、构型空间、路径规划、A* 算法

来源

Wikipedia: Probabilistic roadmap
Lynch & Park, Modern Robotics（§10.5.2 The PRM Algorithm）