CBS with Continuous-Time Revisit
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "CBS with Continuous-Time Revisit".
Title and authors: Tom: So we're looking at this paper "CBS with Continuous-Time Revisit," and it focuses on how continuous time complicates the classic Conflict Based Search.
Jane: They are showing that CCBS, which is supposed to be optimal for MAPFR, actually has issues because of those continuous wait times.
Tom: It boils down to the fact that there are uncountably infinite possibilities when you consider how long an agent can wait before it moves in a continuous setting.
Lu: They prove that the way CCBS generates constraints inherently leads to incompleteness, meaning there's no simple fix for this problem.
Meng: So if we're building a system, we can't just keep adding more constraints hoping it gets us there because the underlying structure itself is flawed.
Lalam: They break down the ambiguity by looking at two ways to interpret those waiting agents: either the wait times are fixed beforehand, or they are calculated dynamically during the search.
The paper's summary: Tom: So what they summarize is that under both interpretations of how those wait durations work, CCBS ends up being either unsound, incomplete, or both.
Jane: It means that the original claim that CCBS is the first optimal algorithm for MAPFR in continuous environments is not fully supported by their analysis.
Tom: They look at two specific sub-problems to get a better handle on this: one called MAPFR-NO and another called MAPFR-DT.
Lu: In MAPFR-NO, they restrict interactions between moving agents and waiting agents down only to vertex collisions, which they show is solvable by reducing it to the Pebble Motion Problem, though not by using CCBS itself.
Meng: So for that restricted case, we can guarantee a solution exists, but CCBS isn't the tool that finds it optimally in that specific setup.
Lalam: Then there's MAPFR-DT where they restrict wait durations to fixed amounts, like unit duration, and they show that this version is actually optimally solvable by CCBS because the state space becomes countable.
The paper's improvements: Tom: The paper suggests a couple of ways to try and fix this, looking at two different constraint interpretations: motion constraints assuming fixed wait times versus vertex range constraints assuming dynamically computed ones.
Jane: They show that even those two approaches have their own problems; one leads to non-termination because there are too many waiting motions that could collide.
Lu: The second interpretation, where a vertex range constraint forbids any waiting motion from overlapping the interval regardless of when it starts, is also incomplete because a pair of constraints can eliminate all feasible solutions at once.
Meng: That's tough to debug at scale; you'd need a way to handle those complex interactions without eliminating good solutions just by applying constraints.
Lalam: They also look at related problems like MAPFR-NO again, and they show that while the non-optimal version is solvable in polynomial time, proving optimal solvability for the general problem remains an open question.
Conclusion: Tom: So to wrap up, the paper "CBS with Continuous-Time Revisit" shows that CCBS isn't sound or complete because of the infinite state space from continuous wait durations.
Jane: The main thing is that solving general MAPFR in continuous time still feels like a problem we haven't fully cracked yet, and it needs a fundamentally new approach to handle the time aspect.
Lu: They point out that for completeness, you need two things: the state space has to be countable, and all step costs have to be non-negative.
Meng: And they argue that any real extension of CCBS must introduce a brand new type of constraint so that a finite number of constraints can actually bring the solution cost down to any arbitrary finite value.
Lalam: Ultimately, the paper says we need either novel constraints inside CCBS or entirely different algorithmic approaches to tackle this continuous temporal domain.
Andy Li, Zhe Chen, Mor Vered, Daniel Harabor
Monash University
cs.MA
Submitted: 2025-01-13
Updated: 2026-11-18
Code: https://github.com/PathPlanning/Continuous-CBS
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
The gist: Multi-Agent Path Finding in Continuous Time (MAPFR) extends the classical MAPF problem by allowing agents to operate in continuous time and conflict-based search with continuous time (CCBS) is found…
Key concepts
- Incompleteness of CCBS
- CCBS fails for MAPFR because continuous wait times lead to an uncountably infinite state space. This means the search algorithm can never guarantee finding a solution or terminating reliably, as there is no simple way to define constraints for these continuous waiting periods.
- Motion Constraints (A Priori Wait)
- This interpretation assumes wait durations are fixed beforehand. A motion constraint forbids starting an action during a specific time interval. However, this approach is incomplete because uncountably many possible wait motions can still collide with the planned movement, leading to non-termination.
- Vertex Range Constraints (Dynamic Wait)
- This interpretation computes wait durations dynamically. A vertex range constraint prevents any waiting motion from overlapping a forbidden time interval at a specific vertex, regardless of when the waiting action begins. This model is also incomplete because certain combinations of constraints can eliminate all feasible solutions.
Terminology
Summary
Multi-Agent Path Finding in Continuous Time (MAPFR) extends the classical MAPF problem by allowing agents to operate in continuous time and conflict-based search with continuous time (CCBS) is found to be incomplete due to an uncountably infinite state space created by continuous wait durations. p. 0 Revisiting Conflict Based Search with Continuous-Time
ANDY LI, Monash University, Australia
ZHE CHEN, Monash University, Australia
MOR VERED, Monash University, Australia
DANIEL HARABOR, Monash University, Australia
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.Where the paper says it
Incompleteness of CCBS
The paper revisits the theoretical claims of CCBS and shows the algorithm is incomplete because of an uncountably infinite state space arising from continuous wait durations. The authors prove that the constraint generation method used by CCBS inherently leads to incompleteness, meaning there is no simple fix. p. 0 We then prove that the constraint generation method employed by
CCBS inherently leads to incompleteness (i. , there is no simple fix). In this work, we show that the original constraint definition in CCBS Andreychuk et al. (2022)
leads to two distinct interpretations regarding wait actions: the first interpretation assumes wait durations are
specified a priori, the second assumes durations are computed dynamically.Where the paper says it
Where the paper says it
Analysis of Constraint Interpretations
The paper details two interpretations of constraints for resolving conflicts between moving and waiting agents.
-
Motion Constraints assume wait durations are specified a priori, where a motion constraint forbids the start of an action within a constraint interval. p. 3
However, Lemma 3 demonstrates that this leads to non-termination because there are uncountably many wait motions at a vertex that can collide with the conflicting motion. p. 4Where the paper says it
For the sake of clarity, we assign distinct names to each interpretation: • Waiting durations are determined a priori: In this model, the respective constraint, termed a motion constraint, forbids the start of an action (whether movement or wait) within the constraint interval. We analyse CCBS with motion constraints in Section 4.
Where the paper says it
Thus, each constraint only forbids a single wait motion at vertex 𝑣1. However, there are uncountably many wait motions at 𝑣1 that can collide with the conflicting motion 𝑚𝑗@𝑡2 and it becomes infeasible to resolve such conflicts through motion constraints alone: lemma 3.
-
Vertex Range Constraints assume wait durations are computed dynamically, where a vertex range constraint forbids any waiting motion from overlapping with the constraint interval regardless of when it starts. p. 3
This model is also incomplete because a pair of vertex and motion constraints can eliminate feasible solutions, as shown in Figure 1. p. 5Where the paper says it
We analyse CCBS with motion constraints in Section 4. • Waiting durations are computed dynamically: In this model, the respective constraint, termed a vertex range constraint, forbids any waiting motion from overlapping with the constraint interval, regardless of when it starts.
Where the paper says it
1 Elimination of Feasible Solutions We observe that the combination of a vertex range and motion constraints pair is not sound, as it eliminates feasible solutions. An example illustrating the problem is shown in Figure 1.
Variants and Solvability Results
The authors investigate two related sub-problems to better understand the technical challenges.
MAPFR-NO
This problem restricts interactions between moving and waiting agents to vertex collisions only, leading to a reduction to the Pebble Motion Problem which establishes solvability guarantees for this special case but not by CCBS.
MAPFR-DT
This problem restricts wait durations to fixed amounts (unit duration), showing that the problem is optimally solvable, including by CCBS. The state space of MAPFR-DT is countable, and CCBS is sound and complete for this variant. p. 8 Revisiting Conflict Based Search with Continuous-Time • 111:9
In this section we attempt to clarify the situation by introducing MAPFR-Discrete Time (MAPFR-DT for short),
a variant of MAPFR which restricts all wait durations to a single unit-time interval. We show that the state-space
of MAPFR-DT remains countable, unlike MAPFR.Where the paper says it
Implications for General MAPFR
The paper concludes by noting that the primary challenge in solving general MAPFR lies in handling continuous wait durations. While MAPFR-DT is solvable, the solvability of the general MAPFR problem remains unknown. p. 9 This raises an important open question: how
can we solve the MAPFR problem efficiently, or even determine whether it is solvable in the general case? 8 Toward Solvability for MAPFR
It is unclear whether theoretical guarantees which hold for MAPFR-DT also hold for MAPFR.Where the paper says it
Essential Conditions for Optimality
Mapping the MAPF problem to a tree search framework requires two fundamental conditions for completeness: (1) The state space must be countable (either finite or countably infinite), and (2) All step costs must be non-negative. The authors argue that an effective extension of CCBS must introduce a novel type of constraint to ensure that a finite number of constraints can raise the solution cost lower bound to any arbitrary finite value C. p. 8 Furthermore, from Lemma 4, we know that the solution space for any MAPFR-DT instance
is countable. Since all motion costs are positive and fixed, and the number of agents is finite, this implies that the
number of valid (collision-free) solutions under any given cost bound is also finite. 111:10 • Andy Li, Zhe Chen, Mor Vered, and Daniel Harabor
leads to infinite expansions due to its continuous temporal domain. This raises an important open question: how
can we solve the MAPFR problem efficiently, or even determine whether it is solvable in the general case?Where the paper says it
Where the paper says it
Conclusion on CCBS Limitations
The findings fundamentally undermine the completeness and optimality guarantees of CCBS and its many enhancements because they lead to unsound termination or unbounded expansion. All improvements directly built upon CCBS are similarly affected. p. 7 Such results underscore the necessity of exploring an entirely different approach to tackle the incompleteness
challenge in CCBS, or to solve the MAPFR problem optimally in an entirely different way. 7 MAPFR with Discrete Time
Upon its introduction the MAPFR problem was defined to support arbitrary-duration wait motions Walker et al. □
Theorem 3 and Property 1 show that patching the termination failure issue in CCBS is non-trivial, and even hints
at fundamental limitations of relying on pairs of motion and vertex range constraints to achieve completeness. Such results underscore the necessity of exploring an entirely different approach to tackle the incompleteness
challenge in CCBS, or to solve the MAPFR problem optimally in an entirely different way.Where the paper says it
Where the paper says it
Future Directions
The paper highlights two types of spatial interference caused by agents waiting in MAPFR: Edge Overlapping and Vertex Overlapping. The authors define a special subclass called MAPFR-Non-Overlapping to exclude these complications. p. 9 This spatial interference significantly complicates conflict resolution and motion planning. We define two types of spatial interference caused by agents waiting in MAPFR:
• Edge Overlapping: This occurs when a waiting agent blocks the traversal of an edge due to its physical
presence. In the case of MAPFR-DT, we show that the problem is optimally solvable
including by CCBS. It remains an open question whether MAPFR, which allows arbitrary wait durations, is optimally solvable. With this additional restriction we can derive a reduction to the Pebble Motion Problem Kornhauser
et al. (1984) and thus establish solvability guarantees for a special case of the general MAPFR problem, but not
for CCBS.Where the paper says it
Where the paper says it
Where the paper says it
A Computing Collision Interval
The paper provides a detailed example on how collision interval is computed in implementation. Following the conceptual example in Figure 3, the collision interval between a wait action and a move action is defined as (t0 + (M, H)2 − (P1, H)2, t1). p. 8 Furthermore, each motion
has an associated cost comprised of the following:
• Each move action 𝑒𝑗 has a fixed cost 𝑒𝑗
. 𝐷, and;
• The wait action, 𝑤𝑣 , has a fixed cost, typically 1 unit cost per wait. Therefore, the conflict is not resolved in the child node with
the vertex range constraint. If the 𝛿 = 0, then the constraint interval I on 𝑚𝑗 becomes a single real number
(constraint on a single time) that does not eliminate the conflict between any 𝑚𝑗@(𝑡𝑗 + 𝑑), 𝑑 ∈ (0, |𝐼𝑐 |] and an
agent occupying vertex 𝑣. This example empirically proves that a pair of vertex and motion constraints, is not complete. In Appendix B, we
provide a concrete example where eliminating such a situation leads to a suboptimal solution. The first condition ensures that any valid solution can be reached through one of the un-expanded CT nodes. Since CCBS conducts a best-first search over the CT and prioritises expanding CT nodes with the lowest cost, the
second condition enables CCBS to guarantee finding an optimal MAPFR solution.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
B Counter Example
A concrete example is presented where eliminating such a situation leads to a suboptimal solution. In this example, the constraints generated by CCBS eliminate the solution of agents a1 and a2 performing wait motions prior to departing. p. 5 These constraints eliminate the collision-free solution where agent 𝑎1 waits for a while and then departs (represented by the orange arrowed lines), and agent 𝑎2 also waits before leaving and returning (blue arrowed lines). This example empirically proves that a pair of vertex and motion constraints, is not complete. (2024), including in the original implementation of CCBS1
. While
vertex range constraints often lead to empirical termination, a closer examination reveals that this model is also
incomplete, although the problem arises in a different manner than for motion constraints (which we discuss
in Section 4). The first condition ensures that any valid solution can be reached through one of the un-expanded CT nodes. Since CCBS conducts a best-first search over the CT and prioritises expanding CT nodes with the lowest cost, the
second condition enables CCBS to guarantee finding an optimal MAPFR solution.Where the paper says it
Where the paper says it
Where the paper says it
Acknowledgment
The authors give special thanks to the original authors of CCBS for their valuable feedback on an earlier version of this handcrafted solution. Their input helped reduce its cost and improve its robustness against floating-point precision errors. p. 0 Classical MAPF models Stern et al. (2019) reduce these problems to a simplified (grid-based, unit-cost)
combinatorial core, which is nonetheless NP-hard Yu and LaValle (2013); Banfi et al. CCBS then makes the following claims:
claim 1. The pair of constraints for resolving a conflict is sound, and any MAPFR solution that violates both
constraints must have a conflict:
lemma 1. 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. The first condition ensures that any valid solution can be reached through one of the un-expanded CT nodes. Since CCBS conducts a best-first search over the CT and prioritises expanding CT nodes with the lowest cost, the
second condition enables CCBS to guarantee finding an optimal MAPFR solution.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
References
The paper cites several related works including Andreychuk et al. (2022) and Walker et al. p. 1 Continuous
Time CBS (CCBS) Andreychuk et al. (2022) is claimed to be the first optimal algorithm for solving this problem. It remains an open question whether MAPFR, which allows arbitrary wait durations, is optimally solvable. JAIR Track: Insert JAIR Track Name Here
JAIR Associate Editor: Insert JAIR AE Name
JAIR Reference Format:
Andy Li, Zhe Chen, Mor Vered, and Daniel Harabor. With this additional restriction we can derive a reduction to the Pebble Motion Problem Kornhauser
et al. (1984) and thus establish solvability guarantees for a special case of the general MAPFR problem, but not
for CCBS. The algorithm is widely popular in the literature and several subsequent works provide further improvements
Andreychuk et al. (2021); Walker et al. MAPFR extends the classical MAPF model by generalising the time dimension to real-valued domains, allowing
agents to move in continuous time and wait for any arbitrary amount of real-valued time duration. Continuous
Time CBS (CCBS) Andreychuk et al. The algorithm is widely popular in the literature and several subsequent works provide further improvements
Andreychuk et al. (2021); Walker et al. Revisiting Conflict Based Search with Continuous-Time
ANDY LI, Monash University, Australia
ZHE CHEN, Monash University, Australia
MOR VERED, Monash University, Australia
DANIEL HARABOR, Monash University, Australia
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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Sound Pair of Shifting Constraints: Implement a method to construct a pair of sound constraints that is not limited to shifting constraints, aiming to resolve conflicts without eliminating feasible solutions when using vertex range and motion constraints together. This would address the finding that
a pair of vertex and motion constraints, is not complete
by providing a mechanism for more robust constraint generation. -
Novel Constraint Modeling: Develop a constraint reasoning model that moves beyond the two interpretations (motion constraints vs. vertex range constraints) to handle arbitrary wait durations soundly and completely. This could involve exploring an
entirely different approach to tackle the incompleteness challenge in CCBS,
as suggested by the authors, potentially utilizing techniques from Satisfiability Modulo Theories (SMT-CBS). -
Solvability Verification for General MAPFR: Create a framework to determine whether a general MAPFR instance is solvable, moving beyond current reliance on solvers that only guarantee completeness for the restricted MAPFR-DT variant. This system should provide guarantees for the original problem by addressing the challenges posed by continuous temporal reasoning and physical agent interference like Edge Overlapping and Vertex Overlapping.
-
Handling Physical Interference: Integrate mechanisms to model and resolve
Edge Overlapping
where a waiting agent blocks an edge, andVertex Overlapping
where waiting agents physically collide even if at distinct vertices. This would allow the system to account for the physical embodiment of agents as described in Section 8.
Abstract
Multi-Agent Path Finding in Continuous Time 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 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 while preserving optimality guarantees. By restricting waiting duration to fixed amounts, we identify a related sub-problem on graphs, which we show is optimally solvable, including by CCBS. It remains an open question whether similar models exist for, a generalised version of that allows arbitrary wait times, and, which further allows arbitrary movements in continuous space.
Sources
- Prioritized Planning for Continuous-time Lifelong Multi-agent Pathfinding
- Collision Detection for Agents in Multi-Agent Pathfinding
Related papers
- MultiAgentBench: Evaluating the Collaboration and Competition of LLM agents
- Iterative Negotiation and Oversight: A Case Study in Decentralized Air Traffic Management
- Towards using Large Language Models for Risk Negotiation and Consensus-building in One Health contexts
- A-MapReduce: Executing Wide Search via Agentic MapReduce
- AgentCue: Statistical Summaries for Guiding Decentralized Multi-Agent Self-Organization
- Events as Triggers for Behavioral Diversity in Multi-Agent Reinforcement Learning