Variations of A* for searching in abstraction hierarchies.

Abstract

The aim of this work is to show the usefulness of abstraction in heuristic search. We use the abstract spaces created by applying abstraction techniques to the original problem. These abstract spaces are then used to generate all the heuristic information necessary in order to find an optimal or near optimal solution to the original problem. One of our objectives is to preserve optimal paths while speeding up search. We have developed new approaches to speed-up A$\sp{*}$ in an abstraction hierarchy: abstract solutions, minimum edge weight, P-G to generated heuristics from the length of the solution path for those nodes visited during search, and reuse of heuristic information generated from previous searches. We also consider an approach which postpones the calculation of heuristics obtained by searching in the abstract space. This approach is referred to as Lazy Evaluation. Another of our objectives is to achieve more speed in search sacrificing optimality. For this we introduce a technique called Selective Method. Our last objective is to identify which abstraction method is the best for the search. We build abstraction hierarchies with different abstraction methods and we evaluate them using different search techniques: Classical Refinement (CR), Optimal Refinement (OR), and Alternating Opportunism (AO), and our variations of A$\sp{*}$.