Avoiding Errors in Learned Heuristics in Bounded-Suboptimal Search

Authors

  • Matias Greco Departamento de Ciencia de la Computación, Pontificia Universidad Católica de Chile
  • Jorge A. Baier Departamento de Ciencia de la Computación, Pontificia Universidad Católica de Chile Instituto Milenio Fundamentos de los Datos, Chile

Keywords:

Machine And Deep Learning In Search

Abstract

Despite being very effective, learned heuristics in bounded-suboptimal search can produce heuristic plateaus or move the search to zones of the state space that do not lead to a solution. In addition, it produces inadmissible cost-to-go estimates; therefore, it cannot be exploited with classical algorithms like WA* to produce w-optimal solutions. In this paper, we present two ways in which Focal Search can be modified to exploit a learned heuristic in a bounded suboptimal search: Focal Discrepancy Search, which, to evaluate each state, uses a discrepancy score based on the best-predicted heuristic value; and K-Focal Search, which expands more than one node from the FOCAL list in each expansion cycle. Both algorithms return w-optimal solutions and explore different zones of the state space than the ones that focal search, using the learned heuristic to sort the FOCAL list, would explore.

Downloads

Published

2022-07-17