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

Authors

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

DOI:

https://doi.org/10.1609/aaai.v34i05.6219

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.

Downloads

Published

2020-04-03

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. https://doi.org/10.1609/aaai.v34i05.6219

Issue

Section

AAAI Technical Track: Multiagent Systems