Hierarchical task network planning

 

 

 

 

 

Tero Hagström

Tik-76.275 Seminar on Knowledge Engineering

11.12.1997

 

 

Table of contents

1. Introduction

1.1 Motivation of HTN planning

1.1.1 A natural way to design

1.1.2 Hierarchical decomposition

1.2 History

2. Formalism

2.1 An overview of HTN planning

2.2 Basic concepts

2.3 Basic algorithm

2.4 Syntax for HTN planning

2.5 UMCP

2.5.1 A provably correct planning algorithm

2.5.2 The implementation

3. Constraints in UMCP

3.1 Using constraints

3.2 Domain-specific critics

4. Analysis

4.1 Complexity

4.2 Expressivity: HTN vs. state-based

5. Application fields

6. Conclusions

7. References

7.1 Publications

7.2 Web sites

 

  1. Introduction

    2. This paper first considers some ideas and motivation behind HTN planning, and also some history of the field.

    Next part formalises the concepts of HTN planning, and represent a provably correct HTN algorithm based on the formalism.

    Chapter 3 discusses the role of critics and constraints.

    In chapter 4 HTN planning is analysed from the view of complexity and expressivity. The latter is done as a comparison to STRIPS-type planning.

    Finally we take a look on some real-world applications.

    1. Motivation of HTN planning
      1. A natural way to design

When dealing with complex systems, a natural approach is to divide it into subsystems that can be studied separately without constant attention to their interactions. For example, when studying a car, it can be divided into body, transmission, electrical system, engine, steering system and fuel system. This approach is natural to humans both in studying and designing complex systems. Some motivations behind it are:

  1. The apparent complexity of the problem can be reduced by partitioning it.
  2. The partitioning can be done before considering the details of the subsystems, because they are irrelevant to the global design.
  3. The labour can be divided among many designers.

First two points apply also to planning systems. And the third also, if we consider distributed planning.

Complex systems can be divided into subsystems, but some interactions between the subsystems remain. If we think of the previous car example, we see, that engine can not be designed independently from fuel system, electrical system, transmission and body, but all these subsystems must be designed to work together.

These interactions may be weak, but they can not be neglected. This idea of a complex system built from loosely coupled subsystems is known as nearly decomposable system.

When this idea is applied to design process and planning, it results in nearly independent subproblems. In hierarchical planning solution is first sketched out as abstract steps, which are then refined into specific operations during planning process. This is called hierarchical decomposition.
      1. Hierarchical decomposition

Hierarchical decomposition is an approach used by many practical planners to address the problem complexity.

If a planning problem is considered on a very low level, the number of steps involved in the plan becomes too big, and a solution will not be found in a reasonable time. On the other hand, if the problem is only considered on a high level, no actual actions will result from the plan, and it cannot be carried out.

Hierarchical composition allows nonprimitive operators to be included in plans, with a known decomposition into more primitive steps. An abstract (nonprimitive) operator can be decomposed into a group of steps, which together form a plan that implement the abstract operator.

Figure 1. Example of a nonprimitive operator with two different decompositions.

It all seems such a great idea at first thought, but one has to remember, that subproblems interact. One of the main concerns in hierarchical planning is finding interactions among subproblems and resolving the conflicts.

One way of dealing with conflicts resulting from the interactions is the use of critics. Critics are procedures for recognising and resolving interactions.
    1. History

Abstraction hierarchies were introduced by Sacerdoti, in the ABSTRIPS system, 1974. They are a way of coping with the large size of the search space, and focusing on the most critical parts of the problem first. All conditions of the planning domain are given a criticality level (using heuristic methods), and planning proceeds in levels, starting with highest criticality level. This is not quite the same as hierarchical decomposition, because no decomposition of abstract operators (or tasks, as they are sometimes called) is done.

Task decomposition techniques were first introduced in the NOAH system developed by Sacerdoti in the mid 70's, and were enhanced in NONLIN by Tate in 1977.

NOAH represented planning problems as partially ordered lists of tasks. The information of how to decompose tasks was encoded procedurally in 'soup code'. Soup code was a collection of procedures, that handled task decomposition. The name implies, that domain knowledge on how to decompose tasks was not very easy to describe in the system. NOAH used an improved version of critics to find and resolve interactions between tasks. (Critics are procedures for finding and resolving interactions between subproblems.) Critics were first introduced by Sussman in 1975 in HACKER system for dealing with interacting subgoals. Sussman's critics used heuristic methods for identifying and patching conflicts between subgoals. HACKER stored patches that worked well for later use in similar problems, so it can be seen as a sort of case-based planner.

The representation of task decomposition knowledge was clarified in NONLIN, which represented the decomposition of tasks in a declarative way with 'opschemas', instead of the 'soup code'. It also used backtracking when an incorrect planning decision was made, unlike NOAH, which would fail in that situation.

SIPE, designed by Wilkins in 1983, used a taxonomy for storing the characteristics of objects in the domain. It placed emphasis on resource management and interaction with the user of the planning system.

Unlike most state-based planners, HTN planners have had success in practical applications. See chapter 5.
  1. Formalism

    2. This chapter presents a formalism for HTN planning as presented by Erol in [1]. But first, a short intuitive introduction to HTN planning is given in chapters 2.2 and 2.3.

    1. An overview of HTN planning

      2. In HTN planning representations of actions and world states are similar to those used in state-based planning. Each state is represented with a set of atoms (atomic predicate formulae) true in that state. Actions, or primitive tasks, are represented using STRIPS-type operators.

      The main difference between state-based planning and HTN planning is what they plan for. In the former the objective is to find a sequence of actions that change the world state so that it satisfies the goals. In the latter planners search for plans that accomplish task networks, not just goals.

    2. Basic concepts

      3. A task network is a collection of tasks that need to be accomplished, and constraints. Constraints define the order the tasks can be carried out, the way variables can be instatiated, and what literals must be true before or after each task is performed.

      A task network consisting only of primitive tasks (tasks that can be performed with one action), is a primitive task network. Such is the case in scheduling problems, where the planner tries to find a task ordering and variable bindings that satisfy all the constraints of the primitive task network.

      In a general case though, a task network can contain non-primitive tasks, which the planner has to accomplish in some way. A non-primitive task is an activity, which cannot be performed with one action. Ways of carrying out non-primitive tasks are represented by methods. A method is of the form (a, d), where a is the non-primitive task, and d is a task network that accomplishes a when all its tasks are achieved without violating its constraints.

    3. Basic algorithm

HTN planning works basically in the following way:
    1. Input a planning problem P.
    2. If P contains only primitive tasks, then resolve the conflicts in P and return the result. If conflicts cannot be resolved, return failure.
    3. Choose a non-primitive task t in P.
    4. Choose an expansion d for t.
    5. Replace t with d.
    6. Use critics to find interactions among tasks in P, and suggest ways of handling them.
    7. Apply one of the ways suggested in step 6.
    8. Go to step 2

Expanding a non-primitive task is done by finding a method that accomplishes the task, and replacing the task with the task-network produced by the method.

The task network produced may contain conflicts caused by interactions between tasks. Critics are used for finding and resolving those interactions.
    1. Syntax for HTN planning

In [1] Erol presents a formal syntax for HTN planning. It is a long list of concept definitions, with some explanations and examples thrown in.

A language L for HTN planning is a first-order language with some extensions.

Def: Vocabulary of L is a tuple <V, C, P, F, T, N>, where V is an infinite set of variable symbols, C is a finite set of constant symbols, P is a finite set of predicate symbols, F is a finite set of primitive-task symbols, T is a finite set of compound-task symbols, and N is an infinite set of symbols used for labeling tasks. All these symbols are mutually disjoint.

Def: A state is a list of ground atoms.

Atoms in the list are true in that state, and atoms not in the list are false in that state. This is the same principle as in STRIPS-type planning.

Def: A primitive task has the form do[f(x1,...xk)], where f Î F and x1,...xk are terms.

A primitive task has exactly one operator in the domain.

Def: Operator has the form [operator f(v1,...vk)
:pre l1,...lm :post l'1...l'm]

This is slightly different from STRIPS-type syntax: delete list and add list are represented as one postcondition list, with deleted atoms negated.

Def: A plan is a sequence of ground primitive tasks.

Def: A goal task has the form achieve[l], where l is a literal. A compound task has the form perform[t(x1,...,xk)], where tÎ T and x1,...xk are terms.

Def: A task network has the form [(n1: a1)...(nm: am), f], where each ai is a task, each ni Î N is a label for ai and f is a boolean formula constructed from atomic HTN constraints. f can contain the usual logic connectives conjunction, disjunction, and negation.

Atomic constraint types are:

Using constraints are discussed in more detail in chapter 3.

Example. Using the definitions we have so far, we can derive a formal representation of the task network in the figure:

Figure 2 A graphical representation of a task network.

[(n1: achieve[clear(v1)])(n2: achieve[clear(v2)])(n3: do[move(v1, v3, v2)])
(n1 < n3) Ù (n2 < n3) Ù (n1, clear(v1), n3) Ù (n2, (clear(v2)), n3) Ù
(on(v1, v3), n3) Ù Ø (v1 = v2) Ù Ø (v2 = v3) Ù Ø (v1 = v3)]

Figure 3 A formal representation of a task network.

Def: A task network containing only primitive tasks is called a primitive task network.

Def: A method is a construct of the form (a, d), where a is a non-primitive task and d is a task network.

This means, that one way of accomplishing a is to accomplish the task network d (accomplish all the tasks in the task network without violating constraints). A non-primitive task can have an arbitrary number of methods. As an example, a method for achieving on(v1, v2) could be (achieve(on(v1, v2)), d), where d is the task network in Figure 3.

Def: A planning domain D is a pair <Op, Me>, where Op is a list of operators, and Me is a list of methods.

Def: A planning problem instance P is a triple <d, I, D>, where D is a planning domain, I is the initial state, and d is the input task network to plan for.
    1. UMCP

      2. In [1] Erol presents a provably correct HTN algorithm that he calls UMCP (Universal Method-Composition Planner). He also presents the realisation of the abstract algorithm into the UMCP planning system.

      1. A provably correct planning algorithm
    1. Input a planning problem P = <d, I, D>.
    2. If d is primitive, then
      If comp(d, I, D) != 0, return a member of it.
      Otherwise return Failure.
    3. Pick a non-primitive task node (n: a) in d.
    4. Nondeterministically choose a method m for a.
    5. Set d = reduce(d, n, m)
    6. Set G = t(d, I, D)
    7. Nondeterministically set d = some element of G.
    8. Go to step 2.

comp(d, I, D) is the set of plans that accomplish the primitive task network d in domain D.

reduce(d, n, m) is a task network obtained from non-primitive task network d by substituting task labelled n with the task network resulting from decomposition according to method m.

t is a critic function, which takes as input an initial state I, a task network d, and a planning domain D. It produces as its output a set of task networks G. Each member of G is a candidate for resolving some of the conflicts in d. Only some, because some conflicts would be too expensive or impossible to resolve at a given level, so handling them will be postponed.

Two restrictions are required on t to ensure that it preserves soundness and completeness:

Let d' Î t(d, I. D) be a set of task networks produced by a critic t.
    1. Any plan for d' must be a plan for d (soundness).
    2. If there is a plan for d (no more than k task expansions away), then there is a plan for some d' (no more than k task expansions away). (completeness)

The proof of the soundness and correctness of Erol's algorithm includes a gruelling list of definitions, so it will not be included here.

      1. The implementation

UMCP was implemented using Common Lisp. The implementation can be downloaded [6] with instructions for installing, running and domain definition

UMCP uses branch-and-bound approach to prune search space by eliminating in advance some variable bindings, orderings or methods, that would lead to dead ends. UMCP works by refining a task network into a set of task networks, whose sets of solutions together form the set of solutions for the original task network. The task networks whose sets of solutions are determined to be empty, are filtered out.

UMCP has both domain-dependent and domain-independent critics. The domain-dependent critics are user-definable procedures, which the user is free to write as long as he meets the soundness and completeness restrictions mentioned earlier. Domain-independent critics are constraint-refinement algorithms described in more detail in chapter 3.1.

Erol developed a benchmarking domain [5]of his own, since the classics 'Blocks World' and 'Towers of Hanoi' weren't complex enough to evaluate UMCP's features and capabilities. This domain, which he calls UM Translog, deals with transport logistics.
  1. Constraints in UMCP

    2. As mentioned before, many planning systems use critics to deal with interactions. Critics help prune the search space by detecting dead ends in advance and by resolving many types of conflicts as soon as they appear.

    UMCP implements the function of domain-independent critics with constraint refinement algorithms. Erol states, that interactions are based on constraints and the influence of primitive tasks on constraints. Thus interaction detection and conflict resolution are viewed as a constraint satisfaction problem.

    1. Using constraints

UMCP uses constraint refinement techniques for constraint satisfaction. These techniques include
  1. Constraint selection, which chooses the constraints to work on.
  2. Constraint enforcement, which produces a set of task networks, one task network for each way of enforcing the selected constraints. This phase adds commitments to make the constraints true.
  3. Constraint propagation, which for each task network tries to enforce the constraints on its promissory list (the list of constraints that could not be made true at the current level of detail in the task network).
  4. Constraint evaluation, which evaluates the constraint formula of each task network and filters out the task networks whose formula evaluates to false.

Figure 4 Constraint refinement in UMCP.
    1. Domain-specific critics

The capabilities and performance of UMCP can be further enhanced with domain-specific critics. They are user defined procedures that input a task network and output a set of task networks. It is the responsibility of the domain engineer writing the domain-specific critics to ensure, that they preserve soundness, completeness and systemacity.

Erol's paper does not discuss domain-specific critics in detail, and does not include any examples of them.
  1. Analysis
    1. Complexity

      2. Plan existence in HTN planning is a semi-decidable problem. That may seem surprising, since the state space is finite (the number and size of states). But HTN planning can represent compound tasks, that accomplish something, that requires going through the same state many times.

      Plan existence can be made decidable by restricting the methods to be acyclic. Then a task can be expanded to only a finite depth, and the effective state space also becomes finite.

      Another way of making plan existence decidable is to restrict the interactions among the tasks. This can be achieved by restricting the task networks to be totally ordered (forbid interleaving subtasks of different tasks).

    2. Expressivity: HTN vs. state-based

    In [1] Erol compares the expressivity of HTN planning and STRIPS-type planning, and states that HTN planning is strictly more expressive. He presents complexity-based, model-theoretic, and operational expressivity results that all support the fact.

    HTN paradigm provides all the concepts STRIPS does (states, actions, goals), but STRIPS lacks the concepts of constraints, compound tasks, task networks and task decomposition. This implies, that HTN planning is more expressive.

    In state-based planning it is for example difficult to express the task of making a round-trip to Turku, because the initial and final states are the same.

  2. Application fields

    3. HTN planners have been used for many real-world purposes. This chapter describes some applications of different HTN planning systems. For details and differences of the planning systems see chapter 1.2, History.

    NOAH was used in mechanical engineers apprentice supervision, NONLIN was applied to electricity turbine overhaul, DEVISER was applied to Voyager spacecraft mission sequencing.

    SIPE and SIPE 2 [7] have been applied to air campaign planning, military operations planning, oil spill response, production line scheduling and construction planning.

    Figure 5 Architecture of the SIPE-2 system.

    Optimum-AIV is a planner used by the European Space Agency in the assembly, integration, and verification of spacecraft. The system was used both in generating plans and in monitoring their execution. Optimum-AIV is based on the open planning architecture O-Plan by Currie and Tate.

    O-Plan [4] is an open planning architecture upon many practical planning systems have been developed. These systems include software acquisition planning, back axle assembly process planning (Jaguar Cars), factory production planning at Hitachi, space platform construction, satellite planning and control, house building, logistics and non-combatant evacuation operations.

  3. Conclusions

    4. HTN planning has reached a firm position in the field of planning, especially in practical systems. Most of the practical planners today are HTN planners.

    This is so partly because hierarchical planning is intuitive for people, partly because HTN approach makes it possible to have more control over the planning process than STRPIS-type planning. HTN representation resembles the way people think and design, so designing and using HTN systems is comparatively easy. Task decomposition gives a powerful and elegant way of controlling domain knowledge on different levels of detail.

    It is often argued whether HTN planning is more expressive than STRIPS-type planning, or not. Some claim that it is strictly so, and give examples of problems that are supposedly impossible to represent with STRIPS syntax. While those claims may not be entirely accurate, it is easy to accept, that some problems are very awkward in STRIPS-type representation.

    In spite of its advantages and success in practical systems HTN paradigm has not overthrown the position of classical STRIPS-type planning. Instead the both approaches are being studied further.

  5. References
    1. Publications
      2.

      [1] Kutluhan Erol. Hierarchical task network planning: Formalization, analysis and implementation. University of Maryland at College Park, Dept. of Computer Science, 1995.

      [2] Stuart Russell and Peter Norvig. Artificial intelligence: A modern approach. Prentice-Hall, 1995.

      [3] Mark Stefvik. Planning with constraints (MOLGEN: Part 1). Standford University, Dept. of Computer Science.

    2. Web sites

[4] http://www.aiai.ed.ac.uk/~oplan/
O-Plan (Open Planning Architecture) home page.

[5] http://www.cs.umd.edu/projects/plus/UMT/
UM Translog planning benchmark domain is available here.

[6] http://www.cs.umd.edu/projects/plus/umcp/
Lisp implementation of UMCP (Universal Method Composition Planner, a sound and complete HTN planner) with graphical user interface is available here.

[7] http://www.ai.sri.com/~sipe/
SIPE home page.