Mostrar el registro sencillo del ítem
dc.contributor.author | Zhang, Han | |
dc.contributor.author | Salzman, Oren | |
dc.contributor.author | Felner, Ariel | |
dc.contributor.author | Kumar, T. K.Satish | |
dc.contributor.author | Ulloa, Carlos Hernández | |
dc.contributor.author | Koenig, Sven | |
dc.date.accessioned | 2024-09-26T00:49:33Z | |
dc.date.available | 2024-09-26T00:49:33Z | |
dc.date.issued | 2023 | |
dc.identifier.issn | 2334-0835 | |
dc.identifier.uri | https://repositorio.uss.cl/handle/uss/13688 | |
dc.description | Publisher Copyright: Copyright © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. | |
dc.description.abstract | 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. | en |
dc.language.iso | eng | |
dc.relation.ispartof | vol. 33 Issue: no. 1 Pages: 452-461 | |
dc.source | Proceedings International Conference on Automated Planning and Scheduling, ICAPS | |
dc.title | Efficient Multi-Query Bi-Objective Search via Contraction Hierarchies | en |
dc.type | Artículo de conferencia | |
dc.identifier.doi | 10.1609/icaps.v33i1.27225 | |
dc.publisher.department | Facultad de Ingeniería, Arquitectura y Diseño |
Ficheros | Tamaño | Formato | Ver |
---|---|---|---|
No hay ficheros asociados a este ítem. |