Toward a General Framework for Hierarchical Task-Network Planning

Foundations of Automatic Planning - The Classical Approach and Beyond

Volume

Papers from the 1993 AAAI Spring Symposium

Contents

In AI planning research, planning practice (as embodied in implemented planning systems) tends to run far ahead of the theories that explain the behavior of those planning systems. For example, the past few years have seen much analysis of the properties of totally- and partially-ordered planning systems using STRIPS-style planning operators. However, most of the practical work on AI planning systems for the last fifteen years has been based on hierarchical task-network (HTN) decomposition as opposed to STRIPS systems, yet there has been very little similar analytical work on the properties of hierarachical task-network (HTN) planning systems. One of the primary obstacles impeding such work has been the lack of a clear theoretical framework explaining what a HTN planning system is. A primary goal of our current work is to correctly define, analyze, and explicate features of the design of HTN planning systems. In this report, we describe some first steps toward that goal: We set out a formal definition of HTN planning, present a nondeterministic HTN planning procedure P_HTN that is general enough to include most existing HTN planning procedures as special cases, and present theorems showing that P_HTN is sound and complete. In addition, we present theorems showing that if P_HTN is run on planning problems P1 and P2 that equivalent except that P2 has more informed methods and/or critics, then P_HTN will perform more efficiently on P2. These results are analogous to the informedness results for the well-known A* search procedure.