Constrained Motion Planning and Multi-Agent Path Finding on directed graphs

We discuss C-MP and C-MAPF, generalizations of the classical Motion Planning (MP) and Multi-Agent Path Finding (MAPF) problems on a directed graph G. Namely, we enforce an upper bound on the number of agents that occupy each member of a family of vertex subsets. For instance, this constraint allows maintaining a safety distance between agents. We prove that finding a feasible solution of C-MP and C-MAPF is NP-hard. Also, we propose a method to convert these problems to standard MP and MAPF by strengthening the constraints. The method consists in finding a subset of vertices W and a reduced graph GW, such that a feasible solution of MP and MAPF on GW provides, in polynomial time, a feasible solution of C-MP and C-MAPF on G. However, since the conversion into standard MP and MAPF is obtained by strengthening constraints, feasible solutions of C-MP and C-MAPF on G may exist even if MP and MAPF on GW do not admit any feasible solution. We also study the problem of finding W of maximum cardinality. First, we show that such problem is strongly NP-hard. Then, we propose a heuristic approach for its solution.