Week 19 · Build: Breadth-first search

Session 2 of 4 · Plan a route · Phase 5

Plan about 15 minutes for explanation, 30 minutes for practical work and 10–15 minutes for documentation. A longer build may continue into the next session: stop safely, commit the current state and record the next check. Desktop simulations count as software evidence; label them clearly and record physical validation separately.

Engineering challenge

Can you find a route that respects the robot’s size and the map’s uncertainty? This session focuses on breadth-first search.

Before you start

The previous week’s recorded baseline and Week 18, Improve. For later sessions this week, retain the preceding session’s files and predictions.

Equipment: Desktop Python, editor, paper and ruler; for physical work, the configured 3pi+ 2040, clear floor mat and hardware checklist. Week 3 additionally uses the separate low-voltage LED circuit described in its procedure.

For any motion, verify the stop button, short time limit and clear floor area first. Keep the wheels raised for a new device program until its commands and stop behaviour are checked. A hazard or uncertain input is a reason to stop and document, not to force the trial to finish.

Theory and mathematics

Breadth-first search

A grid can be viewed as a graph: cells are nodes and allowed moves are edges. Breadth-first search explores the start, then nodes one move away, then two away. A queue preserves this order. Track visited nodes so cycles cannot run forever, and remember each node’s predecessor to reconstruct a path. With equal-cost four-neighbour moves, BFS finds a path with the fewest edges when one exists. It does not minimize travel time, turning count or energy automatically. A blocked goal or disconnected region must return no route clearly.

Worked example — illustrative values

On a 5 × 5 grid, moving from (0,0) to (4,4) with four-neighbour unit moves needs at least |4−0| + |4−0| = 8 moves. A returned path contains 9 cells including the start. With 0.20 m cells, its centre-line length is 1.60 m. Obstacles can make this longer or make a route impossible.

Write the calculation in your notebook before running code. State which values you measured, which you assumed and which the program calculates. A correct numerical calculation cannot rescue an incorrect physical assumption.

Run and explain the model

The following is desktop Python, not a ready-to-run motor program. Download this week’s example, save it in your student repository and run python3 code/w19.py from the repository root. The same small model is reused across the week so you can learn it, build with it, test it and revise it.

# Desktop Python teaching example. Numerical inputs are illustrative.
from collections import deque

def bfs(width, height, blocked, start, goal):
    valid = lambda p: 0 <= p[0] < width and 0 <= p[1] < height and p not in blocked
    if not valid(start) or not valid(goal):
        return None
    queue, parent = deque([start]), {start: None}
    while queue:
        point = queue.popleft()
        if point == goal:
            path = []
            while point is not None:
                path.append(point)
                point = parent[point]
            return path[::-1]
        x, y = point
        for nxt in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if valid(nxt) and nxt not in parent:
                parent[nxt] = point
                queue.append(nxt)
    return None

print(bfs(5, 5, {(2, 1), (2, 2), (2, 3)}, (0, 0), (4, 4)))

Run the example on desktop Python before adapting it. Change one valid input and check the result; keep device-only calls in a separate adapter. If an exception appears, read its final line, identify the input or assumption that caused it and make the smallest explained correction. Do not delete validation merely to obtain output.

Understanding the model and its limits

The queue explores cells in increasing move count, while the parent dictionary serves both as visited tracking and a route reconstruction record. Start maps to None, marking the end of the backward chain. The function returns None when endpoints are invalid or the reachable region is exhausted. It does not inflate obstacles; prepare that blocked-cell set from robot dimensions before calling it. Path cells must be converted to world centres consistently. Inspect each consecutive pair: its Manhattan difference should be one, and neither endpoint may be blocked. These checks catch plausible-looking but disconnected routes.

Practical instructions

Trace the queue by hand for the first six expansions, then run the example.
Implement or adapt BFS with visited tracking and predecessor reconstruction.
Check that every returned move is one four-neighbour step and every cell is allowed.
Convert cells to metre-valued centre waypoints and save the map as data.

Experiment

Check six returned path cells manually and deliberately block the goal to verify a no-route result.

Before testing, record your prediction, changed factor, measured response, fixed conditions and stopping rule. Save every attempted run, including failures, with a condition and source version. If hardware is unavailable, use an explicitly labelled synthetic/replay dataset and list the physical question it cannot answer. Do not invent completed trials.

Deliverable

A terminating BFS with valid reconstructed moves and consistent metre conversion.

Save notebook/w19-s2.md, the relevant code revision, raw CSV or test-case records, and one labelled diagram/plot/table. Link the files relatively from your notebook. Use the entry template and report guide.

Completion criteria

Explain breadth-first search in your own words using this session’s example and its units/assumptions.
Produce the specific evidence above: A terminating BFS with valid reconstructed moves and consistent metre conversion.
Keep predictions and raw outcomes, distinguish observations from interpretation, and explain one limitation or unresolved failure.
Review the Git diff, commit the session’s intended files and state the next experiment or safe continuation point.

A documented failed prediction can meet the learning criteria. A missing physical trial must remain marked untested; software success alone does not validate the robot.

Reading and video

Focused reading: Amit Patel: graph search and breadth-first search. Study task: Step through the BFS animation and reconstruct a route from predecessors.
Video/lecture option: MIT OpenCourseWare: Macro ME robot demonstration. Study task: Compare its sensors with your robot; do not copy hardware assumptions. Watch a relevant 5–10 minute excerpt or use the linked notes if video is inaccessible. This is supporting conceptual material; hardware in a demonstration may differ from yours.
Practical reference: Engineering handbook and hardware setup. Manufacturer/API references and video metadata were checked on 2026-10-09; recheck the actual firmware before transferring code.

Reflection and next step

Which assumption most affected your result? Point to one observation that supports your explanation and one alternative explanation the evidence has not ruled out. Write a specific next test with a changed factor and measurable outcome, then proceed through the week’s Learn → Build → Experiment → Improve cycle.