Warehouse robot planners are almost always benchmarked in a world where demand behaves politely. In the standard "lifelong" setting, where robots keep receiving new pick-up and drop-off jobs, a robot gets its next job at the moment it finishes the current one. Load therefore stays constant, and it is tied to how fast the planner works. Real fulfillment centers do not behave this way: orders arrive on their own schedule, in bursts and with skewed popularity, whether or not a robot is free. We argue that the "replenish on completion" convention is itself a static-environment assumption, and a well-hidden one. It never asks a planner to absorb a surge of jobs whose destinations run against the traffic patterns it has learned to exploit. We propose to remove this assumption in a controlled way. Job arrival will be decoupled from job completion. Planners will be broken into a few swappable stages behind narrow interfaces, so that any change in behavior can be traced to a specific stage. The question is which of today's winning ingredients stop working when demand stops being stationary.
The core claim is that the ingredients behind recent large-scale results are implicitly tuned to stationary load. These ingredients are traffic guidance graphs computed offline, warm-starting each replan from the previous plan, and deliberately parking some robots. We expect their advantage to shrink or reverse under bursty open-stream arrivals, measured by how long a job waits from arrival to completion rather than by saturated throughput. The modular decomposition is what makes this claim testable rather than anecdotal. The mechanism we test as a remedy is deliberately simple: an arrival-triggered rule that discards warm-start guidance only for robots whose job set changed or whose planned paths cross the regions where new jobs land.
What exists and what it leaves open
Lifelong multi-agent path finding means planning collision-free routes for many robots that continuously receive new goals. It is usually handled by planning over short rolling windows. Lifelong Multi-Agent Path Finding in Large-Scale Warehouses introduced this scheme (RHCR), resolving collisions only within a horizon $w$ and replanning every $h$ steps. It showed that short windows match infinite ones in throughput while being far cheaper.
Three works supply the components whose stationarity we question:
- Offline guidance graphs. Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings describes WPPL, the system that won the League of Robot Runners. It fuses windowed PIBT (a fast rule where each robot moves by priority and pushes lower-priority neighbors aside), parallel local repair, offline guidance graphs and agent disabling. Its authors themselves flag online, adaptive guidance as open.
- Congestion-aware guide paths. Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding computes per-agent guide paths that penalize vertex congestion and head-on corridor traffic.
- Warm-starting from the previous plan. Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities (PIE-D) warm-starts each replan from the previous paths. It handles only execution delays on pre-assigned goals, not new arrivals.
Every one of these is evaluated under completion-driven replenishment, so none of them has been asked how it behaves when 500 jobs land at once and none at the next step.
On the evaluation side, the closest work is The League of Robot Runners Competition. It standardizes a boundary between planner and simulator, but treats the planner as one black box and uses a simple task replenisher. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks and Tracking Progress in Multi-Agent Path Finding are strictly one-shot.
The motivating evidence that demand shape matters comes from Caching-Augmented Lifelong Multi-Agent Path Finding. It shows that skewed and temporally local request distributions change travel latency and congestion, though only inside one fixed warehouse design.
Our method for isolating effects is borrowed from modular evaluation systems in other fields:
- VeriBench separates the workload generator from the systems under test.
- A Composable Evaluation System for Reproducible Omni-Modal Foundation Model Evaluation shows that unisolated evaluation glue alone can swing scores by up to 80 points.
Both also warn of constraints we take seriously. VeriBench reports a generic adapter that crippled one database's range queries, so an interface can erase a system's strengths. In our setting, abstraction overhead could eat into a 1,000 ms planning budget.
Research Program
We will build on the League of Robot Runners harness rather than replace it. We will add an arrival interface that emits timestamped jobs independently of robot state. Its generators cover:
- Poisson arrivals at a set rate.
- Bursty arrivals, with on/off periods of controllable intensity.
- Skewed popularity, using the 7:2:1 and temporally local distributions from CAL-MAPF.
- Replay of the real warehouse transaction trace CAL-MAPF uses.
Each generator is seeded, so every planner sees the identical job stream.
Inside the planner, we separate four stages that today's submissions bundle together:
- the job assigner, which decides which robot takes which pending job;
- the guidance stage, which produces a cost map or guide paths;
- the warm-start policy, which decides what part of the previous plan seeds the next one;
- the collision-resolution kernel, which is PIBT or a windowed search.
Data passes between stages as in-memory arrays, not serialized messages. We will report per-step overhead of the boundaries as a fraction of the step budget. If the overhead exceeds a few percent at 10,000 robots, that is itself a finding about where modular boundaries can live.
The switch from closed to open arrivals changes the right metric. Under completion-driven replenishment, throughput measures saturated capacity. Under open arrivals, throughput simply equals the arrival rate until the system falls behind. The quantities that matter are therefore:
- mean and 95th-percentile sojourn time, the delay from job arrival to completion;
- sustainable arrival rate, the highest rate at which the pending-job queue stays bounded over a long run, estimated by bisection over the rate;
- recovery time after a burst, the number of steps until sojourn time returns to its pre-burst level.
The proposed remedy is a staleness rule in the warm-start stage. When a batch of jobs arrives, we mark grid regions within a radius of each new destination. Previous-path guidance is dropped only for robots that were reassigned or whose current guide path enters a marked region, and only those robots get fresh congestion-aware guide paths. Everyone else keeps their warm start. The rule has one parameter, the radius. At radius zero it reduces to pure warm start; at a radius covering the map it becomes full regeneration of guidance.
Baselines
The naive reference point is periodic batch replanning with robots waiting at their targets. Incoming jobs are buffered and released every $h$ steps, and idle robots stay parked. RHCR reports that rolling-horizon replanning without endpoint waiting improves throughput by 6–7% over this style of policy in the closed-loop setting (Lifelong Multi-Agent Path Finding in Large-Scale Warehouses). We expect the gap to widen under bursts. Any configuration that fails to beat this baseline on sojourn time would indicate a broken pipeline.
The strongest existing method is WPPL (Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings). It ranked first overall in the League of Robot Runners, and its guidance graphs improved throughput by nearly 200% over its baseline on the Warehouse 8000 instance. We will run its released competition entry inside the harness if it executes there unmodified. Otherwise we will reimplement it from the description and label it as a reimplementation. It receives the same 1,000 ms step limit, the same core count, and the same seeded arrival streams. Its guidance graph is precomputed offline under the closed-loop workload exactly as its authors intend; we additionally give it a version retuned on a held-out bursty stream, with the same tuning budget we give our method. No reported result was found on Lacuna for WPPL's sojourn time or sustainable arrival rate under open-stream arrivals. Beating it therefore means one of two outcomes on at least the sortation and warehouse maps: a higher sustainable arrival rate, or lower 95th-percentile sojourn time at a matched rate. Matching its closed-loop throughput is not enough.
The second strong competitor is PIBT with online congestion-aware guide paths (Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding). It already recomputes guidance when a robot receives a goal, sustains roughly 2,000 more agents than its baseline before degrading, and returns moves for 10,000 agents in under a second. It is the most direct threat to our remedy, because it is already partly arrival-aware.
PIE-D-style warm starting from previous paths (Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities) serves as the pure-warm-start pole. It reports up to 3x throughput over waiting baselines and up to 2x better solution cost than distance-to-goal heuristics.
The ablation that isolates our ingredient sweeps the staleness radius from zero, which is pure warm start, to full-map, which is complete guidance regeneration. Everything else is held fixed. The claim survives only if an intermediate radius beats both endpoints at equal compute.
Why not just…?
Why not just plug a Poisson generator into the existing competition harness and run the entries? We agree, and that is our first step. It is cheap, and it already answers whether closed-loop rankings survive open arrivals. What it cannot do is explain a ranking change, because the entries are monoliths. If WPPL degrades, we cannot tell whether the guidance graph, the warm start, or agent disabling is responsible. The four-stage decomposition exists only for this attribution. If the black-box comparison shows no ranking change, we will stop there and report that closed-loop benchmarks are adequate.
Why not just regenerate congestion-aware guidance for every robot at every replan? This is a real threat. Online guide paths are already fast enough for 10,000 agents within a second (Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding), and full regeneration is the large-radius end of our own ablation. PIE-D's 2x cost gain from previous-path guidance (Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities) suggests that discarding history has a price, but that evidence comes from delays, not arrivals. If full regeneration matches the best intermediate radius on sojourn time at equal compute, we will report that the useful lesson is "make guidance online," not "make it local," and drop the locality claim.
Why not just replan from scratch with an exact solver whenever jobs arrive? Integrated exact assignment-and-routing collapses even at small scale. Optimal CBS-TA-MLA reached only a 29% success rate on a dense map with 20 agents (Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding). Sequencing alone took over half the runtime in MS*. We include bounded-suboptimal ECBS-TA-MLA only on small maps, as a quality reference for sojourn time.
Why not just scale robot count in the closed-loop setting, since saturation already stresses the planner? Closed-loop saturation tests capacity under constant load; it never produces a surge whose destinations oppose the established flow. This is an empirical question, and we settle it directly. Across all planner configurations, we compute the rank correlation between closed-loop throughput and open-stream 95th-percentile sojourn time. If the correlation is high (Kendall's tau above roughly 0.8), the hidden-assumption claim is wrong and existing benchmarks suffice.
Proposed Experiments
We will use the following maps:
- the RHCR fulfillment (33×46) and sorting-center (37×77) maps;
- the League of Robot Runners Random, Sortation (140×500, up to 10,000 robots) and Paris city maps;
- the CAL-MAPF 27×71 warehouse with its three demand distributions, including the real trace;
maze-32-32-4from the MovingAI suite as a negative control. Guidance is known to help little there (Tracking Progress in Multi-Agent Path Finding), so we expect no effect from any guidance variant.
For each map, arrival generator and burst intensity, we will measure the sustainable arrival rate, sojourn-time percentiles, burst recovery time and per-step planning time, over at least ten seeds. Differences will be reported with confidence intervals.
Three checks decide the outcome:
- Do planner rankings change between closed-loop and bursty open-stream evaluation, as measured by the rank correlation above?
- When they change, does swapping a single stage account for most of the degradation?
- Does an intermediate staleness radius beat both pure warm start and full regeneration on burst recovery at matched compute?
Abstraction overhead will be reported alongside, as the share of the 1,000 ms budget consumed by the stage boundaries at 10,000 robots.
References
- Lifelong Multi-Agent Path Finding in Large-Scale Warehouses
- Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding
- Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities
- The League of Robot Runners Competition: Goals, Designs, and Implementation
- Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks
- Tracking Progress in Multi-Agent Path Finding
- Caching-Augmented Lifelong Multi-Agent Path Finding
- VeriBench: Analyzing the Performance of Database Systems with Verifiability
- A Composable Evaluation System for Reproducible Omni-Modal Foundation Model Evaluation
- Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding
- MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding