跳到正文
arXiv cs.MA· Andy Li, Zhe Chen, Danial Harabor, Mor Vered·· 23 小时前AI 评分19

论文重新审视 CCBS:连续时间多智能体路径规划算法被证明不完备

CBS with Continuous-Time Revisit

AI 导读

一篇 arXiv 论文重新审视 CCBS(Conflict-Based Search with Continuous Time)的理论主张,证明该算法因连续等待时长造成不可数无限状态空间而不完备。

正文 · AI 翻译

查看 PDF HTML(实验性)

摘要:连续时间多智能体路径规划(\mapfr)通过允许智能体在连续时间中运行,扩展了经典的 MAPF 问题。连续时间冲突基搜索(CCBS)是求解 \mapfr 最优解的基础算法。本文重新审视 CCBS 的理论主张,并证明该算法是不完备的,原因在于连续等待时长造成了不可数无限的状态空间。通过理论分析和反例,我们考察了将现有 MAPF 求解器扩展以处理 \mapfr 并同时保持最优性保证所固有的挑战。通过将等待时长限制为固定值,我们识别出图上的一个相关子问题 \mapfrdt,并证明该子问题可最优求解,包括用 CCBS 求解。对于 \mapfrct(\mapfrdt 的推广版本,允许任意等待时间)以及 \mapfrcs(进一步允许在连续空间中任意移动),是否存在类似的模型仍是一个开放问题。
主题: 多智能体系统(cs.MA)
引用为: arXiv:2501.07744 [cs.MA]
  (或 arXiv:2501.07744v4 [cs.MA] 查看此版本)
  https://doi.org/10.48550/arXiv.2501.07744

由 DataCite 颁发的 arXiv DOI

提交历史

来自:Andy Li [查看邮箱]
[v1] 2025年1月13日星期一 23:14:38 UTC(347 KB)
[v2] 2025年4月17日星期四 00:46:08 UTC(344 KB)
[v3] 2025年8月28日星期四 06:22:22 UTC(385 KB)
[v4] 2026年11月18日星期三 01:28:36 UTC(574 KB)

来源:arXiv cs.MA · arxiv.org