Justified plans and ordered hierarchies

The use of abstraction in problem solving is an effective approach to reducing search, but finding good abstractions is a difficult problem. The first attempt to automatically generate a hierarchy of abstraction spaces was made by Sacerdoti in 1974. In 1990 Knoblock built the system ALPINE, which completely automates the formation of a hierarchy by abstracting preconditions of operators. To formalize his method, Knoblock introduced the notion of ordered abstraction hierarchies, which captures the intuition behind "good" hierarchies. In this thesis we continue the work started by Knoblock. We present further formalization of several important notions of abstract planning and describe methods to increase the number of abstraction levels without violating the ordered property of a hierarchy. We start by defining the justification of a non-linear plan. Justification captures the intuition behind "good" plans, which do not contain useless actions. We introduce several kinds of justification, and describe algorithms that find different justifications of a given plan by removing useless operators. We prove that the task to find the "best possible" justification is NP-complete. The notion of justified plans leads us to define several kinds of semi-ordered abstraction hierarchies, which preserve the "good" properties of Knoblock's ordered hierarchies, but may have more abstraction levels. Finally, we present an algorithm for automatically abstracting not only preconditions but also effects of operators. This algorithm generates hierarchies with more levels of abstraction than ALPINE, and may increase the efficiency of planning in many problem domains. The algorithm may generate both problem-independent and problem-specific hierarchies.