On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs
Bernhard Nebel
2020Proceedings of the International Conference on Automated Planning and Scheduling27 citationsDOIOpen Access PDF
Abstract
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 can be decided 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.
Topics & Concepts
PathfindingComputational complexity theoryTime complexityComputer scienceDirected graphTheoretical computer scienceMathematicsPolynomialCombinatoricsAlgorithmGraphShortest path problemMathematical analysisAI-based Problem Solving and PlanningConstraint Satisfaction and OptimizationOptimization and Search Problems