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


  • Thayne T. Walker University of Denver
  • Nathan R. Sturtevant University of Alberta
  • Ariel Felner Ben-Gurion University



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.




How to Cite

Walker, T. T., Sturtevant, N. R., & Felner, A. (2020). Generalized and Sub-Optimal Bipartite Constraints for Conflict-Based Search. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05), 7277-7284.



AAAI Technical Track: Multiagent Systems