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

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

← Home