Universidad San Sebastián  
 

Repositorio Institucional Universidad San Sebastián

Búsqueda avanzada

Descubre información por...

 

Título

Ver títulos
 

Autor

Ver autores
 

Tipo

Ver tipos
 

Materia

Ver materias

Buscar documentos por...




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 en el ítem

Ficheros Tamaño Formato Ver

No hay ficheros asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem