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

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

Lizenzen

Open Access
Paper: CC BY 4.0

Alles Folgende stützt sich auf das vollständige Paper unter seiner Lizenz CC BY 4.0; die Abbildung wird mit Nennung der Autoren gezeigt.

Kurz gesagt

SILLM imitiert einen starken suchbasierten Solver, ergänzt räumliche Kommunikation, Verkehrsführung und PIBT-Kollisionsreparatur und plant für 10.000 Agenten in weniger als 1 s pro Schritt mit dem höchsten Durchsatz.

Warum es wichtig ist

Automatisierte Lager betreiben bereits Tausende von Robotern (das Paper nennt mehr als 4.000 in Amazon-Logistikzentren im Jahr 2022), sodass ein Planer, der in dieser Größenordnung bei Planung unter einer Sekunde pro Schritt einen hohen Durchsatz hält, für die Flottensteuerung unmittelbar relevant ist. Die Ergebnisse zeigen, dass eine gelernte Policy in Kombination mit suchartiger Kollisionsbehandlung und verkehrsbewusster Führung die stärksten skalierbaren suchbasierten Solver übertreffen kann und nicht nur langsame optimale.

Problem

Lifelong Multi-Agent Path Finding (LMAPF) gibt jedem Agenten ein neues Ziel, sobald er eines erreicht, sodass kollisionsfreie Pfade fortlaufend neu geplant werden müssen, während der Durchsatz (erreichte Ziele pro Zeitschritt) maximiert wird. Lernbasierte Solver reagieren schnell auf Grundlage lokaler Beobachtungen, wurden aber meist nur mit Dutzenden bis Hunderten von Agenten getestet und schlagen skalierbare suboptimale Such-Solver wie PIBT nicht. Das Paper zielt darauf, sowohl lern- als auch suchbasierte Solver in der Größenordnung von 10.000 Agenten zu schlagen.

Lösungsansatz

SILLM ist eine von allen Agenten geteilte Faltungs-Policy über ein 11×11-Sichtfeld mit einem Spatially-Sensitive-Communication-Modul, das den Merkmalsvektor jedes Nachbarn an dessen exakter relativer Gitterposition einfügt. Die Beobachtungen kodieren eine von drei heuristischen Führungskarten (Backward Dijkstra, eine Static Guidance mit sich kreuzenden Schnellstraßen oder eine auf TrafficFlow basierende Dynamic Guidance), und ein vereinfachter CS-PIBT-Schritt behält die gelernte Aktion bei, wenn sie kollisionsfrei ist, und repariert sie andernfalls mit PIBT. Die Policy wird durch iterative Imitation von Windowed MAPF-LNS, dem Kern von WPPL, dem Gewinner der League of Robot Runners 2023, auf verkleinerten Karten mit 600 Agenten trainiert.

Wichtigste Erkenntnisse

Merkmale der Nachbarn an ihren exakten relativen Positionen zu platzieren (räumlich sensitive Kommunikation), schlug in der Ablation aufmerksamkeitsbasierte Kommunikation und keine Kommunikation, was auf präzises räumliches Schließen als wichtig für LMAPF hindeutet.
Die Imitation eines Anytime-Solvers für große Probleme (Windowed MAPF-LNS) vermeidet die kleinen Trainingsinstanzen (8–10 Agenten), die frühere Imitationslerner wie PRIMAL2, SCRIMP und MAGAT einschränkten.
Die beste Führung hängt von der Karte ab: Static Guidance eignete sich für die Kreuzungs-Sortier- und Lagerkarten, Backward Dijkstra für Zufallskarten, und Dynamic Guidance schnitt auf den Stadtkarten von Paris und Berlin am besten ab.
PIBT-basierte Kollisionsreparatur behält die gelernte Aktion bei, wann immer sie kollisionsfrei ist, und vermeidet die unnötigen Wartezeiten und Deadlocks der üblichen 'Freeze'-Strategie.
Einfaches MAPPO-Reinforcement-Learning schnitt schlechter ab als Imitationslernen, und MAPPO nach der Imitation anzuwenden, brachte keinen messbaren Gewinn.

Hauptergebnisse

Auf sechs großen Karten mit 10.000 Agenten stieg der durchschnittliche Durchsatz um 137,7 % gegenüber der besten lernbasierten Baseline und um 16,0 % gegenüber der besten suchbasierten Baseline.
Punktzahl im Wettbewerbsstil auf großen Karten: SILLM 0,99, SILLM (nur Dynamic Guidance) 0,94, WPPL 0,88, TrafficFlow 0,81, PIBT 0,61, Follower 0,52; RHCR und SCRIMP benötigten Minuten pro Schritt und konnten in dieser Größenordnung nicht evaluiert werden.
Durchschnittliche Planungszeit pro Einzelschritt auf großen Karten: 0,349 s für SILLM gegenüber 4,143 s für WPPL und 4,125 s für Follower.
Learnable PIBT schlug einfaches PIBT bei jedem Führungstyp auf großen Karten (durchschnittliche Punktzahl 0,80 vs. 0,61 mit Backward Dijkstra, 0,85 vs. 0,75 mit Static Guidance, 0,94 vs. 0,81 mit Dynamic Guidance).
Im nachgebildeten Lager erreichten 10 reale Roboter ihre Ziele ohne Kollisionen; mit 100 virtuellen Robotern erzielte Learnable PIBT 50 % mehr Durchsatz als PIBT.
Jede Imitationsiteration sammelt 15 Millionen Aktions-Beobachtungs-Paare in 50 Episoden und wird 12-mal wiederholt; das Training dauert weniger als 12 Stunden pro Karte auf einem Server mit 4 GPUs vom Typ RTX 4090D.

Einschränkungen

Die Autoren geben an, dass Hardware- und Softwaregrenzen die physische Validierung auf 10 reale Roboter plus 100 virtuelle Roboter in einem Mini-Lager beschränkten, und der Lauf mit realen Robotern wird qualitativ berichtet.
Der Planer setzt voraus, dass die Position jedes Agenten perfekt bekannt ist; die realen Roboter benötigten ein OptiTrack-Motion-Capture-System zur Lokalisierung und einen Action Dependency Graph, um Ausführungsfehler abzufangen.
Die Führungsheuristiken sind von Hand entworfen, die beste ist instanzabhängig und muss empirisch gewählt werden, und ihre Hyperparameter beeinflussen die Leistung.
Training mit 10.000 Agenten wurde wegen des Speicherbedarfs vermieden; die Policies werden mit 600 Agenten auf verkleinerten Karten trainiert und auf den großen Karten evaluiert.
Reinforcement Learning half in der getesteten Form nicht; die Autoren überlassen eine bessere Zuweisung der Teambelohnung künftiger Arbeit.

Wirkung auf das Fachgebiet

Das Paper gewann den IEEE ICRA 2025 Best Paper Award on Multi-Robot Systems und den IEEE ICRA 2025 Best Student Paper Award und hat 35 Zitierungen. Laut Paper sollte der Code bei Annahme veröffentlicht werden, und die offizielle Projektseite verlinkt das Code-Repository.

Zusammenfassung

Lifelong Multi-Agent Path Finding (LMAPF) ist eine Variante von MAPF, bei der Agenten fortlaufend neue Ziele zugewiesen werden, was häufiges Neuplanen erfordert, um diese dynamischen Änderungen zu berücksichtigen. In letzter Zeit hat dieses Feld lernbasierte Methoden aufgegriffen, die reaktiv Einzelschrittaktionen auf Grundlage individueller lokaler Beobachtungen erzeugen. Es bleibt für sie jedoch schwierig, mit der Leistung der besten suchbasierten Algorithmen mitzuhalten, insbesondere in groß angelegten Szenarien. Diese Arbeit schlägt einen auf Imitationslernen basierenden LMAPF-Solver vor, der ein neuartiges Kommunikationsmodul sowie systematische Techniken zur Einzelschritt-Kollisionsauflösung und globalen Führung einführt. Unser vorgeschlagener Solver, Scalable Imitation Learning for LMAPF (SILLM), übernimmt mithilfe moderner GPUs die hohe Inferenzgeschwindigkeit lernbasierter Methoden und die hohe Lösungsqualität suchbasierter Methoden. Auf sechs großen Karten mit bis zu 10.000 Agenten und unterschiedlichen Hindernisstrukturen übertrifft SILLM die besten lern- und suchbasierten Baselines und erzielt durchschnittliche Durchsatzsteigerungen von 137,7 % bzw. 16,0 %. Darüber hinaus schlägt SILLM auch die Gewinnerlösung der League of Robot Runners 2023, eines von Amazon Robotics gesponserten internationalen LMAPF-Wettbewerbs. Schließlich haben wir SILLM mit 10 realen Robotern und 100 virtuellen Robotern in einer nachgebildeten Lagerumgebung validiert.

Open Source Robotics