# Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 35 references that are in the map.
- First posted on arXiv 16 Jun 2024.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [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)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Automated Algorithm Selection: Survey and Perspectives](https://mlsanity.com/paper/1811.11597/) (2018)
- [Cross-Modality Attention with Semantic Graph Embedding for Multi-Label Classification](https://mlsanity.com/paper/1912.07872/) (2019)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search](https://mlsanity.com/paper/2103.07116/) (2021)
- [MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings](https://mlsanity.com/paper/2102.12461/) (2021)
- [Automatic Algorithm Selection In Multi-agent Pathfinding](https://mlsanity.com/paper/1906.03992/) (2019)

## Abstract (arXiv)

Multi-agent path finding (MAPF) is the problem of finding paths for multiple agents such that they do not collide. This problem manifests in numerous real-world applications such as controlling transportation robots in automated warehouses, moving characters in video games, and coordinating self-driving cars in intersections. Finding optimal solutions to MAPF is NP-Hard, yet modern optimal solvers can scale to hundreds of agents and even thousands in some cases. Different solvers employ different approaches, and there is no single state-of-the-art approach for all problems. Furthermore, there are no clear, provable, guidelines for choosing when each optimal MAPF solver to use. Prior work employed Algorithm Selection (AS) techniques to learn such guidelines from past data. A major challenge when employing AS for choosing an optimal MAPF algorithm is how to encode the given MAPF problem. Prior work either used hand-crafted features or an image representation of the problem. We explore graph-based encodings of the MAPF problem and show how they can be used on-the-fly with a modern graph embedding algorithm called FEATHER. Then, we show how this encoding can be effectively joined with existing encodings, resulting in a novel AS method we call MAPF Algorithm selection via Graph embedding (MAG). An extensive experimental evaluation of MAG on several MAPF algorithm selection tasks reveals that it is either on-par or significantly better than existing methods.