Lesson 5-2 · Finding the Path
Lesson 5-2 · Finding the Path
Teacher mode is on — the gray boxes are yours only. Flip the switch (bottom-right) to preview the student view.
In Lesson 5-1 you labeled every intersection with its distance to the destination. That
tells you how far the start is, but not the path, and the robot needs a path: a list of
intersections to drive to, like the one the Manhattan planner hands it. So this lesson
answers two questions. What's the path? And how would we write a compute_bfs_path()
function that finds it? The lesson ends with a review of the whole algorithm in plain
words, which is what you'll turn into Python in Lesson 5-5.
Learning Objectives
By the end of this lesson you will be able to:
- Walk downhill from the start to find a shortest path, and explain why the path leaves the start out
- Explain why the wave starts at the destination
- Explain why a computer takes intersections oldest-first, and why the numbers are all it needs
- Carry out the algorithm exactly as a computer would, by hand, including on a grid with no path
Discuss · Where's the path?
Start from the grid you numbered at the end of Lesson 5-1: the wall at (1,0) and (1,1), the destination D at (3,0) numbered 0, and the start S at (0,0), which got a 7.
- You're standing on S, a 7. Which way do you go first?
- Keep going. How do you choose each step, and when do you stop?
- Somewhere you'll find two neighbors with the same number. Which one do you pick?
- Why did we start the wave at D, and not at S?
Walking downhill
Each step of the walk is an intersection the robot drives to. Written down in order, they are the path. One answer for the wall grid is
[(0, 1), (0, 2), (1, 2), (2, 2), (3, 2), (3, 1), (3, 0)]
The start is left out because the robot is already on it, as in Module 4's
compute_manhattan_path, so len(path) is the number of steps: 7. A classmate who picked
differently at a tie might have [..., (2, 2), (2, 1), (2, 0), (3, 0)]: also 7 steps,
also right. In Lesson 5-6 you'll test the planner by checking what must be true of any
correct answer, not by comparing against one list.
Walking downhill, you are on an intersection numbered 4. Its open neighbors are numbered 3, 3 and 5. Where can you step?
Discuss · Teaching it to a computer
You numbered the grid with your eyes: you looked at the whole board and found "all the 2s" at once. A computer can't do that. It sees one intersection and its open neighbors, the same limit your own rule had in Lesson 5-1.
- A computer looks around one intersection at a time. In what order should it take them, so that every 1 is looked around before any 2?
- How can it remember that order? What does it write down, and where does each newly numbered intersection go?
- When is the wave finished?
- To walk downhill, what does the computer need to know about each intersection? Does it need anything else?
Activity · Trace it the computer's way
Now do exactly what the computer will do. Use a 3×3 grid with the center, (1,1), blocked. The start is (0,0), the destination (2,2). Check neighbors in the order the code will use: left, right, down, up.
Each step: take the intersection at the front of the to-visit list. Every open neighbor that doesn't have a number yet gets one more than this one's number, and goes on the end of the list. Stop when the list is empty. Copy the table and fill it in; the first two rows are done for you.
| Step | Take off the front | Newly numbered | To-visit afterward |
|---|---|---|---|
| start | — | (2,2): 0 | (2,2) |
| 1 | (2,2) | (1,2): 1, (2,1): 1 | (1,2), (2,1) |
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 | |||
| 7 | |||
| 8 |
Then walk downhill from (0,0) and write the path. When two neighbors tie, take the first one in the order left, right, down, up.
Here is the same trace, run one step at a time, and then the walk. Press Step to see what the computer does next and why.
Why does the computer take intersections from the FRONT of the to-visit list?
Review: the algorithm
Here is breadth-first search all in one place, the way you would explain it if someone asked you how it works.
Number the grid from the destination. Write 0 on the destination and put it on a to-visit list. Then, until the list is empty: take the intersection at the front of the list, the one that has waited longest, and look at each of its open neighbors. A neighbor that doesn't have a number yet gets one more than this intersection's number, and joins the end of the list. A neighbor that already has a number is left alone. When the list is empty, every intersection the wave could reach has its number: its steps to the destination.
Because new intersections join the end and you always take from the front, everything 1 step from the destination is numbered before anything 2 steps away. That's the wave from Lesson 5-1, moving out one step at a time.
Walk downhill from the start. If the start never got a number, the wave never reached it, and there is no path. Otherwise, stand on the start and, until you're on the destination, step to an open neighbor whose number is one less, writing down each intersection you step onto. Leave the start off; the robot is already there. The intersections you wrote down, in order, are the path the robot drives.
That's all it needs: one number per intersection. And while it numbers the grid it never looks at where the start is, which is why walls in the way are no problem.
What in the algorithm makes sure no intersection is ever numbered twice?
What makes sure everything 1 step from the destination is numbered before anything 2 steps away?
Activity · Be the computer
Work in pairs. One of you is the computer: you may look only at the intersection you're working on and its open neighbors, and you keep the to-visit list and the numbers on paper. The other reads the review above aloud, one instruction at a time, and checks that the computer does exactly that and nothing more.
Use a 3×3 grid with the whole middle column blocked: (1,0), (1,1) and (1,2). The start is (0,0), the destination (2,0).
- What ends the numbering, and which intersections got numbers?
- Did the start get a number? What does that mean?
- Swap jobs and run it once more, this time with only (1,1) blocked. What path do you get?
Check your paper against the computer
Nothing goes into robot.py yet. Next lesson works out what a program has to keep track
of to follow the algorithm, and by Lesson 5-5 your own file draws the grid below. For
now your teacher has a demonstration program that runs the 3×3-with-(1,1)-blocked trace
step by step, printing each intersection as it's numbered and the to-visit list after
every step, then the walk and the grid of numbers:
2 | 2 1 0
1 | 3 X 1
0 | 4 3 2
----------
0 1 2
If your trace matches, you ran the algorithm the way the computer does.
Real-world connections
Wavefront planners
Many robots plan exactly this way: spread a wave of numbers out from the goal, then drive downhill from wherever they are.
Paint-bucket fill
The fill tool in a paint program spreads out from where you click with a to-visit list, exactly like the wave from Lesson 5-1.
Maze solvers
A maze solver floods the maze from the exit, then walks downhill from the entrance.
Wrap-up
- How do you get the path from the numbers? (From the start, keep stepping to a neighbor one less until you reach 0.)
- Why does the wave start at the destination? (So the walk starts where the robot is and the path comes out in driving order.)
- Why does the computer take the oldest intersection first? (So the wave front moves out one step at a time.)
- What happens when the start is walled off? (The list empties without reaching it; there is no path.)