On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs
This resolves a long-standing open problem in theoretical computer science, providing clarity for researchers in AI and robotics on the hardness of pathfinding in directed environments.
The paper tackles the computational complexity of multi-agent pathfinding on directed graphs, showing that the general case is NP-hard, while also proving some upper bounds.
The determination of the computational complexity of multi-agent pathfinding on directed graphs has been an open problem for many years. For undirected graphs, solvability can be decided in polynomial time, as has been shown already in the eighties. Further, recently it has been shown that a special case on directed graphs is solvable in polynomial time. In this paper, we show that the problem is NP-hard in the general case. In addition, some upper bounds are proven.