论文标题
在有向图上的约束多代理路径查找
Constrained Multi-Agent Path Finding on Directed Graphs
论文作者
论文摘要
我们讨论了C-MP和C-MAPF，经典运动计划（MP）的概括（MP）以及在有向图G上的多代理路径发现（MAPF）问题。例如，此约束允许保持代理之间的安全距离。我们证明，找到C-MP和C-MAPF的可行解决方案是NP-HARD，我们提出了一种将它们转换为标准MP和MAPF的还原方法。这种还原方法包括找到节点W的子集和降低的图G/W，因此MAPF在G/W上的溶液提供了G/W上的C-MAPF解决方案。
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.
