Week 19 · Learn: A map is a model of free space

Session 1 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 a map is a model of free space.

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

A map is a model of free space

An occupancy grid divides a surveyed area into cells marked free or blocked. Each cell represents a region, not a point the robot can safely occupy automatically. The robot has width and needs clearance. Inflate obstacles by robot radius plus margin before planning a centre path; also exclude the boundary clearance. Coarse cells simplify search but may erase narrow corridors. Choose and record cell size, map origin, blocked-cell convention and the physical measurement method. A path through a wrong map can be mathematically valid and physically unsafe.

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)))

Predict the example’s output by hand. Mark the inputs, units and assumptions; explain where this model could fail. 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

Survey a small paper/floor map and choose a grid cell size.
Measure robot width and add a declared clearance margin; mark inflated blocked regions.
Label origin, axes, start, goal and cell-centre convention.
Predict route existence on an open map, wall-separated map and narrow corridor.

Experiment

Compare route existence before/after adding robot clearance on three paper maps; explain any lost passage.

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 measured map, explicit inflation rule and three route predictions.

Save notebook/w19-s1.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 a map is a model of free space in your own words using this session’s example and its units/assumptions.
Produce the specific evidence above: A measured map, explicit inflation rule and three route predictions.
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.