# MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2014.

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

- [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)
- [Answer Set Planning: A Survey](https://mlsanity.com/paper/2202.05793/) (2022)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding](https://mlsanity.com/paper/2208.01222/) (2022)
- [Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks](https://mlsanity.com/paper/2201.06014/) (2022)
- [A Competitive Analysis of Online Multi-Agent Path Finding](https://mlsanity.com/paper/2106.11454/) (2021)
- [DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologies](https://mlsanity.com/paper/2111.06494/) (2021)
- [QD-MAPPER: A Quality Diversity Framework to Automatically Evaluate Multi-Agent Path Finding Algorithms in Diverse Maps](https://mlsanity.com/paper/2409.06888/) (2024)
- [Planning over MAPF Agent Dependencies via Multi-Dependency PIBT](https://mlsanity.com/paper/2603.23405/) (2026)
- [Plan Execution for Multi-Agent Path Finding with Indoor Quadcopters](https://mlsanity.com/paper/2207.01752/) (2022)
- [Counterexample Guided Abstraction Refinement with Non-Refined Abstractions for Multi-Agent Path Finding](https://mlsanity.com/paper/2301.08687/) (2023)
- [Multi-Agent Pathfinding Under Team-Connected Communication Constraint via Adaptive Path Expansion and Dynamic Leading](https://mlsanity.com/paper/2501.02770/) (2025)
- [Unassigned Agents in Compilation-based Multi-agent Path Finding](https://mlsanity.com/paper/2606.15797/) (2026)
- [Stress-Relief Annealing: Polynomial-Time Simulation-Free Layout Optimization for Automated Warehouses](https://mlsanity.com/paper/2608.01024/) (2026)

## Abstract (arXiv)

Multi-agent path planning is a challenging problem with numerous real-life applications. Running a centralized search such as A* in the combined state space of all units is complete and cost-optimal, but scales poorly, as the state space size is exponential in the number of mobile units. Traditional decentralized approaches, such as FAR and WHCA*, are faster and more scalable, being based on problem decomposition. However, such methods are incomplete and provide no guarantees with respect to the running time or the solution quality. They are not necessarily able to tell in a reasonable time whether they would succeed in finding a solution to a given instance. We introduce MAPP, a tractable algorithm for multi-agent path planning on undirected graphs. We present a basic version and several extensions. They have low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. Even though all algorithmic versions are incomplete in the general case, each provides formal guarantees on problems it can solve. For each version, we discuss the algorithms completeness with respect to clearly defined subclasses of instances. Experiments were run on realistic game grid maps. MAPP solved 99.86% of all mobile units, which is 18--22% better than the percentage of FAR and WHCA*. MAPP marked 98.82% of all units as provably solvable during the first stage of plan computation. Parts of MAPPs computation can be re-used across instances on the same map. Speed-wise, MAPP is competitive or significantly faster than WHCA*, depending on whether MAPP performs all computations from scratch. When data that MAPP can re-use are preprocessed offline and readily available, MAPP is slower than the very fast FAR algorithm by a factor of 2.18 on average. MAPPs solutions are on average 20% longer than FARs solutions and 7--31% longer than WHCA*s solutions.