跳到正文
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)的理论主张,证明该算法因连续等待时长造成不可数无限状态空间而不完备。

正文 · 原文

View PDF HTML (experimental)

Abstract:Multi-Agent Path Finding in Continuous Time (\mapfr) extends the classical MAPF problem by allowing agents to operate in continuous time. Conflict-Based Search with Continuous Time (CCBS) is a foundational algorithm for solving \mapfr optimally. In this paper, we revisit the theoretical claims of CCBS and show the algorithm is incomplete, due to an uncountably infinite state space created by continuous wait durations. Through theoretical analysis and counter-examples, we examine the inherent challenges of extending existing MAPF solvers to address \mapfr while preserving optimality guarantees. By restricting waiting duration to fixed amounts, we identify a related sub-problem on graphs, \mapfrdt which we show is optimally solvable, including by CCBS. It remains an open question whether similar models exist for \mapfrct, a generalised version of \mapfrdt that allows arbitrary wait times, and \mapfrcs, which further allows arbitrary movements in continuous space.
Subjects: Multiagent Systems (cs.MA)
Cite as: arXiv:2501.07744 [cs.MA]
  (or arXiv:2501.07744v4 [cs.MA] for this version)
  https://doi.org/10.48550/arXiv.2501.07744

arXiv-issued DOI via DataCite

Submission history

From: Andy Li [view email]
[v1] Mon, 13 Jan 2025 23:14:38 UTC (347 KB)
[v2] Thu, 17 Apr 2025 00:46:08 UTC (344 KB)
[v3] Thu, 28 Aug 2025 06:22:22 UTC (385 KB)
[v4] Wed, 18 Nov 2026 01:28:36 UTC (574 KB)

来源:arXiv cs.MA · arxiv.org