Probabilistic Roadmap (PRM)

PRM strictly separates computation into a preprocessing (learning) phase and a query phase. In the learning phase, it randomly samples the configuration space to build a graph of collision-free nodes (milestones) connected by local paths. This graph, the roadmap, is stored. In the query phase, given a specific start and goal, it connects these states to the roadmap and performs a graph search (e.g., A*) to find a path. This separation makes it efficient for multiple queries in the same static environment.

PRM is probabilistically complete. This means that as the number of random samples in the learning phase approaches infinity, the probability that the planner will find a solution if one exists converges to 1. It does not guarantee optimality. This property makes it highly effective for complex, high-dimensional spaces (like robotic arm planning) where complete (combinatorial) planners are computationally infeasible.

A core advantage of PRM is its multi-query efficiency. The computationally expensive process of exploring the free space and building the connectivity graph is performed once. Afterward, any number of path queries between different start-goal pairs can be answered rapidly using standard graph search on the precomputed roadmap. This is ideal for logistics scenarios where a fleet of agents operates in a fixed warehouse layout.

The standard PRM is designed for static environments. Its precomputed roadmap becomes invalid if obstacles move or appear. This necessitates:

• Roadmap repair strategies to update invalid edges/nodes.
• Lazy evaluation techniques that check for collisions only on candidate paths during query.
• Use as a global planner paired with a local, reactive collision avoidance layer (like DWA or ORCA) for real-time fleet orchestration in semi-dynamic spaces.

A well-known limitation of uniform random sampling in PRM is the narrow passage problem. The probability of placing a sample inside a tight, critical corridor is low, which can prevent the roadmap from connecting two large regions of free space. Mitigation strategies include:

• Bridge Test: Sampling pairs of points and checking if the midpoint is in collision.
• Gaussian Sampling: Biasing samples near obstacle boundaries.
• Workspace Guidance: Using the task space to guide configuration space sampling.

PRM exists within a family of sampling-based planners:

• RRT (Rapidly-exploring Random Tree): A single-query planner that grows a tree from the start state. It is often more efficient than PRM for one-off queries in dynamic planning.
• RRT*: An asymptotically optimal variant of RRT.
• Lattice Planners: Use a pre-defined, dense set of motion primitives instead of random sampling, guaranteeing dynamical feasibility but requiring more structured state spaces. PRM's graph structure makes its roadmap more reusable than an RRT tree.

PRM excels in planning for robots with many degrees of freedom, such as articulated manipulators (e.g., industrial robot arms) or mobile manipulators. The algorithm's random sampling efficiently explores complex, high-dimensional spaces where traditional grid-based searches are computationally prohibitive.

• Key Use: Planning collision-free arm trajectories around complex obstacles in manufacturing cells.
• Advantage: Decouples the complexity of the robot's kinematics from the planning problem by sampling in the configuration space (C-space).

The classic two-phase PRM structure (learning then querying) is ideal for static or semi-static environments where multiple start-goal queries are expected. The upfront cost of building the roadmap is amortized over many fast graph searches.

• Key Use: Warehouse logistics where the shelf layout is fixed, but thousands of robots need paths from various start points to various pick stations daily.
• Implementation: The roadmap is built once during system initialization. A or Dijkstra's algorithm* is then used on the graph for each new query, yielding paths in milliseconds.

PRM is often used as a global planner to generate a coarse, collision-free path. This path is then passed to a local planner (e.g., Dynamic Window Approach, Model Predictive Control) for refinement and real-time, reactive obstacle avoidance.

• Key Use: Autonomous mobile robot (AMR) navigation where PRM provides the high-level route, and a local planner handles dynamic obstacles (people, other robots) and smooths the trajectory.
• Workflow: PRM → Coarse Waypoints → Local Planner → Executable Velocity Commands.

The core PRM concept has spawned numerous optimized variants that address its limitations, extending its applicability:

• PRM*: An asymptotically optimal version that includes a rewiring step, continuously improving path quality as more samples are added.
• Lazy PRM: Defers expensive collision checking until a query is made, significantly speeding up the learning phase.
• Dynamic PRM: Maintains the roadmap over time by repairing or updating regions affected by environmental changes, bridging towards real-time replanning.

PRM is highly effective in environments with cluttered obstacles and narrow passages. By randomly sampling the free space, it has a probabilistic chance of discovering these passages, which might be missed by deterministic cell-decomposition methods.

• Key Use: Disaster response robotics (search and rescue), where robots must navigate through highly unstructured rubble.
• Challenge: The narrow passage problem can require intelligent sampling strategies (e.g., Gaussian sampling near obstacles) to improve roadmap connectivity in constrained spaces.

While not a direct multi-agent algorithm, PRM provides the foundational pathfinding capability within larger Multi-Agent Path Finding (MAPF) and orchestration systems. Each agent in a heterogeneous fleet can use its own PRM instance (tailored to its kinematics) for individual goal-directed navigation.

• System Role: The orchestration middleware handles task allocation and high-level coordination, while individual agents use PRM-based planners for point-to-point movement.
• Consideration: Pure PRM does not handle inter-agent coordination; it must be combined with collision avoidance systems (e.g., Velocity Obstacles, ORCA) or a centralized Conflict-Based Search layer.

A sampling-based motion planning algorithm that incrementally builds a space-filling tree from a start state towards a goal region. Unlike PRM's two-phase (preprocess/query) approach, RRT is a single-query algorithm that explores the configuration space on-demand. It is particularly effective for non-holonomic and kinodynamic planning problems where vehicle dynamics are critical. Variants like RRT* introduce a rewiring step for asymptotic optimality.

The computational problem of finding collision-free paths for multiple agents from their start to goal locations, optimizing a global objective like makespan (total time) or sum-of-costs. PRM can serve as the underlying single-agent planner within MAPF algorithms. However, MAPF requires higher-level coordination to resolve agent-agent conflicts, which PRM alone does not handle. Common MAPF algorithms include Conflict-Based Search (CBS) and Priority-Based Search.

An advanced control method where a dynamic model of the system is used to predict future behavior. At each control step, it solves a finite-horizon optimization problem to determine optimal control actions, implementing only the first step before re-optimizing (receding horizon control). While PRM provides a geometric path, MPC is used for trajectory tracking and dynamic obstacle avoidance, handling the continuous control inputs and system constraints in real-time.

The problem of finding a trajectory that satisfies both kinematic constraints (e.g., non-holonomic steering) and dynamic constraints (e.g., acceleration, torque limits). Standard PRM plans in configuration space (C-space). Kinodynamic PRM extends the approach to state-space planning, where nodes represent both configuration and velocity, and edges are dynamically feasible motion primitives. This is crucial for high-speed autonomous vehicles and agile robots.

An incremental search algorithm that reuses previous search results to efficiently find new optimal paths when edge costs in a graph change. It is a core algorithm for real-time replanning. While PRM builds the graph, LPA* is an efficient query algorithm for that graph when the cost of traversing edges (e.g., due to newly discovered obstacles) changes dynamically. This combination enables fast plan repair in partially known environments.

Reactive or predictive algorithms that prevent physical conflicts. PRM is a global planner that finds a nominally collision-free path. Local collision avoidance systems (e.g., Velocity Obstacles, Dynamic Window Approach) act as a safety layer, executing short-term maneuvers to avoid dynamic obstacles not present during PRM planning. This creates a hierarchical architecture: PRM provides the strategic route, while reactive systems handle tactical deviations.