Aisles are single lane and every intersection or bay holds one vehicle at a time. Time is discrete: one tick is the time to drive one aisle segment (tau = 4 s, about 1.3 m/s on 5 to 6 m segments). A robot enters a node only if it is empty at the start of the tick, so a robot that wants an occupied node waits for its owner. Collect those waits into a wait-for graph with one edge per blocked robot. Each robot waits for at most one other, so every component is a path or ends in a cycle, and a cycle is a permanent deadlock: nobody in it can ever move, and anyone queued behind it is stuck too.
first-come: fixed shortest route, longest-waiting robot wins a contested node
deadlock <=> the wait-for graph (out-degree <= 1) contains a cycle (colouring DFS, O(N))
reservation: time-expanded A* over (node, t); enter v at t+1 only if v is empty at t and t+1
in the booking table, so a booked plan can never be invalidated
one robot: cycle = d(dock,pick) + d(pick,dock') + 2 dwell, d = 2 + |dc| + |dr| between bays
P(deadlock) = k / n over n runs, 95 % Wilson interval
dock limit: throughput <= docks x 3600 / (tau x dwell)
- Why first-come fails - the policy never looks ahead, so two robots whose shortest routes meet head-on, or four chasing each other round a rack block, form a cycle. The chance of a cycle grows quickly with fleet size, then throughput collapses as robots pile up behind it.
- Why reservation is safe - each plan is feasible against all earlier bookings and never changed, so the booked paths are conflict-free by construction. The price is planning computation and waiting; throughput then saturates at the dock limit instead of collapsing.
- Same model in both pages - one shared module; the pages only draw it. The checks compare the planner with a closed form, a single-robot run with exact enumeration, the cycle detector with a transitive closure, and Monte Carlo batches with each other.
- Honest simplifications - robots move in lock-step ticks with no acceleration or turning time, equal speed, no battery, no breakdowns, no communication delay; the layout and the station roles are illustrative. Real systems add yielding rules, zones and re-planning on a rolling horizon; this is a teaching model, not a fleet manager.