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

Licenças

Acesso aberto
Artigo: CC BY 4.0

Tudo o que segue se baseia no artigo completo sob a licença CC BY 4.0; sua figura é mostrada com crédito aos autores.

Em resumo

O SILLM imita um forte solucionador baseado em busca, acrescenta comunicação espacial, orientação de tráfego e reparo de colisões com PIBT, e planeja para 10.000 agentes em menos de 1 s por passo com a maior vazão.

Por que importa

Armazéns automatizados já operam milhares de robôs (o artigo cita mais de 4.000 nos centros de distribuição da Amazon em 2022), então um planejador que mantém alta vazão nessa escala com planejamento abaixo de um segundo por passo é diretamente relevante para o controle de frotas. Os resultados mostram que uma política aprendida, combinada com tratamento de colisões no estilo da busca e orientação sensível ao tráfego, pode superar os solucionadores escaláveis baseados em busca mais fortes, e não apenas os ótimos lentos.

Problema

O lifelong multi-agent path finding (LMAPF) dá a cada agente um novo objetivo assim que ele alcança um, então caminhos sem colisão precisam ser replanejados continuamente enquanto se maximiza a vazão (objetivos alcançados por passo de tempo). Solucionadores baseados em aprendizado reagem rapidamente a partir de observações locais, mas a maioria só foi testada com dezenas a centenas de agentes e não consegue superar solucionadores de busca subótimos e escaláveis como o PIBT. O artigo busca superar tanto os solucionadores baseados em aprendizado quanto os baseados em busca na escala de 10.000 agentes.

Solução proposta

O SILLM é uma política convolucional compartilhada por todos os agentes sobre um campo de visão de 11×11, com um módulo Spatially Sensitive Communication que insere o vetor de características de cada vizinho em sua posição relativa exata na grade. As observações codificam um de três mapas de orientação heurísticos (Backward Dijkstra, uma Static Guidance de rodovias em grade cruzada ou uma Dynamic Guidance baseada no TrafficFlow), e um passo CS-PIBT simplificado mantém a ação aprendida quando ela é livre de colisões e a repara com PIBT quando não é. A política é treinada por imitação iterativa do Windowed MAPF-LNS, o núcleo do WPPL, vencedor da League of Robot Runners de 2023, em mapas reduzidos com 600 agentes.

Principais ideias

Colocar as características dos vizinhos em suas posições relativas exatas (comunicação espacialmente sensível) superou a comunicação baseada em atenção e a ausência de comunicação na ablação, indicando que o raciocínio espacial preciso é importante para o LMAPF.
Imitar um solucionador anytime e de grande escala (Windowed MAPF-LNS) evita as instâncias de treinamento pequenas (8–10 agentes) que limitavam aprendizes por imitação anteriores, como PRIMAL2, SCRIMP e MAGAT.
A melhor orientação depende do mapa: Static Guidance se adequou aos mapas de triagem em grade cruzada e de armazém, Backward Dijkstra aos mapas aleatórios, e Dynamic Guidance teve o melhor desempenho nos mapas urbanos de Paris e Berlim.
O reparo de colisões baseado em PIBT mantém a ação aprendida sempre que ela é livre de colisões e evita as esperas desnecessárias e os deadlocks da estratégia comum de 'congelar'.
O aprendizado por reforço simples com MAPPO teve desempenho inferior ao aprendizado por imitação, e aplicar MAPPO após a imitação não trouxe ganho mensurável.

Principais resultados

Em seis mapas grandes com 10.000 agentes, a vazão média subiu 137,7 % em relação à melhor referência baseada em aprendizado e 16,0 % em relação à melhor referência baseada em busca.
Pontuação no estilo da competição em mapas grandes: SILLM 0,99, SILLM (apenas Dynamic Guidance) 0,94, WPPL 0,88, TrafficFlow 0,81, PIBT 0,61, Follower 0,52; RHCR e SCRIMP levavam minutos por passo e não puderam ser avaliados nessa escala.
Tempo médio de planejamento de um único passo em mapas grandes: 0,349 s para o SILLM contra 4,143 s para o WPPL e 4,125 s para o Follower.
O Learnable PIBT superou o PIBT simples com todos os tipos de orientação em mapas grandes (pontuação média de 0,80 contra 0,61 com Backward Dijkstra, 0,85 contra 0,75 com Static Guidance, 0,94 contra 0,81 com Dynamic Guidance).
Na maquete de armazém, 10 robôs reais alcançaram seus objetivos sem colisões; com 100 robôs virtuais, o Learnable PIBT deu 50 % mais vazão que o PIBT.
Cada iteração de imitação coleta 15 milhões de pares ação-observação em 50 episódios, repetida 12 vezes; o treinamento leva menos de 12 horas por mapa em um servidor com 4 GPUs RTX 4090D.

Limitações

Os autores afirmam que limitações de hardware e software restringiram a validação física a 10 robôs reais mais 100 robôs virtuais em um mini-armazém, e a execução com robôs reais é relatada de forma qualitativa.
O planejador assume que a posição de cada agente é perfeitamente conhecida; os robôs reais precisaram de um sistema de captura de movimento OptiTrack para localização e de um Action Dependency Graph para absorver erros de execução.
As heurísticas de orientação são projetadas à mão, a melhor depende da instância e precisa ser escolhida empiricamente, e seus hiperparâmetros afetam o desempenho.
O treinamento com 10.000 agentes foi evitado por causa da demanda de memória; as políticas são treinadas com 600 agentes em mapas reduzidos e avaliadas nos mapas grandes.
O aprendizado por reforço não ajudou na forma testada; os autores deixam uma melhor atribuição da recompensa de equipe para trabalhos futuros.

Impacto na área

O artigo ganhou o IEEE ICRA 2025 Best Paper Award on Multi-Robot Systems e o IEEE ICRA 2025 Best Student Paper Award, e tem 35 citações. O artigo afirma que o código seria disponibilizado após a aceitação, e a página oficial do projeto aponta para o repositório de código.

Resumo

Lifelong Multi-Agent Path Finding (LMAPF) é uma variante do MAPF em que os agentes recebem continuamente novos objetivos, o que exige replanejamento frequente para acomodar essas mudanças dinâmicas. Recentemente, essa área adotou métodos baseados em aprendizado, que geram de forma reativa ações de um único passo a partir de observações locais individuais. No entanto, ainda é difícil para eles igualar o desempenho dos melhores algoritmos baseados em busca, especialmente em cenários de grande escala. Este trabalho propõe um solucionador de LMAPF baseado em aprendizado por imitação que introduz um novo módulo de comunicação e técnicas sistemáticas de resolução de colisões de um único passo e de orientação global. Nosso solucionador proposto, Scalable Imitation Learning for LMAPF (SILLM), herda a rapidez de raciocínio dos métodos baseados em aprendizado e a alta qualidade de solução dos métodos baseados em busca com a ajuda de GPUs modernas. Em seis mapas de grande escala com até 10.000 agentes e estruturas de obstáculos variadas, o SILLM supera as melhores referências baseadas em aprendizado e em busca, com ganhos médios de vazão de 137,7 % e 16,0 %, respectivamente. Além disso, o SILLM também supera a solução vencedora da League of Robot Runners de 2023, uma competição internacional de LMAPF patrocinada pela Amazon Robotics. Por fim, validamos o SILLM com 10 robôs reais e 100 robôs virtuais em uma maquete de armazém.

Open Source Robotics