Publication year: 2011
Source: Artificial Intelligence, Volume 175, Issues 16-17, October-November 2011, Pages 2075-2098
Shahab Jabbari Arfaee, Sandra Zilles, Robert C. Holte
We investigate the use of machine learning to create effective heuristics for search algorithms such asor heuristic-search planners such as FF. Our method aims to generate a sequence of heuristics from a given weak heuristicand a set of unsolved training instances using a bootstrapping procedure. The training instances that can be solved usingprovide training examples for a learning algorithm that produces a heuristicthat is expected to be stronger than. Ifis 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. The bootstrap process is then repeated usingin lieu ofuntil a sufficiently strong heuristic is produced. We test this method on the 24-sliding-tile puzzle, the 35-pancake puzzle, Rubikʼs Cube, and the 20-blocks world. In every case our method produces a heuristic that allowsto 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.