This article appeared in a journal published by Elsevier. The attached copy is furnished to the author for internal non-commercial research and education use, including for instruction at the authors institution and sharing with colleagues. Other uses, including reproduction and distribution, or selling or licensing copies, or posting to personal, institutional or third party websites are prohibited. We investigate the use of machine learning to create effective heuristics for search algorithms such as IDA * or heuristic-search planners such as FF. Our method aims to generate a sequence of heuristics from a given weak heuristic h 0 and a set of unsolved training instances using a bootstrapping procedure. The training 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 so weak that it cannot solve any of the given instances we use random walks backward from the goal state to create a sequence of successively more difficult training instances starting with ones that are guaranteed to be 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 this method on the 24-slidingtile puzzle, the 35-pancake puzzle, Rubik's Cube, and the 20-blocks world. In every case our method produces a heuristic that allows IDA * to solve randomly generated problem instances quickly with solutions close to optimal. The total time for the bootstrap process to create strong heuristics for these large state spaces is on the order of days. To make the process effective when only a single problem instance needs to be solved, we present a variation in which the bootstrap learning of new heuristics is interleaved with problem-solving using the initial heuristic and whatever heuristics have been learned so far. This substantially reduces the total time needed to solve a single instance, while the solutions obtained are still close to optimal.
In combinatorial search, FFNs have been used as heuristic functions for the sliding-tile puzzle and Rubik's Cube REF .
Learning heuristic functions for large state spaces
Artif. Intell.
Artif. Intell.
Mathematics Computer Science