A* search through mazes
Repeated Forward, Backward and Adaptive A* finding paths through mazes the agent can't see in advance.
The program generates 50 grid-world mazes. The agent starts knowing nothing about the walls, so it assumes every cell is open, plans the shortest path with A*, and starts walking. When it bumps into a wall it didn't know about, it remembers it and plans again from where it stands, until it reaches the target or proves there's no way through.
A* always expands the cell with the smallest f = g + h, where g is the distance walked so far and h is the Manhattan distance to the target. When cells tie on f, the choice matters a lot: preferring larger g pushes towards the target.
Three versions are compared. Repeated Forward A* searches from the agent to the target; Repeated Backward A* searches from the target to the agent; Adaptive A* reuses what earlier searches learned to sharpen its h-values. The priority queue is a binary heap written by hand.
Maze generator
50 grid worlds
Plan, walk, replan
Forward, backward, adaptive A*
Results
Cells expanded, runtime, pictures
- Maze generator to Plan, walk, replan
- Plan, walk, replan to Results
See it work
What we measured
| Comparison | Cells expanded | Takeaway |
|---|---|---|
| Ties go to larger g vs smaller g | about 9,376 vs 293,723 | About 30 times fewer cells when ties lean towards the target |
| Forward vs Backward A* | about 8,984 vs 151,038 | Forward wins, because the walls the agent discovers are near it, not near the target |
| Forward vs Adaptive A* | about 9,287 vs 8,868 | Adaptive expands fewer cells and ran slightly faster: 42.0 ms vs 42.6 ms |
Averages over the mazes with a path, from our report.