Strategies in heuristic search

摘要

Real-valued heuristic functions have been extensively used as a means for constraining search in combinatorially large problem spaces. In this paper we look at an alternative approach, called strategic search, in which heuristic information is expressed in the form of problem specific strategies. A strategy is considered to be a (possibly partial) function which for a given state in some problem domain returns sequences of states over the problem domain. The strategy is intended to guide one towards a goal state, but there is no guarantee of success. Strategic search generates a search graph by following some strategy or set of strategies, backtracking to previous choice points when the current strategy fails. We first examine algorithms for performing strategic search using both deterministic and non-deterministic (multiple) strategies. Some examples are given which indicate that strategic search can outperform standard heuristic search methods. We then describe some algorithms which are shown to be admissible when the strategy satisfies certain conditions. The construction of strategies is also considered, and means for acquiring strategic knowledge both from analogous problems and from example execution traces are described. Finally, we indicate how these techniques can be extended to hierarchically organized problem spaces and show how meta-level strategies can be used to guide the application of object level strategies.