Conflict-Based Search for Optimal Multi-Agent Path Finding
Guni Sharon, Roni Stern, Ariel Felner, Nathan Sturtevant
2021Proceedings of the International Symposium on Combinatorial Search70 citationsDOIOpen Access PDF
Abstract
We present a new two-level search algorithm for optimal multi-agent path finding called Conflict Based Search (CBS). 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. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.
Topics & Concepts
SpeedupPath (computing)Computer scienceTree (set theory)Search treeOrder (exchange)Search algorithmBeam searchMathematical optimizationAlgorithmMathematicsParallel computingCombinatoricsBusinessComputer networkFinanceRobotic Path Planning AlgorithmsMetaheuristic Optimization Algorithms ResearchOptimization and Search Problems