Can CCBS reliably solve continuous-time MAPF?
CBS with Continuous-Time Revisit
This paper analyzes the completeness and optimality of Conflict-Based Search with Continuous Time (CCBS), an algorithm designed for Multi-Agent Path Finding in Continuous Time (MAPFR), where agents move in continuous space and time. It finds that CCBS, as originally designed, is incomplete because it cannot guarantee termination when dealing with wait actions of arbitrary durations. This arises because resolving conflicts involving wait actions requires eliminating single points in a continuous time domain, leaving infinitely many equivalent collision solutions. The authors explore alternative implementations, including the existing CCBS implementation which uses vertex constraints, but these also prove to be incomplete or suboptimal. They propose "shifting constraints" as a potentially sounder alternative but ultimately demonstrate that even this approach doesn't guarantee termination.
For LLM-based multi-agent systems, the key takeaway is the difficulty of guaranteeing completeness and optimality in continuous time and space. LLMs, when used as agents, often involve continuous outputs or actions (e.g., generating text, controlling a robot in continuous space), which makes direct application of algorithms like CCBS challenging. This research highlights the need for new approaches to conflict resolution and path planning in multi-agent systems that operate in continuous domains, an issue that becomes particularly relevant when dealing with LLM-based agents. The paper’s exploration of different constraint types provides valuable insights for designing conflict resolution mechanisms in such systems.