Bootstrap Learning of Heuristic Functions

search algorithms such as IDA* or heuristic-search planners. Our method aims to generate a strong heuristic from a given weak heuristic h 0 through bootstrapping. The "easy" problem instances that can be solved using h 0 provide training examples for a learning algorithm that produces a heuristic h 1 that is expected to be stronger than h 0 . If h 0 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 h 0 . The bootstrap process is then repeated using h i in lieu of h i –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.