← 研踪 PaperTrailarXiv:2611.21277 · v1
Even Loose Proximity Constraints Make Makespan-optimal Unlabeled Multi-agent Pathfinding Hard
首次提交 2026-11-16 23:46
版本更新 2026-11-16 23:46
雷达观测 2026-11-17 16:10
摘要
We study \textsc{-Connected Unlabeled Multi-agent Pathfinding} (CUMAPF), a variant of MAPF where interchangeable agents have a proximity range , and agents must form a single group in a given graph through limited-range communication at all times. The problem arises in fundamental applications such as self-reconfiguration and platooning, while standard MAPF does not capture proximity constraints. For the problem of finding a makespan-optimal solution, prior work shows \NP-hardness for and polynomial-time solvability when is sufficiently large; the complexity for the intermediate case is largely unknown. To narrow this gap, we show that finding a solution to CUMAPF with makespan at most is \NP-hard for , where is a fixed constant and is the number of vertices. As a consequence, we show that the labeled analogue of CUMAPF is also \NP-hard under the same condition.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-16 23:46 · 最新观测版本
Even Loose Proximity Constraints Make Makespan-optimal Unlabeled Multi-agent Pathfinding Hard
We study \textsc{-Connected Unlabeled Multi-agent Pathfinding} (CUMAPF), a variant of MAPF where interchangeable agents have a proximity range , and agents must form a single group in a given graph through limited-range communication at all times. The problem arises in fundamental applications such as self-reconfiguration and platooning, while standard MAPF does not capture proximity constraints. For the problem of finding a makespan-optimal solution, prior work shows \NP-hardness for and polynomial-time solvability when is sufficiently large; the complexity for the intermediate case is largely unknown. To narrow this gap, we show that finding a solution to CUMAPF with makespan at most is \NP-hard for , where is a fixed constant and is the number of vertices. As a consequence, we show that the labeled analogue of CUMAPF is also \NP-hard under the same condition.
查看此版本解读 →查看此版本原文 ↗