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 | Tamaño | Formato | Ver |
---|---|---|---|
No hay ficheros asociados a este ítem. |