Algorithm Selection for Optimal Multi-Agent Pathfinding

Omri Kaduri, Eli Boyarski, Roni Stern

PosterID: 6 PDF Poster BibTeX

At the past couple of years the research on multi-agent path finding (MAPF) has been flourishing, with new algorithms or algorithmic improvements appearing every year. In particular, although finding optimal solutions to MAPF is NP-Hard, there are to-date several successful algorithms that can find optimal solutions for problems with hundreds of agents. Nevertheless, it appears that no single MAPF algorithm dominates all benchmarks problems. Moreover, there are no clear, provable, guidelines for when each algorithm should be used. To address this, we apply a data-driven approach and propose the first successful algorithm selection method for optimal MAPF. Our algorithm selection method uses standard supervised learning algorithm with a set of hand-crafted MAPF-specific features and a customized weighting of the training instances. The results show that we are able to predict with very high accuracy the best algorithm to use for each instance. Using our algorithm selection method, we are able to achieve maximal coverage and running time over a range of maps and scenarios, compared to the state of the art.

Session E1: Learning for Deterministic Planning
Canb 10/27/2020, 18:00 – 19:00
10/31/2020, 01:00 – 02:00
Paris 10/27/2020, 08:00 – 09:00
10/30/2020, 15:00 – 16:00
NYC 10/27/2020, 03:00 – 04:00
10/30/2020, 10:00 – 11:00
LA 10/27/2020, 00:00 – 01:00
10/30/2020, 07:00 – 08:00