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 翻译
摘要:我们研究 $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