CBS with Continuous-Time Revisit

arXiv:2501.07744 · cs.MA · Submitted 2025-01-13 · Read on arXiv

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

Where the paper says it

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.

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

Where the paper says it

We then prove that the constraint generation method employed by CCBS inherently leads to incompleteness (i. , there is no simple fix).

This issue stems from the ambiguity in defining constraints for waiting agents, leading to two interpretations: wait durations are specified a priori or computed dynamically. p. 1
Where the paper says it

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.

Analysis of Constraint Interpretations

The paper details two interpretations of constraints for resolving conflicts between moving and waiting agents.

  1. 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

    Where 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.

    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. 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.

  2. 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

    Where 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.

    This model is also incomplete because a pair of vertex and motion constraints can eliminate feasible solutions, as shown in Figure 1. p. 5
    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

Where the paper says it

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.

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

Where the paper says it

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.

The authors suggest that meaningful progress requires either novel constraints within CCBS or entirely new algorithmic approaches to address the continuous temporal domain.

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

Where the paper says it

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.

This property is crucial for maintaining both completeness and optimality in the continuous domain. p. 9
Where the paper says it

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?

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

Where the paper says it

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.

The paper emphasizes the necessity of exploring an entirely different approach to tackle the incompleteness challenge in CCBS. p. 7
Where the paper says it

□ 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.

The authors believe meaningful progress requires either novel constraints within the CCBS framework or entirely new algorithmic approaches.

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

Where the paper says it

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.

Although the non-optimal version of MAPFR-NO is solvable in polynomial time, the question of optimal solvability for MAPFR-NO remains open. p. 0
Where the paper says it

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.

The authors stress that establishing the solvability of general MAPFR is a critical step. p. 1
Where the paper says it

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.

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

Where the paper says it

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.

This interval also serves as the time range of the range constraint for an agent waiting at a vertex. p. 7
Where the paper says it

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 𝑣.

The authors present a counter example showing how eliminating such a situation leads to a suboptimal solution when using vertex and motion constraints. p. 5
Where the paper says it

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 final CCBS solution cost was 34. p. 3
Where the paper says it

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.

6.

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

Where the paper says it

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.

This illustrates that the current CCBS implementation is incomplete and may return suboptimal solutions. p. 5
Where the paper says it

(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 authors note that the CCBS implementation expanded 780 high-level nodes before finding the solution, indicating this instance is non-trivial. p. 3
Where the paper says it

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.

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

Where the paper says it

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.

The authors state that the pair of vertex and motion constraints violates Claim 1, hence they are not sound. p. 3
Where the paper says it

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.

This goes to show that the current CCBS implementation is incomplete and may return suboptimal solutions. p. 0
Where the paper says it

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 authors note that the CCBS implementation expanded 780 high-level node before finding the solution, thus, this instance is non-trivial. p. 3
Where the paper says it

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.

References

The paper cites several related works including Andreychuk et al. (2022) and Walker et al. p. 1

Where the paper says it

Continuous Time CBS (CCBS) Andreychuk et al. (2022) is claimed to be the first optimal algorithm for solving this problem.

(2024a). The authors also reference Kornhauser et al. p. 0
Where the paper says it

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.

(1984) regarding the Pebble Motion Problem. p. 1
Where the paper says it

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 paper also cites Walker et al. p. 1
Where the paper says it

The algorithm is widely popular in the literature and several subsequent works provide further improvements Andreychuk et al. (2021); Walker et al.

(2024b) and Andreychuk et al. p. 1
Where the paper says it

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.

(2021) in relation to improvements to conflict-based search. p. 1
Where the paper says it

The algorithm is widely popular in the literature and several subsequent works provide further improvements Andreychuk et al. (2021); Walker et al.

The paper includes references to various other works on multi-agent pathfinding and conflict-based search. p. 0
Where the paper says it

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.

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

  1. 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.

  2. 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).

  3. 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.

  4. Handling Physical Interference: Integrate mechanisms to model and resolve Edge Overlapping where a waiting agent blocks an edge, and Vertex 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

Related papers