Translating HTNs to PDDL: A Small Amount of Domain Knowledge Can Go a Long Way

1 Introduction

Most classical planners are either domain-independent, hence work in any classical planning domain, or domainconfigurable, hence can exploit domain-specific knowledge. Each approach has advantages and disadvantages:

• Domain-configurable planners can read and make use of domain-specific planning knowledge, typically in the form of control rules (e.g., TLPlan [Bacchus and Kabanza, 2000] and TALplanner [Kvarnstr¨om and Doherty, 2001]) or HTN methods (e.g., SIPE-2 [Wilkins, 1988], O-PLAN [Currie and Tate, 1991], SHOP [Nau et al., 1999], and SHOP2 [Nau et al., 2003]). Using this domain knowledge, such planners can solve much larger planning problems, and solve them more quickly, than domain-independent planners. But the domain-specific knowledge used by these planners can sometimes be quite complicated, hence difficult for the general user to specify.
• Domain-independent planners, such as FastForward (FF) [Hoffmann and Nebel, 2001], AltAlt [Nguyen et al., 2002], SGPlan [Chen et al., 2006], HSP [Bonet and

∗This work supported in part by AFOSR grant FA95500610405, NAVAIR contract N6133906C0149, DARPA's Transfer Learning Program, DARPA IPTO grant FA8650-06-C-7606, and NSF grant IIS0412812. The opinions in this paper are those of the authors and do not necessarily reflect the opinions of the funders.

Geffner, 1999], Fast Downward [Helmert, 2006], and LPG [Gerevini et al., 2003], usually do not need any domainspecific knowledge other than the planning operators for a domain. This makes it much easier for the general user to specify the input to these planners. On the other hand, a domain-independent planner may perform much worse in a given domain than a domain-configurable planner that has been given a good set of domain knowledge.

We show that HTN planning knowledge, if it satisfies some restrictions, can automatically be translated into PDDL, and that even small amounts of such knowledge can greatly improve a classical planner's performance. In particular:

• We describe how to translate a restricted class of HTN methods and operators into PDDL. We provide theorems showing that our translation is correct, that its time and space complexity are both linear, and that it can be used even on partial HTN models of a domain (which can be much easier to write than full HTN models).
• Our experiments show that by translating partial HTN models into PDDL, we can substantially improve a classical planner's performance. In experiments with the wellknown Fast-Forward (FF) planner [Hoffmann and Nebel, 2001] on more than 3500 planning problems, the translated knowledge improved FF's running time by several orders of magnitude, and enabled it to solve much larger planning problems than it could otherwise solve.

2 Basic Definitions and Notation

Classical Planning. Our definitions for classical planning are based on the ones in [Ghallab et al., 2004].

Let L be the set of all literals in a function-free first-order language. A state is any set of ground atoms of L. A classical planning problem is a triple P = (s0, g,O), where s0 is the initial state, g is the goal (a set of ground literals of L), and O is a set of operators. Each operator o ∈ O is a triple

where name(o) is o's name and argument list, and precond(o) and effects(o) are sets of literals called o's preconditions and effects. An action α is a ground instance of an operator. If a state s satisfies precond(α), then α is executable in s, producing the state γ(s, α) = (s - {all negated atoms in effects(α)}) ∪ {all non-negated atoms in effects(α)}. A plan is a sequence π = 〈α1, . . . , αn〉 of actions. π is a solution for P if, starting in s0, the actions are executable in the order given and the final outcome is a state sn that satisfies g.

TSTN Planning. [Ghallab et al., 2004] describes a restricted case of HTN planning called Total-order Simple Task Network planning, which we'll abbreviate as TSTN Planning. The definitions are as follows.

A task is a symbolic representation of an activity. Syntactically, it is an expression τ = t(x1, . . . , xq) where t is a symbol called τ's name, and each xi is either a variable or a constant symbol. If t is also the name of an operator, then τ is primitive; otherwise τ is nonprimitive. Intuitively, primitive tasks can be instantiated into actions, and nonprimitive tasks need to be decomposed (see below) into subtasks.

A method is a prescription for how to decompose a task into subtasks. Syntactically, it is a four-tuple

m = (name(m), task(m), precond(m), subtasks(m)), where name(m) is m's name and argument list, task(m) is the task m can decompose, precond(m) is a set of preconditions, and subtasks(m) = 〈t1, . . . , tj〉 is the sequence of subtasks.

• A TSTN planning problem is a four-tuple P = (s0, T0, O,M), where s0 is an initial state, O is a set of operators, T0 is a sequence of ground tasks called the initial task list, and M is a set of methods.

If T0 is empty, then P's only solution is the empty plan π = 〈〉, and π's derivation (the sequence of actions and method instances used to produce π) is δ = 〈〉. If T0 is nonempty (i.e., T0 = 〈t1, . . . , tk〉 for some k > 0), then let T ′ = 〈t2, . . . , tk〉. If t1 is primitive and there is an executable action α with name(α) = t1, then let s1 = γ(s0, α). If P ′ = (s1, T ′ ,O,M) has a solution π with derivation δ, then the plan α · π is a solution to P (where · is concatenation) whose derivation is α · δ. If t1 is nonprimitive and there is a method instance m such that task(m) = t1, and if s0 satisfies precond(m), and if P ′ = (s1, subtasks(m) · T ′ , O, M) has a solution π with derivation δ, then π is a solution to P and its derivation is m · δ.

Using TSTN Planners for Classical Planning. To use a TSTN planner in a classical planning domain D (i.e., a set of classical planning problems that all have the same operator set O), the usual approach is augment D with a set M of methods and a way to translate each classical goal g into a task list T g 0 . This maps each classical planning problem P = (s0, g,O) in D into a TSTN planning problem P ′ = (s0, T g 0 ,O,M). The mapping is correct if P ′ is solvable whenever P is, and if the solutions for P ′ are also solutions for P. Since the objective is for P ′ to have a small search space, the set of solutions for P ′ may be much smaller than the set of solutions for P.

In the above mapping, we will say that M is O-complete if every operator in o ∈ O is mentioned in M, i.e., at least one method in M has a subtask that is an instance of name(o).

3 Translating TSTN to Classical

Let P = (s0, T,O,M) be a TSTN planning problem, and suppose T0 is a correct translation (as defined above) of a classical goal g. We now describe how to translate P (if a restriction holds) into a classical planning problem trans(P ) = (s′0 , g,O′ ) that is equivalent to P in the following sense: as we'll show in Section 4, there is a one-to-one mapping from P's solution derivations to trans(P)'s solutions.

Preliminaries. We begin by introducing a restriction. For every solution π of P , let the non-tail height of π be the number of levels of method decomposition used to produce π, ignoring tail decomposition (i.e., decomposition of the last task in a task list). Then either we need to extend the planning language to include function symbols, 1 or else we must be given an upper bound H on the non-tail height of all solutions of P .

We need the above restriction in order to implement a symbolic representation of a numeric counter, to keep track of the current number of levels of task decomposition. Here is how to implement the counter when H is given: 2

• We'll introduce new constant symbols d0, d1, . . . , dH to denote levels of task decomposition, and a predicate symbol level so that the atom level(di) can be used to mean that the current level of task decomposition is di. We give a special meaning to the constant symbol d0: it marks the successful end of method decomposition process.
• To specify a total ordering of the constant symbols, we will put new atoms next(d1, d2), next(d2, d3), . . . , next(dH-1, dH) into the initial state.

In addition, for each method m(x1, . . . , xk) and task t(y1, . . . , yj) we will introduce new atoms dom(x1, . . . , xk) and dot(y1, . . . , yj).

Translating operators. Let o be any operator in O, and suppose name(o) = o(x1, . . . , xn), precond(o) = {p1, . . . , pj} and effects(o) = {e1, . . . , ek}. If o is not mentioned in M (whence M is not O-complete), then trans(o) = o. Otherwise trans(o) is the following operator o′ , which is like o except that it is applicable only when doo is true, and it decrements the counter:

We define trans(O) = {trans(o) | o ∈ O}.

Translating methods. Let m be any method in M, and suppose name(m) = m(x1, . . . , xn), task(m) = t(y1, . . . , yjt ), and precond(m) = {p1, . . . , pjm }. There are two cases:

1 PDDL includes this extension, but traditional formulations of classical planning (e.g., [Ghallab et al., 2004]) do not.

2 If H is not given but the planning language contains function symbols, we can instead use an unbounded number of ground terms 1, next(1), next(next(1)), . . . .

Case 1: subtasks(m) = ∅ (i.e., m specifies no subtasks for t). Then trans(m) is the operator m′ defined as follows:

Case 2: subtasks(m) = {t1, . . . , tk} for k ≥ 1. Then trans(m) is the set of planning operators {m′0 , . . . ,m′k } defined below, where m′0 is an operator that checks whether m is applicable, and m′1 , . . . ,m′k are operators that correspond to calling m's subtasks. The definition of m′0 is

Intuitively, m′0 's preconditions say that t is the current task and that m's preconditions hold; and m′0 's effect dom1 makes it possible to apply the planning operator m′1 that corresponds to m's first subtask.

For i = 1, . . . , k - 1, if m's ith subtask is ti(yi1, . . . , yiji ) then m′i is defined as follows:

The operator m′k , which corresponds to m's last subtask tk, is like m′i but omits the effects ¬level(v) and level(w).

We define trans(M) = ⋃m∈M trans(m).

Translating planning problems. Finally, we define trans(P ) = (s′0 , g, O′ ), where

4 Properties

The theorems in this section establish the correctness and computational complexity of our translation scheme.

Theorem 1 Let P = (s0, 〈t1, . . . , tk〉, O,M) (where k ≥ 0) be any TSTN planning problem. Let Δ = {all derivations of solutions for P}, and Π = {all solutions for trans(P)}. If M is O-complete, then there is a one-to-one correspondence that maps Δ onto Π.

Sketch of proof. We need to define a mapping F : Δ → Π and show that F is one-to-one and onto. Below we define F ; the proof that it is one-to-one and onto can be done straightforwardly by induction.

Let π be a solution for P with derivation δ. Recall that δ is the sequence of the actions and method instances used to produce π, in the order that they were applied. In particular, δ is a concatenation of subsequences δ1, . . . , δk corresponding to t1, . . . , tk. We will let F(δ) = F (δ1) · . . . · F (δk), where · denotes concatenation, and where each F(δi) is defined recursively as follows:

If δi is empty, then F(δi) also is empty. If δi is nonempty (i.e., δi = 〈αi1, . . . , αik〉), then let δ′i = 〈αi2, . . . , αik〉. There are three cases:

1. If αi1 is an action, then F(δi) = trans(αi1) · F (δ′i ).
2. If αi1 is a substitution instance mθ of a method mwith substitution θ, and subtasks(m) is empty, then F(δi) = m′ θ · F (δ′i ), where m′ is as in Case 1 of Section 3.
3. If αi1 is a substitution instance mθ of a method m and subtasks(m) is nonempty (i.e., subtasks(m) = 〈t′1 , . . . , t′j 〉 for some j > 0), then δ′i is the concatenation of subsequences δ′i1 , . . . , δ′ij produced by decomposing t′1 , . . . , t′j , respectively. In this case,

Corollary 1 In Theorem 1, if M is not O-complete, then the mapping F is one-to-one but not necessarily onto.

Sketch of proof. If M is not O-complete, then there is at least one operator o ∈ O that is not mentioned in M. Consequently, no instance of o will appear in any solution for P, nor in Δ, hence no instance of trans(o) will appear in {F(δ) | δ ∈ Δ}. But instances of trans(o) can appear in solutions to trans(P), in which case F is no longer onto. ✷

Theorem 2 The time and space complexity of computing trans(P ) are both O(|P | + H).

Sketch of proof. For each o ∈ O, trans(o) is a single operator that is computed by a linear-time scan of o, and it can be seen by inspection that the size of that operator is O(|o|). Suppose there are no non-tail recursive methods in M. This means that H = 0 in this case. For each m ∈ M, trans(m) is a set of methods that can be produced by a linear-time scan of m, and it can be seen by inspection that the set of methods has size O(|m|). If there is a non-tail recursive method inM, then H is given as input and it is a fixed number. Thus, the theorem follows. ✷

5 Implementation and Experiments

We implemented an algorithm that uses our translation technique to translate TSTN domain descriptions into PDDL, and did an experimental investigation of the following question:

In domains that are hard for a classical planner, how much can its performance be improved by PDDL translations of partial HTN knowledge?

For the classical planner, we used FF [Hoffmann and Nebel, 2001]. FF is perhaps one of the most influential classical planners available; many recent classical planning algorithms either directly depends on generalizations of FF or they incorporate the core ideas of FF in their systems.

For the planning domains, we chose three planning domains for which we wrote simple HTN domain descriptions with varying amounts of incompleteness: the Blocks World, the Towers of Hanoi problem, and a transportation domain called the Office Delivery domain.

The source code for our translation technique and the HTN method descriptions of the three planning domains described below are available at http://www.cs.umd.edu/ projects/planning/data/alford09translating/.

Towers of Hanoi. The Towers of Hanoi problem causes problems for many classical planners because of its combinatorial nature. On the other hand, it is almost trivially easy to write a set of HTN methods to solve the problem without any backtracking. The methods say basically the following:

· Method to move a disk:

precond: the smallest disk wasn't the last one moved subtask: move the smallest disk clockwise.

· Method to move a disk:

precond: the smallest disk was the last one moved subtask: move the other disk.

Note that in a tower of a Towers of Hanoi problem, the largest disk is always at the bottom of the tower and no disk can be place on a smaller disk - i.e., the disks in a tower are in the increasing order by their sizes with the smallest is always at the top. Thus, whether the smallest disk was the last one moved can be checked in the above methods by examining the towers to the left or to the right of a tower.

The methods above provide an almost-complete solution to the Towers of Hanoi problem, except that the second method doesn't say where to move the disk. To use the PDDL translation, FF must figure out for itself that there is only one place the disk can be moved.

Below, "FF-Plain" refers to FF using the ordinary classicalplanning definition of the Towers of Hanoi domain, and "FFHTN" refers to FF using the PDDL translations of the HTNs described above. We varied the number n of disks from 3 to 14. For each value of n, we ran FF-HTN and FF-Plain each 100 times, averaging the running times. The reason for the multiple runs is because FF makes some random choices during each run that make its running time vary from one run to another. Fig. 1 shows the results.

For FF-Plain at 14 rings (the * in Fig. 1), two runs took longer than 2 hours (our time limit per problem) to finish. We counted these runs as 2 hours each, and averaged them with the other 98 runs; hence the data point for 14 rings makes FF-Plain's performance look better than it actually was.

As shown in Fig. 1, FF-Plain's running times grew much faster than FF-HTN's did. With 14 disks, FF-HTN was about 2 orders of magnitude faster than FF-Plain.

Blocks World. The Blocks World has previously been shown to pose some difficulities for FF. Complete HTN domain descriptions can work very efficiently [Ghallab et al., 2004], but are somewhat complicated. To see how well FF could do with some simple and partial HTN knowledge, we wrote HTNmethods that said basically the following:

· Method to move a block:

precond: the block is not in its final position subtasks: pick up the block; put it in its final position.

· Method to move a block:

precond: the block is not in its final position subtasks: pick up the block; put it on the table.

At each point in the planning process, both of the methods are applicable. To use the PDDL translation of them, FF must use its heuristics to choose which of them to use.

Below, "FF-Plain" refers to FF using the ordinary classicalplanning definition of the Blocks World, and "FF-HTN" refers to FF with the PDDL translations of the methods described above. We ran both FF-HTN and FF-Plain on 100 randomly generated n-block problems for each of n = 5, 10, 15, . . . , 90, giving a total of 1800 Blocks World problems. Fig. 2 shows the results.

As before, we gave FF a 2-hour time limit for each run. At data points where all 100 runs took less than 2 hours each, the data point was the average time per run. At data points where 3 or fewer of the 100 runs failed to finish within 2 hours, we counted each failure as 2 hours when computing the average, and marked the data point with an asterisk. In all of the other cases, a large number of the 100 runs failed to finish with 2 hours, so we omitted those data points.

As shown in Fig. 2, FF-Plain could not solve problems larger than 25 blocks, but FF-HTN could solve problems up to 85 blocks. At 25 blocks, FF-HTN was about 4.2 orders of magnitude faster than FF-Plain.

Office Delivery. This is a transportation domain in which a robot needs to pick up and deliver packages in a building. It is similar to the well-known Robot Navigation Domain [Kabanza et al., 1997], with the following differences: (1) the problem is deterministic, (2) there is a variable number of rooms, and (3) some of the rooms can be quite far from the hallway (hence to get to a room r, the robot may need to go through many other rooms). For this domain, we wrote a very incomplete set of HTN methods:

· Method to move all remaining packages:

precond: there is a package that's not at its destination subtasks: pick up the package; put it in its final location; move all remaining packages.

Above, we omitted (1) how to get to the package's location in order to pick it up, and (2) how to take the package to its destination. To use the PDDL translation of the method, the planner must figure out those things for itself.

Fig. 3 shows the results of our Office Delivery experiments. For the graph on the left, we fixed the number of packages at 40 and varied the number n of office rooms from 10 to 90; and for the graph on the right we fixed the number of rooms at 40 and varied the number k of packages from 10 to 90. For each combination of n and k we ran FF on 100 randomly generated problems, giving a total of 1700 problems.

As shown in Fig. 3, FF-Plain's running time increased much faster than FF-HTN's. On the largest problems (90 rooms and 90 packages), FF-HTN was faster than FF-Plain by about 2.8 and 1.9 orders of magnitude, respectively.

6 RelatedWork

Section 1 began with a discussion of related work on domainindependent and domain-configurable planners. We now discuss additional related work.

[Smith et al., 2008] described the Action Notation Modeling Language (ANML) as an alternative to the exiting planning languages such as PDDL and HTNs, while preserving a clear semantics. [Smith et al., 2008] also describes a tecnique for translating HTNs specified as in ANML into PDDL. The ANML translation has several similarities to ours, but also a difference that can significantly affect planning time and solutions found: the ANML translation does not distinguish (see our "translating operators" subsection) between actions that aren't used as subtasks of methods (in which case we use standard PDDL semantics) and actions that are (in which case we use standard HTN semantics, i.e., the action is applicable only when called by the methods that mention it). This affects both planning time and solutions found, and would seem to relate to the two sides of the controversy described at the start of "HTN Decomposition" section in [Smith et al., 2008]. We believe there is merit in both sides of this controversy.

[Estlin et al., 1997] argued that the knowledge-engineering effort required to produce effective HTN planning knowledge could be reduced by using partial-order-planning techniques such as causal-link analysis and goal regression, and using HTNs only to specify high-level goal hierarchies. They pointed out how more-specific but similar combinations of HTNs and classical-planning techniques were useful and effective in two planning systems developed at NASA.

In a similar vein, [Kambhampati et al., 1998] proposed a plan-space refinement framework to allow HTN planning knowledge to be combined with classical planning, and argued that this would provide a principled way of handling partially hierarchical domains. As an instance of this approach, they cited [Mali and Kambhampati, 1998], which describes how to translate a restricted case of HTN planning into the satisfiability problem.

[Dix et al., 2003] describes a translation of TSTN planning problems into Answer Set Programs (ASPs). In their experiments, the approach did not perform as well as the SHOP planning algorithm [Nau et al., 1999], but it provided substantial speedups compared to direct formulations of classical planning as ASPs.

[Baier et al., 2007] provide a way to translate a subset of GOLOG into classical planning problems via finite state automatons. The translation supports conditionals, loops and non-deterministic choice, but lacks procedures. [Fritz et al., 2008] provides a theoretical extension which supports concurrency and procedures, and would support TSTN translation by first translating to ConGolog. In contrast, we provide a direct translation of TSTNs to PDDL, an implementation, and experimental results.

As a way to do planning with incomplete HTN knowledge, the Duet planner [Gerevini et al., 2008] combines a domain-independent planner, LPG [Gerevini et al., 2003], with a domain-configurable planner, SHOP2 [Nau et al., 2003]. During planning, Duet uses SHOP2 to decompose tasks into smaller subtasks, and LPG to satisfy goal conditions. In their experiments, Duet was able to solve classical planning problems faster, on average, than LPG.

7 Conclusions

Our results show that HTN planning knowledge, if it satisfies the restrictions described in Section 3, can easily be translated into a form usable by domain-independent PDDL planners.

In our experiments with FF, PDDL translations of small amounts of HTN planning knowledge improved FF's performance by several orders of magnitude. This occurred even though the HTN knowledge was incomplete, i.e., it omitted some of the knowledge that an HTN planner would need. In places where the knowledge was missing, FF simply used its ordinary planning heuristics.

FF's ability to augment the translated HTN knowledge with its own heuristics suggests that if we were to take a complete domain description (e.g., for an HTN planner such as SHOP) and translate it into PDDL, this might enable FF (and perhaps other PDDL planners) to perform better than HTN planners. We haven't yet been able to test this hypothesis since our current set of HTNs are only partial domain descriptions, but we hope to test it in the near future.