Conflict-Based Search for Optimal Multi-Agent Path Finding
Abstract
In the multi agent path finding problem (MAPF) paths should be found for several agents, each with a different start and goal position such that agents do not collide. Previous optimal solvers applied global A*-based searches. We present a new search algorithm called Conflict Based Search (CBS). CBS is a two-level algorithm. At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. In many cases this reformulation enables CBS to examine fewer states than A* while still maintaining optimality. We analyze CBS and show its benefits and drawbacks. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.
Cite
Text
Sharon et al. "Conflict-Based Search for Optimal Multi-Agent Path Finding." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8140Markdown
[Sharon et al. "Conflict-Based Search for Optimal Multi-Agent Path Finding." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/sharon2012aaai-conflict/) doi:10.1609/AAAI.V26I1.8140BibTeX
@inproceedings{sharon2012aaai-conflict,
title = {{Conflict-Based Search for Optimal Multi-Agent Path Finding}},
author = {Sharon, Guni and Stern, Roni and Felner, Ariel and Sturtevant, Nathan R.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2012},
pages = {563-569},
doi = {10.1609/AAAI.V26I1.8140},
url = {https://mlanthology.org/aaai/2012/sharon2012aaai-conflict/}
}