# Distributed Heuristic Multi-Agent Path Finding with Communication

arXiv: https://arxiv.org/abs/2106.11365 · HTML: https://mlsanity.com/paper/2106.11365/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 39 references that are in the map.
- First posted on arXiv 21 Jun 2021.

## Builds on (most cited first, 21 of 21)

- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1803.11485/) (2018)
- [Learning to Communicate with Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1605.06676/) (2016)
- [Distributed Prioritized Experience Replay](https://mlsanity.com/paper/1803.00933/) (2018)
- [TarMAC: Targeted Multi-Agent Communication](https://mlsanity.com/paper/1810.11187/) (2018)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Multiagent Cooperation and Competition with Deep Reinforcement Learning](https://mlsanity.com/paper/1511.08779/) (2015)
- [Emergence of Locomotion Behaviours in Rich Environments](https://mlsanity.com/paper/1707.02286/) (2017)
- [Value Iteration Networks](https://mlsanity.com/paper/1602.02867/) (2016)
- [Graph Convolutional Reinforcement Learning](https://mlsanity.com/paper/1810.09202/) (2018)
- [Decentralized Non-communicating Multiagent Collision Avoidance with Deep Reinforcement Learning](https://mlsanity.com/paper/1609.07845/) (2016)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning](https://mlsanity.com/paper/1709.10082/) (2017)
- [Mobile Robot Path Planning in Dynamic Environments through Globally Guided Reinforcement Learning](https://mlsanity.com/paper/2005.05420/) (2020)
- [MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments](https://mlsanity.com/paper/2007.15724/) (2020)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [GLAS: Global-to-Local Safe Autonomy Synthesis for Multi-Robot Motion Planning with End-to-End Learning](https://mlsanity.com/paper/2002.11807/) (2020)

## Built on by (most cited first, 30 of 32)

- [Deep Multiagent Reinforcement Learning: Challenges and Directions](https://mlsanity.com/paper/2106.15691/) (2021)
- [Learning Selective Communication for Multi-Agent Path Finding](https://mlsanity.com/paper/2109.05413/) (2021)
- [Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning](https://mlsanity.com/paper/2310.01207/) (2023)
- [Multi-Agent Path Finding with Prioritized Communication Learning](https://mlsanity.com/paper/2202.03634/) (2022)
- [Distributed Reinforcement Learning for Robot Teams: A Review](https://mlsanity.com/paper/2204.03516/) (2022)
- [Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding](https://mlsanity.com/paper/2312.15908/) (2023)
- [Work Smarter Not Harder: Simple Imitation Learning with CS-PIBT Outperforms Large Scale Imitation Learning for MAPF](https://mlsanity.com/paper/2409.14491/) (2024)
- [SRMT: Shared Memory for Multi-agent Lifelong Pathfinding](https://mlsanity.com/paper/2501.13200/) (2025)
- [CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces](https://mlsanity.com/paper/2201.09467/) (2022)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [Ensembling Prioritized Hybrid Policies for Multi-agent Pathfinding](https://mlsanity.com/paper/2403.07559/) (2024)
- [Deploying Ten Thousand Robots: Scalable Imitation Learning for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2410.21415/) (2024)
- [SACHA: Soft Actor-Critic with Heuristic-Based Attention for Partially Observable Multi-Agent Path Finding](https://mlsanity.com/paper/2307.02691/) (2023)
- [Learning Team-Based Navigation: A Review of Deep Reinforcement Learning Techniques for Multi-Agent Pathfinding](https://mlsanity.com/paper/2308.05893/) (2023)
- [Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning](https://mlsanity.com/paper/2506.23793/) (2025)
- [HiMAP: Learning Heuristics-Informed Policies for Large-Scale Multi-Agent Pathfinding](https://mlsanity.com/paper/2402.15546/) (2024)
- [SIGMA: Sheaf-Informed Geometric Multi-Agent Pathfinding](https://mlsanity.com/paper/2502.06440/) (2025)
- [MFC-EQ: Mean-Field Control with Envelope Q-Learning for Moving Decentralized Agents in Formation](https://mlsanity.com/paper/2410.12062/) (2024)
- [LLMDR: LLM-Driven Deadlock Detection and Resolution in Multi-Agent Pathfinding](https://mlsanity.com/paper/2503.00717/) (2025)
- [Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding](https://mlsanity.com/paper/2605.07637/) (2026)
- [Discrete Diffusion for Complex and Congested Multi-Agent Path Finding with Sparse Social Attention](https://mlsanity.com/paper/2605.13296/) (2026)
- [Optimizing Crowd-Aware Multi-Agent Path Finding through Local Communication with Graph Neural Networks](https://mlsanity.com/paper/2309.10275/) (2023)
- [Cooperative Reward Shaping for Multi-Agent Pathfinding](https://mlsanity.com/paper/2407.10403/) (2024)
- [Multi-Robot Reliable Navigation in Uncertain Topological Environments with Graph Attention Networks](https://mlsanity.com/paper/2411.16134/) (2024)
- [When Agents Break Down in Multiagent Path Finding](https://mlsanity.com/paper/2508.03777/) (2025)
- [Multi-Agent Path Finding via Offline RL and LLM Collaboration](https://mlsanity.com/paper/2509.22130/) (2025)
- [Sequence Pathfinder for Multi-Agent Pickup and Delivery in the Warehouse](https://mlsanity.com/paper/2509.23778/) (2025)
- [Towards Information-Optimized Multi-Agent Path Finding: A Hybrid Framework with Reduced Inter-Agent Information Sharing](https://mlsanity.com/paper/2510.09469/) (2025)
- [SPARC: Spatial-Aware Path Planning via Attentive Agent Communication](https://mlsanity.com/paper/2603.02845/) (2026)
- [VORL-EXPLORE: A Hybrid Learning Planning Approach to Multi-Robot Exploration in Dynamic Environments](https://mlsanity.com/paper/2603.07973/) (2026)

## Abstract (arXiv)

Multi-Agent Path Finding (MAPF) is essential to large-scale robotic systems. Recent methods have applied reinforcement learning (RL) to learn decentralized polices in partially observable environments. A fundamental challenge of obtaining collision-free policy is that agents need to learn cooperation to handle congested situations. This paper combines communication with deep Q-learning to provide a novel learning based method for MAPF, where agents achieve cooperation via graph convolution. To guide RL algorithm on long-horizon goal-oriented tasks, we embed the potential choices of shortest paths from single source as heuristic guidance instead of using a specific path as in most existing works. Our method treats each agent independently and trains the model from a single agent's perspective. The final trained policy is applied to each agent for decentralized execution. The whole system is distributed during training and is trained under a curriculum learning strategy. Empirical evaluation in obstacle-rich environment indicates the high success rate with low average step of our method.