Source-linked AI summary
Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding
Valeriy Vyaltsev, Alsu Sagirova, Anton Andreychuk, Oleg Bulichev, Yuri Kuratov, Konstantin Yakovlev, Aleksandr Panov, Alexey Skrynnik
TL;DR
MAPF requires scalable coordination among agents, but optimal solving is NP-hard and decentralized methods often lack rich communication. LC-MAPF adds multi-round local communication to expert-demonstration learning and outperforms learning-based solvers while preserving scalability.
Problem
MAPF needs efficient coordination despite NP-hard optimal solving and limited communication in existing decentralized learning methods.
Method
LC-MAPF is a transformer-based communication learning framework that uses expert demonstrations and multi-round communication among neighboring agents without explicit communication supervision.
Results
LC-MAPF outperforms state-of-the-art learning-based MAPF solvers across diverse scenarios while maintaining linear scalability with the number of agents.
Takeaways & Limitations
Multi-round local communication provides an effective and scalable approach for decentralized multi-agent pathfinding.
Takeaways & Limitations
Limited communication constrains performance because real-world bandwidth and communication costs, including battery usage, create a performance-cost trade-off.
Abstract
from arXiv · showhide
Multi-agent pathfinding (MAPF) is a widely used abstraction for multi-robot trajectory planning problems, where multiple homogeneous agents move simultaneously within a shared environment. Although solving MAPF optimally is NP-hard, scalable and efficient solvers are critical for real-world applications such as logistics and search-and-rescue. To this end, the research community has proposed various decentralized suboptimal MAPF solvers that leverage machine learning. Such methods frame MAPF (from a single agent perspective) as a Dec-POMDP where at each time step an agent has to decide an action based on the local observation and typically solve the problem via reinforcement learning or imitation learning. We follow the same approach but additionally introduce a learnable communication module tailored to enhance cooperation between agents via efficient feature sharing. We present the Local Communication for Multi-agent Pathfinding (LC-MAPF), a generalizable pre-trained model that applies multi-round communication between neighboring agents to exchange information and improve their coordination. Our experiments show that the introduced method outperforms the existing learning-based MAPF solvers, including IL and RL-based approaches, across diverse metrics in a diverse range of (unseen) test scenarios. Remarkably, the introduced communication mechanism does not compromise LC-MAPF's scalability, a common bottleneck for communication-based MAPF solvers.
Introduction
MAPF coordinates agents in shared environments, but optimal solving is NP-hard and scalable suboptimal methods can sacrifice solution quality. LC-MAPF addresses communication limitations in decentralized learning with multi-round local interaction while maintaining linear scalability.
- Introduction: MAPF models multiple agents moving synchronously in shared environments while seeking conflict-free plans.Agents move or wait at each timestep, and plans must avoid vertex and edge conflicts.
- Introduction: Optimal MAPF solving is NP-hard, whereas scalable suboptimal solvers may significantly degrade solution quality.This creates a central trade-off between computational efficiency and solution quality.
- Introduction: Decentralized MAPF lets agents select actions independently from local observations, with policies potentially learned or hybrid.This formulation avoids requiring each agent to access the full global state.
- Introduction: MAPF-GPT learns collaborative behavior without agent-to-agent communication, limiting explicit interaction during problem solving.Its training data comes from a centralized solver that provides no communication signals.
- Introduction: LC-MAPF introduces multi-round local communication to support negotiation, conflict resolution, and consistent joint plans.The framework uses expert demonstrations without explicit communication supervision.
- Introduction: LC-MAPF maintains linear scalability as the number of agents grows despite incorporating communication.The contribution specifically targets a common scalability concern for communication-based MAPF.
Related Work
Related work spans foundation models, communication-based MAPF, and classical MAPF solvers. Existing learning-based methods introduce communication in different forms, while LC-MAPF builds on the need for richer multi-agent interaction.
- Foundation models: Foundation models use large-scale datasets to support generalization, while their application to multi-agent systems remains relatively limited.MAPF-GPT is identified as a notable decentralized pathfinding example.
- Multi-agent pathfinding: MAPF research includes rule-based, reduction-based, search-based, and learning-based approaches.These approaches differ in computational strategy and solution-quality properties.
- Communication-based learning in MAPF: PRIMAL demonstrated decentralized MAPF solving via learning, with communication limited to corresponding targets.DHC later introduced a dedicated learnable communication block and improved over PRIMAL.
- Communication-based learning in MAPF: DCC learns selective communication, while SCRIMP combines imitation learning, reinforcement learning, and communication mechanisms.Both methods extend earlier communication-based learning approaches.
- Communication-based learning in MAPF: Graph-attention methods dynamically weight neighboring agents’ messages, with later variants using hypergraphs or stacked attention layers.MAGAT, HMAGAT, and MAGAT+ represent this line of work.
Background
MAPF seeks conflict-free multi-agent plans on a graph, evaluated by costs such as sum-of-costs or makespan. Decentralized and imitation-learning formulations derive individual policies from local observations and expert demonstrations.
- Problem Statement: A MAPF instance specifies an environment graph, agent starts and goals, and plans whose actions move or wait.The plans must prevent agents from sharing vertices or traversing edges simultaneously.
- Problem Statement: MAPF solution quality is commonly measured by Sum-of-Costs or makespan.Sum-of-Costs sums individual goal-reaching costs, while makespan is the maximum such cost.
- Decision-making formulations: A centralized MAPF policy selects a joint conflict-free action for all agents at each timestep.The policy may be hand-crafted or learned.
- Decision-making formulations: A decentralized formulation learns a homogeneous policy shared across agents that acts from local observations and possibly communication.Observations typically cover nearby obstacles and agents rather than the full global state.
- Imitation Learning for MAPF: Imitation learning trains a parameterized policy to approximate an expert policy using expert state-action trajectories.In MAPF, the expert can be a centralized solver such as LaCAM*.
- Imitation Learning for MAPF: Decentralized imitation learning extracts each agent’s local observation and corresponding expert action from centralized trajectories.The resulting dataset is used to train the policy by minimizing expert-action negative log-likelihood.
Method
LC-MAPF encodes each agent’s local observation into a compact latent state, exchanges learned messages with neighboring agents over multiple rounds, and predicts decentralized actions end to end.
- Local observation encoding: Each agent tokenizes its local observation, including self and nearby-agent features, so it can reason about collision prevention and coordinated movement.Neighbor identifiers distinguish which nearby agent contributed each token.
- Latent representation: A Transformer encoder converts the embedded observation sequence into contextualized representations, while learnable latent queries compress them into a compact state.The bottleneck avoids propagating the entire observation sequence during communication.
- Communication: Only the compressed latent state participates in communication, making communication cost independent of observation size.This state is paired with a learnable message vector initialized identically across agents.
- Communication: Agents perform iterative local message passing: each decoder fuses neighbor messages with its latent state and produces the message sent in the next round.The decoder integrates contextualized neighbor messages through Transformer-based self-attention and cross-attention.
- Action prediction: After the final communication round, the decoder produces action logits that are converted into action probabilities for decentralized control.The communication and action prediction workflow is trained end to end.
- Training: LC-MAPF uses cross-entropy training on expert demonstrations, while messages receive no direct supervision and learn through their effects on neighboring agents’ action losses.All experiments use four communication rounds.
Experimental Setup
Experiments use the diverse, partially observable POGEMA benchmark with tokenized local observations and bounded neighbor communication, alongside large-scale demonstration training and reported success-rate and solution-cost evaluations.
- Benchmark: The POGEMA benchmark covers Random, Mazes, Warehouse, and Cities environments with partially observable multi-agent pathfinding scenarios.Each agent receives up to 256 tokens from an 11 × 11 local field of view and up to 13 messages within a 5-cell radius.
- Training data: Training uses approximately 23.5 million samples aggregated from mazes, random, and house subsets with a 0.6:0.2:0.2 distribution.Each sample contains observations and ground-truth actions for all agents.
- Training procedure: Training runs for 800,000 iterations with an effective batch size of 512 samples per optimization step, requiring roughly 900 GPU-hours.Mixed-precision bfloat16 training is used to improve throughput and reduce memory footprint.
- Evaluation metrics: Evaluation reports success rates by map type and agent count, with Figure 3 showing shaded 95% confidence intervals.Figure 4 reports solution-cost ratios relative to LaCAM*, where lower is better.
- Model configuration: The model contains approximately 3 million trainable parameters and is trained from scratch with AdamW and cosine learning-rate decay.Key architectural and optimization hyperparameters are summarized in Table 1.
Experimental Results
LC-MAPF matches or surpasses learning-based MAPF baselines across success rate and solution cost, while communication-round, failure, neighborhood, shielding, and deployment studies expose important operating conditions.
- Comparison with the Baselines: LC-MAPF is on par with or better than every evaluated baseline in success rate across all tested map types and agent counts.The comparison includes MAPF-GPT-85M, MAPF-GPT-DDG, MAGAT+, and HMAGAT.
- Communication Rounds Ablation Study: Four communication rounds produce the best ablation performance; at least two are needed for some instances, while additional rounds reduce collisions without improving success rate.The ablation varies communication from 1 to 8 rounds on Warehouse maps with 32–192 agents.
- Message Failure Test: At 50% message failure, LC-MAPF still solves simpler tasks with up to 32 agents but achieves only partial success for larger populations.Random noise messages negatively affect success rates for 48 agents and above, indicating that the learned message information matters.
- Communication Neighborhood: Restricting the communication neighborhood significantly reduces success rates, especially with limits of 4 agents or fewer on instances containing 48 or 64 agents.Tighter limits have little effect with fewer agents because observations often already contain no more agents than the imposed limit.
- Evaluation with Collision Shielding: Collision shielding often improves results but can change relative method rankings and degrade policies whose executed actions diverge from their training-time action histories.With CS-PIBT, MAPF-GPT-85M can perform worse on low-agent Mazes instances, while HMAGAT often achieves better relative cost despite solving fewer instances.
Conclusion
LC-MAPF introduces locally communicating agents that use multi-round interaction to improve decentralized MAPF coordination. The model outperforms learning-based solvers while maintaining linear scalability with the number of agents.
- LC-MAPF is a communication learning framework that uses expert demonstrations without explicit communication supervision.Its communication is organized into rounds to enhance cooperation between agents.
- The transformer-based LC-MAPF model outperforms state-of-the-art learning-based MAPF solvers across diverse scenarios.The reported improvements concern coordination and cooperation on the POGEMA benchmark.
- LC-MAPF maintains linear scalability with the number of agents while multi-round local communication improves performance without sacrificing scalability or generalization.Ablation studies support the contribution of multi-round local communication.