Introduction

Anyone who has carried a couch up a narrow staircase knows the feeling: tilt it, twist it, back up, try again. The classic name for it is the piano mover's problem — get a rigid shape from where it is to where you want it, threading it past every obstacle without bumping into anything.

A robot faces the exact same task, only it has to reason about it explicitly. Instead of thinking about the room, it thinks about its configuration: every position and angle it could occupy. A safe path is a continuous curve through that space of configurations that never touches an obstacle.

That sounds like ordinary pathfinding. But as the robot gains more parts that can move independently — more joints, more arms, more freedom — the space of configurations grows so fast that finding a path stops being a casual chore and becomes one of the hardest kinds of problems we know.

Try It: Guide the Robot

Here is a small cluttered grid. The blue robot starts at the top-left; the green flag is the goal. Click cells to drop or remove obstacles, then use the arrow buttons to drive the robot by hand — or let the planner search for you.

<p class="hint">The blue robot starts top-left; the green flag is the goal. Click cells to toggle <b>obstacles</b>. Drive by hand with the arrows, or press <b>Auto-plan</b> to let the computer search the configuration space — it explores cells one by one and the counter shows how many it had to examine.</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">Drive the robot, or auto-plan a route.</div>
<div class="pad">
  <button id="up" type="button">▲</button>
  <div class="row">
    <button id="left" type="button">◀</button>
    <button id="down" type="button">▼</button>
    <button id="right" type="button">▶</button>
  </div>
</div>
<div class="btns">
  <button id="plan" type="button">Auto-plan</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.grid { display: grid; grid-template-columns: repeat(7, 40px); gap: 3px; margin: .4rem 0; }
.cell { width: 40px; height: 40px; display: flex; align-items: center; justify-content: center;
        font-size: 20px; border-radius: 6px; user-select: none; cursor: pointer;
        background: #eef2f6; border: 1px solid #d6dee6; transition: background .1s; }
.cell:hover { background: #e2e9f0; }
.cell.wall { background: #44525f; border-color: #333d47; cursor: default; }
.cell.seen { background: #fde2c4; border-color: #f3c789; }
.cell.path { background: #cdeccf; border-color: #93cf97; }
.cell.robot { background: #2c6fde; border-color: #1f56b0; }
.cell.goal { background: #2faa55; border-color: #228a43; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.pad { display: flex; flex-direction: column; align-items: flex-start; gap: 3px; margin: .3rem 0; }
.pad .row { display: flex; gap: 3px; }
.pad button { width: 40px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .4rem; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .7rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Robot motion planning on a grid: find a collision-free path from start to goal.
    // With one body and no rotation this is plain grid (configuration-space) search:
    // breadth-first search explores configurations one at a time. The real "piano
    // mover's problem" — a jointed body that can also rotate — is PSPACE-hard (Reif,
    // 1979), because every extra degree of freedom multiplies the space to search.
const R = 6, C = 7;
const START = [0, 0], GOAL = [5, 6];
// Initial obstacles (row,col). The player can toggle more.
const INIT_WALLS = ['1,1','1,2','1,3','3,3','3,4','3,5','4,1','2,5','5,2','0,4'];
let walls = new Set(INIT_WALLS);
let robot = START.slice();
const key = (r, c) => r + ',' + c;
const inb = (r, c) => r >= 0 && r < R && c >= 0 && c < C;

function render(seen, path) {
  seen = seen || new Set(); path = path || new Set();
  const g = document.getElementById('grid'); g.innerHTML = '';
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
    const d = document.createElement('div'); const k = key(r, c);
    d.className = 'cell';
    if (walls.has(k)) d.className += ' wall';
    else if (seen.has(k)) d.className += ' seen';
    if (path.has(k)) d.className += ' path';
    if (r === GOAL[0] && c === GOAL[1]) { d.className += ' goal'; d.textContent = '⚑'; }
    if (r === robot[0] && c === robot[1]) { d.className += ' robot'; d.textContent = '◆'; }
    d.addEventListener('click', () => toggleWall(r, c));
    g.appendChild(d);
  }
}
function toggleWall(r, c) {
  const k = key(r, c);
  if ((r === robot[0] && c === robot[1]) || (r === GOAL[0] && c === GOAL[1])) return;
  walls.has(k) ? walls.delete(k) : walls.add(k);
  render(); setStatus('Drive the robot, or auto-plan a route.', '');
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }
function move(dr, dc) {
  const nr = robot[0] + dr, nc = robot[1] + dc;
  if (!inb(nr, nc) || walls.has(key(nr, nc))) { setStatus('Blocked — that move collides.', 'bad'); return; }
  robot = [nr, nc]; render();
  if (robot[0] === GOAL[0] && robot[1] === GOAL[1]) setStatus('Reached the goal!', 'ok');
  else setStatus('Drive the robot, or auto-plan a route.', '');
}

// BFS over the configuration space (here: grid cells). Returns the path plus the
    // set of every configuration the planner had to examine.
function plan() {
  const start = key(robot[0], robot[1]);
  const goal = key(GOAL[0], GOAL[1]);
  const q = [start], prev = { [start]: null }, seen = new Set([start]);
  let explored = 0;
  while (q.length) {
    const cur = q.shift(); explored++;
    if (cur === goal) break;
    const [r, c] = cur.split(',').map(Number);
    for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nr = r + dr, nc = c + dc, nk = key(nr, nc);
      if (inb(nr, nc) && !walls.has(nk) && !seen.has(nk)) {
        seen.add(nk); prev[nk] = cur; q.push(nk);
      }
    }
  }
  if (!(goal in prev)) { render(seen); setStatus('No path exists — the goal is walled off.', 'bad'); return; }
  const path = new Set(); let cur = goal;
  while (cur) { path.add(cur); cur = prev[cur]; }
  render(seen, path);
  setStatus(fmt('Found a path after exploring %explored% of %v% cells.', { explored: explored, v: R * C }), 'ok');
  console.log('Explored', explored, 'configurations; path length', path.size);
}
document.getElementById('up').addEventListener('click', () => move(-1, 0));
document.getElementById('down').addEventListener('click', () => move(1, 0));
document.getElementById('left').addEventListener('click', () => move(0, -1));
document.getElementById('right').addEventListener('click', () => move(0, 1));
document.getElementById('plan').addEventListener('click', plan);
document.getElementById('reset').addEventListener('click', () => {
  walls = new Set(INIT_WALLS); robot = START.slice(); render();
  setStatus('Drive the robot, or auto-plan a route.', '');
});
render();
Result
Console

Notice what happens when you press Auto-plan. The computer doesn't "see" the route — it explores configurations one by one, fanning out from the start until it reaches the goal. The counter shows how many it had to examine. On this tiny grid that's manageable. Now imagine the robot were an L-shape that could also rotate: each cell would split into several orientations, and the space the planner must comb through would multiply with every extra degree of freedom.

The Real Complexity

How hard is motion planning, really? Not driving a single dot through an empty room — the general version, with linked parts and tight obstacles.

  • Checking a proposed path is easy: walk along it and confirm it never collides.
  • One robot, no rotation is just grid search: explore neighboring cells until you reach the goal. Fast and tidy.
  • Configuration space explodes. Each independently movable part adds a dimension. A robot with d degrees of freedom lives in a d-dimensional space, and the number of distinct configurations grows exponentially in d.
  • It's PSPACE-hard. In 1979 John Reif proved that the generalized mover's problem — planning the motion of a body made of many linked pieces among obstacles — is PSPACE-hard. Coordinating multiple free polyhedra is PSPACE-complete, putting it among the hardest problems solvable with reasonable memory.

That is the punchline: the moment a robot has enough independent parts, deciding whether a goal is even reachable is as hard as any problem in PSPACE. The frustration of wedging a couch through a doorway isn't bad spatial sense — it's a glimpse of genuine intractability.

Where It Matters

"Move this shape from here to there without hitting anything" is a question engineers face constantly, and motion planning is its formal heart:

  • Robot arms and factories: a welding arm must reach every seam without colliding with the car body or itself.
  • Self-driving and warehouse robots: every lane change and aisle turn is a path through a changing configuration space.
  • Surgery and drug design: steering a flexible instrument through tissue, or docking a molecule into a protein pocket, are mover's problems in disguise.
  • Animation and games: making a character walk around furniture is the same search, just for pixels.

Because the exact problem is PSPACE-hard, practitioners almost never solve it exactly. Instead they use sampling-based planners like RRT and PRM that throw random configurations at the space and connect the ones that don't collide — giving up guarantees of the perfect path in exchange for an answer that arrives this century. It is the same bargain seen across NP-hard and traveling salesman routing: when exact is hopeless, approximate and move on.

Conclusion

Motion planning hides a humbling secret: the everyday act of moving an object across a room, when handed to a machine with many moving parts, becomes one of the hardest computational problems we can pose. Checking a path is instant; deciding whether one even exists is PSPACE-hard, because the space of configurations balloons with every degree of freedom.

So the next time you are stuck in a doorway, couch wedged at an impossible angle, take comfort — you haven't failed at geometry. You've simply bumped into the same wall every robot does, the one where the search space outgrows any clever shortcut, and all that's left is to try, tilt, and try again.

Share this article

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

Comments

Loading comments...

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