K-Focal Search for Slow Learned Heuristics

Matias Greco*, Jorge Toro, Carlos Hernandez, Jorge A. Baier

*Autor correspondiente de este trabajo

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

Resumen

Bounded suboptimal heuristic search is a family of search algorithms capable of solving hard combinatorial problems, returning suboptimal solutions within a given bound. Recent machine learning approaches have been shown to learn accurate heuristic functions. Learned heuristics, however, are slow to compute; concretely, given a single search state s and a learned heuristic h , evaluating h(s) is typically very slow relative to expansion time, since state-of-the-art learned heuristics are implemented as neural networks. However, by using a Graphics Processing Unit (GPU), it is possible to compute heuristics using batched computation. Existing approaches to batched heuristic computation are specific to satisficing search and have not studied the problem in the context of bounded-suboptimal search. In this paper, we present K-Focal Search, a bounded suboptimal search algorithm that in each iteration expands K states from the FOCAL list and computes the learned heuristic values of the successors using a GPU. We experiment over the 24-puzzle and Rubik's Cube using DeepCubeA, a very effective and inadmissible learned heuristic. Our results show that K-Focal Search benefits both from batched computation and from the diversity in the search introduced by its expansion strategy. Over standard Focal Search, K-Focal Search improves runtime by a factor of 6, expansions by up to three orders of magnitude, and finds better quality solutions, keeping the theoretical guarantees of Focal Search.

Idioma originalInglés
Páginas (desde-hasta)1599-1607
Número de páginas9
PublicaciónIEEE Access
Volumen12
DOI
EstadoPublicada - 2024

Nota bibliográfica

Publisher Copyright:
© 2013 IEEE.

Áreas temáticas de ASJC Scopus

  • Ciencia de la Computación General
  • Ciencia de los Materiales General
  • Ingeniería General

Huella

Profundice en los temas de investigación de 'K-Focal Search for Slow Learned Heuristics'. En conjunto forman una huella única.

Citar esto