arXiv cs.AI· Foivos Fioravantes, Du\v{s}an Knop, Jan Maty\'a\v{s} K\v{r}i\v{s}\v{t}an, Nikolaos Melissinos, Michal Opler·· 13 小时前AI 评分18
树状结构上带通信约束的多智能体路径规划精确算法
Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
AI 导读
针对带通信约束的多智能体路径规划问题，研究者给出三个精确算法，在输入网络为树拓扑、最大度有界或树宽有界时高效求解。这些算法分别以通信范围、智能体数量或 makespan 为参数。作者同时证明，即使 makespan 为 3、通信范围为 1，以智能体数量为参数也难以构造高效算法。
正文 · AI 翻译
摘要：考虑这样一个场景：多个智能体必须在网络中各自以最优方式移动，每个智能体都朝着自己的终点位置前进，同时避免碰撞。所谓最优，是指尽可能快，这由一种称为所提方案完工时间（makespan）的度量来评估。这就是多智能体路径规划问题所研究的设定。在本工作中，我们额外为智能体提供了一种相互通信的方式。由于规模限制，可以合理地假设每个智能体的通信范围是有限的。那么，为了额外维持一条通信骨干，智能体的轨迹应当是怎样的？在本工作中，我们在参数化复杂度框架下研究了带通信约束的多智能体路径规划问题。
我们的主要贡献是三个精确算法，当考虑输入网络的特定结构时，这些算法是高效的。我们针对以下情形提供了此类算法：通信范围和智能体数量（分别对应完工时间）在输入中给出，且网络具有树形拓扑，或最大度有界（分别具有类树拓扑，即树宽有界）。我们通过证明以下结论来补充这些结果：当把智能体数量作为输入的一部分时，即使完工时间为 $3$ 且通信范围为 $1$，也极不可能构造出高效算法。
| 评论： | 论文最终版本，发表于 Journal of Artificial Intelligence Research |
| 主题： | 计算复杂性（cs.CC）；人工智能（cs.AI） |
| 引用为： | arXiv:2412.08556 [cs.CC] |
| （或本版本使用 arXiv:2412.08556v4 [cs.CC]） | |
| https://doi.org/10.48550/arXiv.2412.08556 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Foivos Fioravantes [查看邮箱]
[v1]
2024年12月11日星期三 17:17:31 UTC（35 KB）
[v2]
2024年12月12日星期四 09:51:26 UTC（35 KB）
[v3]
2025年5月30日星期五 16:14:52 UTC（841 KB）
[v4]
2026年10月28日星期三 19:22:50 UTC（841 KB）
来源：arXiv cs.AI · arxiv.org