## Justified plans and ordered hierarchies

### Eugene Fink

Master Thesis, Department of Computer Science, University of
Waterloo, 1992. Techcnical Report CS-92-42.

### Abstract

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.