Summary
- A wavefront planner is a breadth-first technique for finding paths in a maze
- It provides the shortest path from any starting location to a given goal.
- It requires full knowledge of the maze
Setup
Figure 1: The Goal is the red square. The robot starts at the green square and knows the full layout of the maze.
First Step
Figure 2: Start at the goal. It is 0 squares from the goal so label it 0.
First Expansion
Figure 3: All the neighbors of the goal are a distance of 1 from the goal. (In this example the robot cannot move diagonally).
Next Expansion
Figure 4: All the neighbors of the 1-distance squares are a distance of 2 from the goal.
Subsequent Expansions
Figure 5: Keep expanding until every square is labeled with its distance from the goal.
Using the Plan
Figure 6: Starting at any square (say the green one) the robot moves to the neighbor that is closest to the goal.