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
Challenges
What just happened?
- RRT grows a tree: pick a random spot, find the nearest twig, grow a short step towards it, keep it if the step does not hit a wall.
- Every so often it aims at the goal, which pulls the tree that way. With enough twigs a branch reaches it.
- The first path it finds is wiggly. Smoothing tries straight shortcuts between points on the path.
- A* searches every square in a careful order and finds the shortest path on the grid, but checks a lot of squares.
- RRT is random: it can find different paths each run, and may fail to find one through narrow gaps in time.
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 + hwith 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.