Robotics & Control

Find a Way Around

Draw walls, then let the robot grow a random tree of tries until one branch reaches the goal. Compare it with the careful A* search.

Press Run RRT. I throw out random twigs and keep the ones that do not hit a wall. Then try Smooth and A*!

The map

RRT treeRRT pathsmoothedA* path and searched cells

Challenges

Find a way: run RRT until it connects start and goal.
Shorten it: press Smooth and cut the path by at least 2%.
Compare: run A* on the same map and see how many squares it checked.
Needle in a haystack: pick the Narrow gap map and get RRT through it.
Impossible: draw a wall that closes every way through, then run A* and see it say there is no path.

What just happened?

For grown-ups: what's really going on

RRT (Rapidly-exploring Random Tree, LaValle 1998) samples a random point (8% of the time the goal), extends the nearest tree node by at most 14 units towards it, and adds the new node if the segment is collision-free. It is probabilistically complete: if a path exists it finds one given enough samples, but the path is not optimal (RRT* adds rewiring to converge to the optimum).

  • Collision checking samples every 2 units along each segment on an occupancy grid of 10-unit cells. The robot is a point.
  • Shortcut smoothing: repeatedly choose two points on the path and replace the part between them with a straight segment when it is collision-free.
  • A* uses f = g + h with an octile-distance heuristic, 8-connected moves, and no corner cutting. It is optimal on the grid, but the grid forces 45° turns, so a smoothed RRT path can even be shorter in continuous space.
  • Grid search scales badly with dimensions (a 7-joint arm has 7), where sampling-based planners like RRT remain practical. That is why arms use them.

Further reading: LaValle, Planning Algorithms, ch. 5 · Hart, Nilsson, Raphael (1968), A Formal Basis for the Heuristic Determination of Minimum Cost Paths.