Unbounded Sub-Optimal Conflict-Based Search in Complex Domains
- Thayne T. Walker
- Nathan R. Sturtevant
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
Conflict-Based Search (CBS) is a state of the art algorithm for multi-agent pathfinding (MAPF). CBS has been studied in many domains, however, most research has focused on classic domains with point agents that move with unit time steps and unit costs. In this work, we are interested in MAPF solutions for classic domains and complex domains, that is, domains which include shaped agents, actions with non-unit costs, non-uniform action durations and/or non-holonomic or kinodynamic movement constraints. Prior work on sub-optimal formulations of CBS has focused on heuristics. Instead, our work introduces new types of constraints. We show that certain constraint formulations have properties that can cause CBS to run orders of magnitude faster, but may cause the algorithm to be incomplete and yield sub-optimal results. We introduce new conditional constraints which allow CBS to exploit constraint properties which cause it to run faster and still retain algorithmic completeness. We additionally formulate a new constraint accumulation technique called constraint overloading which utilizes conditional constraints in order to achieve further performance gains.
Citation
T. Walker, N. Sturtevant, A. Felner. "Unbounded Sub-Optimal Conflict-Based Search in Complex Domains". Symposium on Combinatorial Search, (ed: Pavel Surynek, William Yeoh), pp 204-205, July 2019.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Walker+al:SoCS19,
author = {Thayne T. Walker and Nathan R. Sturtevant and Ariel Felner},
title = {Unbounded Sub-Optimal Conflict-Based Search in Complex Domains},
Editor = {Pavel Surynek, William Yeoh},
Pages = {204-205},
booktitle = {Symposium on Combinatorial Search},
year = 2019,
}Last Updated: July 03, 2020Submitted by Sabina P
