CBS with Continuous-Time Revisit
summary
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…
In short
This work investigates Multi-Agent Path Finding in Continuous Time (MAPFR) using Conflict-Based Search with Continuous Time (CCBS). The research reveals that CCBS is incomplete because continuous wait durations create an infinite state space. Analyzing constraint interpretations shows existing methods fail under certain conditions, necessitating new approaches to achieve sound and complete solutions for general MAPFR.
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 used across episodes
This episode discusses
- CBS with Continuous-Time Revisit · Paper Radio
- Prioritized Planning for Continuous-time Lifelong Multi-agent Pathfinding
- Collision Detection for Agents in Multi-Agent Pathfinding
The paper
CBS with Continuous-Time Revisit · Read on arXiv
Andy Li, Zhe Chen, Mor Vered, Daniel Harabor
Monash University
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.
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.
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game