Probabilistic Roadmap

• 又称: PRM, probabilistic roadmap method
• 类别: Planning & manipulation › Motion planning
• 标签: motion-planning, sampling-based-planning, path-planning, graph-search, manipulation

一种基于采样的运动规划器，它构建一张可重复使用的图，由随机的无碰撞构型及它们之间的可行路径组成，然后通过图搜索回答规划查询。

定义

概率路线图（Probabilistic Roadmap，PRM）是一种基于采样的运动规划方法，由 Kavraki、Švestka、Latombe 和 Overmars 于 1996 年提出。PRM 不会针对每个请求重新搜索构型空间，而是先构建一张捕捉机器人自由空间连通性的图，即路线图，然后用这张图回答任意数量的从起点到目标的查询。

规划分为两个阶段。在构建阶段，规划器随机采样机器人的构型，把无碰撞的构型保留为节点，并尝试用一个简单的局部规划器把每个节点与附近的节点相连，局部规划器通常是构型空间中的一条直线，并以细小的间隔进行碰撞检测。成功的连接成为边。在查询阶段，起点构型和目标构型被连接到路线图上，再用 Dijkstra 算法或 A* 等图搜索在图中找到一条路径。

PRM 适合多查询问题，即环境是静态的、机器人必须在同一空间中规划许多运动的情况，因为代价高昂的路线图构建只需进行一次。它具有概率完备性：如果路径存在，随着样本数量增加，路线图包含一条路径的概率趋近于 1。

它的主要弱点是狭窄通道。均匀随机样本很少落在自由空间的狭窄区域中，因此路线图可能无法连通实际上相连的区域。为解决这一问题，人们开发了有偏采样策略，例如在障碍物边界附近采样。PRM* 是一种变体，它通过选择连接半径使路线图具有渐近最优性。

为何重要

PRM 表明，随机采样可以让运动规划在多自由度机器人上变得切实可行，而在这类机器人上精确方法是难以处理的。只要机器人在同一环境中反复工作，例如固定的工业单元，它的路线图思想就仍然有用。

主要应用

• 固定工作单元中机械臂的多查询运动规划
• 静态地图中移动机器人的运动规划
• 人形机器人和双臂机器人等高自由度系统的规划
• 基于采样的规划的教学和基准测试

实际应用

团队通常通过 OMPL 使用 PRM，在机械臂规划中则常常经由 MoveIt 使用，在那里 PRM 和 PRM* 与 RRT-Connect 等基于树的规划器并列。由于路线图可以存储和重复使用，PRM 适合固定的工作单元，在那里机械臂围绕同一批夹具在许多位姿之间移动：路线图离线构建，在运行时查询，只在物体可能已移动的地方重复进行碰撞检测。工程师会调整样本数量和连接半径，并留意路线图中不连通的分量，这通常意味着存在一个需要更多或更有针对性样本的狭窄通道。

常见误解

• 只要存在路径，PRM 就总能找到 — 它是概率完备的，因此这一保证只在样本数量趋于无穷的极限下成立
• PRM 主要用于 2D 地图 — 它的主要用途是高维构型空间，例如机械臂的关节空间
• 路线图永远有效 — 如果障碍物移动，受影响的边必须重新检查，或者重新构建路线图

谁需要了解

• 运动规划工程师
• 工业机器人单元集成商
• 操作研究人员
• 学习基于采样的规划的机器人专业学生

相关技术

• OMPL
• MoveIt
• RRT
• PRM*
• A 搜索（A Search）
• 构型空间（Configuration Space）

相关术语

• Motion Planning
• RRT*
• Configuration Space

相关项目

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design

视频

• Modern Robotics, Chapter 10.5: Sampling Methods for Motion Planning (Part 1 of 2): Northwestern Robotics