On the construction of heuristic functions
George Politowski · 1986
The performance of a heuristic search algorithm is determined by the accuracy of the heuristic. This suggests that the formulation of heuristics is one of the most crucial areas in the application of heuristic search. Despite this there has been little research to establish a methodology for discovering and refining heuristics. Heuristics have typically been ad hoc functions that the researcher tinkered with until reasonable performance was obtained. These functions were generally linear polynomials based on a small number of easily computable features. More recently, Pearl has suggested that heuristics can be derived from relaxed models of problem domains. Our current work concerns both of these approaches to the discovery of heuristics. We have developed a theory of parameter-based heuristic functions. In this theory the heuristic function is represented as an explicit set of feature vectors and their corresponding heuristic values. We show under what conditions the addition of parameters can never worsen the performance of such a heuristic. We suggest a simple method whereby interaction with a search system can facilitate the discovery of useful parameters or features. We show how this approach leads to an admissible but inconsistent heuristic. We then present a search algorithm that is more informed than A* when both are used with the same admissible, inconsistent heuristic. Our work with the notion of models takes two forms. First, we show that the heuristic information generated by a model can be considered as simply another parameter within the parameter-based theory. We feel that this combined approach is the most promising one for practical problems. Second, we use this combined approach to construct highly effective heuristics for both the 15-puzzle and the 2 x 2 x 2 version of the Rubik's cube. The latter puzzle is well known for its resistance to simple heuristics. To our knowledge, this is the first successful construction of a distance-estimating heuristic for that puzzle. This was accomplished despite the fact that we ourselves are not adept at solving the puzzle.