Bootstrap Learning of Heuristic Functions

Proceedings of the International Symposium on Combinatorial Search, 3

Volume

Vol. 3 No. 1 (2010): Third Annual Symposium on Combinatorial Search

Oral Presentations

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.

10.1609/socs.v1i1.18159