Probabilistic Roadmap
Also known as: PRM, Roadmap Method
The Probabilistic Roadmap (PRM) method is a motion planning algorithm that builds a pre-computed graph (roadmap) of feasible paths through the configuration space by sampling random configurations and connecting them if collision-free. Introduced by Kavraki et al. in 1996, PRM is powerful for multi-query planning scenarios where many path queries are answered, amortizing roadmap construction cost across many queries.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use PRM when you need to answer many motion planning queries (100s-1000s) in the same environment; the roadmap amortizes construction cost. Ideal for scenarios like warehouse automation with repeated queries or CAD systems. Avoid PRM if you need single fast queries (RRT faster) or if the environment changes frequently (roadmap becomes invalid).
Strengths & limitations
- Suitable for multi-query scenarios; roadmap reuse amortizes construction cost.
- Works well in high-dimensional spaces with complex obstacles.
- Asymptotically optimal with sufficient samples.
- Simple underlying mechanics (sampling, nearest neighbors, graph search).
- Extends to kinodynamic planning and non-holonomic constraints.
- High initial computation cost; roadmap construction time before first query.
- Memory usage grows with roadmap size (1000s-100,000s nodes for complex tasks).
- Nearest-neighbor queries can be slow in high dimensions.
- May miss narrow passages; requires careful parameter tuning.
- Roadmap must be rebuilt if environment changes.
Frequently asked
What parameters control PRM: number of samples N and neighborhood radius k?
N controls graph density; more samples improve coverage but increase cost. Start with N = 1000 and double until roadmap quality improves. k (nearest neighbors) controls edge density; typical values k = 10-30. Larger k increases connectivity but computation cost O(N log N). Adaptive sampling adds more samples in underexplored regions.
How do I detect if my PRM roadmap is disconnected?
After building the roadmap, check connectivity: label each node with a connected component ID (using BFS/DFS). If start and goal are in different components, the roadmap is disconnected. Add more samples near component boundaries or increase k to bridge gaps.
How does PRM handle narrow passages?
Standard PRM fails in narrow passages; random sampling rarely finds configurations inside narrow spaces. Solutions: (1) Gaussian sampling (sample near obstacles), (2) deformation-based methods (pull roadmap toward obstacles), (3) mixed-mode sampling (combine random and collision-based sampling). These techniques focus samples on difficult regions.
Can I incrementally add queries to an existing roadmap?
Yes, this is a key advantage of PRM: once the roadmap is built, new queries are answered by connecting start/goal to the graph. No need to rebuild. If a query fails to connect, you can add new roadmap samples (refresh) or adapt the graph topology.
Sources
- Kavraki, L. E., Svestka, P., Latombe, J. C., & Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4), 566-580. DOI: 10.1109/70.508439 ↗
- Overmars, M. H., & Svestka, P. (1992). A probabilistic learning approach to motion planning. Proceedings of the Fourth Workshop on Algorithmic Foundations of Robotics, 19-37. link ↗
- LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press. link ↗
How to cite this page
ScholarGate. (2026, June 3). Probabilistic Roadmap. ScholarGate. https://scholargate.app/en/control-theory/probabilistic-roadmap
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Model Predictive ControlControl Theory↔ compare
- Rapidly-Exploring Random TreeControl Theory↔ compare