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

SOCS-22 Volume 15

Volume

Vol. 15 No. 1 (2022): Fifteenth International Symposium on Combinatorial Search

Extended Abstracts

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.

10.1609/socs.v15i1.21785