Where you are. You can build the configuration space of the 2-link arm and read its bands and slivers. That took 129,600 collision checks for two joints. This lesson is about the six-joint arm, where the same approach needs 139 billion.
The dark warehouse and the ball of string
You are somewhere inside an enormous unlit warehouse and you need to reach a door on the far side. You have no map, no lights, and no way to see the racking. What you do have is a torch that shows the floor immediately at your feet, and a ball of string tied to where you started.
Here is a procedure that works. Pick a direction at random. Walk to whichever bit of string you have already laid down that lies nearest that direction, then take five paces that way. If you walked into something, forget it and pick a new direction. If you did not, tie the string down at your new position and start again.
It feels like it should be hopeless. It is not, and the reason is the nearest bit of string clause. Early on there is barely any string, so almost every random direction pulls you into somewhere you have never been. As the string fills a region, new directions start being served by string that is already out at the frontier, so the growth keeps happening at the edges rather than in the middle.
You never learn the warehouse’s layout. You get to the door.
The idea in one paragraph
Past about four joints, free space is too large to build, store, or search exhaustively, and the problem is provably hard in general rather than merely awkward. So sampling-based planners stop trying to know free space at all. They keep only two operations: is this single configuration free, and is this short straight move between two configurations free. Everything else is built out of those calls. A rapidly-exploring random tree grows one tree from the start by repeatedly drawing a random configuration, extending the nearest node of the tree a short way towards it, and keeping the extension if it survived the check. A probabilistic roadmap instead scatters free configurations across the whole space once, connects near neighbours, and answers many later queries against that graph. Both find paths in high dimensions in milliseconds. Both give up something specific in exchange, and knowing exactly what is the difference between using one and trusting one.
The answer you can no longer afford
Grid the configuration space at five degrees per joint and count the cells. On this laptop the collision checker manages about 14,000 configurations a second, and a compiled one in a real stack manages of the order of a million.
| joints | cells | at this laptop’s rate | at 1e6 checks/second |
|---|---|---|---|
| 2 | 5,184 | under a second | under a second |
| 3 | 373,248 | about 25 s | under a second |
| 6 | 139,314,069,504 | about 110 days | about 2 days |
| 7 | 10,030,613,004,288 | about 22 years | about 116 days |
n = 4 trials · one exhaustive pass over a grid at 5 degrees per joint, timed against this laptop's measured rate of about 14,000 checks per second and against an optimistic 1e6 · 2026-08-10
The SO-101 is the third row. A 30-joint humanoid is about cells, which is not a number you make faster; it is a number you abandon.
The only two questions a planner asks
Sampling planners get their leverage by shrinking the interface. The planner never sees your scene, your meshes, your obstacle list or your robot’s geometry. It sees two functions.
Wider than the screen; scroll it sideways.
That is the whole contract, and everything expensive lives on the checker’s side. In the runs below, a single successful plan costs about 600 collision checks. A grid over the same space costs 129,600. The planner is not doing less work per check; it is asking two hundred times fewer questions.
RRT, in four lines
An RRT holds a tree of configurations rooted at the start. One iteration:
- Sample. Draw a configuration uniformly from the whole space. Every so often - five per cent here - use the goal instead, so the tree is pulled towards it.
- Find the nearest node of the tree to that sample, using the wrapped distance from the previous lesson.
- Steer. Take a step of fixed length, 0.25 radians here, from that node towards the sample.
- Check and keep. If the short move is free, add the new configuration as a child. Otherwise throw it away and start again.
When a new node lands within a small tolerance of the goal and the move to the goal is free, walk the parent pointers back to the root and you have your path.
Wider than the screen; scroll it sideways.
Step 2 is the part that looks like bookkeeping and is actually the algorithm. Because the nearest node is chosen, the chance that a given node gets extended is proportional to how much of the space is closer to it than to any other node. Nodes on the frontier own huge regions; nodes buried inside the tree own almost nothing. So uniform sampling of the space produces wildly non-uniform growth of the tree, aimed outward, with nobody having written any code that says “explore”.
Running it
The same query in the same four-disc scene, from the previous lesson’s start and goal, whose straight joint-space line is blocked.
| what was measured | value |
|---|---|
| runs that found a path | 40 / 40 |
| median wall clock | 0.07 s |
| nodes kept, across seeds | 55 to 135 |
| collision checks, seed 0 | 607 |
| path length, across seeds | 5.28 to 7.21 rad (median 5.91) |
| after 200 shortcut attempts | 4.68 rad median |
| straight-line lower bound | 3.88 rad |
n = 40 trials · RRT from (-2.30, 1.05) to (1.15, -1.60), step 0.25 rad, edge check every 0.05 rad, 5% goal bias, one seed each · 2026-08-10
Two things in that table matter more than the speed.
The spread. Same query, same code, forty seeds, and the answers differ by a third in length. An RRT path is a valid path and nothing more; it wanders, it doubles back, and no part of the algorithm was ever trying to make it short. Two hundred rounds of shortcutting - pick two waypoints at random, and if the straight move between them is free, delete everything between - takes the median from 5.91 to 4.68 radians for a few milliseconds of work. That gets you within 21% of a straight line that is not actually available.
The determinism. There is none. Rerun with a different seed and you get a different path, and on a harder query you may get no path at all inside your budget. Anything downstream that assumed the arm takes the same route twice is now wrong.
PRM, briefly
RRT builds a tree for one query and throws it away. A roadmap inverts that.
Building a roadmap of 600 free samples here kept 3,489 of 3,567 candidate edges and took about two and a half seconds. Answering the query against it took under 20 milliseconds and returned a 4.74-radian path, which is better than the RRT’s median before shortcutting. Twenty further queries against the same roadmap all succeeded and cost about a third of a second in total.
The checker is where the lies get in
One number in that results table is a choice, not a measurement: the edge check runs every 0.05 radians. A planner that checks less often is faster and starts stepping over thin obstacles entirely.
| step (rad) | edge spacing (rad) | paths found | paths still clean | cost, against the bottom row |
|---|---|---|---|---|
| 1.20 | 1.20 | 20 | 7 | 9x cheaper |
| 0.80 | 0.80 | 20 | 12 | 6x cheaper |
| 0.50 | 0.50 | 20 | 12 | 4x cheaper |
| 0.25 | 0.25 | 20 | 19 | 2x cheaper |
| 0.25 | 0.05 | 20 | 20 | the reference |
n = 20 trials · the same query at varying step length and edge spacing, then every returned path re-checked at 0.005 rad · 2026-08-10
The top row is about nine times cheaper than the bottom row, and thirteen of its twenty paths drive the arm through a disc. Nothing failed. No exception was raised. The planner returned a path, the path had the right endpoints, and it was wrong.
Check yourself
1. Why does adding a joint hurt an exhaustive planner so much more than it hurts an RRT?
Because the two costs scale off different quantities. An exhaustive method’s work is proportional to the size of the space, and the space multiplies by the number of cells per axis - 72 at five degrees - for every joint added. A sampling planner’s work is proportional to how many samples it needs, which tracks how hard the query is: how much of the space is free, how narrow the corridors are, how far the goal is. A tenth joint that is unobstructed and irrelevant to the task adds one more coordinate to sample and barely changes the sample count, while it multiplies the grid by 72.
2. RRT samples uniformly. Why does the tree not grow uniformly?
Because of which node gets extended. Each iteration extends the node nearest the sample, so a node is extended in proportion to the volume of space closer to it than to any other node - its Voronoi cell. Frontier nodes sit on the edge of the tree and own enormous cells; interior nodes are surrounded and own almost nothing. Uniform samples therefore land in frontier cells almost every time, and the tree grows outwards into unexplored space. The bias is a consequence of the nearest-neighbour rule, not an extra heuristic.
3. Your planner returns nothing after ten seconds. Name three explanations that are consistent with that, and say which one you can rule out.
There may be no path at all, because the goal is in a different component of free space. There may be a path through a corridor so narrow that uniform sampling rarely lands in it. Or the budget may simply be too small for a query that is fine. You can rule out none of them from the timeout itself - that is what probabilistic completeness does and does not promise. The useful next moves are to check the goal is collision-free at all, to raise the budget and see whether the failure is stable, and to run a bidirectional search or a coarse grid check if the space is small enough to afford one.
4. Shortcutting cut the median path from 5.91 to 4.68 radians for a few milliseconds. Why not build the shortness into the planner instead?
You can, and that is RRT*, which rewires the tree as it grows so the path converges on the optimum. It costs more per node and it changes the guarantee from “a path” to “a path that improves with time”, which means you now have to decide when to stop. Shortcutting is the cheap 80%: it cannot escape the homotopy class the RRT happened to find - if the tree went round the left of an obstacle, no amount of shortcutting takes it round the right - but within that class it removes nearly all the wandering for almost no cost. Reach for it first and for RRT* when the difference between “a route” and “a good route” is worth paying for on every plan.
5. Thirteen of twenty paths at a 1.20-radian edge check drove the arm through an obstacle, and nothing reported an error. What does that tell you about where to put your trust?
In the collision checker, not in the planner. The planner’s output is only as true as the questions it asked, and it has no way to know that a question was too coarse - a path that skipped over an obstacle is indistinguishable, from inside the algorithm, from a path that went round it. So the edge resolution is a safety parameter rather than a performance parameter, it belongs with the geometry rather than with the planner’s tuning, and the check worth running is an independent one at a finer resolution on the finished path. Continuous collision checking removes the parameter entirely, which is why production planners use it.
Do this
Open code/rrt_2link.py. Three TODO(you) markers: the edge check, the extension step inside rrt(), and the shortcutter. It imports your collision checker from the previous lesson, so finish that one first. About an hour.
python module-02-simulation/code/rrt_2link.py # ~10 s
python module-02-simulation/code/rrt_2link.py --prm # ~3 s
python module-02-simulation/code/rrt_2link.py --grid # ~2 s
python module-02-simulation/code/rrt_2link.py --nopath # ~10 s
python module-02-simulation/code/rrt_2link.py --audit # ~12 s1. Break the Voronoi bias on purpose. Replace the nearest-node search with a uniformly random node of the tree and re-run the forty seeds. The tree stops reaching outward and starts thickening where it already is. Report what happened to the node count and the success rate; this is the cheapest way to convince yourself the bias is the algorithm.
2. Sweep the goal bias. Try 0.0, 0.05, 0.2 and 0.8. At zero the tree explores beautifully and never aims anywhere; at 0.8 it drives straight at the goal, gets stuck against the first obstacle in the way, and stops exploring. Find where the elbow of that curve is on this query, then say in one sentence why the answer would move if the obstacles did.
3. Make the planner lie to you. Run --audit and reproduce the top row. Then take one of the paths it accepted at a 1.20-radian check, find the offending edge, and print the configurations along it. Look at where the arm actually is in the middle of that move.
4. Ask for something impossible. Run --nopath. Then raise the budget to 50,000 nodes and watch it fail more expensively. Write down what your calling code should do with that answer, given that it is not evidence of impossibility.
5. Roadmap economics. In --prm, drop the sample count from 600 to 200 and then to 100, and record the build time, the query success rate over twenty queries, and the path length. Somewhere below 600 the roadmap stops covering the space and queries start failing to attach; find roughly where, and note that this failure looks exactly like the query being impossible.
What you can now do
You can state why exhaustive planning stops being available at about four joints, in cells rather than in adjectives, and why that is a property of the space rather than of anyone’s code. You can implement an RRT from scratch and explain the one line - nearest node, not random node - that makes it explore. You can name what you bought and what you sold: milliseconds and high dimensions, in exchange for paths that vary run to run, are not short unless you shorten them, and can never come back with a proof that no path exists. And you can say why the collision checker’s resolution is the number that decides whether any of the rest is true.