Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search

  • Jiaoyang Li University of Southern California
  • Daniel Harabor Monash University
  • Peter J. Stuckey Monash University
  • Ariel Felner Ben-Gurion University
  • Hang Ma University of Southern California
  • Sven Koenig University of Southern California

Abstract

Multi-Agent Path Finding (MAPF) is the planning problem of finding collision-free paths for a team of agents. We focus on Conflict-Based Search (CBS), a two-level tree-search state-of-the-art MAPF algorithm. The standard splitting strategy used by CBS is not disjoint, i.e., when it splits a problem into two subproblems, some solutions are shared by both subproblems, which can create duplication of search effort. In this paper, we demonstrate how to improve CBS with disjoint splitting and how to modify the low-level search of CBS to take maximal advantage of it. Experiments show that disjoint splitting increases the success rates and speeds of CBS and its variants by up to 2 orders of magnitude.

Published
2019-07-06