The paper studies continuous-time Multi-Agent Path Finding with geometric motion, timed actions, waiting, and collision avoidance among multiple agents sharing an environment. In classical MAPF, time is discretized, whereas the MAPF-R formulation considered here represents motion and action durations in continuous time. Each agent must move from a start vertex to a goal vertex, and the central objective is to find collision-free plans with minimum cost, primarily sum of costs, or SOC. The work focuses on the theoretical reliability of exact search rather than merely finding feasible paths.
The first contribution is a framework for analyzing CCBS-style branching rules through the notion of sound constraint pairs. A branching rule is sound when its expansion does not remove all valid plans that could be part of a solution. The paper then introduces Optimal Continuous-time Conflict-Based Search, or OC-CBS, with a branching rule satisfying this condition. It proves that OC-CBS is exact and solution complete under the stated assumptions, and argues that it can replace CCBS in existing methods that relied on CCBS correctness guarantees. The supplied excerpt does not establish that every existing continuation method has been reimplemented or empirically reevaluated.
CCBS-style algorithms search a constraint tree. When a collision is found in a set of individual agent plans, the algorithm creates child nodes by adding constraints intended to prevent the conflicting behavior. The paper decomposes motion and vertex restrictions into sets of forbidding constraints and defines soundness in terms of preserving at least one relevant valid plan during branching. It proves that the soundness of the branching rule is equivalent to the soundness of the underlying pair of constraint sets. This result is combined with a lower-bound property on constraint-tree objective values supplied by the low-level planner, and with a finite-termination argument, to establish exactness and solution completeness. The OC-CBS implementation builds on the public CCBS implementation and uses analytical interval computation rather than a binary search with a specified precision. The reported implementation assumes circular agents, straight-line traversals, constant speed, and finite-precision arithmetic.
The evaluation compares publicly available CCBS with OC-CBS, where the principal difference is the branching rule. It includes a constructed counterexample, benchmark comparisons of solution quality and runtime, and an ablation study of the parameter used by the OC-CBS branching rule. The experiments use circular agents moving along edges in straight lines at constant speed and optimize SOC; the reported setup also discusses makespan and computation time. Runs were performed on a 2025 Mac Studio with a 16-core M4 Max CPU, 64 GB of memory, and macOS Sequoia 15.3. The supplied excerpt does not provide the complete benchmark inventory, all numerical measurements, averages, variability, or statistical tests, so those facts cannot be inferred here.
The central failure mode is that CCBS's implemented branching rule is unsound for some move-wait conflicts. It can remove valid solutions from the search, which means CCBS can return a suboptimal solution even though it has commonly been treated as an exact baseline. This matters beyond CCBS itself because theoretical guarantees of methods built on top of it may depend on a correctness property that does not actually hold. OC-CBS addresses the root cause by changing the branching rule rather than abandoning conflict-based search. Its formal guarantees do not by themselves establish that it is faster on every instance, and the excerpt does not report a universal runtime advantage. The parameter ablation is explicitly limited to the studied gridlike roadmaps; its conclusions may differ for other map families, obstacle patterns, start-goal configurations, or agent geometries. The framework is presented as a basis for future exact MAPF-R solver design, but the supplied material does not specify a complete agenda or quantify all remaining scalability limitations.
Multi-Agent Path Finding asks several agents to reach individual goals in a shared environment without collisions or deadlocks. It has applications in warehouses, factories, video games, traffic management, airport surface operations, and search and rescue. Classical optimal MAPF is NP-hard, motivating both suboptimal strategies such as prioritization and restricted time windows and exact methods such as Conflict-Based Search. Continuous-time variants are needed when motion durations and collision timing cannot be represented faithfully by discrete time steps.
A MAPF-R instance is represented using a directed graph embedded in a two-dimensional metric space, together with mappings from agents to start and goal vertices and a finite set of move actions. A move action describes one possible way to traverse an edge and has a motion function from time to position, with a duration and specified start and end locations. An individual plan is a finite sequence of timed actions whose transitions are temporally and spatially consistent. The final action is an infinite wait, capturing that an agent remains at its last location indefinitely. The optimization problem is to select valid plans for all agents while avoiding collisions and minimizing the chosen objective.
The paper distinguishes soundness, exactness, and solution completeness. Soundness concerns whether branching preserves valid solutions; exactness concerns returning an optimal solution; solution completeness concerns terminating with a solution on every solvable instance. A key lemma establishes that a pair of constraint sets is sound exactly when the corresponding branching rule is sound. The main theoretical route is then to combine a sound branching rule with a lower-bound property for constraint-tree nodes and a finite-termination proof. These ingredients support the claims that OC-CBS is exact and solution complete under the paper's assumptions.
The experimental code includes the public CCBS implementation and the authors' OC-CBS implementation. The counterexample contains four agents and is designed to expose a choice between waiting interactions that the original branching rule handles incorrectly. Benchmark experiments compare solution quality and runtime, while the ablation varies the parameter associated with OC-CBS's branching rule. The implementation uses circular agents with a radius, straight-line edge traversal, constant speed, and SOC optimization. The excerpt does not state the full number of maps, instances, or trials.
On the constructed counterexample, OC-CBS is reported to produce lower SOC, lower makespan, and lower computation time than CCBS. The authors also validate the optimality of OC-CBS's solution for that specific problem by constructing a tailored Satisfiability Modulo Theory model and solving it with Z3; the excerpt says confirmation took roughly hours but does not give a more precise duration. Across the benchmark evaluation, OC-CBS is described as competitive with CCBS in runtime and as occasionally producing better solutions. No exact aggregate speedup, solved-instance count, or distribution of objective values is supplied in the evidence provided here.
The paper concludes that OC-CBS is an exact and solution-complete continuous-time MAPF solver under finite-precision arithmetic and the stated modeling assumptions. It repairs a gap caused by the invalidated correctness guarantees of CCBS and can serve as a replacement in systems that depend on CCBS. The analytical treatment of constraint soundness and termination is also intended as a reusable foundation for evaluating and designing future CCBS-like solvers. The authors characterize the work both as a correction to the CCBS lineage and as a step toward a more rigorous theory of optimal continuous-time MAPF.
The empirical implementation uses a specific geometric model: circular agents, straight-line motion, and constant speed. Runtime competitiveness is reported, but the supplied excerpt does not establish dominance over CCBS across all instances or hardware. The ablation study's conclusions are limited to the studied gridlike roadmaps, and the authors warn that other map structures, obstacle arrangements, start-goal assignments, and agent geometries may behave differently. The evidence provided also does not describe experiments with alternative motion models, larger classes of agents, or a full scalability analysis.
The work is important because it challenges an assumption embedded in a widely used exact baseline for continuous-time MAPF. It shows that a theoretically plausible search framework can lose optimality through a concrete implementation choice in its branching rule. OC-CBS supplies both a corrective algorithm and explicit criteria for checking whether future CCBS-like methods preserve solutions. This can improve the reliability of comparative studies and of continuation methods whose guarantees depend on an exact low-level or high-level solver.
The paper is recommended for researchers working on continuous-time MAPF, MAPF-R, CCBS, CBS, and formal guarantees for multi-agent planning. It is especially relevant to readers maintaining CCBS-based systems, studying the correctness of branching rules, or designing exact solvers with continuous collision geometry. It is also useful for survey readers who need to separate feasibility, soundness, optimality, and solution completeness. Readers seeking a comprehensive numerical comparison across many motion models or a complete scalability study should consult the full paper, because those details are not established by the supplied excerpt.