The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True

Authors

  • Bernhard Nebel Albert-Ludwigs-Universitaet Freiburg

DOI:

https://doi.org/10.1609/icaps.v33i1.27208

Keywords:

Theoretical foundations of planning and scheduling, Multi-agent and distributed planning

Abstract

The determination of the computational complexity of multi-agent pathfinding on directed graphs (diMAPF) has been an open research problem for many years. While diMAPF has been shown to be polynomial for some special cases, only recently, it has been established that the problem is NP-hard in general. Further, it has been proved that diMAPF will be in NP if the short solution hypothesis for strongly connected directed graphs holds. In this paper, it is shown that this hypothesis is indeed true, even when one allows for synchronous rotations.
ICAPS-23 Proceedings Cover

Downloads

Published

2023-07-01

How to Cite

Nebel, B. (2023). The Small Solution Hypothesis for MAPF on Strongly Connected Directed Graphs Is True. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 304-313. https://doi.org/10.1609/icaps.v33i1.27208

Issue

Vol. 33 (2023): Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling

Section

Main Track