Adaptive Search by Explanation-Based Learning of Heuristic Censors

Abstract

We introduce an adaptive search technique that speeds up state space search by learning heuristic censors while searching. The censors speed up search by pruning away moTe and more of the space until a solution is found in the pruned space. Censors are learned by explaining dead ends and other search failures. To learn quickly, the technique over-generalizes by assuming that certain constraints aTe preservable, i.e., remain true on at least one solution path. A recovery mechanism detects violations of this assumption and selectively relaxes learned censors. The technique, implemented in an adaptive problem solver named FAILSAFE-2, learns useful heuristics that cannot be learned by other reported methods. Its effectiveness is indicated by a preliminary complexity analysis and by experimental results in three domains, including one in which PRODIGY failed to learn eflective search control rules.