The Urmston robotsWhen every agent takes the shortest route
A real road network, invented robots, and a timetable they all have to share.
The learner downloads the roads of Urmston, Flixton and Davyhulme from OpenStreetMap in one query, 1,606 roads adding up to 204.4 km, and reduces them to a network of 2,113 junctions and road ends joined by 2,479 links. Then the rules are invented, and stated as invented. Imaginary delivery robots move 20 metres every 10-second tick. Only one robot may stand at a junction in any tick, and two robots may not travel along the same link towards each other at the same time. Each robot gets its own start and destination, and it leaves the network when it arrives.
First every robot plans alone, taking its shortest route and ignoring the others. With 40 robots on the road, those plans clash 37 times, and 29 of the 40 robots are caught up in at least one clash. Then the learner switches to prioritised planning with a reservation table, the method David Silver called cooperative A* in 2005. Robots plan one at a time. Each searches in space and time, allowed to move or to wait a tick, and treats every junction and link already booked by an earlier robot as unavailable at that moment. Its own route is then written into the table for the next robot to respect.
Simulated robots on the Urmston road network: clashes when planning alone, and total delay in ticks after planning around each other, our Python run| Robots | Clashes, planning alone | Delay, longest trip first | Delay, shortest trip first | Delay, 20 random orders |
|---|
| 20 | 11 (12 robots) | 63 ticks | 70 ticks | 50 to 86 ticks |
| 40 | 37 (29 robots) | 165 ticks | 163 ticks | 125 to 209 ticks |
| 80 | 152 (68 robots) | 457 ticks | 493 ticks | 416 to 640 ticks |
After prioritised planning there are no clashes at all, which the program confirms by checking every pair of plans, and no robot is left without a route. The cost is small in total: for 40 robots, 165 ticks of delay, about 27 and a half minutes spread across the whole fleet against 5,173 ticks of travel, with the worst single robot 21 ticks, three and a half minutes, late. Nine robots waited at a junction at least once, and thirteen more were delayed only by taking a longer way round. The order matters more than it looks. With 80 robots, twenty random orders produced anything from 416 to 640 ticks of delay, and planning the longest trips first beat planning the shortest first. No order is guaranteed to win, and choosing it is a real design decision.
Ages 8 to 11
Move three counters across a squared board in turns without two ever sharing a square.
Ages 11 to 15
Plan one route in Python with breadth-first search, then add a second robot and find the clash.
Ages 15 and up
Write space-time A* with a reservation table and test different priority orders.
Sources and assumptions
Roads are from OpenStreetMap contributors under the Open Database Licence, read with one Overpass query on 1 October 2026. Prioritised planning goes back to Erdmann and Lozano-Pérez in 1987, and cooperative A* to Silver in 2005. The robots, their speed and every rule about junctions and links are ours, invented for the exercise; no delivery robots are claimed to operate in Urmston.
