Resumen
Contraction Hierarchies (CHs) have been successfully used as a preprocessing technique in single-objective graph search for finding shortest paths. However, only a few existing works on utilizing CHs for bi-objective search exist, and none of them uses CHs to compute Pareto frontiers. This paper proposes an CH-based approach capable of efficiently computing Pareto frontiers for bi-objective search along with several speedup techniques. Specifically, we propose a new preprocessing approach that computes CHs with fewer edges than the existing preprocessing approach, which reduces both the preprocessing times (up to 3× in our experiments) and the query times. Furthermore, we propose a partial-expansion technique, which dramatically speeds up the query times. We demonstrate the advantages of our approach on road networks with 1 to 14 million states. The longest preprocessing time is less than 6 hours, and the average speedup in query times is roughly two orders of magnitude compared to BOA*, a state-of-the-art single-query bi-objective search algorithm.
Idioma original | Inglés |
---|---|
Páginas (desde-hasta) | 452-461 |
Número de páginas | 10 |
Publicación | Proceedings International Conference on Automated Planning and Scheduling, ICAPS |
Volumen | 33 |
N.º | 1 |
DOI | |
Estado | Publicada - 2023 |
Evento | 33rd International Conference on Automated Planning and Scheduling, ICAPS 2023 - Prague, República Checa Duración: 2023 → 2023 |
Nota bibliográfica
Publisher Copyright:Copyright © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Áreas temáticas de ASJC Scopus
- Inteligencia artificial
- Informática aplicada
- Gestión y sistemas de información