Skip to main content

Lesson 8 · Building Experience

Module 5 · Dijkstra's Algorithm

Lesson 8 · Building Experience

55 minMemory + file I/OThe robot learns
👩‍🏫

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

In Lesson 7 the robot rediscovered every obstacle from scratch each run — like being surprised by the same construction zone every morning. This lesson gives it memory: it remembers obstacles from one run and plans smarter on the next. Just like Waze learns from drivers, the robot learns from its own experience.

Learning Objectives

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

  • Explain why remembering obstacles improves navigation
  • Keep a blocked list across runs so the robot pre-plans around known obstacles
  • Compare Run 1 and Run 2 with metrics (steps, reroutes)
  • Explain the GPS/Waze analogy for crowd-sourced obstacle data
  • (Challenge) Save and load the blocked list with a file so it survives restarts
Printable knowledge checks — the 5 questions from this lesson on one page, with room to write. Teachers: answer key.

Why memory matters​

The Dijkstra algorithm doesn't change between runs. The Navigator doesn't change. 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 leads to better performance. The robot isn't running a smarter algorithm on Run 2 — it's running the same algorithm on better information.

Knowledge Check

Why does the robot navigate better on Run 2?

Activity · Measure the improvement​

"It seemed faster" isn't evidence — measure. Track total steps, reroutes, and newly discovered obstacles for each run:

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

Fill it in from your own two runs — the numbers are the evidence, and they'll differ with your grid and where the obstacles sit.

Keeping the same blocked_list variable across both runs is all it takes — its Run 1 discoveries are already there when Run 2 begins.

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 smarter route may pass nodes Run 1 never visited — and one of those could be blocked. So Run 2 can still discover something new, and Run 3 would start with even more knowledge. Eventually the robot knows every relevant obstacle and its paths are optimal from the start — that's convergence.

Knowledge Check

Can Run 2 discover an obstacle Run 1 never found?

Activity · Persistence with a file​

Within one program run, a list variable persists between function calls. But close the program and it's gone — Python variables don't survive a restart. To keep knowledge across separate runs, save it to a file:

def save_obstacles(blocked, filename="obstacles.txt"):
    with open(filename, "w") as f:
        for node in blocked:
            f.write(f"{node[0]},{node[1]}\n")     # one "row,col" per line

def load_obstacles(filename="obstacles.txt"):
    blocked = []
    try:
        with open(filename, "r") as f:
            for line in f:
                row, col = line.strip().split(",")
                blocked.append((int(row), int(col)))
    except FileNotFoundError:
        pass                                       # no file yet → start fresh
    return blocked

Load at the start, save at the end. Now the robot's experience survives being powered off — run it a third time and the file holds obstacles from every prior run.

Knowledge Check

Why is a file needed to remember obstacles between separate program runs?

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 accumulate examples — the same "better data, better results" idea.

Apps

Saved state

Games, editors, and browsers save progress to files so you pick up where you left off.

Wrap-up​

  • 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.)
  • Why a file instead of just a variable? (Variables vanish on restart; files persist.)

Wrap-up quiz​

Knowledge Check

What is 'convergence' in this context?

Resources​