Probabilistic Roadmap (PRM)

PRM strictly separates computation into a preprocessing phase and a query phase. During preprocessing, the planner randomly samples the Configuration Space (C-Space) and connects valid, collision-free configurations into a graph (the roadmap). During the online query phase, start and goal configurations are connected to the roadmap, and a graph search algorithm like A* finds the shortest path. This separation means the heavy computational cost is paid once, enabling sub-second responses to multiple queries.

PRM is probabilistically complete, not resolution-complete. This means the probability of finding a path, if one exists, approaches 1 as the number of sampled nodes approaches infinity. In practice, this allows PRM to solve problems in high-dimensional spaces that would be computationally intractable for deterministic, grid-based methods. The trade-off is that failure to find a path does not definitively prove no path exists; it may indicate insufficient sampling density in narrow passages.

The primary failure mode of standard PRM is the narrow passage problem. In C-Space, valid paths often squeeze through tight corridors. Uniform random sampling has a vanishingly small probability of placing nodes inside these critical regions. This leads to disconnected roadmap components. Advanced variants address this through biased sampling strategies:

• Gaussian sampling: Concentrates samples near obstacle boundaries
• Bridge test: Identifies narrow corridors by probing points between obstacles
• Medial axis sampling: Targets the topological skeleton of free space

PRM relies on two critical sub-components. The local planner checks if a straight-line path between two configurations is collision-free, typically using the Gilbert-Johnson-Keerthi (GJK) Algorithm for convex shapes or Continuous Collision Detection (CCD) for swept volumes. The distance metric defines the cost of moving between configurations. For rigid bodies, a weighted Euclidean distance in C-Space is common. For articulated robots, the metric must account for joint limits and the non-linear mapping between joint space and workspace, often using the manipulability ellipsoid.

PRM and Rapidly-exploring Random Tree (RRT) are both sampling-based but serve different use cases. PRM is a multi-query planner: build the roadmap once, then answer many queries in the same static environment. RRT is a single-query planner: it grows a tree from the start state toward the goal for each new problem. PRM is preferred for known, static workspaces like a robotic workcell. RRT excels in dynamic environments or when the robot's geometry changes, as rebuilding a PRM roadmap is expensive. Informed RRT* bridges the gap by focusing sampling once a solution is found.

PRM is a core algorithm in the Open Motion Planning Library (OMPL), which serves as the planning backend for MoveIt, the standard motion planning framework in the Robot Operating System (ROS). In MoveIt, PRM is configured as the ompl_interface/OMPLPlanner with the PRM or PRMstar (asymptotically optimal variant) plugin. The framework handles the integration with Inverse Kinematics (IK) solvers and Trajectory Optimization post-processing, allowing engineers to deploy PRM on real manipulators without implementing the low-level sampling and collision-checking routines.

A single-query sampling-based planner that builds a space-filling tree from the start state. Unlike PRM's two-phase approach, RRT is designed for online planning in high-dimensional spaces without a preprocessing step. Variants like RRT* provide asymptotic optimality by rewiring the tree as samples are added. Best suited for scenarios where the environment changes between queries, making PRM's roadmap construction impractical.

The mathematical foundation underlying all sampling-based planners. C-Space transforms the robot into a point by mapping every possible configuration to a coordinate in an n-dimensional space, where n equals the robot's Degrees of Freedom (DOF). Obstacles are inflated by the robot's geometry, reducing the path planning problem to finding a continuous curve for a point through free space. PRM samples are drawn directly from this space.

The computational bottleneck in PRM construction. Each sampled configuration and edge must be verified as collision-free. Key algorithms include:

• Gilbert-Johnson-Keerthi (GJK): Computes minimum distance between convex shapes
• Signed Distance Fields (SDF): Precompute distance to nearest obstacle for O(1) queries
• Continuous Collision Detection (CCD): Prevents tunneling by checking entire swept volumes along edges

A post-processing refinement step applied after PRM finds a geometric path. While PRM produces a piecewise-linear path through C-Space, trajectory optimization smooths this into a dynamically feasible trajectory by minimizing jerk, acceleration, or energy subject to kinematic constraints. Techniques like CHOMP and STOMP use gradient-based optimization to push paths away from obstacles while maintaining smoothness.

An asymptotically optimal single-query planner that bridges concepts from both PRM and RRT. Once an initial solution is found, sampling is restricted to an ellipsoidal subset of the configuration space defined by the current solution cost. This focused sampling dramatically accelerates convergence toward the optimal path. Unlike PRM, it does not require a preprocessing phase, making it suitable for dynamic environments.

The de facto standard open-source library implementing PRM and related algorithms. OMPL provides:

• Multiple PRM variants including PRM*, LazyPRM, and PRM with obstacle-based sampling
• Integration with MoveIt for robotic arm planning
• Pluggable samplers, distance metrics, and collision checkers
• Benchmarking tools for comparing planner performance Used extensively in ROS-based industrial automation systems.