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

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

Licencias

Acceso abierto
Artículo: CC BY 4.0

Todo lo que sigue se basa en el artículo completo bajo su licencia CC BY 4.0; su figura se muestra con crédito a los autores.

En resumen

SILLM imita a un potente solucionador basado en búsqueda, añade comunicación espacial, guiado del tráfico y reparación de colisiones con PIBT, y planifica para 10.000 agentes en menos de 1 s por paso con el mayor rendimiento de procesamiento.

Por qué importa

Los almacenes automatizados ya funcionan con miles de robots (el artículo cita más de 4000 en los centros logísticos de Amazon en 2022), por lo que un planificador que mantiene un alto rendimiento de procesamiento a esa escala con una planificación de menos de un segundo por paso es directamente relevante para el control de flotas. Los resultados muestran que una política aprendida, combinada con una gestión de colisiones al estilo de la búsqueda y un guiado consciente del tráfico, puede superar a los solucionadores escalables basados en búsqueda más potentes, y no solo a los óptimos lentos.

Problema

El lifelong multi-agent path finding (LMAPF) da a cada agente un objetivo nuevo en cuanto alcanza uno, de modo que hay que replanificar continuamente trayectorias sin colisiones mientras se maximiza el rendimiento de procesamiento (objetivos alcanzados por paso de tiempo). Los solucionadores basados en aprendizaje reaccionan rápido a partir de observaciones locales, pero la mayoría solo se ha probado con decenas o cientos de agentes y no logra superar a solucionadores de búsqueda subóptimos y escalables como PIBT. El artículo pretende superar tanto a los solucionadores basados en aprendizaje como a los basados en búsqueda a la escala de 10.000 agentes.

Solución propuesta

SILLM es una política convolucional compartida por todos los agentes sobre un campo de visión de 11×11, con un módulo Spatially Sensitive Communication que inserta el vector de rasgos de cada vecino en su posición relativa exacta en la cuadrícula. Las observaciones codifican uno de tres mapas de guiado heurísticos (Backward Dijkstra, una Static Guidance de autopistas en cuadrícula cruzada o una Dynamic Guidance basada en TrafficFlow), y un paso CS-PIBT simplificado conserva la acción aprendida cuando no produce colisiones y la repara con PIBT cuando sí. La política se entrena por imitación iterativa de Windowed MAPF-LNS, el núcleo de WPPL, ganador de la League of Robot Runners de 2023, en mapas reducidos con 600 agentes.

Ideas clave

Colocar los rasgos de los vecinos en sus posiciones relativas exactas (comunicación sensible al espacio) superó a la comunicación basada en atención y a la ausencia de comunicación en la ablación, lo que apunta a que el razonamiento espacial preciso es importante para LMAPF.
Imitar a un solucionador anytime y a gran escala (Windowed MAPF-LNS) evita las instancias de entrenamiento pequeñas (8–10 agentes) que limitaban a anteriores aprendices por imitación como PRIMAL2, SCRIMP y MAGAT.
El mejor guiado depende del mapa: Static Guidance funcionó bien en los mapas de clasificación en cuadrícula cruzada y de almacén, Backward Dijkstra en los mapas aleatorios y Dynamic Guidance dio los mejores resultados en los mapas urbanos de París y Berlín.
La reparación de colisiones basada en PIBT conserva la acción aprendida siempre que no produce colisiones y evita las esperas innecesarias y los bloqueos mutuos de la estrategia habitual de 'congelar'.
El aprendizaje por refuerzo simple con MAPPO rindió por debajo del aprendizaje por imitación, y aplicar MAPPO después de la imitación no dio ninguna mejora medible.

Resultados principales

En seis mapas grandes con 10.000 agentes, el rendimiento de procesamiento medio subió un 137,7 % respecto a la mejor referencia basada en aprendizaje y un 16,0 % respecto a la mejor referencia basada en búsqueda.
Puntuación al estilo de la competición en mapas grandes: SILLM 0,99, SILLM (solo Dynamic Guidance) 0,94, WPPL 0,88, TrafficFlow 0,81, PIBT 0,61, Follower 0,52; RHCR y SCRIMP tardaban minutos por paso y no pudieron evaluarse a esta escala.
Tiempo medio de planificación de un solo paso en mapas grandes: 0,349 s para SILLM frente a 4,143 s para WPPL y 4,125 s para Follower.
Learnable PIBT superó al PIBT simple con todos los tipos de guiado en los mapas grandes (puntuación media de 0,80 frente a 0,61 con Backward Dijkstra, 0,85 frente a 0,75 con Static Guidance, 0,94 frente a 0,81 con Dynamic Guidance).
En la maqueta de almacén, 10 robots reales alcanzaron sus objetivos sin colisiones; con 100 robots virtuales, Learnable PIBT dio un 50 % más de rendimiento de procesamiento que PIBT.
Cada iteración de imitación recoge 15 millones de pares acción-observación en 50 episodios, y se repite 12 veces; el entrenamiento tarda menos de 12 horas por mapa en un servidor con 4 GPU RTX 4090D.

Limitaciones

Los autores indican que los límites de hardware y software restringieron la validación física a 10 robots reales más 100 robots virtuales en un minialmacén, y la prueba con robots reales se presenta de forma cualitativa.
El planificador supone que la posición de cada agente se conoce perfectamente; los robots reales necesitaron un sistema de captura de movimiento OptiTrack para la localización y un Action Dependency Graph para absorber los errores de ejecución.
Las heurísticas de guiado están diseñadas a mano, la mejor depende de la instancia y debe elegirse empíricamente, y sus hiperparámetros afectan al rendimiento.
Se evitó entrenar con 10.000 agentes por las exigencias de memoria; las políticas se entrenan con 600 agentes en mapas reducidos y se evalúan en los mapas grandes.
El aprendizaje por refuerzo no ayudó en la forma probada; los autores dejan para trabajo futuro una mejor asignación de la recompensa de equipo.

Impacto en el campo

El artículo ganó el IEEE ICRA 2025 Best Paper Award on Multi-Robot Systems y el IEEE ICRA 2025 Best Student Paper Award, y tiene 35 citas. El artículo indica que el código se publicaría tras la aceptación, y la página oficial del proyecto enlaza al repositorio de código.

Resumen

Lifelong Multi-Agent Path Finding (LMAPF) es una variante de MAPF en la que a los agentes se les asignan continuamente nuevos objetivos, lo que exige replanificar con frecuencia para adaptarse a estos cambios dinámicos. Recientemente, este campo ha adoptado métodos basados en aprendizaje, que generan de forma reactiva acciones de un solo paso a partir de observaciones locales individuales. Sin embargo, todavía les resulta difícil igualar el rendimiento de los mejores algoritmos basados en búsqueda, sobre todo en escenarios a gran escala. Este trabajo propone un solucionador de LMAPF basado en aprendizaje por imitación que introduce un nuevo módulo de comunicación y técnicas sistemáticas de resolución de colisiones de un solo paso y de guiado global. Nuestro solucionador propuesto, Scalable Imitation Learning for LMAPF (SILLM), hereda la rapidez de razonamiento de los métodos basados en aprendizaje y la alta calidad de solución de los métodos basados en búsqueda con la ayuda de las GPU modernas. En seis mapas a gran escala con hasta 10.000 agentes y estructuras de obstáculos variadas, SILLM supera a las mejores referencias basadas en aprendizaje y en búsqueda, con mejoras medias del rendimiento de procesamiento del 137,7 % y del 16,0 %, respectivamente. Además, SILLM también supera a la solución ganadora de la League of Robot Runners de 2023, una competición internacional de LMAPF patrocinada por Amazon Robotics. Por último, validamos SILLM con 10 robots reales y 100 robots virtuales en una maqueta de almacén.

Enlaces

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
Código: https://github.com/DiligentPanda/Scalable-Imitation-Learning-for-LMAPF
Página del proyecto: https://diligentpanda.github.io/SILLM/