Generalized and Sub-Optimal Bipartite Constraints for Conflict-Based Search
- Thayne T. Walker
- Nathan R. Sturtevant
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
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.
Citation
T. Walker, N. Sturtevant, A. Felner. "Generalized and Sub-Optimal Bipartite Constraints for Conflict-Based Search". National Conference on Artificial Intelligence (AAAI), pp 7277-7284, February 2020.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
| doi |
BibTeX
@incollection{Walker+al:AAAI20,
author = {Thayne T. Walker and Nathan R. Sturtevant and Ariel Felner},
title = {Generalized and Sub-Optimal Bipartite Constraints for Conflict-Based
Search},
Pages = {7277-7284},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2020,
}Last Updated: July 13, 2020Submitted by Sabina P
