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.
翻译:我们讨论了C-MP和C-MAPF, 传统运动规划(MP)和多机构路径发现(MAPF)问题在方向图G上的概括化问题。 也就是说,我们对占用每个顶点子子子集家庭成员的代理人数量实施上限限制,例如,这一限制允许在代理人之间保持安全距离。 我们证明,寻找C-MP和C-MAPF的可行解决办法是NP硬的,我们建议了一种削减方法,将其转换为标准的MP和MAPF。 这一削减方法包括找到一个节点W子和减少的G/W图,因此G/W的MAPF的解决方案为G/W提供了C-MAPF的解决方案。 此外,我们研究了找到最高度的基点W的问题,这是非常硬的NP。