Anytime Automatic Algorithm Selection for the Multi-Agent Path Finding Problem

Abstract

In this study, we propose and develop a Machine Learning-based metasolver for the Multi-Agent Path Finding (MAPF) problem, with the aim of selecting the most suitable solver based on the specific characteristics of the problem and a user-provided time constraint. The approach aims to improve the performance of the best-performing solver on average and approximate the performance of a perfect selector. To achieve this, a comprehensive and diverse dataset was compiled, and state-of-the-art algorithms were selected and modified to efficiently handle the time constraint. Also, relevant features were identified, and a precise and robust Machine Learning model was constructed using the XGBoost algorithm. The model was evaluated and compared against other state-of-the-art methods. The results demonstrate that the proposed approach is effective and consistent, outperforming the Single Best Solver and approximating the performance of the Virtual Best Solver.

Keywords

• Algorithm selection
• multi-agent path finding
• machine learning