Forbidding Preconditions and Ordered Abstraction Hierarchies

Foundations of Automatic Planning - The Classical Approach and Beyond

Volume

Papers from the 1993 AAAI Spring Symposium

Contents

The use of abstraction in problem solving is an effective approach to reducing search, but finding good abstractions is a difficult problem. The first algorithm that completely automates the generation of abstraction hierarchies is Knoblock’s ALPINE. The algorithm is based on the notion of ordered abstraction hierarchies, which formalizes an important intuition behind "good" hierarchies. In this paper we continue the work on formalizing the notion of ordered hierarchies. The paper shows that the hierarchies generated by ALPINE are over-constrained by restrictions that are not necessary for the ordered monotonicity property. We present necessary and sufficient conditions for an abstraction hierarchy to be ordered and describe an algorithm based on these conditions to improve the quality of abstraction hierarchies.