Motion Planning

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.

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">{{hint}}</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">{{status_default}}</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">{{btn_plan}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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.

"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.

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.