K-Focal Search for Slow Learned Heuristics (Extended Abstract)

Authors

  • Matias Greco Departamento de Ciencia de la Computación, Pontificia Universidad Católica de Chile, Chile
  • Jorge Toro Departamento de Ciencia de la Computación, Pontificia Universidad Católica de Chile, Chile
  • Carlos Hernández-Ulloa Facultad de Ingeniería y Tecnología, Universidad San Sebastián, Chile
  • Jorge A. Baier Departamento de Ciencia de la Computación, Pontificia Universidad Católica de Chile, Chile Instituto Milenio Fundamentos de los Datos, Chile

Keywords:

Machine And Deep Learning In Search, Combinatorial Puzzles

Abstract

Learned heuristics, though inadmissible, can provide very good guidance for bounded-suboptimal search. 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 nodes from the FOCAL list and computes the learned heuristic values of the successors using a GPU. We experiment over the Rubik's Cube domain using DeepCubeA, a very effective 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 FS, it improves runtime by a factor of 6, expansions by up to three orders of magnitude, and finds better solutions, keeping the theoretical guarantees of Focal Search.

Downloads

Published

2022-07-17