arXiv:2505.10387v1 宣告类型: cross 摘要: 多智能体路径规划（MAPF）问题要求在一个图上找到一系列路径，使得当这些智能体同步遵循这些路径时，它们永远不会遇到冲突。在最普遍的MAPF形式化中，即所谓的经典MAPF，忽视了智能体的大小，并考虑了两种类型的冲突：占据同一顶点或在同一时间步使用同一边。而在许多实际应用中，例如在机器人技术中，考虑到智能体的大小是确保可以获得安全执行的MAPF解决方案的关键。引入大型智能体会导致一种额外类型的冲突，当一个智能体遵循一条边，其身体与另一台实际上未使用这条边（例如停留在图中其他顶点）的智能体的身体重叠时产生。迄今为止，还未清楚当在规划时考虑这种冲突时问题变得有多么困难。具体来说，已知在无向图上解决经典MAPF问题是可以在多项式时间内完成的，但是尚未提出完整的多项式时间算法来解决具有大型智能体的MAPF问题。在这篇论文中，我们首次证明了后者问题是NP难的，并且如果不等式P≠NP成立，这种问题将不可能有高效的多项式时间算法。我们的证明基于该领域常用的将经典3SAT问题（众所周知是一个NP完全问题）归约到当前问题的方法。特别是，对于任意的3SAT公式，我们按程序构建一个专用的图及其特定的起始和目标顶点，并证明给定的3SAT公式是可满足的当且仅当相应的路径规划实例有解。