# Improving Learnt Local MAPF Policies with Heuristic Search

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 15 references that are in the map.
- First posted on arXiv 29 Mar 2024.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Convolutional Neural Network Architectures for Signals Supported on Graphs](https://mlsanity.com/paper/1805.00165/) (2018)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [Graph Neural Networks for Decentralized Multi-Robot Path Planning](https://mlsanity.com/paper/1912.06095/) (2019)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [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)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Message-Aware Graph Attention Networks for Large-Scale Multi-Robot Path Planning](https://mlsanity.com/paper/2011.13219/) (2020)
- [SCRIMP: Scalable Communication for Reinforcement- and Imitation-Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2303.00605/) (2023)

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

- [Work Smarter Not Harder: Simple Imitation Learning with CS-PIBT Outperforms Large Scale Imitation Learning for MAPF](https://mlsanity.com/paper/2409.14491/) (2024)
- [Deploying Ten Thousand Robots: Scalable Imitation Learning for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2410.21415/) (2024)
- [Graph Attention-Guided Search for Dense Multi-Agent Pathfinding](https://mlsanity.com/paper/2510.17382/) (2025)
- [Lightweight and Effective Preference Construction in PIBT for Large-Scale Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.12623/) (2025)
- [DeepFleet: Multi-Agent Foundation Models for Mobile Robots](https://mlsanity.com/paper/2508.08574/) (2025)
- [Pairwise is Not Enough: Hypergraph Neural Networks for Multi-Agent Pathfinding](https://mlsanity.com/paper/2602.06733/) (2026)
- [Learning-guided Prioritized Planning for Lifelong Multi-Agent Path Finding in Warehouse Automation](https://mlsanity.com/paper/2603.23838/) (2026)
- [Windowed MAPF with Completeness Guarantees](https://mlsanity.com/paper/2410.01798/) (2024)
- [LLMDR: LLM-Driven Deadlock Detection and Resolution in Multi-Agent Pathfinding](https://mlsanity.com/paper/2503.00717/) (2025)
- [Planning over MAPF Agent Dependencies via Multi-Dependency PIBT](https://mlsanity.com/paper/2603.23405/) (2026)
- [Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding](https://mlsanity.com/paper/2605.07637/) (2026)
- [Search-Aided Joint Agent-Environment Reinforcement Learning for Robust Lifelong Multi-Agent Path Finding with Rotations](https://mlsanity.com/paper/2608.05588/) (2026)
- [Real-Time LaCAM for Real-Time MAPF](https://mlsanity.com/paper/2504.06091/) (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)

Multi-agent path finding (MAPF) is the problem of finding collision-free paths for a team of agents to reach their goal locations. State-of-the-art classical MAPF solvers typically employ heuristic search to find solutions for hundreds of agents but are typically centralized and can struggle to scale when run with short timeouts. Machine learning (ML) approaches that learn policies for each agent are appealing as these could enable decentralized systems and scale well while maintaining good solution quality. Current ML approaches to MAPF have proposed methods that have started to scratch the surface of this potential. However, state-of-the-art ML approaches produce "local" policies that only plan for a single timestep and have poor success rates and scalability. Our main idea is that we can improve a ML local policy by using heuristic search methods on the output probability distribution to resolve deadlocks and enable full horizon planning. We show several model-agnostic ways to use heuristic search with learnt policies that significantly improve the policies' success rates and scalability. To our best knowledge, we demonstrate the first time ML-based MAPF approaches have scaled to high congestion scenarios (e.g. 20% agent density).