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

正文 · AI 翻译

查看 PDF HTML(实验性)

摘要:我们研究 $r$-连通无标号多智能体路径规划($r$CUMAPF),这是 MAPF 的一个变体,其中可互换的智能体具有邻近范围 $r\in \mathbb{N}$,并且智能体必须在给定图 $G$ 中通过有限范围通信始终形成一个单一群体。该问题出现在自重构和车队编队等基础应用中,而标准 MAPF 并未刻画邻近约束。对于寻找 makespan 最优解的问题,已有工作表明当 $r=1$ 时该问题是 NP 难的,而当 $r$ 足够大时可在多项式时间内求解;中间情形 $2\le r$ 的复杂度在很大程度上仍未知。为缩小这一差距,我们证明:对于 $2\le r= O(|V|^{1-\varepsilon})$(其中 $0<\varepsilon\le 1$ 为固定常数,$|V|$ 为顶点数),寻找 makespan 至多为 $2$ 的 $r$CUMAPF 解是 NP 难的。由此,我们证明在相同条件下,$r$CUMAPF 的标号版本也是 NP 难的。
学科: 多智能体系统(cs.MA)
引用为: arXiv:2611.21277 [cs.MA]
  (或 arXiv:2611.21277v2 [cs.MA] 用于此版本)
  https://doi.org/10.48550/arXiv.2611.21277

由 DataCite 颁发的 arXiv DOI

提交历史

来自:Takahiro Suzuki [查看邮箱]
[v1] 2026年11月16日星期一 15:46:15 UTC(42 KB)
[v2] 2026年11月17日星期二 07:42:39 UTC(42 KB)

来源:arXiv cs.MA · arxiv.org