🤖 AI

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

Este artículo introduce LC-MAPF, un modelo preentrenado generalizable que mejora la búsqueda de rutas descentralizada para múltiples agentes mediante la incorporación de un módulo de comunicación multi-ronda escalable y aprendible para el intercambio eficiente de características, el cual supera a los solucionadores basados en aprendizaje existentes en diversos escenarios sin comprometer la escalabilidad.

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

Publicado 2026-05-11

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

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

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina un almacén masivo y bullicioso lleno de cientos de robots idénticos. Su trabajo es simple: recoger un paquete en un punto y dejarlo en otro. Pero aquí está el truco: todos deben moverse al mismo tiempo, y si dos robots chocan entre sí, toda la operación se detiene por completo.

Este es el problema de la Búsqueda de Trayectorias Multiagente (MAPF). Es como intentar que mil hormigas crucen una acera abarrotada sin pisarse entre sí, pero todas tienen destinos diferentes.

El problema de los robots "silenciosos"

En el pasado, los investigadores intentaron enseñar a estos robots mediante Aprendizaje por Imitación. Piensa en esto como mostrarle a un robot un video de un experto perfecto resolviendo el laberinto y decirle: "Haz exactamente lo que hizo el experto".

Un método reciente, llamado MAPF-GPT, fue muy bueno en esto. Aprendió de una biblioteca masiva de videos de expertos. Sin embargo, tenía un defecto mayor: enseñó a los robots a estar en silencio. Los robots aprendieron a moverse bien, pero no hablaban entre sí. Eran como un coro que canta perfectamente afinado pero nunca se mira entre sí para ajustar su ritmo. Si la situación se volvía demasiado abarrotada, no podían coordinarse para resolver un atasco porque simplemente adivinaban qué hacer basándose en lo que veían solos.

Otros métodos intentaron solucionar esto permitiendo que los robots hablaran, pero sus conversaciones a menudo eran superficiales. Podían gritar: "¡Estoy aquí!" o "¡Voy a la izquierda!", pero no realmente negociaban ni planificaban juntos. Era como un grupo de personas intentando resolver un rompecabezas mientras solo se les permitía decir una palabra.

La solución: LC-MAPF (El enfoque de "Mesa Redonda")

Los autores de este artículo introdujeron un nuevo sistema llamado LC-MAPF. En lugar de solo observar a un experto, enseñaron a los robots a mantener una conversación de múltiples rondas antes de hacer un movimiento.

Así es como funciona, usando una analogía simple:

La configuración: Imagina que los robots están sentados alrededor de una mesa. Solo pueden ver a las personas sentadas a su lado (sus vecinos locales).
Ronda 1: Todos susurran su plan actual a sus vecinos. "Voy a moverme hacia adelante".
Ronda 2: Ahora, todos escuchan a sus vecinos. Si un vecino dice: "Yo también voy hacia adelante", te das cuenta: "¡Oh, vamos a chocar!". Así que susurras un nuevo plan: "Vale, esperaré un segundo".
Rondas 3 y 4: Siguen pasando estos susurros de ida y vuelta. Con cada ronda, refinan su plan, resuelven conflictos y acuerdan un flujo suave.
El movimiento: Después de cuatro rondas de charla, todos se mueven a la vez, perfectamente coordinados.

La magia de LC-MAPF es que los robots aprendieron a hablar por sí mismos. Los investigadores no los programaron con un lenguaje específico ni les dijeron qué decir. Solo les dieron el objetivo (no chocar, llegar al destino) y dejaron que la IA descubriera que "hablar" era la mejor manera de lograrlo. Los mensajes que intercambian no son palabras humanas; son señales matemáticas que llevan justo la información necesaria para resolver el rompecabezas.

Por qué esto es un gran logro

El artículo destaca tres victorias principales:

Es más inteligente: En las pruebas, LC-MAPF resolvió con éxito más escenarios de laberinto que cualquier otro método basado en aprendizaje, incluido el famoso MAPF-GPT. Manejó mejor las habitaciones abarrotadas porque realmente podía "negociar" con sus vecinos.
Es escalable: Por lo general, cuando agregas más robots a un sistema de conversación, el sistema se vuelve lento y se cae porque hay demasiada charla. LC-MAPF es diferente. Incluso con miles de robots, se mantiene rápido. Es como una multitud bien organizada donde todos solo hablan con las personas justo a su lado, en lugar de gritar a través de todo el estadio.
Funciona en el mundo real: Los investigadores no solo ejecutaron esto en una computadora. Construyeron un laberinto físico con robots reales (basados en un pequeño kit de IA llamado Jetbot). Pusieron el cerebro de LC-MAPF en los robots reales, y los robots navegaron con éxito el laberinto físico sin chocar, demostrando que los "susurros" funcionan en la vida real.

La conclusión

Este artículo presenta una nueva forma de enseñar a los robots a trabajar juntos. En lugar de ser solistas silenciosos o habladores superficiales, estos robots ahora son conversadores colaborativos. Mantienen reuniones breves y eficientes con sus vecinos para acordar un plan, lo que les permite moverse a través de entornos complejos y abarrotados de manera fluida y segura. El sistema es rápido, escalable y ya ha demostrado funcionar con hardware real.

Resumen Técnico: Aprender a Comunicarse Localmente para la Búsqueda de Caminos Multiagente a Gran Escala

Enunciado del Problema

La Búsqueda de Caminos Multiagente (MAPF) es una abstracción fundamental para coordinar múltiples agentes homogéneos en entornos compartidos, como almacenes automatizados o flotas de vehículos autónomos. El objetivo es calcular planes individuales para $n$ agentes que se muevan desde vértices de inicio hasta vértices de meta en un grafo sin colisiones (conflictos de vértice o arista). Aunque existen solucionadores óptimos para MAPF, el problema es NP-duro y la escalabilidad se degrada rápidamente a medida que aumenta el número de agentes.

Los enfoques descentralizados, donde los agentes toman decisiones basadas en observaciones locales, ofrecen una vía hacia la escalabilidad, pero a menudo luchan con la calidad de la coordinación. Los métodos recientes basados en aprendizaje, como MAPF-GPT, han logrado resultados sólidos utilizando aprendizaje por imitación (IL) en grandes conjuntos de datos. Sin embargo, estos modelos carecen típicamente de comunicación interagente explícita, confiando únicamente en observaciones locales para inferir comportamientos colaborativos. Los métodos descentralizados basados en comunicación existentes a menudo limitan la interacción a intercambios de una sola ronda de observaciones locales, lo cual puede ser insuficiente para resolver conflictos complejos en entornos densos.

Metodología: LC-MAPF

Los autores proponen LC-MAPF (Comunicación Local para Búsqueda de Caminos Multiagente), un marco descentralizado basado en aprendizaje que introduce un módulo de comunicación multi-ronda aprendible para mejorar la coordinación entre agentes.

Arquitectura

El modelo se basa en una arquitectura Transformer con aproximadamente 3 millones de parámetros. El flujo de trabajo para cada agente $u$ en el paso de tiempo $t$ implica:

Codificación de Observación: Los agentes reciben una observación local estructurada $o^t_u$ , tokenizada en una secuencia que incluye matrices de costo hasta la meta, características propias (posición, meta, acción codiciosa, historial) y características de los $k$ vecinos más cercanos. Esto se incrusta en una secuencia $X_{0,u}$ .
Compresión del Estado Latente: Para garantizar una escalabilidad de la comunicación independiente del tamaño de la observación, un codificador Transformer procesa la entrada y un "cuello de botella latente" (inspirado en la arquitectura Perceiver) comprime los tokens codificados en un estado latente compacto $z_u \in \mathbb{R}^{T_{latent} \times d_{latent}}$ .
Comunicación Iterativa: Los agentes realizan $R_{comm}$ $R_{co mm}$ rondas de comunicación local (valor predeterminado $R_{comm}=4$ $R_{co mm} = 4$ ).
- En cada ronda $r$ , un agente recibe mensajes de sus vecinos (y de sí mismo).
- Un decodificador fusiona el estado latente del agente $z_u$ con los mensajes de vecinos recibidos $C^r_u$ .
- Una cabeza de mensaje genera un vector de mensaje actualizado $m^r_u$ para ser enviado en la siguiente ronda.
- Crucialmente, los mensajes no están supervisados. La red aprende a comunicar qué información es necesaria para minimizar la pérdida de acción final mediante retropropagación, permitiendo que las estrategias de comunicación surjan naturalmente.
Predicción de Acción: Después de la ronda final de comunicación, una cabeza de predicción emite logit de acción, que se convierten en una distribución de probabilidad para la selección de acciones.

Entrenamiento

LC-MAPF se entrena mediante Aprendizaje por Imitación utilizando demostraciones de expertos. El conjunto de datos de entrenamiento consiste en aproximadamente 750 millones de pares observación-acción derivados de un solucionador centralizado (LaCAM*) a través de diversos tipos de mapas (Laberintos, Aleatorios, Casas). El objetivo es minimizar la pérdida de entropía cruzada entre las acciones predichas y las acciones del experto. No se proporciona supervisión explícita para los mensajes de comunicación; el modelo aprende a comunicarse únicamente para mejorar la calidad de la acción colectiva.

Contribuciones Clave

Marco de Comunicación Novel: La introducción de LC-MAPF, un marco que permite a los agentes comunicarse utilizando solo demostraciones de acciones de expertos, sin requerir etiquetas de comunicación explícitas ni supervisión.
Rendimiento de Vanguardia: Un modelo Transformer de 3 millones de parámetros que establece un nuevo estado del arte entre los solucionadores descentralizados de MAPF aprendibles, superando a los enfoques existentes de IL y Aprendizaje por Refuerzo (RL) (incluidas las variantes de MAPF-GPT, SCRIMP, DCC y MAGAT) en diversas métricas y topologías de mapas.
Escalabilidad con Comunicación: La demostración de que el mecanismo de comunicación multi-ronda propuesto mantiene una escalabilidad lineal a medida que crece el número de agentes, abordando un cuello de botella común en los solucionadores basados en comunicación.
Análisis de Ablación y Robustez: Estudios extensos que muestran que:
- La comunicación multi-ronda (específicamente 4 rondas) es crítica para altas tasas de éxito.
- El sistema es robusto ante fallos de mensajes (hasta un 50% de ruido) en poblaciones de agentes más pequeñas.
- Limitar el tamaño del vecindario de comunicación degrada significativamente el rendimiento en escenarios densos.

Resultados Experimentales

Los experimentos se realizaron en la prueba de referencia POGEMA, que cubre tipos de mapas Aleatorios, Laberintos, Almacenes y Ciudades.

Tasa de Éxito: LC-MAPF logró tasas de éxito iguales o superiores a todas las líneas base, incluido MAPF-GPT de 85 millones de parámetros, en todos los tipos de mapas y conteos de agentes (hasta 256 agentes en pruebas estándar y hasta 5,000 agentes en evaluaciones a gran escala).
Calidad de la Solución: En términos de Suma de Costos (SoC) relativa al planificador óptimo centralizado (LaCAM*), LC-MAPF logró consistentemente las mejores o casi mejores relaciones.
Escalabilidad: En pruebas a gran escala con hasta 5,000 agentes en mapas de 256x256, LC-MAPF mantuvo una escalabilidad lineal, con tiempos de cálculo aumentando predeciblemente (por ejemplo, ~0.12s/paso para 1,000 agentes a ~0.65s/paso para 5,000 agentes).
Despliegue en el Mundo Real: Los autores desplegaron con éxito LC-MAPF en una plataforma física de múltiples robots (JetBots modificados) en un entorno de laberinto modular. Al unir la planificación discreta con el control continuo (utilizando sincronización de rotación/espera), los agentes coordinaron con éxito para alcanzar las metas sin colisiones, validando la aplicabilidad práctica del método.

Significado y Afirmaciones

El artículo afirma que LC-MAPF representa un avance significativo en la coordinación descentralizada multiagente al demostrar que una comunicación local iterativa efectiva puede aprenderse implícitamente a partir de trayectorias de expertos. A diferencia de los métodos anteriores que ignoran la comunicación o dependen de intercambios supervisados de una sola ronda, LC-MAPF utiliza un mecanismo de comunicación multi-ronda no supervisado que permite a los agentes negociar y resolver conflictos dinámicamente.

Los autores enfatizan que este enfoque equilibra con éxito la calidad de la solución y la escalabilidad, superando el compromiso típico donde los métodos basados en comunicación sufren cuellos de botella computacionales. Los resultados sugieren que LC-MAPF sirve como un modelo preentrenado generalizable capaz de manejar entornos diversos e inéditos y poblaciones de agentes a gran escala, ofreciendo una solución robusta para aplicaciones robóticas del mundo real como logística y búsqueda y rescate.