Search Methods Using Heuristic Strategies

Abstract

Real-valued heuristic functions have been extensively used as a means for constraining search in large problem spaces. In this paper we look at an alternative approach, called strategic search, in which heuristic information is expressed as strategies. Strategic search generates a search graph by following some strategy or set of strategies, backtracking to previous choice points when the current strategy f ails. We first examine algorithms for performing strategic search using both determinisitic and nondeterministic strategies. Some examples are given which indicate that strategic search can out-perform standard heuristic search methods. The construction of strategies is also considered, and ~eansfor acquiring strategic information both from analagous problems and from example execution traces are described. Finally, we indicate how meta-level strategies can be used to guide the application of object level strategies, thus providing a hierarchy of strategic information.