A probabilistic roadmap pre-builds a network of collision-free connections through a space, so a robot can quickly find paths between many start-goal pairs — the sampling-based planner of choice when the environment stays fixed.
A probabilistic roadmap scatters random points through the free space and connects nearby ones into a web of safe routes. Once that map exists, the robot can quickly plan a path between almost any two spots by searching the web.
Some robots plan one path and move on; others must plan many paths through the same space over and over. For the latter, the probabilistic roadmap (PRM) is ideal — do the hard work once, then answer queries fast.
Two phases
PRM splits planning into a build phase and a query phase:
Build (learning) the roadmap. Randomly sample many points in the configuration space, keep the collision-free ones, and connect each to its nearby neighbors with collision-free local paths. The result is a graph (roadmap) — a web of safe routes woven through the free space.
Query. To plan from a start to a goal, connect both into the roadmap and run a graph search (A*/Dijkstra) to find a path — fast, because the hard collision-checking work is already done.
Build a reusable web of safe routes
The roadmap is built once and reused. Any new start-goal pair becomes a quick graph search, not a fresh plan from scratch.
PRM vs RRT
Both are sampling-based, but suit different situations:
PRM — multi-query: build the roadmap once, answer many path requests against a fixed environment cheaply. Great for a robot arm repeatedly moving in the same workspace.
RRT / RRT* — single-query: grow a tree from the start toward the goal, ideal when you plan once, or when the environment changes so a prebuilt roadmap would be stale.
The heavy cost in both is collision checking — PRM amortizes it across many queries.
Strengths and limits
Efficient reuse. Unbeatable when the space is static and queried repeatedly.
Handles high dimensions. Like all sampling planners, it scales where grids can't.
Stale if the world changes. A moving obstacle invalidates roadmap edges, requiring updates (dynamic/lazy PRM variants help).
Completeness. Probabilistically complete — with enough samples it finds a path if one exists.
Why it matters
PRM introduced the powerful idea of precomputing a reusable map of free space for fast repeated planning. It's a foundational sampling-based planner, especially for fixed-workspace robot arms, and a cornerstone of the motion-planning toolkit alongside RRT.
