跳到正文
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)问题。

正文 · 原文

View PDF HTML (experimental)

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