# MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 25 references that are in the map.
- First posted on arXiv 24 Feb 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [graph2vec: Learning Distributed Representations of Graphs](https://mlsanity.com/paper/1707.05005/) (2017)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Automatic Algorithm Selection In Multi-agent Pathfinding](https://mlsanity.com/paper/1906.03992/) (2019)

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

- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [HiMAP: Learning Heuristics-Informed Policies for Large-Scale Multi-Agent Pathfinding](https://mlsanity.com/paper/2402.15546/) (2024)
- [Tracking Progress in Multi-Agent Path Finding](https://mlsanity.com/paper/2305.08446/) (2023)
- [Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.19219/) (2025)
- [Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding](https://mlsanity.com/paper/2406.10827/) (2024)
- [DeepClean: Integrated Distortion Identification and Algorithm Selection for Rectifying Image Corruptions](https://mlsanity.com/paper/2407.16302/) (2024)

## Abstract (arXiv)

Solving the Multi-Agent Path Finding (MAPF) problem optimally is known to be NP-Hard for both make-span and total arrival time minimization. While many algorithms have been developed to solve MAPF problems, there is no dominating optimal MAPF algorithm that works well in all types of problems and no standard guidelines for when to use which algorithm. In this work, we develop the deep convolutional network MAPFAST (Multi-Agent Path Finding Algorithm SelecTor), which takes a MAPF problem instance and attempts to select the fastest algorithm to use from a portfolio of algorithms. We improve the performance of our model by including single-agent shortest paths in the instance embedding given to our model and by utilizing supplemental loss functions in addition to a classification loss. We evaluate our model on a large and diverse dataset of MAPF instances, showing that it outperforms all individual algorithms in its portfolio as well as the state-of-the-art optimal MAPF algorithm selector. We also provide an analysis of algorithm behavior in our dataset to gain a deeper understanding of optimal MAPF algorithms' strengths and weaknesses to help other researchers leverage different heuristics in algorithm designs.