Proceedings of the International Conference on Automated Planning and Scheduling · 2018 · 151 citations · 21 references
ComputingComputer ScienceAlgorithmsConflict ResolutionPath PlanningHeuristic OptimizationHeuristic SearchMetaheuristic OptimizationMulti-agent SystemsSearching AlgorithmsAdmissible HeuristicsMulti-agent Decision MakingMulti-agent Path PlanningMulti-agent PlanningMulti-agent Search
Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for the multi-agent path-finding problem. However,existing variants of CBS do not use any heuristics that estimate future work. In this paper, we introduce different admissible heuristics for CBS by aggregating cardinal conflicts among agents. In our experiments, CBS with these heuristics outperforms previous state-of-the-art CBS variants by up to a factor of five.
21
Conflict-based search for optimal multi-agent pathfinding
Guni Sharon, Roni Stern, Ariel Felner et al. · Artificial Intelligence · 2014 · 1.2K citations
The increasing cost tree search for optimal multi-agent pathfinding
Guni Sharon, Roni Stern, Meir Goldenberg et al. · Artificial Intelligence · 2012 · 322 citations