@inproceedings{c86cf89230464f1892c1747d4c6e7491,
title = "Intractability of Optimal Multi-Agent Pathfinding on Directed Graphs",
abstract = "In Multi-Agent Pathfinding (MAPF) problems, multiple agents move simultaneously to reach their individual destinations without colliding with each other. The computational complexity of the problem has been extensively studied for undirected graphs over the past decades. However, plan existence for Directed MAPF (diMAPF) was only recently studied and was shown to be in PSPACE as well as NP-hard. In this paper, we study the optimization versions (on makespan and on travel distance of agents) of diMAPF problems and show that they remain NP-hard even when various important non-trivial restrictions are imposed (e.g., when considering the problem on directed, acyclic, and planar graphs where the vertex-degrees are bounded). We have also provide membership results, thus presenting the first set of NP-completeness results for various optimal diMAPF variants.",
author = "Xing Tan and Pascal Bercher",
note = "{\textcopyright} 2023 The Authors.; 26th European Conference on Artificial Intelligence, ECAI 2023 ; Conference date: 30-09-2023 Through 04-10-2023",
year = "2023",
month = sep,
day = "28",
doi = "10.3233/FAIA230531",
language = "English",
series = "Frontiers in Artificial Intelligence and Applications",
publisher = "IOS Press BV",
pages = "2315--2321",
editor = "Kobi Gal and Ann Nowe and Nalepa, \{Grzegorz J.\} and Roy Fairstein and Roxana Radulescu",
booktitle = "ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings",
address = "Netherlands",
}