Probabilistic Roadmaps

A robot arm folding car doors, a surgical robot threading between organs, a video-game character weaving through a crowd — all face the same core challenge: how do you find a collision-free path through a complex space when you can barely describe that space explicitly?

One elegant answer is the Probabilistic Roadmap (PRM), introduced by Kavraki, Švestka, Latombe, and Overmars in 1996. The idea sounds almost too simple: scatter random collision-free points through the space, connect nearby ones with a straight-line check, and call the resulting graph a roadmap. Build that graph once, then answer arbitrarily many path queries by connecting your start and goal into it and running shortest-path search.

The magic is the separation between the one-time construction cost and the near-instant query cost. You pay once to learn the topology of free space; you reap the benefit across thousands of queries. This trade-off is central to understanding what PRM is — and what it is not.

The demo below builds a probabilistic roadmap in a 2-D obstacle field. Click Build Roadmap to scatter random collision-free nodes and connect nearby pairs. Then click Find Path to run a shortest-path search from the green start to the red goal.

<!-- {{c_html_intro}} -->
<div class="controls">
  <button id="btnBuild" type="button">{{btn_build}}</button>
  <button id="btnPath" type="button">{{btn_find}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="380" height="320"></canvas>
<div id="status" class="status">{{hint_build}}</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; display: block;
         background: #f5f8fa; max-width: 100%; }
.status { font-size: .9rem; font-weight: 600; margin-top: .45rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }

// Code not found

Notice the asymmetry. Building the roadmap takes a moment — each new node is tested for collisions and each candidate edge is checked along its length. Querying a path is then nearly instant: the roadmap is a plain graph and any shortest-path algorithm handles it in milliseconds. Build once, query many times.

PRM is not a single algorithm but a family of ideas, and its complexity picture has several layers.

Building the roadmap with $n$ nodes and connection radius $r$:

• Collision-checking each node costs $O(n)$ calls; checking each candidate edge adds $O(n^2)$ in the worst case, though practical implementations use $k$-nearest neighbours to keep it closer to $O(n \log n)$.
• Memory is $O(n + m)$ where $m$ is the number of edges that pass collision checks.

Querying the roadmap:

• Connect start and goal to the roadmap — one local connection each.
• Run Dijkstra or $A^*$ on the graph: $O((n + m) \log n)$ in the worst case, milliseconds for typical roadmap sizes.

Probabilistic completeness is the key theoretical guarantee: as $n \to \infty$, if a path exists, PRM will find one with probability approaching 1. The rate of convergence depends on the clearance of free space — narrow passages slow everything down, a known weakness of basic PRM.

Asymptotic optimality (PRM*) requires a shrinking connection radius $r(n) \propto (\log n / n)^{1/d}$ in $d$ dimensions; with this schedule the path cost converges to the optimum as $n \to \infty$.

The build-once-query-many idea travels well across domains where the geometry of free space is complex and queries are plentiful:

• Industrial robot arms: a factory cell changes layout rarely but runs the same arm through thousands of trajectories per day. Build the roadmap overnight, query in real time.
• Autonomous vehicles: the configuration space of a car in a parking structure is low-dimensional but obstacle-rich; PRMs and their variants seed motion planners on self-driving platforms.
• Protein folding and molecular docking: atoms occupy a high-dimensional conformation space; sampling-based planners derived from PRM explore folding pathways and binding poses.
• Character animation and game AI: game engines use roadmap-style structures to let dozens of characters navigate complex environments simultaneously without per-frame path searches.
• Surgical robotics: planning collision-free paths for a tool near delicate tissue is exactly the narrow-passage challenge PRMs are tuned to handle.

PRM shares its sampling philosophy with Rapidly-exploring Random Trees (RRT), and together they dominate modern motion planning for high-dimensional systems. The lesson is general: when the obstacle geometry is too complex to reason about symbolically, random sampling can still discover the shape of free space.

Probabilistic Roadmaps capture a beautiful algorithmic trade-off: invest once in learning the shape of free space through random sampling, then reap the benefit across every future query. The roadmap itself is just a graph — the depth is in how that graph is built and what it guarantees.

The PRM idea also teaches a broader lesson. When a space is too complex to describe exactly, random sampling often reveals its structure faster than any explicit construction. That insight underlies not just motion planning but also Monte Carlo methods, random hashing, and the growing family of randomised algorithms at the heart of modern computing. Next time you watch a robot arm move gracefully around an obstacle, remember: somewhere a random graph made it possible.