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

Authors

  • Jingyao Ren University of Southern California
  • Vikraman Sathiyanarayanan University of Southern California
  • Eric Ewing University of Southern California
  • Baskin Senbaslar University of Southern California
  • Nora Ayanian University of Southern California

Keywords:

Multiagent Systems, Multi Agent Path Finding, Artificial Intelligence, Algorithm Selection, Deep Learning

Abstract

Solving Multi-Agent Path Finding (MAPF) problems optimally is known to be NP-Hard for both make-span and total arrival time minimization. Many algorithms have been developed to solve MAPF problems optimally and they all have different strengths and weaknesses. There is no dominating MAPF algorithm that works well in all types of problems and no standard guidelines for when to use which algorithm. Therefore, there is a need for developing an automatic algorithm selector that suggests the best optimal algorithm to use given a MAPF problem instance. We propose a model based on convolutions and inception modules by treating the input MAPF instance as an image. We further show that techniques such as single-agent shortest path annotation and graph embedding are very effective for improving training quality. We evaluate our model and show that it outperforms all individual algorithms in its portfolio, as well as an existing state-of-the-art MAPF algorithm selector.

Downloads

Published

2021-05-18

How to Cite

Ren, J., Sathiyanarayanan, V., Ewing, E., Senbaslar, B., & Ayanian, N. (2021). Automatic Optimal Multi-Agent Path Finding Algorithm Selector (Student Abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 35(18), 15877-15878. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17935

Issue

Section

AAAI Student Abstract and Poster Program