Hierarchical Task Network Planning: Formalization and Analysis

Parallel Understanding Systems Group, Computer Science Dept., University of Maryland at College Park

Abstract:

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:

Status/Availability:

The UMCP is currently under development. Contact Kutluhan Erol at kutluhan@cs.umd.edu for further information.

We also have a Common Lisp version of Tate's Nonlin planner available for ftp, UM Nonlin.

Recent Papers:

R. Tsuneto, K. Erol, J. Hendler and D. Nau. "Commitment Strategies in Hierarchical Task Network Planning" in AAAI-96, Portland, August, 1996.

K. Erol, D. Nau, J. Hendler and R. Tsuneto. "A Critical Look at Critics in HTN Planning." in IJCAI-95, Montreal, August, 1995.

K. Erol, D. Nau, J. Hendler. "UMCP: A Sound and Complete Planning Procedure for Hierarchical Task-Network Planning." In AIPS-94, Chicago, June, 1994.

K. Erol, D. Nau, J. Hendler. "HTN Planning: Complexity and Expressivity." In AAAI-94, Seattle, July, 1994.

K. Erol, D. Nau, J. Hendler."Complexity Results for Hierarchical Task-Network Planning." To appear in Annals of Mathematics and Artificial Intelligence.

People:


Enhanced with SHOE