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

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

Licences

• Accès libre
• Article: CC BY 4.0

Tout ce qui suit s'appuie sur l'article complet sous sa licence CC BY 4.0 ; sa figure est montrée en citant les auteurs.

En bref

SILLM imite un solveur fondé sur la recherche performant, y ajoute une communication spatiale, un guidage du trafic et une réparation des collisions par PIBT, et planifie pour 10 000 agents en moins de 1 s par pas avec le débit le plus élevé.

Pourquoi c'est important

Les entrepôts automatisés font déjà fonctionner des milliers de robots (l'article cite plus de 4 000 robots dans les centres de distribution d'Amazon en 2022) ; un planificateur qui maintient un débit élevé à cette échelle avec une planification de moins d'une seconde par pas est donc directement pertinent pour la commande de flottes. Les résultats montrent qu'une politique apprise, combinée à une gestion des collisions de type recherche et à un guidage tenant compte du trafic, peut surpasser les solveurs fondés sur la recherche les plus performants à grande échelle, et pas seulement les solveurs optimaux lents.

Problème

Le Lifelong Multi-Agent Path Finding (LMAPF) donne à chaque agent un nouvel objectif dès qu'il en atteint un, de sorte que des chemins sans collision doivent être replanifiés en continu tout en maximisant le débit (objectifs atteints par pas de temps). Les solveurs fondés sur l'apprentissage réagissent rapidement à partir d'observations locales, mais la plupart n'ont été testés qu'avec des dizaines à des centaines d'agents et ne parviennent pas à battre des solveurs de recherche sous-optimaux passant à l'échelle comme PIBT. L'article vise à battre à la fois les solveurs fondés sur l'apprentissage et ceux fondés sur la recherche à l'échelle de 10 000 agents.

Solution proposée

SILLM est une politique convolutive partagée par tous les agents sur un champ de vision de 11×11, avec un module Spatially Sensitive Communication qui insère le vecteur de caractéristiques de chaque voisin à sa position relative exacte dans la grille. Les observations encodent l'une de trois cartes de guidage heuristiques (Backward Dijkstra, une Static Guidance à autoroutes entrecroisées ou une Dynamic Guidance fondée sur TrafficFlow), et une étape CS-PIBT simplifiée conserve l'action apprise lorsqu'elle est sans collision et la répare avec PIBT dans le cas contraire. La politique est entraînée par imitation itérative de Windowed MAPF-LNS, le cœur de WPPL, vainqueur de la League of Robot Runners 2023, sur des cartes réduites avec 600 agents.

Idées clés

• Placer les caractéristiques des voisins à leurs positions relatives exactes (communication sensible à l'espace) a battu, dans l'ablation, la communication fondée sur l'attention et l'absence de communication, ce qui indique qu'un raisonnement spatial précis est important pour le LMAPF.
• Imiter un solveur anytime à grande échelle (Windowed MAPF-LNS) évite les petites instances d'entraînement (8–10 agents) qui limitaient les apprenants par imitation antérieurs tels que PRIMAL2, SCRIMP et MAGAT.
• Le meilleur guidage dépend de la carte : Static Guidance convenait aux cartes de tri en croisillons et d'entrepôt, Backward Dijkstra aux cartes aléatoires, et Dynamic Guidance a donné les meilleurs résultats sur les cartes urbaines de Paris et de Berlin.
• La réparation des collisions fondée sur PIBT conserve l'action apprise chaque fois qu'elle est sans collision et évite les attentes inutiles et les interblocages de la stratégie courante de « gel » (freeze).
• Un simple apprentissage par renforcement MAPPO a obtenu de moins bons résultats que l'apprentissage par imitation, et appliquer MAPPO après l'imitation n'a apporté aucun gain mesurable.

Principaux résultats

• Sur six grandes cartes avec 10 000 agents, le débit moyen a augmenté de 137,7 % par rapport à la meilleure référence fondée sur l'apprentissage et de 16,0 % par rapport à la meilleure référence fondée sur la recherche.
• Score de type compétition sur les grandes cartes : SILLM 0,99, SILLM (Dynamic Guidance seule) 0,94, WPPL 0,88, TrafficFlow 0,81, PIBT 0,61, Follower 0,52 ; RHCR et SCRIMP prenaient plusieurs minutes par pas et n'ont pas pu être évalués à cette échelle.
• Temps moyen de planification par pas sur les grandes cartes : 0,349 s pour SILLM contre 4,143 s pour WPPL et 4,125 s pour Follower.
• Learnable PIBT a battu PIBT simple pour chaque type de guidage sur les grandes cartes (score moyen 0,80 contre 0,61 avec Backward Dijkstra, 0,85 contre 0,75 avec Static Guidance, 0,94 contre 0,81 avec Dynamic Guidance).
• Dans l'entrepôt reconstitué, 10 robots réels ont atteint leurs objectifs sans collision ; avec 100 robots virtuels, Learnable PIBT a donné 50 % de débit de plus que PIBT.
• Chaque itération d'imitation collecte 15 millions de paires action-observation en 50 épisodes, répétée 12 fois ; l'entraînement prend moins de 12 heures par carte sur un serveur équipé de 4 GPU RTX 4090D.

Limites

• Les auteurs indiquent que des limites matérielles et logicielles ont restreint la validation physique à 10 robots réels plus 100 robots virtuels dans un mini-entrepôt, et l'essai sur robots réels est rapporté de manière qualitative.
• Le planificateur suppose que la position de chaque agent est parfaitement connue ; les robots réels ont eu besoin d'un système de capture de mouvement OptiTrack pour la localisation et d'un Action Dependency Graph pour absorber les erreurs d'exécution.
• Les heuristiques de guidage sont conçues à la main, la meilleure dépend de l'instance et doit être choisie empiriquement, et leurs hyperparamètres influent sur les performances.
• L'entraînement à 10 000 agents a été évité en raison des besoins en mémoire ; les politiques sont entraînées avec 600 agents sur des cartes réduites et évaluées sur les grandes cartes.
• L'apprentissage par renforcement n'a pas aidé sous la forme testée ; les auteurs laissent une meilleure attribution de la récompense d'équipe à des travaux futurs.

Impact sur le domaine

L'article a remporté l'IEEE ICRA 2025 Best Paper Award on Multi-Robot Systems et l'IEEE ICRA 2025 Best Student Paper Award, et compte 35 citations. L'article indique que le code serait publié à l'acceptation, et la page officielle du projet renvoie au dépôt de code.

Résumé

Le Lifelong Multi-Agent Path Finding (LMAPF) est une variante du MAPF dans laquelle de nouveaux objectifs sont continuellement attribués aux agents, ce qui nécessite une replanification fréquente pour s'adapter à ces changements dynamiques. Récemment, ce domaine a adopté des méthodes fondées sur l'apprentissage, qui génèrent de manière réactive des actions à pas unique à partir d'observations locales individuelles. Il leur reste cependant difficile d'égaler les performances des meilleurs algorithmes fondés sur la recherche, en particulier à grande échelle. Ce travail propose un solveur LMAPF fondé sur l'apprentissage par imitation qui introduit un nouveau module de communication ainsi que des techniques systématiques de résolution des collisions à pas unique et de guidage global. Le solveur que nous proposons, Scalable Imitation Learning for LMAPF (SILLM), hérite de la vitesse de raisonnement rapide des méthodes fondées sur l'apprentissage et de la haute qualité de solution des méthodes fondées sur la recherche grâce aux GPU modernes. Sur six cartes à grande échelle comptant jusqu'à 10 000 agents et des structures d'obstacles variées, SILLM surpasse les meilleures références fondées sur l'apprentissage et sur la recherche, avec des améliorations moyennes du débit de 137,7 % et 16,0 % respectivement. En outre, SILLM bat également la solution gagnante de la League of Robot Runners 2023, une compétition internationale de LMAPF parrainée par Amazon Robotics. Enfin, nous avons validé SILLM avec 10 robots réels et 100 robots virtuels dans un environnement d'entrepôt reconstitué.

Liens

• arXiv 2410.21415: https://arxiv.org/abs/2410.21415
• DOI 10.1109/ICRA55743.2025.11127445: https://doi.org/10.1109/ICRA55743.2025.11127445
• PDF: https://arxiv.org/pdf/2410.21415v1
• Code: https://github.com/DiligentPanda/Scalable-Imitation-Learning-for-LMAPF
• Page du projet: https://diligentpanda.github.io/SILLM/