Conflict-Based Search (CBS)

CBS operates on two distinct levels. The high-level search explores a Constraint Tree (CT), where each node contains a set of constraints and a solution. The low-level search is a single-agent path planner (like A*) that finds optimal paths for each agent, respecting the constraints passed down from the high level. This separation of concerns allows CBS to be agent-independent at the low level, meaning any single-agent planner can be used as a subroutine.

The core data structure is a binary Constraint Tree. Each node contains:

• A set of constraints (agent, vertex, timestep).
• A solution: a set of individual agent paths satisfying those constraints.
• A total cost (e.g., sum of path lengths).

When the high-level search finds a conflict (e.g., two agents occupying the same vertex at the same timestep), it generates two child nodes. Each child inherits the parent's constraints plus one new constraint forbidding one agent from being at the conflict location at that timestep. This recursively splits the search space to resolve the conflict.

CBS is provably optimal for common MAPF objectives like Sum of Costs (total timesteps) or Makespan (maximum finish time), provided the low-level planner is optimal for individual agents. The high-level search explores the CT in a best-first order (typically using a priority queue sorted by solution cost). Because it expands the lowest-cost node first, the first conflict-free solution found is guaranteed to be optimal. This makes it a complete algorithm.

CBS explicitly identifies and resolves two primary conflict types:

• Vertex Conflict: Two agents occupy the same location (vertex) at the same timestep.
• Edge Conflict: Two agents traverse the same edge in opposite directions simultaneously.

Some implementations also handle following conflicts (one agent occupies a vertex the previous agent just left) and swap conflicts. Each conflict type generates specific spatial-temporal constraints (e.g., agent 1 != vertex (x,y) at time t) that are added to the child nodes in the CT.

Advanced CBS variants improve efficiency through sophisticated conflict analysis:

• Bypassing: If replanning for one agent in a conflict yields a path with the same cost that avoids the conflict, the solution is updated without branching the CT, reducing search depth.
• Meta-Agent (CBS-MA): When agents are in prolonged conflict, they can be merged into a meta-agent. The low-level planner then finds a joint path for the meta-agent, which is optimal for the subgroup, preventing an exponential blow-up of the CT from repeated pairwise constraints.

While optimal, CBS has significant limitations:

• High-Level Search Space: The CT can grow exponentially with the number of agents and conflicts (O(2^n) in worst case).
• Low-Level Replanning: Each CT node triggers a full replan for at least one agent, which is computationally expensive.
• Dense Environments: Performance degrades in highly congested spaces with many interdependent conflicts.

These limitations led to the development of bounded-suboptimal variants like Enhanced CBS (ECBS) and CBS with Prioritized Planning (CBS-PP), which sacrifice guaranteed optimality for orders-of-magnitude faster planning.

The constraint tree is the core data structure of the CBS algorithm. It is a binary tree where:

• Each node contains a set of constraints (e.g., "agent A cannot be at cell (5,7) at timestep 10") and a set of individual agent paths that respect those constraints.
• The root has no constraints.
• Child nodes are created by resolving a conflict from the parent node, branching to impose the conflict-resolving constraint on one agent or the other.
• CBS performs a best-first search over this tree to find a node where all paths are conflict-free.

In CBS's two-level architecture, the low-level planner is responsible for finding an optimal path for a single agent, subject to the constraints passed down from the high-level search. Typically, this is a variant of A* search (like Space-Time A*) that operates in a space-time domain, ensuring the agent avoids specific cells at specific times as dictated by the constraints. The efficiency of this low-level planner is critical to CBS's overall performance.

CBS performance is heavily influenced by how it classifies and prioritizes conflicts:

• Cardinal Conflict: A conflict where resolving it forces at least one of the involved agents to incur a longer path. These are the most important to resolve first.
• Semi-Cardinal Conflict: A conflict where resolving it forces exactly one agent to take a longer path.
• Non-Cardinal Conflict: A conflict where both agents can avoid it without increasing their path cost. Advanced CBS variants (ICBS) use this classification in a conflict prioritization strategy to dramatically reduce the size of the constraint tree searched.

Space-Time A* is the most common low-level planner used within CBS. It extends the classic A* algorithm by adding time as an explicit dimension in its search space. The state is defined as (x, y, t). This allows the planner to:

• Enforce vertex constraints (avoid a specific cell at a specific time).
• Enforce edge constraints (avoid moving from cell A to cell B during a specific time interval).
• Find paths that are optimal in a space-time continuum, which is necessary for CBS to guarantee optimality in terms of sum-of-costs.

A key value proposition of CBS is its guarantee of optimality. In MAPF, this is defined by two primary objective functions:

• Sum-of-Costs: The sum of the path lengths (or travel times) for all agents. CBS is optimal with respect to this metric.
• Makespan: The total time until the last agent reaches its goal. While CBS can be adapted for this, its standard form optimizes for sum-of-costs. The algorithm's best-first search over the constraint tree ensures the first conflict-free solution found has the lowest possible sum-of-costs, given the constraints propagated from the high-level search.