Adaptive Search by Explanation-Based Learning of Heuristic Censors

Neeraj Bhatnagar, Jack Mostow

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 more 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 are 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 effective search control rules.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.