arXiv cs.MA· Takahiro Suzuki, Keisuke Okumura·· 9 小时前AI 评分18
即使宽松的邻近约束也会让 makespan 最优的无标签多智能体路径规划变难
Even Loose Proximity Constraints Make Makespan-optimal Unlabeled Multi-agent Pathfinding Hard
AI 导读
针对可互换智能体需在有限通信距离 r 内始终保持单一连通群体的 r-Connected Unlabeled Multi-agent Pathfinding(rCUMAPF)问题。
正文 · 原文
Abstract:We study $r$-Connected Unlabeled Multi-agent Pathfinding ($r$CUMAPF), a variant of MAPF where interchangeable agents have a proximity range $r\in \mathbb{N}$, and agents must form a single group in a given graph $G$ 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 $r=1$ and polynomial-time solvability when $r$ is sufficiently large; the complexity for the intermediate case $2\le r$ is largely unknown. To narrow this gap, we show that finding a solution to $r$CUMAPF with makespan at most $2$ is NP-hard for $2\le r= O(|V|^{1-\varepsilon})$, where $0<\varepsilon\le 1$ is a fixed constant and $|V|$ is the number of vertices. As a consequence, we show that the labeled analogue of $r$CUMAPF is also NP-hard under the same condition.
| Subjects: | Multiagent Systems (cs.MA) |
| Cite as: | arXiv:2611.21277 [cs.MA] |
| (or arXiv:2611.21277v2 [cs.MA] for this version) | |
| https://doi.org/10.48550/arXiv.2611.21277 arXiv-issued DOI via DataCite |
Submission history
From: Takahiro Suzuki [view email]
[v1]
Mon, 16 Nov 2026 15:46:15 UTC (42 KB)
[v2]
Tue, 17 Nov 2026 07:42:39 UTC (42 KB)
来源:arXiv cs.MA · arxiv.org