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 Satish Kumar, T. K.
dc.contributor.author Skyler, Shawn
dc.contributor.author Ulloa, Carlos Hernández
dc.contributor.author Koenig, Sven
dc.date.accessioned 2024-09-26T00:49:30Z
dc.date.available 2024-09-26T00:49:30Z
dc.date.issued 2023
dc.identifier.issn 2832-9171
dc.identifier.uri https://repositorio.uss.cl/handle/uss/13684
dc.description Publisher Copyright: © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org).
dc.description.abstract In bi-objective graph search, each edge is annotated with a cost pair, where each cost corresponds to an objective to optimize. We are interested in finding all undominated paths from a given start state to a given goal state (called the Pareto front). Almost all existing works of bi-objective search use single-valued heuristics, which use one number for each objective, to estimate the cost between any given state and the goal state. However, single-valued heuristics cannot reflect the trade-offs between the two costs. On the other hand, multi-valued heuristics use a set of pairs to estimate the Pareto front between any given state and the goal state and are more informed than single-valued heuristics. However, they are rarely studied and have yet to be investigated in explicit state spaces by any existing work. In this paper, we are interested in using multi-valued heuristics to improve bi-objective search algorithms in explicit state spaces. More specifically, we generalize Differential Heuristics (DHs), a class of memorybased heuristics for single-objective search, to bi-objective search, resulting in Bi-objective Differential Heuristics (BODHs). We propose several techniques to reduce the memory usage and computational overhead of BO-DHs significantly. Our experimental results show that, with suggested improvement and tuned parameters, BO-DHs can reduce the node expansion and runtime of a bi-objective search algorithm by up to an order of magnitude, paving the way for more effective multi-valued heuristics. en
dc.language.iso eng
dc.relation.ispartof vol. 16 Issue: no. 1 Pages: 101-109
dc.source The International Symposium on Combinatorial Search
dc.title Towards effective multi-valued heuristics for bi-objective shortest-path algorithms via differential heuristics en
dc.type Artículo de conferencia
dc.identifier.doi 10.1609/socs.v16i1.27288
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