🤖 AI

Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding

Este artigo apresenta o LC-MAPF, um modelo pré-treinado generalizável que aprimora a busca de caminhos descentralizada para múltiplos agentes ao incorporar um módulo de comunicação multi-round escalável e aprendível para compartilhamento eficiente de características, superando solucionadores baseados em aprendizado existentes em diversos cenários sem comprometer a escalabilidade.

Autores originais: Valeriy Vyaltsev, Alsu Sagirova, Anton Andreychuk, Yuri Kuratov, Konstantin Yakovlev, Aleksandr Panov, Alexey Skrynnik

Publicado 2026-05-11

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Valeriy Vyaltsev, Alsu Sagirova, Anton Andreychuk, Yuri Kuratov, Konstantin Yakovlev, Aleksandr Panov, Alexey Skrynnik

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um armazém enorme e movimentado, repleto de centenas de robôs idênticos. Sua tarefa é simples: pegar um pacote em um ponto e deixá-lo em outro. Mas eis o problema: todos precisam se mover ao mesmo tempo, e se dois robôs colidirem, toda a operação entra em colapso.

Este é o problema da Busca de Caminhos para Múltiplos Agentes (MAPF). É como tentar fazer mil formigas atravessarem uma calçada lotada sem pisar umas nas outras, mas todas têm destinos diferentes.

O Problema dos Robôs "Silenciosos"

No passado, pesquisadores tentaram ensinar esses robôs usando Aprendizado por Imitação. Pense nisso como mostrar a um robô um vídeo de um especialista perfeito resolvendo o labirinto e dizer: "Faça exatamente o que o especialista fez".

Um método recente, chamado MAPF-GPT, foi muito bom nisso. Ele aprendeu a partir de uma vasta biblioteca de vídeos de especialistas. No entanto, tinha uma falha grave: ensinou os robôs a permanecerem silenciosos. Os robôs aprenderam a se mover bem, mas não conversavam entre si. Eram como um coral cantando perfeitamente afinado, mas nunca olhando uns para os outros para ajustar o tempo. Se a situação ficasse muito lotada, eles não conseguiam coordenar-se para resolver um engarrafamento porque apenas adivinhavam o que fazer com base no que viam sozinhos.

Outros métodos tentaram corrigir isso permitindo que os robôs conversassem, mas suas conversas eram frequentemente superficiais. Podiam gritar "Estou aqui!" ou "Estou indo para a esquerda!", mas não realmente negociavam ou planejavam juntos. Era como um grupo de pessoas tentando resolver um quebra-cabeça sendo permitidas a dizer apenas uma palavra.

A Solução: LC-MAPF (A Abordagem "Mesa Redonda")

Os autores deste artigo introduziram um novo sistema chamado LC-MAPF. Em vez de apenas observar um especialista, ensinaram os robôs a realizar uma conversa de múltiplas rodadas antes de fazer um movimento.

Veja como funciona, usando uma analogia simples:

O Cenário: Imagine os robôs sentados ao redor de uma mesa. Eles só podem ver as pessoas sentadas ao lado (seus vizinhos locais).
Rodada 1: Todos sussurram seu plano atual para seus vizinhos. "Vou me mover para frente."
Rodada 2: Agora, todos ouvem seus vizinhos. Se um vizinho diz "Também vou para frente", você percebe: "Ah, vamos colidir!". Então, sussurra um novo plano: "Ok, vou esperar um segundo."
Rodadas 3 e 4: Eles continuam passando esses sussurros de um lado para o outro. A cada rodada, refinam seu plano, resolvem conflitos e concordam com um fluxo suave.
O Movimento: Após quatro rodadas de conversa, todos se movem ao mesmo tempo, perfeitamente coordenados.

A mágica do LC-MAPF é que os robôs aprenderam a conversar por conta própria. Os pesquisadores não os programaram com uma linguagem específica nem lhes disseram o que dizer. Apenas deram a eles o objetivo (não colidir, chegar ao destino) e deixaram a IA descobrir que "conversar" era a melhor maneira de alcançá-lo. As mensagens que trocam não são palavras humanas; são sinais matemáticos que carregam informação suficiente para resolver o quebra-cabeça.

Por Que Isso é Importante

O artigo destaca três grandes vitórias:

É Mais Inteligente: Nos testes, o LC-MAPF resolveu mais cenários de labirinto com sucesso do que qualquer outro método baseado em aprendizado, incluindo o famoso MAPF-GPT. Lidou melhor com salas lotadas porque podia realmente "negociar" com seus vizinhos.
Escala Bem: Geralmente, quando você adiciona mais robôs a um sistema de conversação, o sistema fica lento e falha porque há muita conversa. O LC-MAPF é diferente. Mesmo com milhares de robôs, permanece rápido. É como uma multidão bem organizada onde todos só falam com as pessoas logo ao lado, em vez de gritar através de todo o estádio.
Funciona no Mundo Real: Os pesquisadores não executaram isso apenas em um computador. Eles construíram um labirinto físico com robôs reais (baseados em um pequeno kit de IA chamado Jetbot). Colocaram o cérebro do LC-MAPF nos robôs reais, e os robôs navegaram com sucesso pelo labirinto físico sem colidir, provando que os "sussurros" funcionam na vida real.

A Conclusão

Este artigo apresenta uma nova maneira de ensinar robôs a trabalhar juntos. Em vez de serem solistas silenciosos ou conversadores superficiais, esses robôs agora são conversadores colaborativos. Eles realizam reuniões breves e eficientes com seus vizinhos para concordar com um plano, permitindo que se movam através de ambientes complexos e lotados de forma suave e segura. O sistema é rápido, escalável e já foi comprovado que funciona com hardware real.

Resumo Técnico: Aprendizado para Comunicação Local em Busca de Caminhos para Múltiplos Agentes em Grande Escala

Declaração do Problema

A Busca de Caminhos para Múltiplos Agentes (MAPF) é uma abstração fundamental para coordenar múltiplos agentes homogêneos em ambientes compartilhados, como armazéns automatizados ou frotas de veículos autônomos. O objetivo é calcular planos individuais para $n$ agentes moverem-se de vértices de início a vértices de destino em um grafo sem colisões (conflitos de vértice ou de aresta). Embora existam solucionadores ótimos para MAPF, o problema é NP-difícil, e a escalabilidade degrada-se rapidamente à medida que o número de agentes aumenta.

Abordagens descentralizadas, nas quais os agentes tomam decisões com base em observações locais, oferecem um caminho para a escalabilidade, mas frequentemente lutam com a qualidade da coordenação. Métodos recentes baseados em aprendizado, como o MAPF-GPT, alcançaram resultados sólidos usando aprendizado por imitação (IL) em grandes conjuntos de dados. No entanto, esses modelos geralmente carecem de comunicação explícita entre agentes, confiando apenas em observações locais para inferir comportamento colaborativo. Métodos descentralizados baseados em comunicação existentes frequentemente limitam a interação a trocas de uma única rodada de observações locais, o que pode ser insuficiente para resolver conflitos complexos em ambientes densos.

Metodologia: LC-MAPF

Os autores propõem o LC-MAPF (Comunicação Local para Busca de Caminhos para Múltiplos Agentes), um framework descentralizado e baseado em aprendizado que introduz um módulo de comunicação multi-rodada aprendível para aprimorar a coordenação entre agentes.

Arquitetura

O modelo é construído sobre uma arquitetura baseada em Transformer com aproximadamente 3 milhões de parâmetros. O fluxo de trabalho para cada agente $u$ no passo de tempo $t$ envolve:

Codificação da Observação: Os agentes recebem uma observação local estruturada $o^t_u$ , tokenizada em uma sequência incluindo matrizes de custo até o objetivo, recursos próprios (posição, objetivo, ação gananciosa, histórico) e recursos dos $k$ vizinhos mais próximos. Isso é incorporado em uma sequência $X_{0,u}$ .
Compressão do Estado Latente: Para garantir escalabilidade da comunicação independente do tamanho da observação, um codificador Transformer processa a entrada, e um "gargalo latente" (inspirado na arquitetura Perceiver) comprime os tokens codificados em um estado latente compacto $z_u \in \mathbb{R}^{T_{latent} \times d_{latent}}$ .
Comunicação Iterativa: Os agentes realizam $R_{comm}$ $R_{co mm}$ rodadas de comunicação local (padrão $R_{comm}=4$ $R_{co mm} = 4$ ).
- Em cada rodada $r$ , um agente recebe mensagens de seus vizinhos (e de si mesmo).
- Um decodificador funde o estado latente do agente $z_u$ com as mensagens de vizinhos recebidas $C^r_u$ .
- Uma cabeça de mensagem gera um vetor de mensagem atualizado $m^r_u$ a ser enviado na próxima rodada.
- Crucialmente, as mensagens não são supervisionadas. A rede aprende a comunicar quais informações são necessárias para minimizar a perda final de ação por meio de retropropagação, permitindo que estratégias de comunicação surjam naturalmente.
Previsão de Ação: Após a rodada final de comunicação, uma cabeça de previsão emite logits de ação, que são convertidos em uma distribuição de probabilidade para seleção de ação.

Treinamento

O LC-MAPF é treinado via Aprendizado por Imitação usando demonstrações de especialistas. O conjunto de dados de treinamento consiste em aproximadamente 750 milhões de pares observação-ação derivados de um solucionador centralizado (LaCAM*) em diversos tipos de mapas (Labirintos, Aleatórios, Casa). O objetivo é minimizar a perda de entropia cruzada entre as ações previstas e as ações do especialista. Nenhuma supervisão explícita é fornecida para as mensagens de comunicação; o modelo aprende a comunicar apenas para melhorar a qualidade da ação coletiva.

Principais Contribuições

Framework de Comunicação Inovador: A introdução do LC-MAPF, um framework que permite aos agentes comunicar-se usando apenas demonstrações de ações de especialistas, sem exigir rótulos de comunicação explícitos ou supervisão.
Desempenho de Estado da Arte: Um modelo Transformer de 3 milhões de parâmetros que estabelece um novo estado da arte entre solucionadores descentralizados aprendíveis para MAPF, superando abordagens existentes de IL e Aprendizado por Reforço (RL) (incluindo MAPF-GPT, SCRIMP, DCC e variantes MAGAT) em diversas métricas e topologias de mapas.
Escalabilidade com Comunicação: A demonstração de que o mecanismo de comunicação multi-rodada proposto mantém escalabilidade linear à medida que o número de agentes cresce, abordando um gargalo comum em solucionadores baseados em comunicação.
Análise de Ablação e Robustez: Estudos extensivos mostrando que:
- A comunicação multi-rodada (especificamente 4 rodadas) é crítica para altas taxas de sucesso.
- O sistema é robusto a falhas de mensagem (até 50% de ruído) em populações menores de agentes.
- Limitar o tamanho do bairro de comunicação degrada significativamente o desempenho em cenários densos.

Resultados Experimentais

Os experimentos foram conduzidos no benchmark POGEMA, cobrindo tipos de mapas Aleatórios, Labirintos, Armazéns e Cidades.

Taxa de Sucesso: O LC-MAPF alcançou taxas de sucesso iguais ou superiores a todas as linhas de base, incluindo o MAPF-GPT de 85 milhões de parâmetros, em todos os tipos de mapas e contagens de agentes (até 256 agentes em testes padrão e até 5.000 agentes em avaliações em grande escala).
Qualidade da Solução: Em termos de Soma de Custos (SoC) relativa ao planejador ótimo centralizado (LaCAM*), o LC-MAPF consistentemente alcançou as melhores ou quase melhores razões.
Escalabilidade: Em testes em grande escala com até 5.000 agentes em mapas de 256x256, o LC-MAPF manteve escalabilidade linear, com tempos de cálculo aumentando de forma previsível (por exemplo, ~0,12s/passo para 1.000 agentes até ~0,65s/passo para 5.000 agentes).
Implantação no Mundo Real: Os autores implantaram com sucesso o LC-MAPF em uma plataforma física de múltiplos robôs (JetBots modificados) em um ambiente de labirinto modular. Ao conectar o planejamento discreto com controle contínuo (usando sincronização de rotação/espera), os agentes coordenaram-se com sucesso para alcançar os objetivos sem colisões, validando a aplicabilidade prática do método.

Significado e Alegações

O artigo afirma que o LC-MAPF representa um avanço significativo na coordenação descentralizada de múltiplos agentes, demonstrando que comunicação local iterativa e eficaz pode ser aprendida implicitamente a partir de trajetórias de especialistas. Diferentemente de métodos anteriores que ignoram a comunicação ou dependem de trocas supervisionadas de uma única rodada, o LC-MAPF utiliza um mecanismo de comunicação multi-rodada e não supervisionado que permite aos agentes negociar e resolver conflitos dinamicamente.

Os autores enfatizam que essa abordagem equilibra com sucesso qualidade da solução e escalabilidade, superando o compromisso típico onde métodos baseados em comunicação sofrem com gargalos computacionais. Os resultados sugerem que o LC-MAPF serve como um modelo pré-treinado generalizável capaz de lidar com ambientes diversos e não vistos e populações de agentes em grande escala, oferecendo uma solução robusta para aplicações robóticas do mundo real, como logística e busca e resgate.