Towards effective multi-valued heuristics for bi-objective shortest-path algorithms via differential heuristics

Han Zhang, Oren Salzman, Ariel Felner, T. K. Satish Kumar, Shawn Skyler, Carlos Hernández Ulloa, Sven Koenig

Producción científica: Contribución a una revistaArtículo de la conferenciarevisión exhaustiva

2 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Páginas (desde-hasta)101-109
Número de páginas9
PublicaciónThe International Symposium on Combinatorial Search
Volumen16
N.º1
DOI
EstadoPublicada - 2023
Evento16th International Symposium on Combinatorial Search, SoCS 2023 - Prague, República Checa
Duración: 20232023

Nota bibliográfica

Publisher Copyright:
© 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org).

Áreas temáticas de ASJC Scopus

  • Redes de ordenadores y comunicaciones

Huella

Profundice en los temas de investigación de 'Towards effective multi-valued heuristics for bi-objective shortest-path algorithms via differential heuristics'. En conjunto forman una huella única.

Citar esto