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 systems. There is much recent analysis of the properties of total- and partial-order planning systems using STRIPS-style planning operators. STRIPS-style planning systems, however, were developed more than twenty years ago, and most of the practical work on AI planning systems during the last fifteen years has been based on hierarchical task network (HTN) decomposition. Until now, there has been very little analytical work on the properties of HTN planners. 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 this project is to define, analyze, and explicate features of the design of HTN planning systems. We have done the following to this end:
- We have developed a logical formalism for HTN planning systems including a syntax for expressing HTN constructs, a model-theoretic semantics that precisely defines the meaning of HTN constructs, and an operational semantics that characterizes the set of solutions to HTN-planning problems. This formalism establishes an analytical framework enabling further research---especially in the development of correct and efficient planning algorithms for HTN planning.
- We have done a complexity analysis of HTN planning based on my formalism. This analysis revealed the source of the complexity of HTN planning to be the interactions among tasks, especially those among subtasks belonging to expansions of different tasks. We have suggested a set of restrictions to limit those kind of interactions and provided algorithms and planning techniques that would work well under those restrictions. This analysis also provided insight to the similarities and differences between STRIPS-style planning and HTN planning. It showed that HTN planners can represent and solve a broader class of planning problems than STRIPS-style planners. It also provided several polynomial transformations from STRIPS-style planning to HTN planning which allowed to transfer some of the complexity results on STRIPS-style planning to HTN planning. We anticipate the use of these transformations for adapting other analytical results on STRIPS-style planning to HTN planning as well.
- We have designed UMCP (Universal Method Composition Planner), the first provably sound and complete HTN planning procedure, and we are in the final stages of its implementation. UMCP provides a test-bed for evaluating various search control strategies and their effect on the performance of the planning systems.
One of the domains being used to test UMCP is UM Translog, a transport logistics planning domain.
- Currently, we are extending the HTN formalism to allow more general action representations such as actions with non-zero durations, whose effects can take place in different future points. We are also extending our formalism to allow numeric variables and constraints. These extensions will enable representing complex real-world applications in the HTN framework.
We also have a Common Lisp version of Tate's Nonlin planner available for ftp, UM Nonlin.