Abstract
Multi-Agent Path Finding (MAPF) is a fundamental motion coordination problem arising in multi-agent systems with a wide range of applications. The problem's intractability has led to extensive research on improving the scalability of solvers for it. Since optimal solvers can struggle to scale, a major challenge that arises is understanding what makes MAPF hard. We tackle this challenge through a fine-grained complexity analysis of time-optimal MAPF on 2D grids, thereby closing two gaps and identifying a new tractability frontier. First, we show that 2-colored MAPF, i.e., where the agents are divided into two teams, each with its own set of targets, remains NP-hard. Second, for the flowtime objective (also called sum-of-costs), we show that it remains NP-hard to find a solution in which agents have an individually optimal cost, which we call an individually optimal solution. The previously tightest results for these MAPF variants are for (non-grid) planar graphs. We use a single hardness construction that replaces, strengthens, and unifies previous proofs. We believe that it is also simpler than previous proofs for the planar case as it employs minimal gadgets that enable its full visualization in one figure. Finally, for the flowtime objective, we establish a tractability frontier based on the number of directions agents can move in. Namely, we complement our hardness result, which holds for three directions, with an efficient algorithm for finding an individually optimal solution if only two directions are allowed. This result sheds new light on the structure of optimal solutions, which may help guide algorithm design for the general problem.
Abstract (translated)
多Agent 路径找到(MAPF)是存在于多种Agent 系统应用领域中的基本运动协调问题。该问题的不可解性导致了对解决它的优化程度的深入研究。由于最优解引擎难以扩展,一个主要挑战是理解是什么导致MAPF 难以解决。我们通过细致的时间最优MAPF在二维网格上的复杂度分析,从而关闭了两个间隙并确定了新的可解性前沿。首先,我们表明2-颜色MAPF,即agents 被分为两个团队,每个团队都有各自的目标,仍然是NP-难问题。其次,对于流量时间目标(也称为总成本),我们表明仍然NP-难的是找到一种解决方案,其中agents 具有个体最优成本,我们称之为个体最优解。这些MAPF 变体先前最紧的结果是针对(非网格)平面图形的(非网格)平面图形。我们使用一种单一的难性质构建来取代、加强并统一了以前的证明。我们认为它也比平面情况下的证明更简单,因为它使用了最小器件,使其在单个图像中充分可视化。最后,对于流量时间目标,我们建立了可解性前沿基于agents 可能移动的方向数。换句话说,我们补充了我们的困难结果,该结果适用于三个方向,如果只允许两个方向移动,以高效算法找到个体最优解。 This result 的新视角照亮了最优解的结构,这可能会指导算法设计对一般问题。
URL
https://arxiv.org/abs/2305.16303