SEARCH, SATISFIABILITY, AND CONSTRAINT SATISFACTION PROBLEMS SEARCH, SATISFIABILITY, AND CONSTRAINT SATISFACTION PROBLEMS SEARCH Incomplete Tree Search using Adaptive Probing

When not enough time is available to fully explore a search tree, different algorithms will visit differ-ent leaves. Depth-first search and depth-bounded discrepancy search, for example, make opposite as-sumptions about the distribution of good leaves. Unfortunately, it is rarely clear a priori which al-gorithm will be most appropriate for a particular problem. Rather than fixing strong assumptions in advance, we propose an approach in which an al-gorithm attempts to adjust to the distribution of leaf costs in the tree while exploring it. By sacrificing completeness, such flexible algorithms can exploit information gathered during the search using only weak assumptions. As an example, we show how a simple depth-based additive cost model of the tree can be learned on-line. Empirical analysis using a generic tree search problem shows that adaptive probing is competitive with systematic algorithms on a variety of hard trees and outperforms them when the node-ordering heuristic makes many mis-takes. Results on boolean satisfiability and two dif-ferent representations of number partitioning con-firm these observations. Adaptive probing com-bines the flexibility and robustness of local search with the ability to take advantage of constructive heuristics.