Skip to main content

Lesson 5-6 · Testing and Swapping

Module 5 · Pathfinding Around Obstacles

Lesson 5-6 · Testing and Swapping

50–60 minTesting by propertiesOne harness, any plannerSlides (PowerPoint)
👩‍🏫

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

Your planner passes five tests. Now test it properly, with a testing idea that outlasts this course. Then point the same tests at Module 4's Manhattan planner and watch it fail, for exactly the reason this module exists.

Learning Objectives

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

  • Explain why an exact-match test is wrong for BFS and right for Manhattan
  • Name the five properties every correct path has, and write each as one if
  • Explain why the walled-off case needs its own test
  • Hand a function to another function, and explain what planner(position, destination) does inside the harness
  • Run one harness against Manhattan and BFS and explain every FAIL line
  • Write a main program that works with either planner by changing one name

Two right answers, one test​

Compare your Lesson 5-5 Test 1 path with a classmate's. If they match, here's another correct one:

[(1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)] # yours, maybe
[(0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)] # also six steps, also right

Now here's the test from Module 4's Lesson 4-3, still in your file as run_test():

if actual == expected:
print(test_name, "- PASS")

One of those two correct paths gets marked FAIL. Exact match was fine for Manhattan, which has exactly one answer. BFS doesn't, so it needs a different kind of test, with a different name. run_test() stays in the MANHATTAN PLANNER section, doing its job.

Test what must be true​

Forget the exact list. What must be true of any correct path from (0, 0) to (3, 3)?

  1. The first step is next to the start.
  2. The last step is the destination.
  3. Every step is next to the one before it.
  4. No step is a blocked intersection.
  5. With nothing blocked, the number of steps is the Manhattan distance.

Each is a one-line check. Together they are stricter than an exact match, which only tells you a path is the one you expected, and they allow every correct answer. That's a property test: check what must be true, not what you happened to expect.

Test 4: from S at (0, 0) to D at (3, 0) with (1, 0) and (1, 1) blocked. Left, the BFS path around the wall, 7 steps, with badges showing properties 1 to 4 holding. Middle, the five properties; the fifth, steps equal the Manhattan distance, is only checked on an open grid. Right, Manhattan's path goes straight across to the right through blocked (1, 0) and fails property 4.
The checks never ask which shortest path you found, only whether it is a legal one of the right length.
Knowledge Check

Why are the five property checks stronger than comparing with one expected path?

This lesson's skeleton​

Paste this at the end of the BFS PLANNER section. You write the two helpers and the checker. run_all_tests() (the suite) and navigate() are given: they are the "same program" in "same program, swap the planner."

# --- Lesson 5-6: the property harness ---
# Tests any planner by what must be true of its path, not by
# one expected list, because BFS has many right answers.
# run_all_tests() is handed a planner FUNCTION and runs the
# six cases through it: one program tests Manhattan and BFS.
# Module 4's run_test() stays; exact match is right there.

def manhattan_distance(a, b):
"""Steps between a and b with nothing in the way."""
pass

def is_neighbor(a, b):
"""True when a and b are one step apart."""
pass

def check_path(path, start, destination):
"""Return a list of everything wrong with path as a route
from start to destination; [] means it is good."""
# problems = []
# an empty path is fine only if already there; return
# 1. first step next to the start?
# 2. last step the destination?
# 3. every step next to the one before it?
# 4. no step in BLOCKED?
# return problems
pass

def run_path_test(test_name, planner, start, destination, expected_steps):
"""Ask planner for a path, check the five properties, print
PASS or FAIL with the path; return True on a pass."""
# path = planner(start, destination)
# problems from check_path(), plus 5. the step count
# no problems: print " PASS ", test_name, "", path
# otherwise: print " FAIL " the same way, then each
# problem on its own line, " - " in front
pass

def run_no_path_test(test_name, planner, start, destination):
"""For a walled-off destination the only right answer is
[]; print PASS or FAIL and return True on a pass."""
pass

def run_all_tests(name, planner):
"""The six cases, through whichever planner is handed in:
four on the open grid, the wall, and walled off."""
print("==========", name, "==========")
passed = 0
clear_blocked()
if run_path_test("open (0, 0) to (3, 3)", planner, (0, 0), (3, 3), 6):
passed = passed + 1
if run_path_test("open (0, 0) to (0, 3)", planner, (0, 0), (0, 3), 3):
passed = passed + 1
if run_path_test("open (2, 1) to (0, 3)", planner, (2, 1), (0, 3), 4):
passed = passed + 1
if run_path_test("open (1, 1) to (1, 1)", planner, (1, 1), (1, 1), 0):
passed = passed + 1
add_blocked((1, 0))
add_blocked((1, 1))
if run_path_test("wall at (1,0),(1,1): (0,0) to (3,0)", planner, (0, 0), (3, 0), 7):
passed = passed + 1
add_blocked((1, 2))
add_blocked((1, 3))
if run_no_path_test("walled off: (0,0) to (3,0)", planner, (0, 0), (3, 0)):
passed = passed + 1
clear_blocked()
print(name + ":", passed, "of 6 passed")

def navigate(planner, position, destination):
"""Plan with planner and print the path; return
destination, where the robot would be after driving it."""
path = planner(position, destination)
print(" Path from", position, "to", destination, ":", path, " Steps:", len(path))
return destination

Activity · Build the harness​

Step 1 · Two helpers​

manhattan_distance() is the Lesson 5-1 count: the x difference plus the y difference, each made positive with abs(). is_neighbor() asks whether that distance is exactly 1. Write both.

Step 2 · check_path() returns a list of problems​

One if per property, each appending a sentence to problems when it fails; an empty list means the path is good. The outline's first line is the special case: an empty path is correct when position == destination and a problem otherwise. Either way there are no steps to check, so return at once.

Make the sentences specific. A bare FAIL gets ignored; "drives through blocked intersection (1, 0)" tells you what to fix. That's why it returns problems, not True/False. Build each with + and str(): property 1's is "first step " + str(path[0]) + " is not next to the start " + str(start), and the others likewise name the step and say what's wrong. Property 3 loops from the second step to the last, comparing each with the one before; property 4 loops over every step.

run_path_test() checks the fifth property, the step count, against the count its caller gives it.

One case check_path can't judge: an empty path for a walled-off destination is correct, but looks just like "forgot to look." So walled-off gets its own small test, run_no_path_test(), where the only right answer is [].

Knowledge Check

A planner returns [(0,1), (0,3)] for (0,0) to (0,3). Which property fails, and what does the FAIL line say?

Step 3 · Hand the harness its planner​

The one new Python idea in the lesson: handing a function to a function. Look at run_path_test()'s planner parameter and the two lines you're about to write:

def run_path_test(test_name, planner, start, destination, expected_steps):
path = planner(start, destination)
...

run_all_tests("Manhattan", compute_manhattan_path)
run_all_tests("BFS", compute_bfs_path)

compute_bfs_path, with no parentheses, is the function itself, handed over like a number or a list. run_all_tests passes it on to run_path_test, where planner(position, destination) calls it. Both planners have the same shape, so the harness never needs to know which one it has.

Try it at the prompt first: f = compute_bfs_path, then f((0, 0), (3, 3)).

The test harness run_all_tests(name, planner) runs the same six cases and checks, calling planner(position, destination) through a slot. Either compute_manhattan_path or compute_bfs_path can be handed in. Manhattan passes 4 of 6; BFS passes 6 of 6.
The harness has a slot shaped like a planner call. Any function that fits can be handed in.

Now write run_path_test() and run_no_path_test() from their outlines. Each returns True on a pass so run_all_tests() can count. PASS and FAIL lines look like this:

PASS open (0, 0) to (0, 3) [(0, 1), (0, 2), (0, 3)]
FAIL wall at (1,0),(1,1): (0,0) to (3,0) [(1, 0), (2, 0), (3, 0)]
- drives through blocked intersection (1, 0)
- expected 7 steps, got 3
Knowledge Check

Inside run_path_test, what does `path = planner(start, destination)` do when the harness was called with run_all_tests("BFS", compute_bfs_path)?

Activity · Run it against both​

Write test_harness(), the two run_all_tests() lines above, and set the run line to it. BFS should pass 6 of 6. Then read Manhattan's lines carefully:

========== Manhattan ==========
computing path from: (0, 0) to: (3, 3)
PASS open (0, 0) to (3, 3) [(1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]
computing path from: (0, 0) to: (0, 3)
PASS open (0, 0) to (0, 3) [(0, 1), (0, 2), (0, 3)]
computing path from: (2, 1) to: (0, 3)
PASS open (2, 1) to (0, 3) [(1, 1), (0, 1), (0, 2), (0, 3)]
computing path from: (1, 1) to: (1, 1)
PASS open (1, 1) to (1, 1) []
computing path from: (0, 0) to: (3, 0)
FAIL wall at (1,0),(1,1): (0,0) to (3,0) [(1, 0), (2, 0), (3, 0)]
- drives through blocked intersection (1, 0)
- expected 7 steps, got 3
computing path from: (0, 0) to: (3, 0)
FAIL walled off: (0,0) to (3,0) [(1, 0), (2, 0), (3, 0)]
- there is no way through, so the path should be empty
Manhattan: 4 of 6 passed

Manhattan isn't broken. It does exactly what Module 4 built it to do, across then up or down, and it has no idea what a wall is. The harness just showed why this module exists.

Then the same swap in a main program. navigate(), the skeleton's last function, plans with the planner it's handed, prints the path, and returns the destination: where the robot would be after driving it. Write test_swap(): block (2, 0), then run two trips, (0, 0) to (3, 3) and back, with each planner. Only the planner's name changes:

position = navigate(compute_manhattan_path, (0, 0), (3, 3)) # through the wall
position = navigate(compute_bfs_path, (0, 0), (3, 3)) # around it

Finally, break a property on purpose: make compute_bfs_path return path[1:] (drop the first step), then path + [destination]. Which property catches each?

Do this after your functions version works on the robot. It is not graded; it is for when there is time. Once it works, use it from here on.

Real-world connections​

Software

Property-based testing

Professional test tools generate thousands of random inputs and check properties, exactly as this harness checks paths — because for most real programs there is no single expected answer.

Design

Plug-in parts

Handing a function (or object) to code that doesn't know which one it got is how programs are built from swappable parts: sort orders, file formats, planners.

Robotics

Test before you drive

Everything the harness checks here is checked without a robot. Real robot teams test the planner on a laptop for the same reason: it's faster, and it separates "the algorithm is wrong" from "the robot drove wrong."

Wrap-up​

  • Why not compare with one expected path? (BFS has many correct answers; the properties allow all of them and check validity.)
  • What are the five properties? (Starts next to the start; ends at the destination; every step a neighbor; no blocked step; Manhattan-distance length on an open grid.)
  • Why does walled-off get its own test? (check_path can't tell it from a broken planner's [].)
  • What's passed in run_all_tests("BFS", compute_bfs_path)? (The function itself.)
  • Why does Module 4's run_test() keep its name and its job? (Exact match is right for a planner with one answer.)

Resources​