The Wokingham projectThe Canadian traveller problem on Wokingham streets
The agent has the map. Nobody has told it which roads are shut today.
One request to OpenStreetMap returns 2,839 mapped roads inside a box around Wokingham, from main roads to residential streets. The learner's program joins them into a network of 3,382 junctions and 3,712 links, 271.6 km of road in all. Then the experiment begins. The program picks two junctions at least 2 km apart by road and shuts each link at random with a fixed chance. The agent starts with the full map and no knowledge of the closures. Standing at a junction, it can see whether the roads leaving that junction are open. Each time it spots a closure it replans the shortest route using everything seen so far. We compare its journey with a hindsight route, the shortest one a traveller could take who knew every closure before setting out.
Replanning agent against the hindsight route, 500 Wokingham trips at each closure rate (our Python run, OpenStreetMap data)| Links shut | Trips as short as hindsight | Average distance, hindsight = 1 | Worst trip |
|---|
| 2% | 271 of 500 | 1.083 | 2.33 |
| 5% | 142 of 500 | 1.232 | 3.66 |
| 10% | 55 of 500 | 1.504 | 5.85 |
With 2% of links shut, the average open-map route was 4,904 m, the hindsight route 5,216 m and the agent's actual journey 5,776 m. It replanned a little over twice per trip. More than half its journeys could not have been shorter. The cost sits in the tail: one trip in twenty was at least 1.48 times the hindsight distance, and the unluckiest was 2.33 times. At 10% the typical trip is about a third longer than hindsight and the worst is nearly six times.
Next the learner gives the agent slightly better eyes: it can now also see the roads at any junction one open link ahead. Nothing else changes. At 2% closures the perfect trips rise from 271 to 305 and the average factor falls from 1.083 to 1.066. At 5% the factor drops from 1.232 to 1.185, and at 10% from 1.504 to 1.393. A small amount of early warning is worth real distance, and the learner can put a number on it. Two cautions belong with these results. The closures are random draws made by our program and have nothing to do with actual roadworks in Wokingham. And we kept only trips where the destination could still be reached, discarding 72 draws at 2%, 236 at 5% and 986 at 10%, so the figures describe journeys that remained possible.
Ages 8 to 11
Play it as a board game: a friend hides "road closed" cards on a paper map and you find your way across.
Ages 11 to 15
Code the map as a Python dictionary and write the agent that replans each time it meets a closure.
Ages 15 and up
Run 500 trips, compare against hindsight, then test whether seeing one junction ahead pays for itself.
Data credit and limits
Road data (C) OpenStreetMap contributors, Open Database Licence, read 30 September 2026. The network, the simulated closures and every figure are our own work. Roads that cross the edge of the box are cut there, and the results would shift with a different box or different random draws.
