AGTBRIEF
The PUSH algorithm trades exhaustive look ahead for staggered planning over a rotating slice of agents, and authors report scaling lifelong path finding to massive simulated fleets.
Imagine a warehouse where ten thousand robots weave between each other every second, none of them stopping for a global traffic boss. The hard part isn't getting them to move; it's getting them to plan far enough ahead to avoid gridlock without grinding the whole floor to a halt. A new arXiv preprint, Path Updates over Staggered Horizons (PUSH), lands directly on that trade-off.
PUSH sits inside lifelong multi-agent path finding (LMAPF), the subfield built around fleets that run forever and must reroute on the fly. Older rule-based planners like Enhanced PIBT react step by step and stay fast, but they're myopic. Windowed planners like RHCR look several steps ahead but buckle when fleets grow large. TP scales by planning only a slice of agents per step, but only on highly structured maps.
PUSH combines the strengths of all three approaches. Like TP, it picks a staggered subset of agents to replan each step. Like RHCR, it plans windowed paths over multiple steps, but on general maps. And like EPIBT, it uses priority inheritance and backtracking to keep throughput up in congested settings. The authors report that this combination achieves significantly higher system throughput than all baselines across both tested scenarios, while still planning over a multi-step horizon.
In one benchmark, PUSH coordinated thousands of simulated agents (e.g., roughly 10,000) in under a second, matching the agent loads that much faster step-by-step planners handle while planning over multiple steps.
Caveat: the result is in simulation on synthetic warehouse and city-style MAPF scenarios. No warehouse, port, or delivery operator is named, and the 10,000-agent number is author-stated, not yet replicated.