SHOP2 can do axiomatic inference, mixed symbolic/numeric computations, and calls to external programs.

SHOP2 also has capabilities that go significantly beyond those of SHOP:

- **SHOP2 allows tasks and subtasks to be partially ordered; thus plans may interleave**
subtasks from different tasks. This often makes it possible to specify domain knowledge in a more intuitive manner than was possible in SHOP.

- **SHOP2 incorporates many features from PDDL, such as quantifiers and conditional**
effects.

- **If there are alternative ways to satisfy a method's precondition, SHOP2 can sort the**
alternatives according to a criterion specified in the definition of the method. This gives a convenient way for the author of a planning domain to tell SHOP2 which parts of the search space to explore first. In principle, such a technique could be used with any planner that plans forward from the initial state.

- So that SHOP2 can handle temporal planning domains, we have a **way to translate**
temporal PDDL operators into SHOP2 operators that maintain **bookkeeping information for multiple timelines within the current state. In principle, this technique**
could be used with any non-temporal planner that has sufficient expressive power.
The rest of this paper is organized as follows. Section 2 gives some background on HTN
planning, and Section 3 describes SHOP2's features and planning algorithm. Section 4 describes how to write domain descriptions for SHOP2: in particular, Section 4.1 discusses basic problem-solving strategies, and Sections 4.2 and 4.3 **describe aspects of SHOP2 that**
are specific to handling temporal and metric domain features. Section 5 discusses SHOP2's performance in the competition, Section 6 discusses related work, and Section 7 gives a summary and conclusion. Appendix A contains a SHOP2 domain description for one of the problem domains in the planning competition.

## 2. Htn Planning

HTN planning is like classical AI planning in that each state **of the world is represented by** a set of atoms, and each action corresponds to a deterministic state transition. However, HTN planners differ from classical AI planners in what they plan for, and how they plan for it.

The objective of an HTN planner is to produce a sequence of actions that perform some activity or *task***. The description of a planning domain includes a set of operators similar** to those of classical planning, and also a set of *methods***, each of which is a prescription for**
how to decompose a task into *subtasks* **(smaller tasks). Figure 1 gives a simple example.**
Given a planning domain, the description of a planning problem will contain an initial state like that of classical planning—but instead of a goal formula, the problem specification will contain a partially ordered set of tasks to accomplish.

Planning proceeds by using the methods to decompose tasks recursively into smaller and smaller subtasks, until the planner reaches *primitive tasks* that can be performed directly using the planning operators. For each nonprimitive **task, the planner chooses an**