标题： 多智能体路径搜索对于大规模智能体是难以处理的 显示英文标题

标题： Multi-Agent Path Finding For Large Agents Is Intractable

摘要： 多智能体路径寻找（MAPF）问题要求在一个图上找到一组路径，使得当这些路径同步执行时，智能体之间不会发生冲突。 在最广泛的MAPF公式化中，所谓的经典MAPF问题中，忽略了智能体的大小，并且考虑了两种类型的冲突：占据同一顶点或在同一时间步骤使用同一条边。 同时，在许多实际应用中，例如在机器人学中，考虑到智能体的大小对于确保MAPF解决方案能够安全执行至关重要。 引入大智能体会产生一种额外的冲突类型，即当一个智能体沿着某条边移动时，它的身体与另一个实际上没有使用这条边的智能体的身体重叠（例如，停留在图中的某个不同顶点上）。 直到现在，还不清楚在规划时考虑这种冲突会使问题变得多么困难。 具体来说，已知无向图上的经典MAPF问题可以在多项式时间内解决，然而还没有提出能够在多项式时间内解决具有大智能体的MAPF问题的完整算法。 在本文中，我们首次证明后一个问题是一个NP难问题，因此，如果P≠NP，则不幸的是无法提出一个多项式时间算法来解决它。 我们的证明基于该领域普遍采用的技术，即将著名的3SAT问题（已知是一个NP完全问题）归约到当前问题。 具体而言，对于任意的3SAT公式，我们构造一个专用的图，具有特定的起始和目标顶点，并表明给定的3SAT公式可满足当且仅当相应的路径寻找实例有一个解。 显示英文摘要

摘要： The multi-agent path finding (MAPF) problem asks to find a set of paths on a graph such that when synchronously following these paths the agents never encounter a conflict. In the most widespread MAPF formulation, the so-called Classical MAPF, the agents sizes are neglected and two types of conflicts are considered: occupying the same vertex or using the same edge at the same time step. Meanwhile in numerous practical applications, e.g. in robotics, taking into account the agents' sizes is vital to ensure that the MAPF solutions can be safely executed. Introducing large agents yields an additional type of conflict arising when one agent follows an edge and its body overlaps with the body of another agent that is actually not using this same edge (e.g. staying still at some distinct vertex of the graph). Until now it was not clear how harder the problem gets when such conflicts are to be considered while planning. Specifically, it was known that Classical MAPF problem on an undirected graph can be solved in polynomial time, however no complete polynomial-time algorithm was presented to solve MAPF with large agents. In this paper we, for the first time, establish that the latter problem is NP-hard and, thus, if P!=NP no polynomial algorithm for it can, unfortunately, be presented. Our proof is based on the prevalent in the field technique of reducing the seminal 3SAT problem (which is known to be an NP-complete problem) to the problem at hand. In particular, for an arbitrary 3SAT formula we procedurally construct a dedicated graph with specific start and goal vertices and show that the given 3SAT formula is satisfiable iff the corresponding path finding instance has a solution.