Learning to Estimate Search Progress Using Sequence of States

Abstract

Many problems of interest can be solved using heuristic search algorithms. When solving a heuristic search problem, we are often interested in estimating search progress, that is, how much longer until we have a solution. Previous work on search progress estimation derived formulas based on some relevant features that can be observed from the behavior of the search algorithm. In this paper, rather than manually deriving such formulas we leverage machine learning to learn more accurate search progress predictors automatically. We train a Long Short-Term Memory (LSTM) network, which takes as input sequences of nodes expanded by the search algorithm, and predicts how far along with the search we are. Importantly, our approach still treats the search algorithm as a black box and does not look into the contents of search nodes. An empirical evaluation shows our technique outperforms previous search progress estimation techniques.