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 翻译
摘要:连续时间多智能体路径规划(\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