Conflict-Based Search (CBS)

CBS operates on two distinct levels:

• High-Level (Constraint Tree Search): This level searches a binary tree where each node represents a set of constraints imposed on agents to resolve conflicts (e.g., "Agent A cannot be at cell (5,3) at timestep 7"). The algorithm expands nodes by identifying the first conflict in the current solution and creating two child nodes, each adding a constraint to one of the conflicting agents.
• Low-Level (Single-Agent Planner): For each agent, a low-level search (typically A*) finds an optimal path from start to goal that satisfies all constraints currently assigned to that agent from the high-level node. This separation is key to CBS's optimality and modularity.

CBS is provably optimal for common MAPF cost functions like Sum of Costs (total timesteps for all agents) or Makespan (maximum finish time). It guarantees finding a conflict-free solution with the minimum possible cost because:

• The high-level tree is systematically explored.
• The low-level planner is optimal for the single-agent problem given its constraints.
• The algorithm only prunes branches of the constraint tree when it can prove no better solution exists below them, ensuring no optimal solution is missed.

Conflicts are the core abstraction. A conflict is a tuple (a_i, a_j, v, t) where agents a_i and a_j occupy the same vertex v at timestep t (vertex conflict) or swap positions along an edge (edge conflict).

• Resolution: CBS resolves a conflict by generating vertex constraints (a_i, v, t) or edge constraints (a_i, u, v, t).
• Propagation: These constraints are passed to the low-level planners, which must replan paths that avoid the specified state at the given time. This method transforms a multi-agent problem into a series of constrained single-agent problems.

CBS excels in structured, discrete environments where optimality is critical:

• Warehouse Automation: Coordinating fleets of Autonomous Mobile Robots (AMRs) on a grid-based factory floor to move goods from shelves to packing stations without deadlocks.
• Video Game AI: Planning optimal, collision-free paths for multiple non-player characters (NPCs) in strategy or simulation games.
• Aircraft Towing: Scheduling optimal, conflict-free routes for vehicles towing planes on airport aprons.
• Multi-Drone Delivery: Planning precise takeoff, flight, and landing sequences for a swarm of delivery drones in an urban airspace grid.

Compared to other MAPF approaches, CBS offers distinct benefits:

• Optimality: Unlike reactive or prioritized planning, CBS guarantees an optimal solution.
• Completeness: It will find a solution if one exists, unlike some heuristic methods.
• Modularity: The low-level planner can be swapped (e.g., using Dijkstra's for weighted graphs) without altering the high-level logic.
• Conceptual Clarity: The constraint-tree visualization makes the search process and conflict resolution transparent and debuggable.

CBS's strengths come with trade-offs:

• Scalability: The number of high-level tree nodes can grow exponentially with the number of agents and complexity of the environment. It is typically used for tens of agents, not hundreds.
• Memory Usage: The entire constraint tree must be stored during search, which can be large.
• Runtime: While optimal, it can be slower than suboptimal but fast algorithms like Prioritized Planning or Windowed Hierarchical Cooperative A* (WHCA*).
• Continuous Domains: CBS is designed for discrete, graph-based environments. Applying it to continuous state spaces requires significant discretization.

CBS is extensively used in video game engines and crowd simulation software to generate natural-looking, collision-free movement for hundreds of non-player characters (NPCs). It is the preferred method when optimality guarantees are desired for squad-based tactics or complex crowd scenes. Unlike reactive methods, CBS plans full paths from start to goal, preventing oscillatory or deadlock behavior common in local methods.

• Key Problem Solved: Creating believable, purposeful group movement in real-time simulations.
• Performance: Modern adaptations like CBS with Prioritization (CBS-P) are used for real-time performance with dozens of agents.

In flexible manufacturing cells, multiple robotic arms collaborate to assemble products. CBS coordinates their motions to avoid arm-to-arm collisions while minimizing the cycle time for the entire workcell. Each robot's path is a sequence of joint-space or Cartesian-space waypoints, and conflicts are defined as simultaneous occupancy of the same physical volume.

• Key Problem Solved: Safe, efficient coordination of manipulators in a shared workspace.
• Engineering Consideration: Must be integrated with real-time Motion Planning and Trajectory Optimization for smooth, dynamically feasible movements.

CBS is favored in applications requiring provable optimality (e.g., minimizing total makespan). Its two-level architecture offers distinct engineering advantages:

• Modularity: The low-level pathfinder (e.g., A*) can be swapped for any graph search algorithm, even for continuous spaces.
• Completeness: If a solution exists, CBS will find it.
• Constraint-Based Reasoning: The constraint tree provides an explicit, auditable record of every conflict resolution decision, which is valuable for debugging and validation in safety-critical systems like aviation or healthcare robotics.

Contrast with Reactive Methods: Unlike Optimal Reciprocal Collision Avoidance (ORCA), which computes velocities instantaneously, CBS provides a full planned path, preventing myopic decisions that can lead to deadlocks in complex mazes.

Multi-Agent Path Finding (MAPF) is the foundational computational problem that CBS solves. It involves finding collision-free paths for multiple agents (e.g., robots, warehouse AMRs) from their start positions to designated goals in a shared environment, typically represented as a graph. The objective is to optimize a global metric, such as:

• Sum of costs: Minimizing the total time or distance traveled by all agents.
• Makespan: Minimizing the time until the last agent reaches its goal.
• Flowtime: The sum of each agent's completion time. MAPF is NP-hard, making optimal solvers like CBS essential for planning in complex, congested spaces like fulfillment centers or factory floors.

Optimal Reciprocal Collision Avoidance (ORCA) is a decentralized, reactive algorithm for local collision avoidance, contrasting with CBS's centralized, deliberative planning. ORCA operates in continuous space and time, where each agent observes the velocities of nearby agents and computes a new velocity that is guaranteed to be collision-free for a short time horizon, assuming other agents follow the same reciprocal rules. Key characteristics:

• Real-time: Computes velocities every control cycle (e.g., 10-100 Hz).
• Velocity obstacles: Agents consider the set of velocities that would lead to a future collision.
• Reactive vs. Planned: ORCA handles dynamic, unforeseen obstacles but does not provide global optimality or deadlock resolution, which is where CBS excels.

Multi-Robot Task Allocation (MRTA) is the problem of assigning a set of tasks to a team of robots to optimize overall performance. It is often a prerequisite to path planning with CBS. MRTA determines which robot does what, while CBS determines how they move without colliding. Common MRTA formulations include:

• Single-Task robots (ST): Each robot can execute at most one task at a time.
• Single-Robot tasks (SR): Each task requires exactly one robot.
• Multi-Robot tasks (MR): Tasks may require simultaneous coordination of multiple robots. Algorithms like auction-based coordination (e.g., using a consensus-based bundle algorithm) are frequently used for decentralized MRTA, after which CBS can plan collision-free paths for the assigned goals.

Spatio-temporal planning is the general approach of finding plans that specify both where and when an agent should be. CBS is a quintessential spatio-temporal planner. It enforces vertex constraints (agent i cannot be at vertex v at time t) and edge constraints (agent i cannot move from vertex u to vertex v at time t). This is more expressive than purely spatial planning, enabling:

• Deadlock avoidance: Preventing two agents from indefinitely blocking each other in a narrow corridor.
• Synchronization: Coordinating agents to meet at a location for a handoff.
• Temporal optimization: Minimizing total time or ensuring all agents arrive before a deadline. The constraint tree in CBS systematically explores the space of possible spatio-temporal constraints to resolve conflicts.

Decentralized control is an architectural paradigm for multi-robot systems where each robot makes decisions based on local sensory information and communication with nearby neighbors, without a central coordinator. This contrasts with CBS's centralized two-level search. Decentralized approaches offer:

• Scalability: Performance degrades gracefully as the number of robots increases.
• Robustness: The system can tolerate the failure of individual robots.
• Flexibility: Robots can dynamically join or leave the team. While CBS is centralized, its principles inform decentralized variants (e.g., CBS with disjoint splitting) and hybrid architectures where a central planner like CBS handles high-congestion zones, and decentralized reactive controllers like ORCA handle local navigation.

The constraint tree is the core data structure and search space of the CBS algorithm's high-level search. Each node in this tree represents a set of constraints imposed on the agents (e.g., "Agent 2 must avoid cell (5,3) at time 7"). The root node has an empty constraint set. The algorithm proceeds as follows:

1. Low-level search: For each node, a single-agent pathfinder (like A*) finds an optimal path for each agent that respects the node's constraints.
2. Conflict detection: The resulting set of paths is checked for collisions (vertex or edge conflicts).
3. Branching: If a conflict is found between agents i and j, the node generates two child nodes. One child adds a constraint preventing agent i from being in the conflicted state, and the other adds a symmetric constraint for agent j. The tree is systematically explored (often using best-first search) until a node is found where all agent paths are conflict-free, guaranteeing an optimal solution.