Efficient Approximate Search for Multi-Objective Multi-Agent Path Finding

Authors

  • Fangji Wang Tsinghua University
  • Han Zhang University of Southern California
  • Sven Koenig University of Southern California
  • Jiaoyang Li Carnegie Mellon University

DOI:

https://doi.org/10.1609/icaps.v34i1.31524

Abstract

The Multi-Objective Multi-Agent Path Finding (MO-MAPF) problem is the problem of computing collision-free paths for a team of agents while minimizing multiple cost metrics. Most existing MO-MAPF algorithms aim to compute the Pareto frontier. However, the Pareto frontier can be time-consuming to compute. Our first main contribution is BB-MO-CBS-pex, an approximate MO-MAPF algorithm that computes an approximate frontier for a user-specific approximation factor. BB-MO-CBS-pex builds upon BB-MO-CBS, a state-of-the-art MO-MAPF algorithm, and leverages A*pex, a state-of-the-art single-agent multi-objective search algorithm, to speed up different parts of BB-MO-CBS. We also provide two speed-up techniques for BB-MO-CBS-pex. Our second main contribution is BB-MO-CBS-k, which builds upon BB-MO-CBS-pex and computes up to k solutions for a user-provided k-value. BB-MO-CBS-k is useful when it is unclear how to determine an appropriate approximation factor. Our experimental results show that both BB-MO-CBS-pex and BB-MO-CBS-k solved significantly more instances than BB-MO-CBS for different approximation factors and k-values, respectively. Additionally, we compare BB-MO-CBS-pex with an approximate baseline algorithm derived from BB-MO-CBS and show that BB-MO-CBS-pex achieved speed-ups up to two orders of magnitude.

Downloads

Published

2024-05-30

How to Cite

Wang, F., Zhang, H., Koenig, S., & Li, J. (2024). Efficient Approximate Search for Multi-Objective Multi-Agent Path Finding. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1), 613-622. https://doi.org/10.1609/icaps.v34i1.31524