Probabilistic Roadmap
- Also called: PRM, probabilistic roadmap method
- Category: Planning & manipulation › Motion planning
- Tags: motion-planning, sampling-based-planning, path-planning, graph-search, manipulation
A sampling-based motion planner that builds a reusable graph of random collision-free configurations and the feasible paths between them, then answers planning queries by graph search.
Definition
Probabilistic Roadmap (PRM) is a sampling-based motion planning method introduced by Kavraki, Švestka, Latombe and Overmars in 1996. Instead of searching the configuration space afresh for every request, PRM first builds a graph, the roadmap, that captures the connectivity of the robot's free space, and then uses that graph to answer any number of start-to-goal queries.
Planning has two phases. In the construction phase, the planner samples random configurations of the robot, keeps the collision-free ones as nodes, and tries to connect each node to nearby nodes with a simple local planner, usually a straight line in configuration space checked for collisions at fine intervals. Successful connections become edges. In the query phase, the start and goal configurations are connected to the roadmap, and a graph search such as Dijkstra's algorithm or A* finds a path through it.
PRM suits multi-query problems, where the environment is static and the robot must plan many motions in the same space, because the expensive roadmap construction is done once. It is probabilistically complete: if a path exists, the probability that the roadmap contains one approaches 1 as the number of samples grows.
Its main weakness is narrow passages. Uniform random samples rarely land in thin regions of free space, so the roadmap may fail to connect areas that are in fact linked. Biased sampling strategies, such as sampling near obstacle boundaries, were developed to address this. PRM* is a variant that chooses connection radii so that the roadmap becomes asymptotically optimal.
Why it matters
PRM showed that random sampling could make motion planning practical for robots with many degrees of freedom, where exact methods are intractable. Its roadmap idea remains useful whenever a robot works repeatedly in the same environment, such as a fixed industrial cell.
Key applications
- Multi-query motion planning for robot arms in fixed workcells
- Path planning for mobile robots in static maps
- Planning for high-degree-of-freedom systems such as humanoids and dual-arm robots
- Teaching and benchmarking sampling-based planning
In practice
Teams typically use PRM through OMPL, often via MoveIt for arm planning, where PRM and PRM* sit beside tree-based planners such as RRT-Connect. Because a roadmap can be stored and reused, PRM fits fixed workcells in which an arm moves between many poses around the same fixtures: the roadmap is built offline and queried at run time, with collision checks repeated only where objects may have moved. Engineers adjust the number of samples and the connection radius, and they watch for disconnected components in the roadmap, which usually point to a narrow passage that needs more or better-targeted samples.
Common misconceptions
- PRM always finds a path if one exists — it is probabilistically complete, so the guarantee holds only in the limit of infinitely many samples
- PRM is mainly for 2D maps — its main use is in high-dimensional configuration spaces such as the joint space of an arm
- A roadmap stays valid forever — if obstacles move, affected edges must be rechecked or the roadmap rebuilt
Who should know this
- Motion planning engineers
- Industrial robot cell integrators
- Manipulation researchers
- Robotics students learning sampling-based planning
Related technologies
- OMPL
- MoveIt
- RRT
- PRM*
- A* Search
- Configuration Space
Related terms
Related projects
- 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
Videos
- Modern Robotics, Chapter 10.5: Sampling Methods for Motion Planning (Part 1 of 2): Northwestern Robotics