🤖 AI

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

This paper introduces LC-MAPF, a generalizable pre-trained model that enhances decentralized multi-agent pathfinding by incorporating a scalable, learnable multi-round communication module for efficient feature sharing, which outperforms existing learning-based solvers across diverse scenarios without compromising scalability.

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

Published 2026-05-11

📖 4 min read☕ Coffee break read

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive, busy warehouse filled with hundreds of identical robots. Their job is simple: pick up a package at one spot and drop it off at another. But here's the catch: they all have to move at the same time, and if two robots bump into each other, the whole operation grinds to a halt.

This is the problem of Multi-Agent Pathfinding (MAPF). It's like trying to get a thousand ants to cross a crowded sidewalk without stepping on each other, but they all have different destinations.

The Problem with "Silent" Robots

In the past, researchers tried to teach these robots using Imitation Learning. Think of this as showing a robot a video of a perfect expert solving the maze and saying, "Do exactly what the expert did."

One recent method, called MAPF-GPT, was very good at this. It learned from a massive library of expert videos. However, it had a major flaw: it taught the robots to be silent. The robots learned to move well, but they didn't talk to each other. They were like a choir singing perfectly in tune but never looking at each other to adjust their timing. If the situation got too crowded, they couldn't coordinate to fix a jam because they were just guessing what to do based on what they saw alone.

Other methods tried to fix this by letting robots talk, but their conversations were often shallow. They might shout, "I'm here!" or "I'm going left!" but they didn't really negotiate or plan together. It was like a group of people trying to solve a puzzle while only allowed to say one word.

The Solution: LC-MAPF (The "Round-Table" Approach)

The authors of this paper introduced a new system called LC-MAPF. Instead of just watching an expert, they taught the robots to hold a multi-round conversation before making a move.

Here is how it works, using a simple analogy:

The Setup: Imagine the robots are sitting around a table. They can only see the people sitting next to them (their local neighbors).
Round 1: Everyone whispers their current plan to their neighbors. "I'm going to move forward."
Round 2: Now, everyone listens to their neighbors. If a neighbor says, "I'm going forward too," you realize, "Oh, we'll crash!" So, you whisper a new plan: "Okay, I'll wait one second."
Round 3 & 4: They keep passing these whispers back and forth. With every round, they refine their plan, resolving conflicts and agreeing on a smooth flow.
The Move: After four rounds of chatting, they all move at once, perfectly coordinated.

The magic of LC-MAPF is that the robots learned how to talk on their own. The researchers didn't program them with a specific language or tell them what to say. They just gave them the goal (don't crash, get to the destination) and let the AI figure out that "talking" was the best way to achieve it. The messages they exchange aren't human words; they are mathematical signals that carry just enough information to solve the puzzle.

Why This is a Big Deal

The paper highlights three main victories:

It's Smarter: In tests, LC-MAPF solved more maze scenarios successfully than any other learning-based method, including the famous MAPF-GPT. It handled crowded rooms better because it could actually "negotiate" with its neighbors.
It Scales: Usually, when you add more robots to a talking system, the system gets slow and crashes because there's too much chatter. LC-MAPF is different. Even with thousands of robots, it stays fast. It's like a well-organized crowd where everyone only talks to the people right next to them, rather than shouting across the whole stadium.
It Works in the Real World: The researchers didn't just run this on a computer. They built a physical maze with real robots (based on a small AI kit called Jetbot). They put the LC-MAPF brain into the real robots, and the robots successfully navigated the physical maze without crashing, proving the "whispers" work in real life.

The Bottom Line

This paper presents a new way to teach robots to work together. Instead of being silent soloists or shallow talkers, these robots are now collaborative conversationalists. They hold brief, efficient meetings with their neighbors to agree on a plan, allowing them to move through complex, crowded environments smoothly and safely. The system is fast, scalable, and has already been proven to work with actual hardware.

Technical Summary: Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding

Problem Statement

Multi-Agent Pathfinding (MAPF) is a fundamental abstraction for coordinating multiple homogeneous agents in shared environments, such as automated warehouses or autonomous vehicle fleets. The objective is to compute individual plans for $n$ agents to move from start vertices to goal vertices on a graph without collisions (vertex or edge conflicts). While optimal MAPF solvers exist, the problem is NP-hard, and scalability degrades rapidly as the number of agents increases.

Decentralized approaches, where agents make decisions based on local observations, offer a path to scalability but often struggle with coordination quality. Recent learning-based methods, such as MAPF-GPT, have achieved strong results using imitation learning (IL) on large datasets. However, these models typically lack explicit inter-agent communication, relying solely on local observations to infer collaborative behavior. Existing communication-based decentralized methods often limit interaction to single-round exchanges of local observations, which may be insufficient for resolving complex conflicts in dense environments.

Methodology: LC-MAPF

The authors propose LC-MAPF (Local Communication for Multi-agent Pathfinding), a decentralized, learning-based framework that introduces a learnable, multi-round communication module to enhance agent coordination.

Architecture

The model is built upon a Transformer-based architecture with approximately 3 million parameters. The workflow for each agent $u$ at time step $t$ involves:

Observation Encoding: Agents receive a structured local observation $o^t_u$ , tokenized into a sequence including cost-to-go matrices, self-features (position, goal, greedy action, history), and features of the $k$ closest neighbors. This is embedded into a sequence $X_{0,u}$ .
Latent State Compression: To ensure communication scalability independent of observation size, a Transformer encoder processes the input, and a "latent bottleneck" (inspired by the Perceiver architecture) compresses the encoded tokens into a compact latent state $z_u \in \mathbb{R}^{T_{latent} \times d_{latent}}$ .
Iterative Communication: Agents perform $R_{comm}$ $R_{co mm}$ rounds of local communication (default $R_{comm}=4$ $R_{co mm} = 4$ ).
- In each round $r$ , an agent receives messages from its neighbors (and itself).
- A decoder fuses the agent's latent state $z_u$ with the received neighbor messages $C^r_u$ .
- A message head generates an updated message vector $m^r_u$ to be sent in the next round.
- Crucially, messages are not supervised. The network learns to communicate what information is necessary to minimize the final action loss through backpropagation, allowing communication strategies to emerge naturally.
Action Prediction: After the final communication round, a prediction head outputs action logits, which are converted to a probability distribution for action selection.

Training

LC-MAPF is trained via Imitation Learning using expert demonstrations. The training dataset consists of approximately 750 million observation-action pairs derived from a centralized solver (LaCAM*) across diverse map types (Mazes, Random, House). The objective is to minimize the cross-entropy loss between the predicted actions and the expert actions. No explicit supervision is provided for the communication messages; the model learns to communicate solely to improve the collective action quality.

Key Contributions

Novel Communication Framework: The introduction of LC-MAPF, a framework enabling agents to communicate using only expert action demonstrations, without requiring explicit communication labels or supervision.
State-of-the-Art Performance: A 3-million-parameter Transformer model that sets a new state-of-the-art among learnable decentralized MAPF solvers, outperforming existing IL and Reinforcement Learning (RL) approaches (including MAPF-GPT, SCRIMP, DCC, and MAGAT variants) across diverse metrics and map topologies.
Scalability with Communication: The demonstration that the proposed multi-round communication mechanism maintains linear scalability as the number of agents grows, addressing a common bottleneck in communication-based solvers.
Ablation and Robustness Analysis: Extensive studies showing that:
- Multi-round communication (specifically 4 rounds) is critical for high success rates.
- The system is robust to message failures (up to 50% noise) in smaller agent populations.
- Limiting the communication neighborhood size significantly degrades performance in dense scenarios.

Experimental Results

Experiments were conducted on the POGEMA benchmark, covering Random, Mazes, Warehouse, and Cities map types.

Success Rate: LC-MAPF achieved success rates equal to or higher than all baselines, including the 85M-parameter MAPF-GPT, across all map types and agent counts (up to 256 agents in standard tests, and up to 5,000 agents in large-scale evaluations).
Solution Quality: In terms of Sum-of-Costs (SoC) relative to the centralized optimal planner (LaCAM*), LC-MAPF consistently achieved the best or near-best ratios.
Scalability: In large-scale tests with up to 5,000 agents on 256x256 maps, LC-MAPF maintained linear scalability, with computation times increasing predictably (e.g., ~0.12s/step for 1,000 agents to ~0.65s/step for 5,000 agents).
Real-World Deployment: The authors successfully deployed LC-MAPF on a physical multi-robot platform (modified JetBots) in a modular maze environment. By bridging discrete planning with continuous control (using rotation/wait synchronization), the agents successfully coordinated to reach goals without collisions, validating the method's practical applicability.

Significance and Claims

The paper claims that LC-MAPF represents a significant advancement in decentralized multi-agent coordination by demonstrating that effective, iterative local communication can be learned implicitly from expert trajectories. Unlike previous methods that either ignore communication or rely on single-round, supervised exchanges, LC-MAPF utilizes a multi-round, unsupervised communication mechanism that allows agents to negotiate and resolve conflicts dynamically.

The authors emphasize that this approach successfully balances solution quality and scalability, overcoming the typical trade-off where communication-based methods suffer from computational bottlenecks. The results suggest that LC-MAPF serves as a generalizable pre-trained model capable of handling diverse, unseen environments and large-scale agent populations, offering a robust solution for real-world robotic applications such as logistics and search-and-rescue.