Cost Splitting for Multi-Objective Conflict-Based Search


  • Cheng Ge Tsinghua University
  • Han Zhang University of Southern California
  • Jiaoyang Li Carnegie Mellon University
  • Sven Koenig University of Southern California



Multi-agent and distributed planning, Heuristic search


The Multi-Objective Multi-Agent Path Finding (MO-MAPF) problem is the problem of finding the Pareto-optimal frontier of collision-free paths for a team of agents while minimizing multiple cost metrics. Examples of such cost metrics include arrival times, travel distances, and energy consumption. In this paper, we focus on the Multi-Objective Conflict-Based Search (MO-CBS) algorithm, a state-of-the-art MO-MAPF algorithm. We show that the standard splitting strategy used by MO-CBS can lead to duplicate search nodes and hence can duplicate the search effort of MO-CBS. To address this issue, we propose two new splitting strategies for MO-CBS, namely cost splitting and disjoint cost splitting. Our theoretical results show that, when using either splitting strategy, MO-CBS maintains its completeness and optimality guarantees. Our experimental results show that disjoint cost splitting, our best splitting strategy, speeds up MO-CBS by up to two orders of magnitude and substantially improves its success rates in various settings.




How to Cite

Ge, C., Zhang, H., Li, J., & Koenig, S. (2023). Cost Splitting for Multi-Objective Conflict-Based Search. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 128-137.