Skip to main content

Lesson 5-8 · Building Experience

Module 5 · Pathfinding Around Obstacles

Lesson 5-8 · Building Experience

50 minBetter data, same algorithmThe robot learnsSlides (PowerPoint)
👩‍🏫

Teacher mode is on. Toggle it off (bottom-right) to preview the student view.

In Lesson 5-7 the robot re-planned once, then a break stopped the loop. Two things are missing:

  • The robot should keep going: follow the new path, re-plan at each new wall, and arrive.
  • Each run, it rediscovers every obstacle from scratch.

This lesson fixes both: a function that re-plans until arrival, and a way to start Run 2 knowing what Run 1 found.

Learning Objectives

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

  • Write navigate_with_detection(): Lesson 5-7's detect-and-reroute step inside a while loop that runs until the robot arrives
  • Explain why remembering obstacles improves navigation
  • Start a run with obstacles already known, so the planner avoids them from the first path
  • Compare Run 1 and Run 2 with metrics (steps, reroutes)
  • Explain the GPS/Waze analogy for crowd-sourced obstacle data

This lesson's skeleton​

Paste this at the end of the OBSTACLES section, under test_detect_once(): one setting, and the function the capstone is built from.

# --- Lesson 5-8: re-plan until you arrive ---
# navigate_with_detection() is the 5-7 loop inside a while:
# plan, follow, and if something got in the way, plan again
# from here, until a whole path is driven with no reroute. It
# hands back position and heading, as drive_path() does, plus
# the step and reroute counts. KNOWN_OBSTACLES is what the
# last run found, typed in by you: memory between runs.
KNOWN_OBSTACLES = [] # what the last run printed; empty on Run 1

def navigate_with_detection(position, heading, destination, rangefinder, obstacle_cm):
"""Drive from position (facing heading) to destination,
re-planning around every obstacle the rangefinder finds;
return (position, heading, step_count, reroute_count)."""
# step_count = 0 ; reroute_count = 0
# arrived = False
# while not arrived:
# plan from position; print the path
# if the path is empty: say "No path"; return the four
# rerouted = False
# for each next_pos in path: -- Lesson 5-7
# face it
# look ahead with rangefinder.distance()
# if closer than obstacle_cm:
# add_blocked(next_pos); count the reroute
# rerouted = True ; break
# else:
# arrive; position = next_pos; count the step
# if not rerouted: arrived = True
# return position, heading, step_count, reroute_count
pass

From break to "until you arrive"​

Lesson 5-7's loop broke out as soon as it re-planned. Now put that for loop inside a while that ends only when the for runs all the way through without a reroute: plan, follow, and if something got in the way, plan again from here.

  • The inner for is Lesson 5-7's, except the re-plan moves to the top of the while. The break only has to get out of the for.
  • The rerouted flag tells the while how the for ended. It is False before the for and set True in the obstacle branch. After the for, "not rerouted" means the whole path was driven: arrived.
  • The function returns the new position and heading, because the next trip is planned from there. Lesson 5-9 chains several trips.
A loop. Plan from here with compute_bfs_path(position, dest). Follow it, looking ahead before each step. If something is ahead: tell the planner with add_blocked(next_pos), set rerouted, break out of the for loop, and the while loop plans again from where the robot is. If every step was followed with nothing ahead, the robot has arrived and the function returns position, heading and the counts.
Plan, follow, and if something got in the way, plan again from here.

rangefinder and obstacle_cm are already in the file, but passing them in makes the def line say what the function needs, and lets a test hand in a different cutoff. For the dry run, swap the one look-ahead line, as in Lesson 5-7.

The empty-path check matters now. A boxed-in robot gets [] from compute_bfs_path() (Lesson 5-5). Without the check, the for runs zero times, rerouted stays False, and the robot declares itself arrived at the wrong intersection.

Knowledge Check

In navigate_with_detection(), what makes the while loop finally stop?

Knowledge Check

Why does the function return the pose (position and heading), not just the step counts?

If you built the Navigator class in Lesson 4-6, this function wants to be a method of it: position and heading become self.position and self.heading and drop out of the parameter list and the return, the driving calls go through self.line_track. and self.get_desired_heading() / self.turn_to(), and the planner calls are planner.add_blocked() and planner.compute_path(). It returns only the two counts; the caller reads navigator.position afterwards, as in Lesson 4-6.

Why memory matters​

Between runs, the planner and the driving functions stay the same. Only the input changes: the blocked list starts with more information.

Run 1: empty blocked list -> discover obstacles the hard way -> many reroutes
Run 2: pre-loaded list -> plan around known obstacles -> few or no reroutes

Better data, better performance: Run 2 runs the same algorithm on better information.

Two runs from S at (0, 0) to D at (3, 3) with obstacles at (2, 0), (2, 2) and (3, 1). Run 1 starts with an empty list and finds each obstacle only when it faces it: 8 steps and 3 reroutes, backing up once. Run 2 starts with the three obstacles typed in and plans around them from the start: 6 steps and 0 reroutes.
One example with three obstacles. Your numbers will depend on your grid; the shape of the difference won't.
Knowledge Check

Why does the robot navigate better on Run 2?

Activity · Drive until you arrive​

Step 1 · Dry run​

Write the body from the outline, with simulate_rangefinder(next_pos) in the look-ahead line for now. Then write test_navigate(), which the rest of the lesson uses:

  1. Hand each entry of KNOWN_OBSTACLES to add_blocked() (a two-line for loop).
  2. Set position (0, 0), heading 0, destination (3, 3). Plan the path, print it, and wait for the button.
  3. Call the function and assign all four return values (below).
  4. Print where the robot arrived and the step and reroute counts, then, on its own line, "All known obstacles:" and BLOCKED.
position, heading, steps, reroutes = navigate_with_detection(
position, heading, destination, rangefinder, OBSTACLE_CM
)

Robot at (0, 0) facing North on an empty grid, run line set to it, both presses. With SIMULATED_OBSTACLES still [(2, 0), (2, 2)], the robot should reach (1, 0), "see" (2, 0), print a new path, take it, and arrive at (3, 3) with one reroute. (Lesson 5-7 stopped at the reroute.)

Step 2 · The real sensor​

Change the look-ahead line to rangefinder.distance(). Put two obstacles on intersections the printed path crosses, and run again. The robot should reroute around each obstacle it meets, and arrive. Write down the last line it prints: the blocked list.

Activity · Carry what you learned into the next run​

BLOCKED lasts between function calls, which is why the while loop works. But variables don't survive the program ending. So how does Run 2 start out knowing what Run 1 found?

You tell it. Your test prints the list at the end of the run:

All known obstacles: [(1, 2), (2, 2), (3, 0)]

Type that list into KNOWN_OBSTACLES, and the first two lines of your test hand each intersection to the planner:

KNOWN_OBSTACLES = [(1, 2), (2, 2), (3, 0)] # what Run 1 discovered

Run it again. The robot plans around all three from its first path. If it finds a fourth, the printed list has four entries, ready for Run 3.

You are the memory. The robot found the obstacles, you carried them to the next run, and the algorithm never changed. The planner has now heard about walls three ways (a test in 5-6, the rangefinder in 5-7, you here), and each was a call to add_blocked(). A real system would save and reload the list itself, but what it carries is exactly what you just did by hand.

Knowledge Check

Run 1 finishes and prints [(1,2), (2,2)]. What has to happen for Run 2 to start out knowing about those two obstacles?

Activity · Measure the improvement​

"It seemed faster" isn't evidence: measure. Your test prints steps and reroutes. Write them down for each run:

Metric Run 1 Run 2
Starting obstacles 0 (from Run 1)
Reroutes ____ ____
Total steps ____ ____

Your numbers will depend on your grid and where the obstacles sit.

Knowledge Check

Run 1 took 12 steps with 3 reroutes; Run 2 took 8 steps with 0 reroutes. Why the change?

Could Run 2 still find new obstacles?​

Yes. Run 2 avoids everything it already knows, but its new route may pass intersections Run 1 never visited, and one could be blocked. Then Run 3 starts knowing even more. Eventually the robot knows every relevant obstacle and its paths are right from the start: that's convergence.

Knowledge Check

Can Run 2 discover an obstacle Run 1 never found?

Real-world connections​

Systems that accumulate and reuse experience are everywhere:

Maps

Waze traffic

One driver hits traffic; the app warns everyone behind them. Shared, remembered data.

AI

Learning from data

Machine-learning systems improve as they collect examples: better data, better results.

Apps

Saved state

Games, editors and browsers save your progress before closing: the automatic version of carrying your list by hand.

Wrap-up​

  • What turns Lesson 5-7's single reroute into "drive until you arrive"? (A while not arrived loop around the for, with a rerouted flag.)
  • What actually changes between Run 1 and Run 2? (The data, the blocked list, not the algorithm.)
  • How do you show Run 2 is better? (Measure steps and reroutes.)
  • What has to happen between runs for the robot to keep what it learned? (The list has to be handed back to add_blocked(): a variable doesn't survive the program ending.)

Wrap-up quiz​

Knowledge Check

What is 'convergence' in this context?

Resources​