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.
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.
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