Seminar on Computational Learning and Adaptation

 Learning to Search Trees

Wheeler Ruml
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, CA 94304 USA

Heuristic best-first search has long been a core topic in AI, but most work has concentrated on shortest-path problems.  I'll present an algorithm, best-leaf-first search (BLFS), that extends heuristic search to the problem of finding the best leaf in a tree of bounded depth (combinatorial optimization or constraint satisfaction problems).  BLFS maintains an explicit model of the search tree that predicts the costs of leaves.  The algorithm uses the model to visit leaves in an efficient approximation of increasing predicted cost.  By learning the cost model on-line, BLFS can derive an appropriate search order directly from the tree during the search.  Empirical results show that this adaptive approach can outperform existing methods on challenging optimization and constraint satisfaction benchmarks.  In addition to generalizing previous approaches, BLFS unifies search for combinatorial optimization with traditional work in AI on shortest-path problems.
 

Return to the seminar schedule