Bootstrap Learning of Heuristic Functions

Authors

  • Shahab Jabbari Arfaee University of Alberta
  • Sandra Zilles University of Regina
  • Robert Holte University of Alberta

DOI:

https://doi.org/10.1609/socs.v1i1.18159

Keywords:

Learning heuristics, Heuristic search, Heuristic planning

Abstract

search algorithms such as IDA* or heuristic-search planners. Our method aims to generate a strong heuristic from a given weak heuristic h0 through bootstrapping. The "easy" problem instances that can be solved using h0 provide training examples for a learning algorithm that produces a heuristic h1 that is expected to be stronger than h0. If h0 is too weak to solve any of the given instances we use a random walk technique to create a sequence of successively more difficult instances starting with ones that are solvable by h0. The bootstrap process is then repeated using hi in lieu of hi–1 until a sufficiently strong heuristic is produced. We test our method on the 15- and 24-sliding tile puzzles, the 17- and 24-pancake puzzles, and the 15- and 20-blocks world. In every case our method produces a heuristic that allows IDA* to solve randomly generated problem instances extremely quickly with solutions very close to optimal.

Downloads

Published

2010-08-25