Back to start

Two robots, one house

A* and RRT* plan a route through the same floor plan and drive it at the same speed. Press play.

A*

Cuts the house into a grid of 5 cm cells, marks the cells a robot cannot stand in, then searches outward from the start, always trying the most promising cell first. It finds the shortest route on that grid, and the same route every time.

RRT*

Throws random points into free space and grows two trees toward them, one from the start and one from the goal. When a shorter link appears it rewires nearby branches. It stops as soon as the trees meet, so the route depends on where the random points fell.

Results over 30 seeds

Every route was planned once per seed with each planner. Click a row to watch it above. Each dot is one RRT* run. The yellow line is A*, which is the same in every run.

RouteA* (m)RRT* mean (m)RRT* best / worst (m)All runsMedian time, A* / RRT* (ms)

What I found

A* found the shorter path on average on every route, and it found the same path every time. RRT* was less predictable. From the kitchen to the bedroom it took the short hallway in only of 30 runs and drove around through the bathroom in the rest. That hallway is narrow and has a bend, so random points rarely land inside it before the trees meet another way.

A* is not always shortest. From the bathroom to the bedroom the best RRT* run ( m) beat A* ( m), because A* can only step between neighbouring grid cells while RRT* can connect points at any angle.

RRT* was usually faster here, but that is mostly the grid. Most of A*'s time goes into building the grid, not into the search. In a small house that is cheap. In a large map, or one that changes often, the grid has to be rebuilt every time and that cost grows.

Limits

This is one small 2D world with a round robot that drives along the path at constant speed. The robots do not sense anything. When the hallway closes they are told about it and plan again from scratch. The RRT* in PyRoboSim stops as soon as its trees connect, so it does not keep improving its path with extra time the way RRT* can. Times were measured on one laptop and change from machine to machine. Path lengths do not.