Introduction

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.

Try It: Build and Query

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.

<!-- PRM demo layout - canvas for drawing, controls, and status line -->
<div class="controls">
  <button id="btnBuild" type="button">Build Roadmap</button>
  <button id="btnPath" type="button">Find Path</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<canvas id="canvas" width="380" height="320"></canvas>
<div id="status" class="status">Click "Build Roadmap" to scatter random nodes and connect nearby pairs.</div>

/* PRM demo styles */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Probabilistic Roadmap (PRM) - build a random graph through free space once, */
/* then answer many path queries cheaply with shortest-path search. */

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

/* Rectangular obstacle definitions [x, y, width, height] */
const OBSTACLES = [
  { x: 60,  y: 60,  w: 70, h: 50 },
  { x: 200, y: 80,  w: 60, h: 90 },
  { x: 80,  y: 200, w: 80, h: 55 },
  { x: 270, y: 190, w: 75, h: 60 },
  { x: 155, y: 155, w: 50, h: 45 }
];

/* Fixed start (S) and goal (G) nodes - always added first as nodes[0] and nodes[1] */
const START = { x: 20, y: 20 };
const GOAL  = { x: 355, y: 295 };

const MARGIN = 6;   /* collision margin in pixels - keep nodes away from obstacle edges */
const SAMPLES = 120;
const CONN_RADIUS = 90;  /* connect nodes within this pixel radius if the straight edge is clear */

/* Global roadmap state */
let nodes = [];
let edges = [];
let path = [];
let built = false;

/* Point-in-obstacle test with margin */
function hitRect(px, py, obs) {
  return px >= obs.x - MARGIN && px <= obs.x + obs.w + MARGIN &&
         py >= obs.y - MARGIN && py <= obs.y + obs.h + MARGIN;
}
function inObstacle(px, py) {
  return OBSTACLES.some(o => hitRect(px, py, o));
}

/* Walk along the edge and reject if any sample point hits an obstacle */
function edgeClear(a, b) {
  const steps = Math.ceil(Math.hypot(b.x - a.x, b.y - a.y) / 4);
  for (let i = 0; i <= steps; i++) {
    const t = i / steps;
    const x = a.x + (b.x - a.x) * t;
    const y = a.y + (b.y - a.y) * t;
    if (inObstacle(x, y)) return false;
  }
  return true;
}

/* Euclidean distance between two nodes */
function dist(a, b) {
  return Math.hypot(b.x - a.x, b.y - a.y);
}

/* Build the roadmap - sample free-space nodes then connect nearby pairs */
function buildRoadmap() {
  nodes = [START, GOAL];
  edges = [];
  path = [];

  /* Sample random collision-free nodes */
  let attempts = 0;
  while (nodes.length < SAMPLES + 2 && attempts < SAMPLES * 10) {
    attempts++;
    const px = 5 + Math.random() * (W - 10);
    const py = 5 + Math.random() * (H - 10);
    if (!inObstacle(px, py)) nodes.push({ x: px, y: py });
  }

  /* Connect all pairs within CONN_RADIUS if the straight edge is clear */
  for (let i = 0; i < nodes.length; i++) {
    for (let j = i + 1; j < nodes.length; j++) {
      if (dist(nodes[i], nodes[j]) <= CONN_RADIUS && edgeClear(nodes[i], nodes[j])) {
        edges.push([i, j]);
      }
    }
  }
  built = true;
}

/* Dijkstra shortest-path on the roadmap graph */
function dijkstra() {
  const n = nodes.length;
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  const INF = Infinity;
  const d = Array(n).fill(INF);
  const prev = Array(n).fill(-1);
  d[0] = 0;
  /* Simple priority queue (array sorted on demand - fine for < 200 nodes) */
  const pq = [[0, 0]]; /* [cost, nodeIndex] */
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [dd, u] = pq.shift();
    if (dd > d[u]) continue;
    for (const v of adj[u]) {
      const nd = d[u] + dist(nodes[u], nodes[v]);
      if (nd < d[v]) { d[v] = nd; prev[v] = u; pq.push([nd, v]); }
    }
  }
  /* Reconstruct path from goal (node 1) back to start (node 0) */
  if (d[1] === INF) return [];
  const p = [];
  for (let cur = 1; cur !== -1; cur = prev[cur]) p.unshift(cur);
  return p;
}

/* Render the scene - obstacles, edges, nodes, path, start and goal */
function draw() {
  ctx.clearRect(0, 0, W, H);

  /* Draw obstacles as filled rectangles */
  ctx.fillStyle = '#c8d6e0';
  ctx.strokeStyle = '#8fa5b2';
  ctx.lineWidth = 1;
  for (const o of OBSTACLES) {
    ctx.fillRect(o.x, o.y, o.w, o.h);
    ctx.strokeRect(o.x, o.y, o.w, o.h);
  }

  if (built) {
    /* Draw roadmap edges in light blue */
    ctx.strokeStyle = 'rgba(100,140,180,0.35)';
    ctx.lineWidth = 1;
    for (const [a, b] of edges) {
      ctx.beginPath();
      ctx.moveTo(nodes[a].x, nodes[a].y);
      ctx.lineTo(nodes[b].x, nodes[b].y);
      ctx.stroke();
    }

    /* Draw sampled nodes as small circles */
    ctx.fillStyle = 'rgba(80,120,180,0.65)';
    for (let i = 2; i < nodes.length; i++) {
      ctx.beginPath();
      ctx.arc(nodes[i].x, nodes[i].y, 3, 0, Math.PI * 2);
      ctx.fill();
    }
  }

  /* Draw the found path in orange */
  if (path.length > 1) {
    ctx.strokeStyle = '#e07b00';
    ctx.lineWidth = 2.5;
    ctx.beginPath();
    ctx.moveTo(nodes[path[0]].x, nodes[path[0]].y);
    for (let i = 1; i < path.length; i++) {
      ctx.lineTo(nodes[path[i]].x, nodes[path[i]].y);
    }
    ctx.stroke();
  }

  /* Draw start (green) and goal (red) markers */
  ctx.fillStyle = '#1a9e4c';
  ctx.beginPath();
  ctx.arc(START.x, START.y, 7, 0, Math.PI * 2);
  ctx.fill();

  ctx.fillStyle = '#c92f3c';
  ctx.beginPath();
  ctx.arc(GOAL.x, GOAL.y, 7, 0, Math.PI * 2);
  ctx.fill();

  /* Label start S and goal G */
  ctx.font = 'bold 11px system-ui, sans-serif';
  ctx.fillStyle = '#fff';
  ctx.textAlign = 'center';
  ctx.textBaseline = 'middle';
  ctx.fillText('S', START.x, START.y);
  ctx.fillText('G', GOAL.x, GOAL.y);
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + cls;
}

/* Build roadmap on button click */
document.getElementById('btnBuild').addEventListener('click', () => {
  buildRoadmap();
  draw();
  setStatus(i18nFmt('Roadmap ready: %n% nodes, %e% edges.', { n: nodes.length - 2, e: edges.length }), 'info');
  document.getElementById('btnPath').disabled = false;
});

/* Find shortest path on button click */
document.getElementById('btnPath').addEventListener('click', () => {
  if (!built) return;
  path = dijkstra();
  draw();
  if (path.length > 1) {
    const hops = path.length - 1;
    setStatus(i18nFmt('Path found in %hops% hops.', { hops: hops }), 'ok');
  } else {
    setStatus('No path found — try rebuilding the roadmap.', 'bad');
  }
});

/* Reset everything on button click */
document.getElementById('btnReset').addEventListener('click', () => {
  nodes = []; edges = []; path = []; built = false;
  document.getElementById('btnPath').disabled = true;
  draw();
  setStatus('Click "Build Roadmap" to scatter random nodes and connect nearby pairs.', '');
});

/* Initialise - disable Find Path until roadmap is built */
document.getElementById('btnPath').disabled = true;
draw();
Result
Console

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.

The Real Complexity

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

Building the roadmap with nn nodes and connection radius rr:

  • Collision-checking each node costs O(n)O(n) calls; checking each candidate edge adds O(n2)O(n^2) in the worst case, though practical implementations use kk-nearest neighbours to keep it closer to O(nlog⁡n)O(n \log n).
  • Memory is O(n+m)O(n + m) where mm 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∗A^* on the graph: O((n+m)log⁡n)O((n + m) \log n) in the worst case, milliseconds for typical roadmap sizes.

Probabilistic completeness is the key theoretical guarantee: as n→∞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)∝(log⁡n/n)1/dr(n) \propto (\log n / n)^{1/d} in dd dimensions; with this schedule the path cost converges to the optimum as n→∞n \to \infty.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/probabilistic-roadmaps/Content licensed under CC BY-NC 4.0.