# HiMAP: Learning Heuristics-Informed Policies for Large-Scale Multi-Agent Pathfinding

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 20 references that are in the map.
- First posted on arXiv 23 Feb 2024.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong](https://mlsanity.com/paper/2010.08184/) (2020)
- [SCRIMP: Scalable Communication for Reinforcement- and Imitation-Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2303.00605/) (2023)
- [Distributed Heuristic Multi-Agent Path Finding with Communication](https://mlsanity.com/paper/2106.11365/) (2021)
- [Learning Selective Communication for Multi-Agent Path Finding](https://mlsanity.com/paper/2109.05413/) (2021)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings](https://mlsanity.com/paper/2102.12461/) (2021)
- [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)
- [RDE: A Hybrid Policy Framework for Multi-Agent Path Finding Problem](https://mlsanity.com/paper/2311.01728/) (2023)

## Built on by (most cited first, 4 of 4)

- [Ensembling Prioritized Hybrid Policies for Multi-agent Pathfinding](https://mlsanity.com/paper/2403.07559/) (2024)
- [EvoNav: Evolutionary Reward Function Design for Robot Navigation with Large Language Models](https://mlsanity.com/paper/2605.11859/) (2026)
- [USPR: Learning a Unified Solver for Profiled Routing](https://mlsanity.com/paper/2505.05119/) (2025)
- [GRACE: A Unified 2D Multi-Robot Path Planning Simulator & Benchmark for Grid, Roadmap, And Continuous Environments](https://mlsanity.com/paper/2603.10858/) (2026)

## Abstract (arXiv)

Large-scale multi-agent pathfinding (MAPF) presents significant challenges in several areas. As systems grow in complexity with a multitude of autonomous agents operating simultaneously, efficient and collision-free coordination becomes paramount. Traditional algorithms often fall short in scalability, especially in intricate scenarios. Reinforcement Learning (RL) has shown potential to address the intricacies of MAPF; however, it has also been shown to struggle with scalability, demanding intricate implementation, lengthy training, and often exhibiting unstable convergence, limiting its practical application. In this paper, we introduce Heuristics-Informed Multi-Agent Pathfinding (HiMAP), a novel scalable approach that employs imitation learning with heuristic guidance in a decentralized manner. We train on small-scale instances using a heuristic policy as a teacher that maps each single agent observation information to an action probability distribution. During pathfinding, we adopt several inference techniques to improve performance. With a simple training scheme and implementation, HiMAP demonstrates competitive results in terms of success rate and scalability in the field of imitation-learning-only MAPF, showing the potential of imitation-learning-only MAPF equipped with inference techniques.