On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs

“Multi-agent pathfinding”, also called “pebble motion on graphs” or “cooperative pathfinding”, is the problem of deciding the existence of or generating a collision-free movement plan for a set of agents moving on a graph. While the non-optimizing variant of multi-agent pathfinding on undirected graphs is known to be a polynomial-time problem since forty years, a similar result for directed graphs was missing. In the talk, it will be shown that this problem is NP-complete. For strongly connected directed graphs, however, the problem is polynomial. And both of these results hold even if one allows for synchronous rotations on fully occupied cycles.