Automatic Optimal Multi-Agent Path Finding Algorithm Selector (Student Abstract)

Jingyao Ren, Vikraman Sathiyanarayanan, Eric Ewing, Baskin Senbaslar, Nora AyanianAAAI 2021 · DOI

Introduction

Multi-Agent Path Finding (MAPF) is a fundamental challenge in robotics and logistics, where a team of agents must navigate to their respective goals without colliding. While several "optimal" solvers exist—ranging from search-based methods like Conflict-Based Search (CBS) to optimization-based approaches—their performance is highly inconsistent across different environments. This "No Free Lunch" problem means that an algorithm excelling in open spaces might fail in narrow corridors. To address this, researchers have developed MAPFAST, an automated algorithm selector that uses deep learning to predict the fastest solver for any given MAPF instance.

Methodology

MAPFAST frames algorithm selection as a classification task using a Convolutional Neural Network (CNN). The architecture integrates Inception modules, which allow the network to extract features at multiple spatial scales simultaneously. This is particularly useful for MAPF, as it enables the model to recognize both local bottlenecks (like doorways) and global topological structures (like large rooms) that influence solver performance.

Input Representation and SASP

A critical innovation in MAPFAST is the use of Single-Agent Shortest Paths (SASP) for input annotation. Rather than feeding the raw map into the CNN, the authors provide a 320x320 image containing the obstacles, start/goal locations, and the ideal path for each agent calculated in isolation. This annotation provides the network with a "hint" about potential congestion points, significantly improving the model's ability to identify which solver in its portfolio will handle the predicted collisions most efficiently.

MAPFAST architecture and input representation including Single-Agent Shortest Paths (SASP)

Experimental Setup

The study utilized a benchmark of 2,484 MAPF instances featuring diverse map types and agent configurations. The selector's portfolio includes four high-performance algorithms: BCP (optimization-based), SAT (satisfiability-based), and CBS/CBS-H (search-based). The researchers also explored Graph2Vec (G2V), a graph-embedding technique that allows the model to handle varying map sizes, though it was slightly less accurate than the primary CNN model.

Key Results and Discussion

MAPFAST demonstrated superior performance across all metrics compared to individual algorithms and previous state-of-the-art selectors. It achieved a selection accuracy of 77%, outperforming the previous XGBoost-based baseline of 67%.

In terms of operational efficiency, MAPFAST reached a 97% coverage rate, successfully solving nearly all test instances within the time limit by picking the right tool for the job. Most impressively, the total runtime for all problems using MAPFAST's selections was 1,339 minutes—nearly half the time required by the best single algorithm, BCP (2,256 minutes), and approaching the theoretical limit of the "Oracle" (917 minutes).

Performance comparison of individual algorithms and selectors

Conclusion

MAPFAST proves that spatial pathfinding challenges can be effectively solved by treating them as computer vision problems. By leveraging CNNs and path-based annotations, the system can automate the complex decision-making process of algorithm selection. While current limitations include a fixed input resolution for the CNN, the success of the G2V variant suggests a path toward more flexible, scalable selectors for real-world multi-agent systems.

Summary updated

BibTeX
@inproceedings{ren2021automatic,
  author = {Jingyao Ren and Vikraman Sathiyanarayanan and Eric Ewing and Baskin Senbaslar and Nora Ayanian},
  title = {{Automatic Optimal Multi-Agent Path Finding Algorithm Selector (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i18.17935},
}
Figure