MAPFASTER: A Faster and Simpler take on Multi-Agent Path Finding Algorithm Selection
Jean-Marc Alkazzi, Anthony Rizk, Michel Salomon, Abdallah Makhoul
Abstract
Portfolio-based algorithm selection can help in choosing the best suited algorithm for a given task while leveraging the complementary strengths of the candidates. Solving the Multi-Agent Path Finding (MAPF) problem optimally has been proven to be NP-Hard. Furthermore, no single optimal algorithm has been shown to have the fastest runtime for all MAPF problem instances, and there are no proven approaches for when to use each algorithm. To address these challenges, we develop MAPFASTER, a smaller and more accurate deep learning based architecture aiming to be deployed in fleet management systems to select the fastest MAPF solver in a multi-robot setting. MAPF problem instances are encoded as images and passed to the model for classification into one of the portfolio's candidates. We evaluate our model against state-of-the-art Optimal-MAPF-Algorithm selectors, showing +5.42% improvement in accuracy while being 7.1× faster to train. The dataset, code and analysis used in this research can be found at https://github.com/jeanmarcalkazzi/mapfaster.
BibTeX
@inproceedings{iros2022_mapfasterafaster,
title = {MAPFASTER: A Faster and Simpler take on Multi-Agent Path Finding Algorithm Selection},
author = {Jean-Marc Alkazzi and Anthony Rizk and Michel Salomon and Abdallah Makhoul},
booktitle = {IROS 2022},
year = {2022}
}