Probabilistic Roadmap (PRM)

PRM strictly separates planning into an offline construction phase and an online query phase.

• Construction Phase: Randomly samples the robot's configuration space (C-Space) to generate collision-free milestones. It then connects nearby milestones with simple local planners to form a graph (the roadmap).
• Query Phase: Given a specific start and goal configuration, the algorithm connects these points to the existing roadmap and performs a standard graph search (e.g., A*) to find a path. This separation makes PRM highly efficient for multiple queries in a static environment, as the expensive roadmap is built once and reused.

PRM is probabilistically complete. This means that as the number of random samples approaches infinity, the probability that the algorithm will find a solution, if one exists, converges to 100%. It does not guarantee optimality or a solution in finite time, but it provides a high probability of success with sufficient sampling. This property makes it highly effective for complex, high-dimensional spaces (e.g., 7-DOF robotic arms) where deterministic, complete planners become computationally intractable.

The algorithm's performance hinges on its sampling strategy in C-Space. Basic PRM uses uniform random sampling, which can be inefficient in narrow passages—regions critical for connectivity that occupy a tiny volume of C-Space. Advanced variants address this with:

• Gaussian Sampling: Biases samples near obstacle boundaries.
• Bridge Testing: Actively looks for samples that lie between two obstacles.
• Obstacle-Based Sampling: Concentrates samples on the surface of C-Space obstacles. Effective sampling is key to ensuring roadmap connectivity without an excessive number of collision checks.

After sampling milestones, PRM uses a local planner to attempt connections between nearby nodes. The simplest method is a straight-line interpolation in C-Space, checking for collisions at small increments. The connection heuristic determines which nodes to attempt to connect. A common approach is to connect each new milestone to its k-nearest neighbors or to all neighbors within a fixed radius. This involves a critical trade-off:

• Too few connections: The roadmap may be disconnected.
• Too many connections: Computational cost balloons due to excessive collision checking. Tuning this heuristic is essential for performance.

PRM excels in specific scenarios due to its design:

• High-Dimensional C-Spaces: Scales better to complex robots (e.g., manipulators, humanoids) than combinatorial planners.
• Static Environments: The two-phase design is perfect for environments where the map is known and fixed.
• Multiple Queries: The same roadmap can efficiently solve many start-goal problems (e.g., task and motion planning).
• Parallelizability: The sampling and local planning steps are highly parallel, benefiting from multi-core processing. It is a cornerstone algorithm in libraries like the Open Motion Planning Library (OMPL).

PRM's weaknesses have led to important algorithmic variants:

• Dynamic Environments: Basic PRM cannot handle moving obstacles. PRM* and other optimal planners integrate rewiring.
• Narrow Passages: Uniform sampling fails. Variants like OBPRM (Obstacle-Based PRM) specifically target passage sampling.
• Single-Query Inefficiency: Building a full roadmap for one query is wasteful. RRT (Rapidly-exploring Random Tree) was developed as a single-query alternative.
• Path Quality: The initial path is often suboptimal. PRM* asymptotically converges to an optimal path by using an intelligent connection strategy and rewiring. Understanding these limitations is key to selecting the right planner for a given robotics application.

PRM's classic and most efficient application is for multi-query planning in known, static workspaces. The algorithm's two-phase construction-then-query structure is ideal here.

• Phase 1: Roadmap Construction: A graph of collision-free robot configurations (nodes) and feasible local paths between them (edges) is built once, offline. This is computationally expensive but a one-time cost.
• Phase 2: Path Querying: For any new start-goal pair within the same static environment, a standard graph search algorithm (like A* or Dijkstra's) finds a path on the pre-computed roadmap in milliseconds.

This makes PRM the planner of choice for applications like:

• Robotic machining and welding in a fixed factory cell.
• Autonomous warehouse navigation where shelf layouts are known.
• Surgical robot pre-planning based on a patient's pre-operative scan.

PRM excels in planning for robots with many degrees of freedom (DOF), where the configuration space (C-space) is high-dimensional and geometrically complex.

• The Curse of Dimensionality: Analytical planners struggle in spaces with 7+ DOF (e.g., robotic arms, humanoid robots). Explicitly representing obstacles in C-space becomes intractable.
• PRM's Sampling Approach: By randomly sampling the C-space and checking for collisions, PRM builds a sparse graph that captures the connectivity of the free space without needing to model its complex boundaries explicitly.
• Practical Example: Planning a collision-free path for a 7-DOF robotic arm to reach into a cluttered shelf, avoiding obstacles with both the arm and its payload. PRM's samples effectively "feel out" the narrow passages in the high-DOF C-space.

PRM is rarely used in isolation. It is typically the global planner in a hierarchical architecture, providing a coarse, collision-free guide for a local planner or reactive controller.

• Global Path: PRM generates a sequence of waypoints (graph nodes) from start to goal.
• Local Execution: A Dynamic Window Approach (DWA) or Model Predictive Controller (MPC) then tracks this path, handling dynamic obstacles, unmodeled details, and the robot's precise dynamics in real-time.
• Replanning: If the local planner gets stuck (e.g., a new permanent obstacle blocks a path edge), the system can trigger PRM to replan from the robot's current configuration, updating the global roadmap if necessary.

This decoupling is critical for robust autonomy, allowing PRM to handle complex, static geometry while faster algorithms manage immediate reactions.

PRM established the core paradigm for sampling-based motion planning. Many advanced, state-of-the-art algorithms are direct evolutions or hybrids of the PRM concept.

• PRM*: An asymptotically optimal variant that rewires the roadmap to progressively lower the cost of paths as more samples are added.
• Lazy PRM: Defers expensive edge collision checking until a query is performed, speeding up the initial roadmap construction phase.
• Rapidly-exploring Random Graphs (RRG): A variant that grows a graph more like a Rapidly-exploring Random Tree (RRT) but maintains a roadmap structure, facilitating multi-query planning.
• Hybridization: PRM's roadmap can be used to seed or guide other planners. For example, a PRM-generated path can provide an initial guess for a trajectory optimization solver like Sequential Quadratic Programming (SQP) to smooth and optimize the final motion.

PRM is effectively applied to manipulation planning, where the robot must move an object through a cluttered space, and rearrangement planning, where it must move multiple objects to achieve a goal.

• Composite C-Space: For manipulation, the configuration space is expanded to include the pose of the manipulated object. PRM samples both robot and object configurations.
• Mode Switching: The roadmap can encode different "modes," such as grasping an object, carrying it, and placing it. Transitions between these modes become edges in a more complex, multi-modal roadmap.
• Example - Table Clearing: A robot arm planning to pick up dishes from a table and place them in a dishwasher. PRM can plan paths for the arm to approach each dish, the path while holding the dish (with an enlarged collision model), and the path to the dishwasher rack, all within a single, queriable data structure.

The Configuration Space (C-Space) is the fundamental mathematical abstraction where motion planning occurs. It represents every possible state of a robot as a single point. For a robotic arm, a point in C-space is defined by its joint angles; for a mobile robot, it could be its (x, y, θ) pose.

• Key Concept: Physical obstacles in the workspace are transformed into forbidden regions or C-obstacles within this higher-dimensional space.
• PRM's Role: PRM's sampling phase randomly generates points within this C-space, checking each for collision. The resulting roadmap is a graph embedded directly in the C-space, enabling pathfinding in this abstract representation.

Rapidly-exploring Random Tree (RRT) is the primary single-query counterpart to the multi-query PRM. While PRM builds a complete roadmap for repeated use, RRT grows a tree incrementally from a specific start point toward a goal.

• Algorithm Contrast: RRT is designed for efficiency in finding a single path as quickly as possible, often without building a dense map of the entire free space.
• Hybrid Use: RRT* (RRT-star) is an asymptotically optimal variant that rewires the tree to improve path quality. In practice, PRM is often used for global, multi-query planning, while RRT variants handle dynamic, single-query scenarios or local replanning.

Sampling-Based Motion Planning is the overarching algorithmic paradigm to which PRM belongs. These methods avoid explicitly constructing the high-dimensional C-space and its obstacles, which is computationally prohibitive.

• Core Principle: Instead, they probe the space with a collision detection module, treating it as a black box. Algorithms like PRM and RRT use these samples to build approximate representations (graphs or trees) of the free space.
• Probabilistic Completeness: These planners are not guaranteed to find a path if one exists, but the probability of success approaches 1 as the number of samples increases—a property known as probabilistic completeness.

Collision Detection is the critical, computationally expensive subroutine at the heart of PRM and all sampling-based planners. For each sampled configuration or potential edge in the roadmap, the algorithm must determine if the robot's geometry intersects with any obstacle.

• Performance Bottleneck: The efficiency of the collision checker directly dictates planner performance. It often uses hierarchical representations like bounding volume trees (e.g., OBBTrees).
• Two-Phase Check: PRM typically performs a two-stage check: a fast broad-phase check to reject obviously collision-free samples, followed by a precise narrow-phase geometric intersection test for candidates.

Trajectory Optimization is a complementary approach that finds a smooth, optimal path (trajectory) by solving a Nonlinear Programming (NLP) problem. It contrasts with PRM's discrete, graph-based search.

• Relationship to PRM: A common pipeline uses PRM to find a feasible, collision-free geometric path in C-space. This path then serves as an initial guess for a trajectory optimization solver (e.g., using Sequential Quadratic Programming) to refine it into a time-parameterized, dynamically feasible, and optimal trajectory.
• Optimization Criteria: The optimizer minimizes cost functions like total time, energy consumption, or jerk (the derivative of acceleration), producing motions that are executable by real actuators.