Efficient Approximate Search for Multi-Objective Multi-Agent Path Finding
Proceedings of the International Conference on Automated Planning and Scheduling · 30.05.2024 · 34 · 613-622
DOI: 10.1609/icaps.v34i1.31524 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 30.05.2024. Verfasst von Fangji Wang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref).
Abstract (Originalsprache)
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.
Zitieren
APA
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, 613-622. https://doi.org/10.1609/icaps.v34i1.31524
Vancouver
Wang F, Zhang H, Koenig S, Li J. Efficient Approximate Search for Multi-Objective Multi-Agent Path Finding. Proceedings of the International Conference on Automated Planning and Scheduling. 2024;34:613-622. doi:10.1609/icaps.v34i1.31524
BibTeX
@article{Wang2024,
author = {Wang, Fangji and Zhang, Han and Koenig, Sven and Li, Jiaoyang},
title = {Efficient Approximate Search for Multi-Objective Multi-Agent Path Finding},
journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
year = {2024},
volume = {34},
pages = {613--622},
doi = {10.1609/icaps.v34i1.31524}
}
EUVIMED