Deploying Ten Thousand Robots: Scalable Imitation Learning for Lifelong Multi-Agent Path Finding

Authors: He Jiang, Yutong Wang, Rishi Veerapaneni, Tanishq Duhan, Guillaume Sartoretti, Jiaoyang Li · ICRA 2025

Licences

Open Access
Paper: CC BY 4.0

Everything below draws on the full paper under its CC BY 4.0 licence; its figure is credited to the authors.

TL;DR

SILLM imitates a strong search-based solver, adds spatial communication, traffic guidance and PIBT collision repair, and plans for 10,000 agents in under 1 s per step with the highest throughput.

Why it matters

Automated warehouses already run thousands of robots (the paper cites more than 4,000 in Amazon fulfillment centres in 2022), so a planner that keeps throughput high at that scale with sub-second planning per step is directly relevant to fleet control. The results show that a learned policy, combined with search-style collision handling and traffic-aware guidance, can outperform the strongest scalable search-based solvers rather than only slow optimal ones.

Problem

Lifelong multi-agent path finding (LMAPF) gives each agent a new goal as soon as it reaches one, so collision-free paths must be replanned continuously while maximising throughput (goals reached per timestep). Learning-based solvers react quickly from local observations, but most have only been tested with tens to hundreds of agents and fail to beat scalable suboptimal search solvers such as PIBT. The paper aims to beat both learning-based and search-based solvers at the scale of 10,000 agents.

Proposed solution

SILLM is a convolutional policy shared by all agents over an 11×11 field of view, with a Spatially Sensitive Communication module that inserts each neighbour's feature vector at its exact relative grid position. Observations encode one of three heuristic guidance maps (Backward Dijkstra, a crisscross-highway Static Guidance, or TrafficFlow-based Dynamic Guidance), and a simplified CS-PIBT step keeps the learned action when it is collision-free and repairs it with PIBT when not. The policy is trained by iterative imitation of Windowed MAPF-LNS, the core of the 2023 League of Robot Runners winner WPPL, on downscaled maps with 600 agents.

Key insights

Placing neighbours' features at their exact relative positions (spatially sensitive communication) beat attention-based communication and no communication in the ablation, pointing to precise spatial reasoning as important for LMAPF.
Imitating an anytime, large-scale solver (Windowed MAPF-LNS) avoids the small training instances (8–10 agents) that limited earlier imitation learners such as PRIMAL2, SCRIMP and MAGAT.
The best guidance depends on the map: Static Guidance suited the crisscross sortation and warehouse maps, Backward Dijkstra suited random maps, and Dynamic Guidance did best on the Paris and Berlin city maps.
PIBT-based collision repair keeps the learned action whenever it is collision-free and avoids the unnecessary waits and deadlocks of the common 'freeze' strategy.
Simple MAPPO reinforcement learning underperformed imitation learning, and applying MAPPO after imitation gave no measurable gain.

Main results

On six large maps with 10,000 agents, average throughput rose 137.7% over the best learning-based baseline and 16.0% over the best search-based baseline.
Competition-style score on large maps: SILLM 0.99, SILLM (Dynamic Guidance only) 0.94, WPPL 0.88, TrafficFlow 0.81, PIBT 0.61, Follower 0.52; RHCR and SCRIMP took minutes per step and could not be evaluated at this scale.
Average single-step planning time on large maps: 0.349 s for SILLM versus 4.143 s for WPPL and 4.125 s for Follower.
Learnable PIBT beat plain PIBT under every guidance type on large maps (average score 0.80 vs 0.61 with Backward Dijkstra, 0.85 vs 0.75 with Static Guidance, 0.94 vs 0.81 with Dynamic Guidance).
In the mock warehouse, 10 real robots reached their goals without collisions; with 100 virtual robots, Learnable PIBT gave 50% more throughput than PIBT.
Each imitation iteration collects 15 million action-observation pairs in 50 episodes, repeated 12 times; training takes under 12 hours per map on a server with 4 RTX 4090D GPUs.

Limitations

The authors state that hardware and software limits restricted physical validation to 10 real robots plus 100 virtual robots in a mini warehouse, and the real-robot run is reported qualitatively.
The planner assumes every agent's position is perfectly known; real robots needed an OptiTrack motion-capture system for localisation and an Action Dependency Graph to absorb execution errors.
The guidance heuristics are hand-designed, the best one is instance-dependent and must be chosen empirically, and their hyperparameters affect performance.
Training at 10,000 agents was avoided because of memory demands; policies are trained with 600 agents on downscaled maps and evaluated on the large maps.
Reinforcement learning did not help in its tested form; the authors leave better team-reward assignment to future work.

Field impact

The paper won the IEEE ICRA 2025 Best Paper Award on Multi-Robot Systems and the IEEE ICRA 2025 Best Student Paper Award, and has 35 citations. The paper states the code would be released on acceptance, and the official project page links the code repository.

Abstract

Lifelong Multi-Agent Path Finding (LMAPF) is a variant of MAPF where agents are continually assigned new goals, necessitating frequent re-planning to accommodate these dynamic changes. Recently, this field has embraced learning-based methods, which reactively generate single-step actions based on individual local observations. However, it is still challenging for them to match the performance of the best search-based algorithms, especially in large-scale settings. This work proposes an imitation-learning-based LMAPF solver that introduces a novel communication module and systematic single-step collision resolution and global guidance techniques. Our proposed solver, Scalable Imitation Learning for LMAPF (SILLM), inherits the fast reasoning speed of learning-based methods and the high solution quality of search-based methods with the help of modern GPUs. Across six large-scale maps with up to 10,000 agents and varying obstacle structures, SILLM surpasses the best learning- and search-based baselines, achieving average throughput improvements of 137.7% and 16.0%, respectively. Furthermore, SILLM also beats the winning solution of the 2023 League of Robot Runners, an international LMAPF competition sponsored by Amazon Robotics. Finally, we validated SILLM with 10 real robots and 100 virtual robots in a mockup warehouse environment.

Open Source Robotics