Meta-Agent Conflict-Based Search For Optimal Multi-Agent Path Finding Conference Paper uri icon

abstract

  • The task in the multi-agent path finding problem (MAPF) isto find paths for multiple agents, each with a different startand goal position, such that agents do not collide. It is possibleto solve this problem optimally with algorithms that arebased on the A* algorithm. Recently, we proposed an alternativealgorithm called Conflict-Based Search (CBS) (Sharonet al. 2012), which was shown to outperform the A*-basedalgorithms in some cases. CBS is a two-level algorithm. Atthe high level, a search is performed on a tree based on conflictsbetween agents. At the low level, a search is performedonly for a single agent at a time. While in some cases CBSis very efficient, in other cases it is worse than A*-based algorithms.This paper focuses on the latter case by generalizingCBS to Meta-Agent CBS (MA-CBS). The main idea isto couple groups of agents into meta-agents if the number ofinternal conflicts between them exceeds a given bound. MACBSacts as a framework that can run on top of any completeMAPF solver. We analyze our new approach and provideexperimental results demonstrating that it outperforms basicCBS and other A*-based optimal solvers in many cases.

published proceedings

  • Proceedings of the International Symposium on Combinatorial Search

author list (cited authors)

  • Sharon, G., Stern, R., Felner, A., & Sturtevant, N.

citation count

  • 9

complete list of authors

  • Sharon, Guni||Stern, Roni||Felner, Ariel||Sturtevant, Nathan

publication date

  • December 2012