  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, and we propose a reduction method to
convert them to standard MP and MAPF. This reduction method consists in finding
a subset of nodes W and a reduced graph G/W, such that a solution of MAPF on
G/W provides a solution of C-MAPF on G. Moreover, we study the problem of
finding W of maximum cardinality, which is strongly NP-hard.
