Skip to main content

Module Overview · The Big Picture

Module 4 · Manhattan Navigation

The Big Picture

20–25 minProblem decompositionClass discussionNo coding yetSlides (PowerPoint)
👩‍🏫

Teacher mode is on — the gray boxes are yours only. Flip the switch (bottom-right) to preview the student view.

Here's the problem this module solves: get the robot from where it starts to a destination on the grid, all by itself.

A cartoon map of midtown Manhattan from above, not to scale. Between the Hudson River on the left and the East River on the right, long avenues run north and south (9th Ave to Madison) and shorter cross streets run east and west (53rd to 59th Street), with Central Park along the top. Every block is filled with buildings. A yellow taxi waits at A, the corner of 8th Avenue and 54th Street. A red dashed straight line from A to B, at 6th Avenue and 57th Street, is crossed out: no cutting through buildings. The taxi route in blue goes 2 blocks east along 54th Street, then 3 blocks north up 6th Avenue, numbered 1 to 5.
A taxi can't cut through the buildings, so every trip is blocks across plus blocks up or down.

A taxi in Manhattan has the same problem. Buildings fill every block, so it can't drive straight from A to B; it drives along the streets, 2 blocks east, then 3 blocks north. The robot is the same: it can only drive along the tape. So the route comes from one rule:

Go east or west until we are at the destination avenue, then north or south until we're at the destination street.

That's the whole algorithm. It's called the Manhattan algorithm.

Learning Objectives

By the end of this overview you will be able to:

  • Describe the problem Module 4 solves: drive to a destination on its own, then to several in a row
  • Split a complex problem into simpler parts: plan the route first, test it with no robot, then drive it
  • Name the planner (compute_manhattan_path), the driver (drive_path), and the list of (x, y) coordinates between them
  • Say what building a program top-down means: the main program first, with stand-ins for the parts below it

Breaking down a complex problem​

Now you know how to find the route. Getting the robot to do it is the next problem.

Street and avenue names are hard to use in a robot program, so we number each intersection instead: a column number, x, and a row number, y. The taxi's trip becomes (1, 1) to (3, 4).

The same cartoon map of midtown Manhattan, with every intersection labeled by a pair of numbers (x, y). x is the column: the avenues are numbered from the west, 9th Ave is x = 0, 8th Ave x = 1, up to Madison, x = 5. y is the row: the streets are numbered from the south, 53rd St is y = 0, 54th St y = 1, up to 58th St, y = 5. The taxi starts at A, (1, 1), the corner of 8th Avenue and 54th Street, and follows the blue route to B, (3, 4), the corner of 6th Avenue and 57th Street.
Each intersection gets a column number x and a row number y, written (x, y).

"Drive over there" sounds like one job, but it's too much to get right in one go. One way to tackle a complex problem is to break it into simpler sub-problems and solve each one. That's called problem decomposition (or top-down design).

Discuss · How would you split it?​

  1. Before the robot moves, could you write down every intersection it will drive through?
  2. How could you check that list is right, without the robot?
  3. Once the list is right, what's left for the robot to do?

Here is that split, one level at a time:

A tree with four levels. At the top, the main program, Lesson 4-1: for each destination, plan the route, then drive it. It splits into the planner, compute_manhattan_path(), Lessons 4-2 and 4-3, and the driver, drive_path(), Lesson 4-4. An arrow labeled list of (x, y) coordinates runs from planner to driver. The driver splits into two steps at each intersection: 1, turn to face the next intersection, Lessons 4-4 and 4-5; 2, drive to the next intersection, the LINE TRACKING functions built in Module 2, used on the robot in Lesson 4-6. Turning splits once more: which way to face, get_desired_heading(), Lesson 4-4, and turn until facing the next intersection, turn_to(), Lesson 4-5.
Click a box with a + to break it down.
The problem, broken into parts. Click a box to open it; each one names the lesson that builds it.

Plan first, then drive​

That's one way to split the problem, and the one this module uses: plan the whole route first, then drive it.

Left: a 4 by 4 grid with (0, 0) at the bottom-left. The robot starts at (0, 0). A blue route goes right to (1, 0) and (2, 0), then up to (2, 1), (2, 2) and (2, 3), each intersection labeled with its coordinates. Right: step 1, Plan: work out the route, print it, check it, no robot needed. An arrow carries the points (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), a list of (x, y) coordinates, down to step 2, Drive: take the list and drive it, one intersection at a time.
The plan is a list of (x, y) coordinates. One function makes it; another drives it.
  1. Plan. The planner, compute_manhattan_path, works out the whole route. It never moves the robot, so you can test it without a robot: print the route and check it against the grid.
  2. Drive. Once the plan is right, the driver, drive_path, takes the plan and drives it, then reports where the robot ended up.

Each intersection is an (x, y) pair, so the plan is a list of coordinates, the one thing the two functions share.

One job each is called separation of concerns, and it makes bugs easy to find: a wrong route is a planner problem; a wrong turn is a driver problem.

Knowledge Check

Why plan the whole route first, as its own function, before writing the code that drives?

From one destination to several​

Picture a delivery driver with packages for several houses, each with its own address. The driver plans a route to the first house and drives it, then plans from there to the next, until every package is delivered.

The robot does the same. Once it can reach one destination, several is just a loop: plan from where it is, drive, repeat.

A 4 by 4 grid. The robot starts at home, (0, 0), the bottom-left corner, facing north. Each leg goes across first, then up or down: leg 1 to (2, 3), leg 2 to (1, 0), leg 3 to (3, 1), leg 4 to (2, 2), and leg 5 back home to (0, 0).
Five deliveries, five legs, each planned from where the last one ended.

Build it from the top down​

You'll build this program top-down: the top of the tree first, then one level at a time. The main program comes first, in the very next lesson, and it runs the day you write it, because every part below it starts as a stub: a stand-in function that does just enough for the program to run, and prints what the real one would do.

Then you swap the stubs for real functions, one per lesson, and run the program after every change. The printout tells you right away whether it still works. The robot only drives in Lesson 4-6, so you never have to wonder whether a bug is in your code or in the robot.

The Python arrives the same way. A position like (1, 1) is a Python tuple, and a route is a Python list. You won't study them first: each lesson teaches the piece of tuples and lists it needs, right where the program needs it. Lesson 4-7 puts it all together.

The module at a glance​

  • 4-1: the main program, with stubs
  • 4-2: the planner, part 1: a path that grows
  • 4-3: the planner, part 2: every direction, and tests
  • 4-4: the driver
  • 4-5: turning
  • 4-6: the stubs out, the robot on the grid
  • 4-7: tuples and lists: what you now know

Wrap-up​

  • What problem does Module 4 solve? (Drive the robot from where it starts to a destination on its own, then to several destinations in a row.)
  • Why plan first? (The planner never moves the robot, so its list of coordinates can be printed and checked with no robot at all. Then the driver only has to follow a plan you already trust.)
  • What are the two halves and their jobs? (compute_manhattan_path plans; drive_path drives.)
  • What is a stub? (A stand-in function that lets the program run before the real function is written.)

Resources​