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

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

Licenze

Open access
Articolo: CC BY 4.0

Tutto ciò che segue si basa sull'articolo completo secondo la sua licenza CC BY 4.0; la figura è riportata citando gli autori.

In breve

SILLM imita un potente risolutore basato sulla ricerca, aggiunge comunicazione spaziale, guida del traffico e riparazione delle collisioni con PIBT, e pianifica per 10.000 agenti in meno di 1 s per passo con il throughput più alto.

Perché è importante

I magazzini automatizzati gestiscono già migliaia di robot (l'articolo cita oltre 4.000 robot nei centri logistici di Amazon nel 2022), quindi un pianificatore che mantiene un throughput elevato a quella scala con una pianificazione sotto il secondo per passo è direttamente rilevante per il controllo delle flotte. I risultati mostrano che una policy appresa, combinata con una gestione delle collisioni in stile ricerca e una guida consapevole del traffico, può superare i risolutori scalabili basati sulla ricerca più forti, e non solo quelli ottimi ma lenti.

Problema

Il lifelong multi-agent path finding (LMAPF) assegna a ogni agente un nuovo obiettivo appena ne raggiunge uno, quindi i percorsi privi di collisioni devono essere ripianificati di continuo massimizzando il throughput (obiettivi raggiunti per passo temporale). I risolutori basati sull'apprendimento reagiscono rapidamente a partire da osservazioni locali, ma la maggior parte è stata testata solo con decine o centinaia di agenti e non riesce a battere risolutori di ricerca subottimi e scalabili come PIBT. L'articolo mira a battere sia i risolutori basati sull'apprendimento sia quelli basati sulla ricerca alla scala di 10.000 agenti.

Soluzione proposta

SILLM è una policy convoluzionale condivisa da tutti gli agenti su un campo visivo di 11×11, con un modulo Spatially Sensitive Communication che inserisce il vettore di feature di ogni vicino nella sua esatta posizione relativa sulla griglia. Le osservazioni codificano una di tre mappe di guida euristiche (Backward Dijkstra, una Static Guidance a corsie incrociate o una Dynamic Guidance basata su TrafficFlow), e un passo CS-PIBT semplificato mantiene l'azione appresa quando è priva di collisioni e la ripara con PIBT quando non lo è. La policy è addestrata per imitazione iterativa di Windowed MAPF-LNS, il nucleo di WPPL, vincitore della League of Robot Runners 2023, su mappe ridotte con 600 agenti.

Idee chiave

Collocare le feature dei vicini nelle loro esatte posizioni relative (comunicazione sensibile allo spazio) ha battuto la comunicazione basata sull'attenzione e l'assenza di comunicazione nell'ablazione, indicando che un ragionamento spaziale preciso è importante per il LMAPF.
Imitare un risolutore anytime su larga scala (Windowed MAPF-LNS) evita le piccole istanze di addestramento (8–10 agenti) che limitavano precedenti metodi di apprendimento per imitazione come PRIMAL2, SCRIMP e MAGAT.
La guida migliore dipende dalla mappa: Static Guidance si è adattata alle mappe di smistamento a griglia incrociata e di magazzino, Backward Dijkstra alle mappe casuali, e Dynamic Guidance ha dato i risultati migliori sulle mappe cittadine di Parigi e Berlino.
La riparazione delle collisioni basata su PIBT mantiene l'azione appresa ogni volta che è priva di collisioni ed evita le attese inutili e i deadlock della comune strategia di 'congelamento'.
Il semplice apprendimento per rinforzo con MAPPO ha reso meno dell'apprendimento per imitazione, e applicare MAPPO dopo l'imitazione non ha dato alcun guadagno misurabile.

Risultati principali

Su sei grandi mappe con 10.000 agenti, il throughput medio è salito del 137,7 % rispetto alla migliore baseline basata sull'apprendimento e del 16,0 % rispetto alla migliore baseline basata sulla ricerca.
Punteggio in stile competizione sulle grandi mappe: SILLM 0,99, SILLM (solo Dynamic Guidance) 0,94, WPPL 0,88, TrafficFlow 0,81, PIBT 0,61, Follower 0,52; RHCR e SCRIMP richiedevano minuti per passo e non è stato possibile valutarli a questa scala.
Tempo medio di pianificazione a singolo passo sulle grandi mappe: 0,349 s per SILLM contro 4,143 s per WPPL e 4,125 s per Follower.
Learnable PIBT ha battuto il PIBT semplice con ogni tipo di guida sulle grandi mappe (punteggio medio 0,80 contro 0,61 con Backward Dijkstra, 0,85 contro 0,75 con Static Guidance, 0,94 contro 0,81 con Dynamic Guidance).
Nel magazzino in scala, 10 robot reali hanno raggiunto i loro obiettivi senza collisioni; con 100 robot virtuali, Learnable PIBT ha dato il 50 % di throughput in più rispetto a PIBT.
Ogni iterazione di imitazione raccoglie 15 milioni di coppie azione-osservazione in 50 episodi, ripetuta 12 volte; l'addestramento richiede meno di 12 ore per mappa su un server con 4 GPU RTX 4090D.

Limiti

Gli autori affermano che i limiti hardware e software hanno ristretto la validazione fisica a 10 robot reali più 100 robot virtuali in un mini-magazzino, e la prova con robot reali è riportata in modo qualitativo.
Il pianificatore presuppone che la posizione di ogni agente sia perfettamente nota; i robot reali hanno avuto bisogno di un sistema di motion capture OptiTrack per la localizzazione e di un Action Dependency Graph per assorbire gli errori di esecuzione.
Le euristiche di guida sono progettate a mano, la migliore dipende dall'istanza e va scelta empiricamente, e i loro iperparametri influiscono sulle prestazioni.
L'addestramento con 10.000 agenti è stato evitato per le richieste di memoria; le policy sono addestrate con 600 agenti su mappe ridotte e valutate sulle grandi mappe.
L'apprendimento per rinforzo non ha aiutato nella forma testata; gli autori lasciano a lavori futuri una migliore assegnazione della ricompensa di squadra.

Impatto sul settore

L'articolo ha vinto l'IEEE ICRA 2025 Best Paper Award on Multi-Robot Systems e l'IEEE ICRA 2025 Best Student Paper Award, e ha 35 citazioni. L'articolo afferma che il codice sarebbe stato rilasciato dopo l'accettazione, e la pagina ufficiale del progetto rimanda al repository del codice.

Abstract

Il Lifelong Multi-Agent Path Finding (LMAPF) è una variante del MAPF in cui agli agenti vengono assegnati di continuo nuovi obiettivi, il che richiede frequenti ripianificazioni per adattarsi a questi cambiamenti dinamici. Di recente, questo campo ha adottato metodi basati sull'apprendimento, che generano in modo reattivo azioni a singolo passo a partire da osservazioni locali individuali. Tuttavia, per questi metodi è ancora difficile eguagliare le prestazioni dei migliori algoritmi basati sulla ricerca, soprattutto in scenari su larga scala. Questo lavoro propone un risolutore LMAPF basato sull'apprendimento per imitazione che introduce un nuovo modulo di comunicazione e tecniche sistematiche di risoluzione delle collisioni a singolo passo e di guida globale. Il risolutore che proponiamo, Scalable Imitation Learning for LMAPF (SILLM), eredita la rapidità di ragionamento dei metodi basati sull'apprendimento e l'elevata qualità delle soluzioni dei metodi basati sulla ricerca con l'aiuto delle GPU moderne. Su sei mappe su larga scala con fino a 10.000 agenti e strutture di ostacoli diverse, SILLM supera le migliori baseline basate sull'apprendimento e sulla ricerca, con miglioramenti medi del throughput rispettivamente del 137,7 % e del 16,0 %. Inoltre, SILLM batte anche la soluzione vincitrice della League of Robot Runners 2023, una competizione internazionale di LMAPF sponsorizzata da Amazon Robotics. Infine, abbiamo validato SILLM con 10 robot reali e 100 robot virtuali in un magazzino in scala.

Link

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
Codice: https://github.com/DiligentPanda/Scalable-Imitation-Learning-for-LMAPF
Pagina del progetto: https://diligentpanda.github.io/SILLM/