Fleet Algorithm Atlas

How it works

1. Number every free cell. This map has 99.
2. From each cell, run one breadth-first search. It spreads outward one layer per step of distance.
3. Stations and parking cells get a distance but pass nothing on. A path may end there, never cross one.
4. Store every distance in one table, 2 bytes each. A lookup is a single array read.

Why we use it

• Shelves make straight-line guesses wrong. Allocation needs real walking distance.
• A* uses it as its guess of the distance left. An exact guess wastes almost no search.
• It costs one BFS per cell, once. Every later lookup is free.

How it works

1. A block_cells event closes aisle cells, and unblock_cells opens them again.
2. A closure takes effect once no robot stands on any of its cells, on the floor and in the coordinator’s map, and then its cells close together. A robot inside a closing aisle drives out first: closing the cells around it would leave it no way out.
3. The coordinator rebuilds the distance table. No path passes through a closed cell or ends on one.
4. Coordinated planners replan the whole fleet at once, so the new plans fit together. The baseline replans each robot whose path now crosses a closed cell.
5. Permits stop short of a closed cell, so no robot is sent into one.

Why we use it

• Aisles close in real warehouses: a spill, a dropped pallet, a person at work. Allocation and planning need the real distances, or they send robots toward dead ends.
• A rebuild runs one breadth-first search per free cell, 330 on warehouse_small, and only when a cell changes.
• A closure is accepted only if the open aisles still reach every station and parking cell, so no order becomes impossible.

The catch: until its cells are empty a closure has not happened, so robots can still drive in. On a busy aisle it can wait a while. With six cells of the middle aisle closed for half of each hour, the four rolling planners delivered at most 0.7% fewer orders per hour than with the aisle open, with no safety stop or violation in 120 runs.

How it works

1. Put the start in the open list with score f = g + h. g is steps taken so far. h is the guess of steps left.
2. Take the open cell with the lowest f. Ties go to the smaller h, then the lower cell number.
3. If it is the goal, stop and follow the parents back. If not, add its free neighbours with g + 1.
4. Skip stations and parking cells, unless one is the goal.
5. With an exact h, every cell off a shortest path scores higher. So A* walks almost straight to the goal.

Why we use it

• It is fast. The default run's median planning call took 0.007 ms.
• The oracle gives an exact h. On this map A* then expands exactly one cell per step of path, plus the goal, for all 9,702 start and goal pairs.
• It is the baseline. Every coordinated planner in Stage 4 has to beat it.

The catch: it plans as if the warehouse were empty. Two robots heading opposite ways down a one-cell aisle meet nose to nose and stop for good. The gridlock demo in Robot safety shows it.

How it works

1. List pending orders, oldest first. Same age: lower order number first.
2. For the oldest, look up each free robot's walking distance to its pickup.
3. The closest robot gets it. On a tie, the lower robot number wins.
4. Take that robot out of the pool. Repeat until orders or robots run out.

Why we use it

• It is cheap: one table lookup per order and robot.
• Oldest first keeps waiting times fair.
• With one order and several free robots, nearest is already optimal.

The catch: with several orders at once, an early pick can take the robot a later order needed. In the two-order scene, nearest spends 9 steps of travel. The best matching spends 5.

How it works

1. Build a table: one row per free robot, one column per waiting order, each cell the robot’s walk to that pickup.
2. Add the robots one at a time. A new robot reaches for an order. If another robot holds it, that robot moves to its next best order, and so on down a chain. The chain is called an augmenting path.
3. Of all chains, the solver takes the one that adds least to the total. A price on every row and column, called a potential, turns that into a shortest-path search, so it never tries every matching.
4. After the last robot joins, no matching is cheaper. With k free robots and n orders it costs O(k² n), and the other way round when orders are fewer.

Why we use it

• It fixes nearest’s trap: in Two orders it walks 5 steps where nearest walks 9.
• It is exact and quick. 25 robots and 25 orders solve in 0.04 ms at p95, 100 and 100 in about 1 ms.
• The cost of a pair is a plug-in. cost_aware and learned reuse the solver with a different cost.

The catch: it is optimal for this instant only, and plain distance knows nothing about traffic. With a backlog it can serve closer orders first, so the oldest order waits longer than under nearest. See Backlog.

How it works

1. The matching sees pending orders oldest first. The ones pending longer than 600 steps come first: the starving orders.
2. The oldest of them, at most one per free robot, are matched first, with the usual costs. The cost still decides which robot takes each.
3. The robots left over then match the orders left over, as before.
4. hungarian, cost_aware and learned all share it. nearest needs none: it already takes the oldest order first.

Why we use it

• The cheapest matching serves the closest orders. When orders come faster than robots can serve them, new orders near the robots keep winning, and a far order can wait for the rest of the run.
• At 0.2 orders per step with 5 and 10 robots, offered at least twice what they can carry, the oldest order still open at the end of an hour had waited 2335 steps on average with the guard and 2556 without.

The catch: those robots walk farther, so the same runs delivered 1.7% fewer orders per hour. Where robots keep up, no order reaches 600 steps and the guard changes nothing.

How it works

1. A robot with an order asks for its station. The first to ask gets the turn.
2. Everyone else gets the nearest free spare parking cell (never a home, at most 8 per station) and waits there.
3. When the robot at the station finishes, the next in line gets the turn and drives in.
4. The endpoint rule: a path may start or end on a station or parking cell, but never pass through one. So parked and working robots block nobody.

Why we use it

• Without queues, robots wait in the aisle beside the station. In the Queues off scenario the station locks for good.
• Without the rule, A* happily routes along the parking row, straight into parked robots.
• Robots rest only on stations and parking, so aisles stay free for traffic.

Scenario note: Going home, rule off is a what-if. The real planner always applies the rule. The other three scenarios run the real coordinator logic, step for step.

How it works

1. A search state is a cell and a step. From each state the robot can wait or move to a free neighbor, one step later.
2. A state is out if a reserved robot stands in that cell at that step, or would swap places with this robot. Endpoints other than the goal stay out, as always.
3. A* orders states by steps so far plus the distance oracle’s steps to go, so it still finds the earliest arrival first.
4. It stops at the goal only when the robot can stay there: no reserved robot comes through later. Windowed planners stop at the window’s end instead.

Why we use it

• Waiting is a move here. In Crossing, R0 waits one step and arrives one step late instead of colliding.
• One search serves every planner: prioritized and WHCA* reserve the paths found so far, CBS adds forbidden cell-steps, ECBS counts conflicts instead of forbidding them.
• After the last reserved robot stops moving, every later step looks the same, so the search folds them into one layer and stays finite.

The catch: it plans one robot. Whoever plans first takes the best cells and steps, and the robots after it get what is left. The next sections are about who plans first.

How it works

1. Sort the robots: oldest order first, idle robots last, then by id.
2. Each robot runs space-time A* around the paths already reserved, then reserves its own.
3. If a robot finds no path, start over with it at the front. There are at most as many restarts as robots.
4. WHCA* checks only the first planning.window steps (20 by default) and trusts the replanning to fix the rest.

Why we use it

• It is fast: one search per robot. At 25 robots it plans in 0.29 ms at p95, 0.22 ms with the window.
• Oldest orders first is a fair rule that robots and people can predict.
• The restart rescues the common bad order. In Restart, the robot inside the pocket must leave before the other comes in.

The catch: it is not complete. In Head-on, both orders fail: whoever plans first walks straight through, and the other cannot reach the side cell in time. The fleet then keeps its old plans and tries again a step later.

How it works

1. The root plans every robot alone with space-time A*, ignoring the others.
2. Take the node with the lowest total cost. Find its earliest clash: two robots in one cell, or swapping cells.
3. Split: one child forbids that cell at that step to the first robot, the other to the second. Each child replans only that robot.
4. The first node without a clash is the answer, and nothing cheaper exists. ECBS expands, among nodes within w of the best bound, the one with the fewest clashes.

Why we use it

• It is optimal: least total steps over all robots, within the window.
• ECBS keeps most of that quality and is far quicker on crowds: in Siding it needs 2 expansions where CBS needs 8.
• ECBS delivered the most at 25 robots and 0.2 orders per step, ahead of WHCA* in all 10 seeds.

The catch: head-on in a one-cell aisle, CBS forbids the same clash one step later again and again, before it tries the siding. In the fleet benchmark that ran its budget out on 2,994 of 9,598 calls at 10 robots and 0.1 orders per step, and froze 2 of those 10 runs.

How it works

1. Rank the robots: away from their goal first, longest away first, then a fixed hash.
2. In rank order, each robot not yet moved tries its cells, nearest to its goal first, staying included.
3. If another robot stands in the chosen cell, that robot must move first, anywhere but into the first robot’s cell. If it cannot, the first robot tries its next cell. That is the backtracking.
4. Repeat for planning.window steps (20 by default) to make the plan, and replan every few steps.

Why we use it

• It never searches: 0.11 ms per call at p95 with 25 robots, the fastest planner here.
• It never fails: every robot always has a next cell, so the fleet keeps moving.
• The dead-end rule fixes its one blind spot on this map. Every parking cell is a dead end under the endpoint rule. In Dead end with the rule off, the two robots wait for each other forever.

The catch: it looks one step ahead. In Head-on, the robot that gives way backs up to the end of the aisle instead of into the side cell, and the two shuffle without passing. In the fleet that costs throughput: 22% less than WHCA* at 25 robots and 0.2 orders per step.

How it works

1. Every replan_period steps, every robot gets a new plan from where it stands, conflict-free for the next window steps.
2. A robot working at a station is no agent. It holds its station as an obstacle until its service ends.
3. Between calls, robots follow their plans. replan_period is at most window, so plans always last until the next call.
4. A call that finds nothing within the budget changes no plan. The old plans stay conflict-free, and the call runs again the next step.

Why we use it

• Orders keep arriving, so plans to the goal go stale. A short window costs less and is redone soon anyway.
• All five planners plug into one loop. With the toggle off, prioritized, CBS and ECBS plan robots whose goal changed all the way to the goal.
• When a station has no free waiting cell, a robot waits at home. Waiting on a station or in an aisle can block the very robot it waits for, and at 25 robots that locked the fleet.

The catch: a robot whose goal changes waits for the next call, up to replan_period − 1 steps. Planning every step removes that wait and multiplies the planning work by replan_period.

How it works

1. When plans are committed, each one is cut into stays: which cell, arriving at which step, and the path index the robot reaches by leaving.
2. For every cell, the stays are sorted by plan time. A move into a cell depends on the stay just before it there.
3. Every tick, a robot may take its next move if the robot before it in that cell has left. It may also go while that robot leaves in the same step; it then follows it out, and yields if that robot misses the step after all.
4. The permit runs on while each further move is already safe, and stops before a closed cell.
5. It needs plans made together, which rolling replanning makes. Planning to goals uses reservations instead.

Why we use it

• Real robots run early or late: a slow wheel, a person in the way, a missed message. Keeping each cell’s order keeps conflict-free plans safe however late anyone runs (Hönig et al., 2019).
• A late robot holds up only the robots planned after it in some cell. Everyone else keeps going.
• In 320 hour-long runs with robots missing up to one step in three, no planner had a single safety stop. With both rules off, the same robots at one missed step in ten were stopped by robot safety 44,170 times.

The catch: delays ripple. With 25 robots missing one step in five, PIBT robots spent 1329 robot-steps per run held and 2421 yielding, and delivered 4% less than on time. ECBS lost 0.1%.

How it works

1. A robot may enter a cell only while it holds the cell’s reservation: the cell is empty, or its robot leaves in the same step.
2. One robot per cell per step. When two want the same cell, the older order wins, then the lower id.
3. Two robots that want each other’s cells both wait.
4. A held robot waits for at most one robot, so following those links finds every cycle.
5. Recovery: rolling replanning moves its next call to the next step. Planning to goals replans the whole fleet together at the next step.

Why we use it

• Planning to goals plans each robot around the others’ plans, at different times. Late robots break those plans, and there is no single plan order for the dependency graph to keep.
• Planning to goals with one robot step in ten missed: with reservations and recovery, 0 of 50 runs froze and none had a safety stop. Without recovery 50 of 50 froze. Without reservations robot safety stopped robots 1,052,387 times and 50 of 50 runs froze.

The catch: reservations do not keep the planned order. With rolling replanning and the dependency graph off, PIBT robots at 25 robots formed 75 cycles per hour that needed a replan, where the dependency graph formed none.

How it works

1. Every command adds to the robot’s reach: the cells from its last reported place on its path up to its permit. A report that arrives resets the reach to the cell it gives.
2. A robot heard this step is where it says. It wins its cell over a silent robot last seen there.
3. No other robot gets a permit into a cell a silent robot may have reached, or a permit to follow it.
4. A silent robot keeps its plan. Replanning it from where it was last seen would plan the others around the wrong cell.
5. A permit is good only in the step its command arrives. A robot that hears nothing stands still, which the traffic rules already treat as a missed step. After 5 steps without a command it holds in safe stop, and station service waits.

Why we use it

• Radios drop messages. A rule that trusts the last report is wrong exactly when one is lost.
• In 320 hour-long runs with up to three messages in ten lost, robot safety stopped no robot, no run broke an invariant, and none froze.
• Two earlier versions failed. Trusting the last report let a robot that had moved on be run into, at step 135 of the first run with one message in five lost. Holding only the cells a silent robot may reach still failed at step 1,362: the coordinator believed two robots on one cell and told a third to follow the wrong one.

The catch: every lost command costs a step. With 10 robots, 8% to 12% fewer orders per hour at one message in twenty lost, and 49% to 55% fewer at three in ten. With 25 robots there is slack: windowed_coop_astar, prioritized, and ecbs lost at most 2% up to one message in five; pibt lost 33% at one in five.

How it works

1. Every report renews a robot’s lease. A robot silent for more than 5 steps (heartbeat_timeout_steps) is declared dead.
2. Its order goes back to the queue. It keeps its age, so it is first in line again.
3. The cells it may stand on close in the coordinator’s map, except a cell a robot heard this step stands on. A station among them stays its turn, so no other robot is sent there. The fleet replans around them.
4. A dead robot stays where it stopped until an operator takes it away (rescue_steps, 120) and tells the coordinator. Its cells open.
5. A robot declared dead that reports again rejoins. Its cells open, a delivery it made meanwhile counts, and it keeps the order it carries unless another robot has picked that order up.

Why we use it

• A lease needs nothing but the reports robots already send every step.
• In 120 hour-long runs of the fault scenario below, the coordinator declared both dead robots dead every time. Robot safety stopped no robot, no run broke an invariant, and none froze.
• The fuzz harness ran 1,000 random scenarios: generated warehouses, fleets, planners, delays, closures, and faults. Every one ran without a violation or an exception, and twice to the same log hash. They held 709 robot deaths, 4,532 false deaths, and 1,108,831 lost messages.

The catch: a slow link looks like a death. With one message in five lost, the loss runs above declared robots dead by mistake 280 times in 80 runs, and 2,448 times at three in ten. A false death sends an order back to the queue, and an order can end up delivered twice: once in the 120 fault runs.

How it works, every step, in this order

1. Intent: each robot wants the next cell on its path. Robots working at a station, waiting, or out of path stay put.
2. Same cell: when two robots want one cell, the lower robot number goes.
3. Head-on: two robots that want each other's cells both stop.
4. Occupied: nobody enters a cell whose robot stays. Each new stop can block the robot behind, so repeat until nothing changes.
5. Everyone left moves at once. Following is fine. So is a loop of four or more.

Why we use it

• The planner can be wrong, and independent A* always is. Safety keeps the physics honest: no shared cells, no swaps.
• Every stop is recorded. With coordinated planners, any stop counts as a violation.
• The same inputs give the same stops, so a run replays to the same trajectory hash.

Why four or more? A grid has no loop of three cells. The smallest loop is a 2×2 block, and a loop of two is a swap.

How it works

1. Every step, each robot stopped by robot safety points at the robot standing in the cell it wanted.
2. A robot wants one cell, so it points at one robot at most. Following the pointers gives chains.
3. A chain that ends at a robot that is not waiting is a queue. It clears when the front robot moves.
4. A chain that loops back is a cycle. Every robot on it waits for the next, so none can move until a plan changes. A cycle that lasts 10 steps is a deadlock, and robots whose chain runs into it are behind it.
5. Separately, a robot with work that makes no progress for 30 steps is stalled. If nobody makes progress for the rest of the run, the run froze at that step.

Why we use it

• Throughput says the baseline failed. The monitor says when, where and who.
• Each robot has one pointer at most, so finding every cycle takes one pass over the fleet per step.
• It reads ground truth only, like the invariant checker, so the coordinator never grades itself.
• It turns “it got stuck” into numbers every later stage must beat: first deadlock, frozen from.

Why wait 10 steps? A new plan can break a cycle in a step or two, as in Breaks early. A deadlock does not break. In the default run, one cycle broke after 16 steps, only because a station turn handed one robot a new path.