A disruption hits. Who has to change their plan?
Twenty robots are delivering parcels. Robots break down, aisles get blocked, urgent orders arrive. Our method repairs only the robots that are affected, by negotiating with nearby robots. The baseline replans everyone. Both run on the same seed so you can compare them directly.
Same run, two planners
Disruptions click one to jump to it
The problem
A fleet of robots shares a warehouse floor. Each robot has a list of pick-and-deliver jobs, and every robot's route is planned in space and time so that no two robots are ever in the same cell, or swap cells, at the same moment.
That plan is only correct until something goes wrong. In a real warehouse things go wrong all the time:
Breakdowns
A robot stops where it is, for 5–20 steps or for good. Its cell becomes an obstacle and its jobs may need a new owner.
Blockages
A cell becomes unusable: a dropped box, a person, a spill. Some clear after a while, some do not.
Emergencies
An urgent order appears with a deadline. Some robot has to take it, and others may need to make way.
The usual fix, and why it hurts
The simple answer is to stop and replan every robot from scratch. That gives good routes, but it is expensive with many robots, it needs one central computer that can talk to everyone, and it changes the routes of robots that had nothing to do with the problem. Every changed route has a cost on a real floor: new reservations, re-sent commands, and more chances for things to go wrong.
What we set out to do
- Repair locally. Only the robots whose plans are actually broken should start the repair.
- Talk only to neighbours. Robots communicate over a range-limited message bus (6 cells), not a central server.
- Change as few plans as possible. Asking another robot to move is allowed, but it has a price.
- Never call the global planner after the start, and never allow a collision.
The warehouse
An 18 × 33 grid: 25 shelf blocks with pickup cells along their faces, 14 delivery stations on the left and right walls, and docks along the top and bottom where robots start and finish. Each robot gets three jobs; a run has 5–50 robots.
How it works
Plan once with a standard method. After that, every disruption is handled by the robots involved, in tiers that escalate only when the cheaper option is not good enough.
1 · Initial plan: prioritized Space-Time A*
Robots are planned one at a time. Each one searches over (cell, time) states with A* and writes its route into a shared
reservation table. Later robots treat those reservations as obstacles, so vertex and swap conflicts are impossible by construction.
2 · Detect who is affected
When a disruption happens, the simulator finds every robot whose remaining plan now conflicts with it (it passes through the blocked cell, collides with the broken robot, or must take the emergency job). Those robots are queued for repair. Nobody else moves.
3 · Repair in tiers
Each queued robot stops at the first tier whose result beats simply going around alone.
Find a new route around the problem. Accept if it is at most 4 steps late (0 for emergencies).
Ask groups of 1–3 robots within 6, then 12 cells to change their routes too. Requests can chain one hop further.
For urgent robots only: jointly replan up to 8 nearby robots that cross its corridor.
A path exists, it is just slow. Take it.
Wait on the current cell and retry every step. The search radius doubles every 10 steps of waiting.
Only robots in the chosen option change their plans. They send an UPDATE to neighbours in range.
The price of asking for help
Each option gets a score:
score = total delay + λ · (number of other robots whose plans change) + deadline penalty
With λ = 3, recruiting one more robot is only worth it if it saves more than three steps of delay. Raising λ means
fewer plans touched but more delay; the results page shows that trade-off.
4 · Safety
All repairs write through the same reservation table as the initial plan, so a repaired plan cannot overlap anyone's committed future. The test suite runs in a strict mode where overwriting another robot's reservation is an error, and checks every committed plan for conflicts after each disruption.
What we compare against
- Full replan: re-run prioritized planning for every robot after each disruption. The baseline.
- Solo: tier 1 only, with no negotiation. Shows what negotiation adds.
- Local v1 (flat): our first version, without chained requests or the group replan.
Where it breaks
We also ran settings designed to make it fail: 20–30% of the floor blocked, a small crowded map, a short radio range, and solvability checks off. Robots then get stuck in two ways. A blockage can cut a goal off entirely, which no planner can fix. Or robots can deadlock while waiting for each other; this happens mostly without negotiation, which is the main thing negotiation prevents.
Stack
Python and NumPy for the planner and simulator, Matplotlib for figures, pytest for safety tests. This page runs the same Python package in the browser with Pyodide inside a Web Worker, and draws it on a canvas.
Results
Every setting runs 10 seeds, and all four planners run on the same seeds. The main sweep varies the number of robots from 5 to 50, with 3% of cells blocked over time, 2 breakdowns and 2 emergencies per run.
Reading the results honestly
- Fewer plans changed is the main win. At 50 robots, a full replan rewrites about 39 routes per disruption. Ours changes about 6, and three quarters of those are robots the disruption hit directly.
- Total travel time is no worse, and is slightly better at large fleets, because a full replan is greedy and can reshuffle robots badly.
- Emergencies are the trade-off. A full replan puts the urgent robot first and meets the deadline more often. Local repair only reorders nearby robots, so it is late more often.
- Repair is slower per disruption at 40–50 robots, since negotiation tries many small joint plans. It is still under a few seconds, and in a real system the work would be spread across the robots.
Run it yourself
git clone https://github.com/SreenityaThatikunta/warehouse-plan-repair cd warehouse-plan-repair python3 -m venv .venv && .venv/bin/pip install -r requirements.txt .venv/bin/python -m warehouse_mapf.run --agents 20 --strategy local --seed 1 .venv/bin/python experiments/run_experiments.py