PRM (Probabilistic Roadmap)

PRM strictly separates planning into a preprocessing (learning) phase and a query phase. In the learning phase, the algorithm samples the robot's configuration space (C-space), retains collision-free samples as milestones, and connects them to form a graph called the roadmap. This graph is built once and stored. In the query phase, for a specific start-goal pair, the planner attempts to connect these points to the existing roadmap and performs a graph search (e.g., A*) to find a path. This separation makes PRM highly efficient for multiple queries in static environments.

PRM is probabilistically complete. This means that as the number of random samples (N) approaches infinity, the probability that the planner will find a solution if one exists converges to 1. It does not guarantee finding a path in finite time, but it guarantees that the chance of failure decreases exponentially with more samples. This property is crucial for high-dimensional planning problems where deterministic, complete algorithms are computationally intractable.

The core of PRM's efficiency is its avoidance of explicitly modeling obstacle geometry in high dimensions. Instead, it uses a collision detection oracle to test randomly sampled configurations. Key sampling strategies include:

• Uniform Random Sampling: The baseline method, simple but may be inefficient in narrow passages.
• Gaussian Sampling: Biases samples near obstacle boundaries to improve connectivity.
• Bridge Test Sampling: Actively seeks configurations in narrow passages by sampling in collision and checking if endpoints of a local bridge are free.
• Obstacle-Based Sampling: Generates samples on the surface of C-space obstacles.

After sampling milestones, PRM uses a simple, deterministic local planner (e.g., a straight line in C-space) to attempt connections between nearby milestones. Connections are added to the roadmap graph only if the local path is verified as collision-free. The "nearness" of milestones is defined by a distance metric in C-space (e.g., Euclidean distance for angles). The resulting roadmap is an undirected graph approximating the connectivity of the free space. Its quality depends heavily on the sampling strategy and the connection radius (k-nearest neighbors or fixed radius).

PRM excels in specific scenarios compared to other planners:

• vs. Grid Search/Visibility Graphs: PRM scales better to high-dimensional C-spaces (e.g., robotic arms with 7+ DOF) where grid-based methods suffer from the curse of dimensionality.
• vs. Single-Query Planners (like RRT): PRM is superior for multiple queries in a fixed environment (e.g., a manufacturing cell) because the roadmap is built once and reused. RRT typically rebuilds a tree for each query.
• vs. Complete (Exact) Planners: PRM trades deterministic completeness for computational feasibility in complex spaces, making it practical for real-world robotics.

PRM's effectiveness is not universal. Key limitations include:

• Narrow Passage Problem: Uniform sampling has a low probability of generating samples in tight passages, causing roadmap disconnection. Adaptive sampling (Bridge Test) is required.
• Dynamic Environments: The static roadmap becomes invalid if obstacles move. Requires replanning or roadmap repair.
• Path Quality: The initial path from graph search is often jagged. It requires post-processing (e.g., shortcut smoothing, trajectory optimization) for smooth, executable motions.
• Kinodynamic Constraints: Basic PRM plans geometric paths. Extensions (kinodynamic PRM) are needed to handle dynamics, differential constraints, and non-holonomic systems.

This is the canonical use case for PRM. A dense roadmap is constructed once in a known, static environment. This preprocessing phase is computationally intensive but amortizes its cost over many subsequent queries. It is ideal for:

• Industrial robot arms performing repetitive pick-and-place or welding tasks from varying start positions.
• Mobile robot fleets in a warehouse where the shelf layout is fixed, but each robot has unique start and goal locations for each retrieval mission.
• Surgical robots operating within a pre-scanned anatomical model, where the plan must be recalculated for different entry points or targets.

PRM excels where traditional grid-based planners fail due to the curse of dimensionality. By sampling randomly, it efficiently explores complex spaces defined by many degrees of freedom.

• Articulated robot manipulators with 7 or more joints, where the C-space is 7-dimensional or higher.
• Humanoid robots planning whole-body motions that involve coordinated movement of legs, torso, and arms.
• Molecular docking simulations, where the configuration space involves the rotational angles of chemical bonds.

PRM is rarely used in isolation in modern systems. Instead, its principles form the backbone of more sophisticated, adaptive algorithms:

• PRM*: An optimal variant that uses heuristic search (like A*) during the query phase to find the shortest path on the roadmap.
• Lazy PRM: Defers expensive collision checking until a path is found, dramatically speeding up roadmap construction for complex geometry.
• Dynamic Roadmaps: The roadmap is periodically repaired or refined in response to environmental changes, bridging the gap between static preprocessing and full replanning.

PRM operates at the motion planning layer but is crucial for executing plans generated by higher-level task planners.

• A Hierarchical Task Network (HTN) planner decomposes a goal like "fetch the cup" into subtasks ("navigate to kitchen," "grasp cup").
• Each subtask requiring movement (e.g., "navigate to kitchen") is passed to the PRM as a query (start: current pose, goal: kitchen entrance).
• The resulting collision-free path is then passed to a trajectory optimization or Model Predictive Control (MPC) layer for smooth, dynamic execution.

Understanding where PRM struggles is critical for correct application. Key limitations include:

• Dynamic Environments: The static roadmap becomes invalid if obstacles move. Requires complete replanning or a dynamic variant.
• Narrow Passages: Uniform random sampling has a low probability of generating nodes within tight corridors, causing connectivity failure. Techniques like bridge testing or Gaussian sampling are required.
• Single-Query Efficiency: For a one-time path in a new environment, algorithms like RRT (Rapidly-exploring Random Tree) are typically faster, as they focus exploration between the given start and goal.

PRM's role is defined in contrast to other core motion planners:

• vs. RRT: PRM builds a global roadmap for multiple queries; RRT grows a single tree focused on connecting one start-goal pair. PRM is multi-query, RRT is single-query.
• vs. Grid Search (A)**: A searches a discretized grid exhaustively. PRM uses sparse sampling, making it feasible in high-dimensional spaces where grid resolution is impossible.
• vs. Trajectory Optimization: Methods like CHOMP or STOMP optimize a continuous trajectory for smoothness and constraints. PRM finds a feasible, often piecewise linear, geometric path, which can then be used as an initial guess for optimization.

A class of motion planning algorithms that avoid constructing an explicit geometric model of obstacles. Instead, they probe the configuration space with random or deterministic samples to build a graph or tree representation of the free space. PRM is a quintessential sampling-based planner, alongside methods like RRT (Rapidly-exploring Random Tree). Key characteristics include:

• Probabilistic completeness: The probability of finding a solution, if one exists, approaches 1 as sampling time increases.
• Efficiency in high-dimensional spaces, such as those for robotic arms with many joints.
• The trade-off is a lack of optimality guarantees compared to some complete, combinatorial planners.

The foundational mathematical abstraction for motion planning. The C-Space is a representation where every possible state (configuration) of a robot is mapped to a single, unique point. Physical obstacles in the workspace become forbidden regions (C-obstacles) within this abstract space. For a simple 2D mobile robot, the C-Space might be 2D (x, y); for a robotic arm with N joints, it is an N-dimensional manifold. PRM operates directly in the C-Space, sampling points and checking them for collision. Understanding C-Space is critical for grasping why planning is computationally challenging and how sampling provides a practical solution.

A prominent single-query sampling-based planner, often contrasted with the multi-query nature of PRM. RRT incrementally grows a tree structure rooted at the start configuration by randomly sampling the C-Space and extending the tree toward the sample. It is designed to quickly explore large, unexplored volumes of space. Key comparisons with PRM:

• Query Type: RRT is for a single start-goal pair; PRM builds a reusable roadmap for many queries.
• Structure: RRT produces a tree; PRM produces a general graph (roadmap).
• Use Case: RRT is often used for real-time or dynamic planning; PRM is favored for static environments where many plans are needed (e.g., a fixed factory floor). Variants like RRT* provide asymptotic optimality.

The specific problem of finding a geometric path from a start to a goal configuration. It is a subset of the broader motion planning problem, which also considers dynamics, timing, and control. Path planning answers "where to go," while motion planning answers "how and when to go." PRM is fundamentally a path planning algorithm. It finds a sequence of collision-free waypoints in C-Space. The output of a PRM query is a path, which must then be processed by trajectory generation and control systems to become an executable motion command for the robot's actuators.

An informed graph search algorithm used to find the shortest path between nodes. A* uses a cost function f(n) = g(n) + h(n), where g(n) is the cost from the start to node n, and h(n) is a heuristic estimating the cost from n to the goal. Once a PRM roadmap is constructed, querying it for a specific start-goal pair is typically solved using A* (or Dijkstra's algorithm if no heuristic is available). The heuristic guides the search efficiently through the roadmap's graph. This demonstrates the hybrid nature of many planning systems: sampling (PRM) creates the graph, and heuristic search (A) finds the path within it*.

The computational geometry core of any sampling-based planner. For every sample and every potential connection (local path) in the PRM, the algorithm must perform a collision check to ensure the robot does not intersect with any obstacle. This is often the most computationally expensive component. Methods include:

• Broad phase: Quickly culling pairs of objects that are far apart (e.g., using bounding volumes).
• Narrow phase: Performing precise geometric intersection tests on the remaining candidate pairs. The efficiency and accuracy of the collision detection engine directly determine the performance and reliability of the PRM. Probabilistic roadmaps are only as good as their collision checker.