Algorithm Selection for Multi-Agent Pathfinding(MAPF) Problems

  1. Home
  2. Algorithm Selection for Multi-Agent Pathfinding(MAPF) Problems

Description

Solving the Multi-Agent Path Finding (MAPF) problem optimally is known to be NP-Hard for both make-span and total arrival time minimization. While many algorithms have been developed to solve MAPF problems, there is no dominating optimal MAPF algorithm that works well in all types of problems and no standard guidelines for when to use which algorithm. In this work, we build deep learning network which takes a MAPF problem instance and attempts to select the fastest algorithm to use from a portfolio of algorithms.

We improve the performance of our model by including single-agent shortest paths in the instance embedding given to our model and by utilizing supplemental loss functions in addition to a classification loss. We evaluate our model on a large and diverse dataset of MAPF instances, showing that it outperforms all individual algorithms in its portfolio as well as the state-of-the-art optimal MAPF algorithm selector. We also provide an analysis of algorithm behavior in our dataset to gain a deeper understanding of optimal MAPF algorithms' strengths and weaknesses to help other researchers leverage different heuristics in algorithm designs.

Investigators

  • Jingyao Ren
  • Eric Ewing
  • Baskin Senbaslar
  • Vikraman Sathiyanarayanan
  • Nora Ayanian

Funding

This research was supported by NSF awards IIS-1553726, IIS-1724392, IIS-1724399, and CNS-1837779 as well as a gift from Amazon.

Related Publications

  • Ren J, Sathiyanarayanan V, Ewing E, Senbaslar B, Ayanian N. "MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings". In Proceedings of the 20th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-21) 2021 May 3 (pp. 1055-1063).
    [ PDF ]
  • Ren J, Sathiyanarayanan V, Ewing E, Senbaslar B, Ayanian N. "Automatic Optimal Multi-Agent Path Finding Algorithm Selector (Student Abstract)". In Proceedings of the AAAI Conference on Artificial Intelligence 2021 May 18 (Vol. 35, No. 18, pp. 15877-15878).
    [ PDF ]