CBS

class w9_pathfinding.mapf.CBS

Conflict-Based Search (CBS) algorithm for multi-agent pathfinding.

CBS is a two-level search algorithm that finds optimal, collision-free paths for multiple agents by incrementally resolving conflicts between them.

  1. High-level search — Constructs a Constraint Tree (CT), where each node represents a set of constraints and corresponding agent paths. The root node has no constraints. The algorithm then performs a Best-First Search over this tree, prioritizing nodes by their Sum-of-Costs (SoC) — the total cost of all agents’ current paths.

  2. Low-level search - For each high-level CT node, the algorithm finds a path for each individual agent using SpaceTimeAStar, respecting all constraints associated with that CT node. If a conflict is detected between agents’ paths, the node is expanded by branching on the conflicting agents and adding new constraints to avoid the collision.

This algorithm is optimal and complete — it is guaranteed to find a solution if one exists, and the solution will be optimal with respect to the Sum-of-Costs objective (i.e., the total cost across all agents’ paths).

While CBS is relatively fast in practice, especially in sparse environments, performance may degrade in large environments or with many agents.

Parameters:

  • env (Environment) – The environment in which to search for paths.

  • seed (int, optional, default None) –

    Seed for the solver’s internal random number generator. Setting the seed makes the results reproducible for the same input.

    The seed only affects the solver behavior when disjoint_splitting=True.

References

  • Sharon et al. 2012 Conflict-Based Search For Optimal Multi-Agent Path Finding

  • Li et al. 2019 Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search

mapf(starts, goals, max_length=100, max_time=1.0, disjoint_splitting=True, reservation_table=None)

Finds non-colliding paths for all agents from their respective start nodes to goal nodes. The result is a list of individual paths — one per agent.

Parameters:

  • starts (list[node]) – A list of start nodes, one per agent.

  • goals (list[node]) – A list of goal nodes, one per agent. Must be the same length as starts.

  • max_length (int, default=100) – The maximum allowed length of any individual agent’s path.

  • max_time (float, default=1.0) – The maximum amount of time (in seconds) allowed for the solver to find a solution. If the time limit is exceeded, a RuntimeError is raised.

  • disjoint_splitting (bool, default=True) – If True, enables disjoint splitting to improve CBS efficiency and performance. If False, standard collision splitting is used.

  • reservation_table (ReservationTable, optional) – Dynamic obstacles.

Returns:

A list of paths, one per agent. If no collision-free paths are found, returns an empty list.

Return type:

list[list[node]]

Raises:

  • ValueError – If the number of starts and goals is different, or if any node is invalid.

  • RuntimeError – If no solution is found within the time constraint.

num_closed_nodes

Number of Constraint Tree (CT) nodes expanded (processed) during the last search.

num_generated_nodes

Total number of Constraint Tree (CT) nodes generated during the last search.

set_seed(seed) → None

Reset the seed for the solver’s random number generator.

The seed only affects the solver behavior when disjoint_splitting=True.

Parameters:

seed (int or None) – Non-negative integer for reproducible results, or None to use nondeterministic behavior.