Exploiting Learned Policies in Focal Search
  Recent machine-learning approaches to deterministic search and
domain-independent planning employ policy learning to speed up search.
Unfortunately, when attempting to solve a search problem by successively
applying a policy, no guarantees can be given on solution quality. The problem
of how to effectively use a learned policy within a bounded-suboptimal search
algorithm remains largely as an open question. In this paper, we propose
various ways in which such policies can be integrated into Focal Search,
assuming that the policy is a neural network classifier. Furthermore, we
provide mathematical foundations for some of the resulting algorithms. To
evaluate the resulting algorithms over a number of policies with varying
accuracy, we use synthetic policies which can be generated for a target
accuracy for problems where the search space can be held in memory. We evaluate
our focal search variants over three benchmark domains using our synthetic
approach, and on the 15-puzzle using a neural network learned using 1.5 million
examples. We observe that Discrepancy Focal Search, which we show expands the
node which maximizes an approximation of the probability that its corresponding
path is a prefix of an optimal path, obtains, in general, the best results in
terms of runtime and solution quality.
