Skip to main content

Module Overview · When the Road Is Blocked

Module 5 · Pathfinding Around Obstacles

When the Road Is Blocked

15–20 minWhere the module goesNo coding yetSlides (PowerPoint)
👩‍🏫

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

Module 4's robot plans its own routes, but always the same way, across and then up, and it assumes nothing is in the way. Put an obstacle on its route and it drives straight at it.

We'll use small boxes on intersections to represent obstacles.

By the end of this module your robot will visit several destinations on a grid with obstacles, plan around the ones it knows about, spot new ones with its rangefinder and re-plan, and do better on its second run. It's the last required module: everything you've built works together.

A 4 by 4 grid of tape with (0, 0) at the bottom-left. An obstacle blocks the intersection (2, 0). From S at (0, 0) to D at (3, 2), the Manhattan route goes across first and runs into the obstacle at (2, 0), where it is crossed out; the rest of its route is faded. The breadth-first search route goes around: right to (1, 0), up to (1, 1), right to (3, 1), and up to D, 5 steps. A note: if an obstacle turns up while the robot drives, the rangefinder sees it and the robot plans again.
One obstacle on the grid. Module 4's planner has one route and it's blocked; this module's planner finds a way around.

Learning Objectives

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

  • Describe what the robot will do by the end of Module 5
  • Explain why the Module 4 planner can't get around a blocked intersection
  • Name the module's three new pieces (a map of the grid, a planner that searches it, obstacle detection) and what each does
  • Explain what it means to swap one planner for another without changing the rest of the program

Three new pieces​

The driving doesn't change: your Module 4 NAVIGATOR drives any list of intersections it's handed. What's new is which list it gets.

Map

The grid as a graph

The grid written so a program can search it: every intersection, what it connects to, and what's blocked.

Planner

Breadth-first search

A planner that finds a shortest route around every blocked intersection on the map.

Senses

Obstacle detection

The rangefinder checks the next intersection before the robot drives there. If something is there, it goes on the map and the robot plans again.

If you write the BFS planner so that it returns its plan as a list of intersections, just like the Manhattan planner, the rest of your program stays the same.

The swap​

Once the BFS planner passes its tests, you swap it in by changing one name, and the route that ran into the obstacle goes around it. That's the payoff of Lesson 4-0: you fixed what passes between planner and driver before writing either, so either side can be replaced without touching the other.

Knowledge Check

The Manhattan planner and the new planner both take a position and a destination and return a list of intersections. Why does that matter?

A robot that learns​

Planning around known obstacles is half the job; the other half is finding new ones. The robot looks ahead before every block. When it finds an obstacle, it marks that intersection blocked, re-plans from where it stands, and carries on. At the end it reports every obstacle it found, so the next run starts knowing them: your Run 2 should beat your Run 1.

Your roadmap​

LessonWhat happens
5-1 · Finding a Way AroundFind a way around a blocked intersection by eye, then work out, as a class, a method that always finds the shortest one. No code.
5-2 · Finding the PathFind the route itself, then work out how a computer would do the whole thing, and review the algorithm in plain words. No code.
5-3 · Pencil to ProgramWork out what the program must remember for each part of the algorithm, and put the grid into Python. The GRID GRAPH section opens.
5-4 · Pathfinding FunctionsKeep a shared list of blocked intersections and build the graph around it. The BFS PLANNER section opens.
5-5 · compute_bfs_path()The pencil method, line for line, in Python, tested after every stage.
5-6 · Testing and SwappingTest any planner without a robot, then swap Manhattan out by changing one name.
5-7 · Obstacle DetectionThe rangefinder looks before each block; if something is there, plan again. The OBSTACLES section opens.
5-8 · Building ExperienceKeep re-planning until the robot arrives, and start the next run knowing what this one found.
5-9 · Capstone ProjectSeveral destinations, obstacles found and avoided, and a second run that does better.

The capstone needs little new code: almost all of it calls sections you've already written and tested, as in Modules 2, 3 and 4. (Lessons 5-5 and 5-6 also have optional class versions.)

Wrap-up​

  • What will the robot do by the end of the module? (Visit several destinations, plan around known obstacles, find new ones while driving, and improve on its second run.)
  • Why can't the Module 4 planner handle an obstacle on its route? (It always plans across then up, and has no idea anything is blocked.)
  • What are the three new pieces? (A map of the grid, a planner that searches it, and detection with the rangefinder.)

Resources​