Generalized and Sub-Optimal Bipartite Constraints for Conflict-Based Search

Thayne T. Walker, Nathan R. Sturtevant, Ariel Felner

Introduction

Multi-Agent Pathfinding (MAPF) is a critical challenge in robotics and logistics, requiring a fleet of agents to navigate to their respective goals without collisions. Conflict-Based Search (CBS) has emerged as a state-of-the-art framework for solving MAPF optimally. However, as the complexity of environments increases—incorporating continuous time, non-unit movement costs, and varied agent shapes—the standard constraint generation in CBS often becomes a bottleneck. This paper, presented at AAAI-20, introduces Bipartite Reduction (BR), a generalized approach to constraint generation that significantly enhances search efficiency.

The Challenge of High-Connectivity Environments

Standard CBS operates on two levels: a low-level search for individual paths and a high-level search that resolves collisions by adding constraints. In simple 4-connected grids, a single constraint (blocking one location at one time) is often sufficient. However, in high-connectivity grids (8-, 16-, or 32-connected) or continuous-time domains, agents have many alternative paths. A single constraint may fail to prune enough of the search space, leading to an explosion in the size of the high-level Conflict Tree. Manually designing specialized constraints for every new domain is impractical.

Methodology: Bipartite Reduction (BR)

The core innovation is the formalization of conflict resolution as a graph problem. When two agents collide, the algorithm identifies all possible actions that could have led to that collision. These actions are used to construct a Bipartite Conflict Graph (BCG).

CBS+TAB: Time-Annotated Bicliques

In the BCG, nodes represent potential actions for each agent, and edges represent collisions between those actions. The algorithm seeks a "max-vertex biclique"—a subset of nodes where every action for Agent A conflicts with every action for Agent B.

Bipartite Conflict Graph (BCG) showing a biclique (b) and its time-annotated version (c).

By generating constraints based on these bicliques, CBS can block multiple conflicting actions simultaneously. This "Time-Annotated Biclique" (TAB) approach prunes the search tree much more aggressively than standard methods while maintaining completeness and optimality.

Time-Range Constraints

In continuous-time domains, conflicts are not instantaneous but occur over intervals. The authors extend TAB by annotating bicliques with "unsafe intervals," creating constraints that block actions over a window of time rather than just a single timestamp.

Mapping conflict intervals to a timeline to determine the shared 'unsafe interval' for a set of actions.

By identifying the overlap in these intervals, the algorithm creates constraints that block actions over a window of time, further reducing the search space.

Sub-Optimal Search with Conditional Constraints

For applications where speed is prioritized over absolute optimality, the authors introduce Conditional Constraints (CBS+TCC/TCP). These constraints block even more actions, including some that might not strictly be in the biclique. To ensure the algorithm doesn't get stuck (completeness), these constraints are "conditional"—they can be turned off probabilistically or if the low-level search fails to find any path.

Evaluation and Results

The methods were evaluated on standard MAPF benchmarks, including maps from Dragon Age and Starcraft, using circular agents to simulate physical volume.

  • Performance in High Connectivity: CBS+TAB demonstrated superior performance in 16- and 32-connected grids, solving significantly more instances than "Classic" CBS or ICTS within a 30-second limit.
  • Search Tree Pruning: The number of nodes expanded in the high-level search tree often dropped by over 60% in complex environments like mazes (e.g., from 13,000 nodes down to 5,000).
  • Sub-optimal Speedups: The sub-optimal variant, CBS+TCP, achieved up to 5x speedups compared to existing greedy CBS variants.

Conclusion

Bipartite Reduction transforms the way CBS handles conflicts, moving from simple, manually-defined constraints to automatically generated, powerful bipartite constraints. By leveraging the spatial and temporal structure of conflicts, this approach enables efficient pathfinding in complex, high-connectivity domains, paving the way for more realistic multi-agent deployments.

Summary updated

Abstract

The main idea of conflict-based search (CBS), a popular, state-of-the-art algorithm for multi-agent pathfinding is to resolve conflicts between agents by systematically adding constraints to agents. Recently, CBS has been adapted for new domains and variants, including non-unit costs and continuous time settings. These adaptations require new types of constraints. This paper introduces a new automatic constraint generation technique called bipartite reduction (BR). BR converts the constraint generation step of CBS to a surrogate bipartite graph problem. The properties of BR guarantee completeness and optimality for CBS. Also, BR's properties may be relaxed to obtain suboptimal solutions. Empirical results show that BR yields significant speedups in 2k connected grids over the previous state-of-the-art for both optimal and suboptimal search.
BibTeX
@inproceedings{walker2020generalized,
  author = {Thayne T. Walker and Nathan R. Sturtevant and Ariel Felner},
  title = {{Generalized and Sub-Optimal Bipartite Constraints for Conflict-Based Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i05.6219},
}
Figure