Conflict-Based Search (CBS)

CBS operates on two distinct levels:

• High-Level (Constraint Tree): A binary search tree where each node contains a set of constraints and a solution. The algorithm detects conflicts between agent paths in the current solution and branches by adding constraints to resolve them.
• Low-Level (Single-Agent Planner): For each node in the constraint tree, a fast single-agent pathfinder (like A*) replans paths for individual agents, respecting all constraints imposed from above. This separation is fundamental, allowing CBS to avoid searching the prohibitively large joint state space directly.

Conflicts are the core driver of CBS's search. When two agents conflict (e.g., a vertex conflict at the same location/time), CBS does not replan arbitrarily. Instead, it generates child nodes with new constraints:

• One child node gets a constraint preventing Agent A from being at the conflicting vertex at that time.
• The other child gets a symmetric constraint for Agent B. The low-level planner is then invoked for the affected agent to find a new path that obeys the new constraint, often by waiting or taking a detour. This methodical branching ensures completeness and optimality.

CBS is provably optimal for minimizing the Sum of Costs (SOC). Optimality is achieved through the systematic exploration of the constraint tree:

• The high-level search uses a priority queue (typically sorted by the SOC of the node's solution).
• It always expands the node with the lowest current total cost.
• Because constraints can only increase path costs (or leave them the same), the first node expanded that contains a conflict-free solution is guaranteed to have the minimum possible SOC. This makes CBS a best-first search over the space of possible constraint sets.

Advanced CBS implementations use Multi-Value Decision Diagrams to enhance conflict detection and resolution. An MDD for an agent is a compact graph showing all possible optimal paths from start to goal within the current cost bound.

• Efficient Cardinal Conflict Identification: By comparing MDDs, CBS can quickly identify cardinal conflicts—conflicts where resolving them must increase the SOC. This allows for more informed pruning of the constraint tree.
• Bypass Detection: MDDs help identify bypasses, where an agent can take a different optimal path to avoid a conflict without increasing its cost, preventing unnecessary branching.

CBS is fundamentally designed to optimize the Sum of Costs, the sum of each agent's individual path length or time. This differs from optimizing makespan (the time until the last agent finishes).

• The low-level planner minimizes cost for a single agent.
• The high-level tree's sorting and expansion strategy minimizes the sum of these individual costs.
• This objective is standard in logistics and warehousing, as it correlates with total fleet energy use, wear-and-tear, and cumulative task completion time.

CBS is complete, meaning it will find a solution if one exists, given sufficient time and memory, for standard MAPF formulations on graphs. Its completeness derives from the fact that the constraint tree represents all possible ways of resolving conflicts through prohibitions.

• If a solution exists, there is a set of constraints (e.g., "Agent 1 avoids vertex v at time t") that describes it.
• CBS's systematic search over the space of constraint sets will eventually generate that set or an equivalent one.
• Note: For lifelong MAPF (LMAPF) or problems with dynamic tasks, standard CBS is not directly applicable and requires online variants.

CBS is deployed in modern fulfillment centers to coordinate fleets of Autonomous Mobile Robots (AMRs). It ensures robots transporting shelves to human pickers or moving packages between stations follow optimal, collision-free paths.

• Key Function: Resolves vertex conflicts (two robots aiming for the same cell) and edge conflicts (head-on collisions in narrow aisles).
• Integration: Often works alongside a Conflict Avoidance Table (CAT) for real-time reservation tracking and real-time replanning engines to handle dynamic obstacles like fallen items or human workers.

In container terminals and logistics yards, CBS plans paths for Automated Guided Vehicles (AGVs) and terminal tractors. The environment is highly structured but dynamic, with containers being constantly loaded and unloaded.

• Challenge: Must respect kinodynamic constraints of large vehicles (turning radius, acceleration) and integrate with spatial-temporal scheduling for crane operations.
• Outcome: Minimizes makespan—the total time to clear a batch of transportation jobs—directly impacting port throughput. Solutions are often k-robust to account for minor execution delays.

For drone swarms performing area coverage, light-show choreography, or last-mile delivery, CBS finds optimal trajectories in 3D airspace. The state space includes altitude, requiring adaptations of the standard 2D grid model.

• Application: Avoids cardinal conflicts where drones' paths are mutually exclusive, ensuring no mid-air collisions.
• Technique: Often uses bounded suboptimal search variants of CBS to generate safe paths in milliseconds, a necessity for real-time flight control. Integrates with reactive collision avoidance systems like Optimal Reciprocal Collision Avoidance (ORCA) for last-moment adjustments.

CBS is used in game engines and military simulations to generate believable, collision-free movement for large groups of non-player characters (NPCs) or units. It provides optimal or bounded-suboptimal group paths that are more coherent than individual agent planning.

• Advantage: Produces solutions that minimize the overall sum of costs (SOC), creating efficient group maneuvers.
• Method: Game engines may use a windowed approach, running CBS over a short planning horizon and replanning frequently to handle player interactions, aligning with Lifelong MAPF (LMAPF) concepts.

In smart manufacturing, CBS coordinates the movement of heterogeneous fleets—such as assembly robots, transport carts, and mobile manipulators—across shared work cells. This is a core component of Software-Defined Manufacturing Automation.

• Requirement: Must interface with zone management protocols (e.g., speed limits in human areas) and priority-based routing for urgent tasks.
• Process: The high-level search tree in CBS efficiently manages deadlock detection and recovery by imposing constraints that prevent cyclical waiting scenarios, a critical failure mode in dense layouts.

Beyond direct deployment, CBS serves as a gold-standard benchmark in academic and industrial research for optimal MAPF. Its clear separation of conflict resolution (high-level) and path planning (low-level) provides a modular framework for innovation.

• Extensions: Foundational for advanced algorithms like ICTS (Increasing Cost Tree Search), which uses Multi-Valued Decision Diagrams (MDDs), and CBS with bypasses, which attempts local path modifications before imposing constraints.
• Role: Used to evaluate new MAPF techniques against a proven optimal solver, driving progress in the entire field of multi-agent orchestration.

Multi-Agent Path Finding (MAPF) is the foundational computational problem that CBS solves. It involves finding collision-free paths for multiple agents from their start positions to their goal positions in a shared, typically discretized, environment. The core challenge is the combinatorial explosion of the joint state space.

• Objectives: Common objectives include minimizing Makespan (total completion time) or Sum of Costs (SOC) (total travel distance/time).
• Constraints: Solutions must avoid Vertex Conflicts (two agents in the same location at the same time) and Edge Conflicts (two agents crossing the same edge in opposite directions).
• Applications: Warehouse robotics, video game character navigation, and autonomous vehicle coordination in structured spaces.

Increasing Cost Tree Search (ICTS) is another optimal MAPF algorithm that takes a different approach from CBS. Instead of resolving conflicts via constraints, ICTS searches a tree of possible cost combinations.

• Mechanism: It first finds the optimal cost for each agent individually. It then searches a tree where each node represents a vector of costs for all agents. For each cost vector, it uses a low-level solver to check if feasible, non-conflicting paths exist for all agents at those exact costs.
• Efficiency: Prunes branches where any agent's individual cost exceeds its allocated budget from the vector.
• Comparison to CBS: While both are optimal, CBS is often more memory-efficient for problems with many conflicts, as it explores constraint trees rather than cost trees.

Multi-Agent A (MAA)** is a centralized, brute-force optimal algorithm that serves as a conceptual baseline. It applies the A* search algorithm directly to the joint state space of all agents.

• Joint State Space: A state is defined as the combined locations of all agents (e.g., (pos_agent1, pos_agent2, ..., pos_agent_n)).
• Scalability Limitation: The state space grows exponentially with the number of agents (O(branching_factor^#agents)), making it impractical for more than a handful of agents.
• Role in MAPF: MAA* provides a gold-standard optimal solution for benchmarking but highlights the need for more sophisticated algorithms like CBS or ICTS that avoid searching the full joint space.

A Conflict Avoidance Table (CAT) is a core data structure used by CBS and many other MAPF algorithms for efficient conflict detection. It stores the space-time reservations of all planned agent paths.

• Function: For a given location (x, y) and time step t, the CAT can instantly return which agent (if any) is planned to be there. This allows the low-level planner in CBS to check for conflicts in constant time.
• Implementation: Often implemented as a hash map where the key is a tuple (x, y, t) and the value is an agent ID.
• Extension: Advanced versions may also store direction of movement or velocity to detect more complex conflict types like Edge Conflicts.

A Multi-Valued Decision Diagram (MDD) is a compact, graph-based representation of all possible optimal paths for a single agent within a specific cost bound (e.g., its shortest path length). It is a key component in advanced CBS variants.

• Structure: An MDD is a directed acyclic graph. Nodes represent the agent being at a specific location at a specific time depth. Edges connect nodes from time t to t+1 if the agent can move between those locations.
• Use in CBS: MDDs allow for high-level reasoning. A Cardinal Conflict can be identified by checking if the MDDs of two agents intersect at only one node, meaning any resolution will increase the sum of costs.
• Efficiency: Enables more informed conflict selection and resolution strategies, improving algorithm performance.

Bounded-Suboptimal Search refers to a class of algorithms, including variants of CBS, that sacrifice guaranteed optimality for dramatic gains in speed and scalability, with a provable cost bound.

• Principle: The algorithm is given a suboptimality factor w (e.g., 1.1). It is allowed to return a solution whose cost is no worse than w * optimal_cost.
• CBS Application: In Weighted CBS (WCBS), the high-level search uses a focal list or an inflated heuristic (like w * h(n)) to guide the search, exploring promising but potentially suboptimal constraint trees first.
• Practical Value: Essential for real-time applications like video games or large-scale robot fleets where a near-optimal solution found quickly is preferable to an optimal solution found too late.