Tight Bounds for HTN Planning with Task Insertion

1 Introduction

Hierarchical Task Network (HTN) planning [Erol et al., 1996] is a planning approach, where solutions are generated via step-wise refinement of an initial task network in a top-down manner. Task networks may contain both compound and primitive tasks. Whereas primitive tasks correspond to standard STRIPS-like actions that can be applied in states where their preconditions are met, compound tasks are abstractions thereof. That is, for every compound task, the domain features a set of decomposition methods, each mapping that task to a task network. Solutions are obtained by applying methods to compound tasks thereby replacing these tasks by the task network of the respective method. HTN planning is strictly more expressive than nonhierarchical (i.e., classical) planning. That is, solutions of HTN problems may be structured in a way that are more complex than solutions of classical planning problems [H¨oller et al., 2014]. However, HTN planning is also harder than David W. Aha U.S. Naval Research Laboratory Washington, DC, USA david.aha@nrl.navy.mil classical planning. The complexity of the plan existence problem ranges up to undecidable even for propositional HTN planning [Erol et al., 1996; Geier and Bercher, 2011; Alford et al., 2015]. Even the verification of HTN solutions is harder than in classical planning [Behnke et al., 2015].

Hierarchical planning approaches are often chosen for realworld application scenarios [Nau et al., 2005; Lin et al., 2008; Biundo et al., 2011] due to the ability to specify solution strategies in terms of methods, but also because human expert knowledge is often structured in a hierarchical way and can thus be smoothly integrated into HTN planning models. On the other side, these methods also make HTN planning less flexible than non-hierarchical approaches, because only those solutions may be generated that are "reachable" via the decomposition of the methods. So, defining only a partially hierarchical domain is not sufficient to produce all desired solutions. Several HTN researchers have thus investigated how partially hierarchical domain knowledge can be exploited during planning without relying on the restricted (standard) HTN formalism [Kambhampati et al., 1998; Biundo and Schattenberg, 2001; Alford et al., 2009; Geier and Bercher, 2011; Shivashankar et al., 2013].

The most natural way to overcome that restriction is to allow both the definition and decomposition of compound tasks and the insertion of tasks from outside the decomposition hierarchy as it is done, for example, by Kambhampati et al. (1998) and Biundo and Schattenberg (2001) in Hybrid Planning - a planning approach fusing HTN planning with PartialOrder Causal-Link (POCL) planning.

This additional flexibility also pays off in terms of computational complexity: allowing arbitrary insertion of tasks into task networks lowers the complexity of the plan existence problem from undecidable (for standard HTN planning) to EXPSPACE membership (for HTN planning with task insertion - TIHTN planning) [Geier and Bercher, 2011]. This reduction of the complexity also has its negative consequences, however. Some planning problems that can be easily expressed in the HTN planning setting may not be expressed in the TIHTN setting (others only with a blowup of the problem size) [H¨oller et al., 2014]. Also, the set of TIHTN solutions of a problem may not correspond to the ones the domain modeler intended: in HTN planning - as opposed to TIHTN planning - only those plans are regarded solutions that can be obtained by decomposition only. Thus, certain plans may be ruled out even if they are executable.

In this paper, we investigate the influence of method structure (partially vs. totally ordered) and of variables (propositional vs. lifted TIHTN problems), and provide tight complexity bounds of the plan existence problem for the four resulting classes of TIHTN problems. The results are summarized in Table 1 (and compared to the respective results from HTN planning in Table 2 in the last section). Notably, we show that propositional TIHTN planning is NEXPTIMEcomplete, easier than the previously known EXPSPACE upper bound. Besides providing tight complexity bounds for the plan existence problem, another contribution is a new algorithm, called acyclic progression, that efficiently solves TIHTN problems. The paper closes with a discussion about the new complexity findings for TIHTN planning that puts them into context of already known results for HTN planning.

2 Lifted HTN Planning with Task Insertion

Geier and Bercher (2011) defined a propositional (settheoretic) formalization of HTN and TIHTN planning problems. Both problem classes are syntactically identical - they differ only in the solution criteria. Recently, we extended their formalization of HTN planning to a lifted representation based upon a function-free first order language [Alford et al., 2015], where the semantics are given via grounding. For the purpose of this paper, we replicate the definitions for lifted HTN planning and extend them by task insertion to allow specifying lifted TIHTN planning problems.

Task names represent activities to accomplish and are syntactically first-order atoms. Given a set of task names X, a task network is a tuple tn = (T, ≺, α) such that:

• T is a finite nonempty set of task symbols.
• ≺ is a strict partial order over T .
• α : T →X maps from task symbols to task names.

Since task networks are only partially ordered and any task name might be required to occur several times, we need a way to "identify" them uniquely. For that purpose, we use the task symbols T as unique place holders. A task network is called ground if all task names occurring in it are variable-free.

A lifted TIHTN problem is a tuple (L,O,M, sI, tnI), where:

• L is a function-free first order language with a finite set of relations and constants.
• O is a set of operators, where each o ∈ O is a triple (n, χ, e), n being its task name (referred to as name(o))
• not occurring in L, χ being a first-order logic formula called the precondition of o, and e being a conjunction of positive and negative literals in L called the effects of o. We refer to the set of task names in O as primitive.
• M is a set of (decomposition) methods, where each method m is a pair (c, tn), c being a (non-primitive or compound) task name, called the method's head not occurring in O or L, and tn being a task network, called the method's subtasks, defined over the names in O and the method heads in M.
• sI is the (ground) initial state and tnI is the initial task network that is defined over the names in O.

We define the semantics of lifted TIHTN planning through grounding. For the details of the grounding process, we refer to [Alford et al., 2015]. The ground (or propositional) TIHTN planning problem obtained from (L, O,M, sI , tnI ) is given by P = (L, O, M, sI , tn′I ).

The operators O form an implicit state-transition function γ : 2L ×O → 2L for the problem, where:

• A state is any subset of the ground atoms in L. The finite set of states in a problem is denoted by 2L;
• o is applicable in a state s iff s |= prec(o);
• γ(s, o) is defined iff o is applicable in s; and
• γ(s, o) = (s \ del(o)) ∪ add(o).

Executability A sequence of ground operators 〈o1, . . . , on〉 is executable in a state s0 iff there exists a sequence of states s1, . . . , sn such that ∀1≤i≤nγ (si-1, oi) = si. A ground task network tn = (T,≺, α) is primitive iff it contains only task names fromO. tn is executable in a state s0 iff tn is primitive and there exists a total ordering t1, . . . , tn of T consistent with ≺ such that 〈α (t1) , . . . , α (tn)〉 is executable in s0.

Task Decomposition Primitive task networks can only be obtained by refining the initial task network via decomposition of compound tasks. Intuitively, decomposition is done by selecting a task with a non-primitive task name, and replacing the task in the network with the task network of a corresponding method. More formally, let tn = (T, ≺, α) be a task network and let m = (α(t), (Tm, ≺m, αm)) ∈ M be a method. Without loss of generality, assume T ∩ Tm = ∅. Then the decomposition of t in tn by m into a task network tn′ , written tn --→ t,m D tn′ , is given by:

If tn′ is reachable by any finite sequence of decompositions of tn, we write tn→∗D tn′ .

Task Insertion TIHTN planning, in addition to decomposition, allows tasks to be inserted directly into task networks. Let tn = (T,≺, α) be a task network, t be a fresh task symbol not in T, and o be a primitive task name. Then task insertion, written tn --→ t,o I tn′ , results in the task network tn′ = (T ∪ {t} ,≺, α∪ {(t, o)}). If tn′ is reachable by any sequence of insertions to tn, we write tn→∗I tn′ .

Task insertion commutes with decomposition, i.e., if tn1 --→ t,m D tn2 --→ t′ ,o I tn3, then there exists a tn′2 such that tn1 --→ t′ ,o I tn′2 --→ t,m D tn3. If tn′ is reachable by any sequence of decompositions and insertions to tn, we write tn→∗DI tn′ .

Solutions Under HTN semantics, a problem P is solvable iff tnI →∗D tn′ and tn′ is executable in sI. The task network tn′ is then called an HTN solution of P. Under TIHTN semantics, P is solvable iff there exists a tn′ such that tnI →∗DI tn′ and tn′ is executable in sI.

The following definitions go beyond those in [Alford et al., 2015; Geier and Bercher, 2011].

Acyclic Decompositions Let tn be a task network sequence starting in tnI and ending in a task network tn′ , s.t. tnI →∗DI tn′ . For each network tnj ∈ tn, every task symbol was either present in tnI, inserted directly via task insertion, or is the result of a sequence of decompositions of a task symbol in tnI. For the tasks arrived at by decomposition, we can define their ancestors in the usual way: For tni, tni+1 ∈ tn with tni ---→ ti,mi D tni+1, ti is an ancestor of each task t′ ∈ tni+1 that comes from mi; and ancestry is transitive, i.e., if ti is an ancestor of tj and tj is an ancestor of tk, then ti is an ancestor of tk. tn is acyclic if for every task t in its final task network, the ancestors of t all have unique task names. Thus, an acyclic series of decompositions and insertions tnI →∗DI tn′ makes no use of recursive methods, regardless of their presence in the set of methods.

Geier and Bercher (2011) represent ancestry using decomposition trees and show that, given a TIHTN solution tn that is obtained via cyclic method application, one can repeatedly remove cycles (replacing orphaned sequences of decomposition with task insertion) to arrive at an acyclic solution tn′ .

The next corollary follows as a special case of the application of Lemma 1 and Lemma 2 by Geier and Bercher (2011).

Corollary 1. Let P = (L,O,M, sI, tnI) be a ground planning problem and let tn = (T, ≺, α) be a task network such that tnI →∗DI tn and 〈t1, . . . , tk〉 is an executable task sequence of tn that does not violate the ordering constraints ≺. Then there exists a task network tn′ = (T ′ ,≺′ , α′ ) with an acyclic decomposition tn→∗DI tn′ and an executable task sequence 〈t′1 , . . . , t′k 〉 of tn′ not violating α′ , such that ∀iα (ti) = α′ (t′i ).

3 Acyclic Progression for TIHTN Planning

HTN planners generally solve problems either using decomposition directly [Erol et al., 1994; Bercher et al., 2014], or by using progression [Nau et al., 2003], which interleaves decomposition and finding a total executable order over the primitive tasks [Alford et al., 2012]. Since progression-based HTN algorithms can be efficient across a number of syntactically identifiable classes of HTN problems [Alford et al., 2015], it makes a useful starting point for designing efficient TIHTN algorithms.

We define acyclic progression for TIHTN planning as a procedure that performs progression on a current state. To that end, it maintains a task network of primitive and compound tasks that still need to be applied to the current state or to be decomposed, respectively. To avoid recursive definitions, it maintains a set of ancestral task names. More precisely, search nodes are tuples (s, tn, h), where s is a state, tn = (T,≺, α) is a task network, and h is a mapping of the tasks in T to the set of ancestral task names, represented as a set of task-task-name pairs. For each node, there are three possible operations:

• Task insertion: If o is an operator such that s |= prec(o), then (γ (s, o) , tn, h) is an acyclic progression of (s, tn, h)
• Task application: If t ∈ T is an unconstrained primitive task (∀t′ ̸=tt′ ⊀ t) and s |= prec (α(t)), then we can apply α(t) to s and remove it from tn and h. So, given

then (γ (s, α(t)) , tn′ , h′ ) is an acyclic progression of (s, tn, h).

• Task decomposition: If t ∈ T is an unconstrained nonprimitive task, (α (t) , tnm) ∈ M is method with tnm = (Tm, ≺m, αm), and none of the task names in α occur as an ancestral task name of t in h, then we can decompose t and update the history. So if tn--→ t,m D tn′ and

then (s, tn′ , h′ ) is an acyclic progression of (s, tn, h).

If there is a sequence of acyclic progressions from the triple (s, tn, h) to (s′ , tn′ , h′ ), we write (s, tn, h)→∗AP (s′ , tn′ , h′ ). Notably, acyclic progression is only acyclic over decompositions, not states reached. If there is any sequence of acyclic decompositions to an empty task network, then the problem has a TIHTN solution:

Lemma 2. Given a ground planning problem P = (L,O,M, sI, tnI), there is a series of acyclic progressions (sI , tnI , ∅)→∗AP (s, tn∅, ∅) (where tn∅ is the empty task network) if and only if P is solvable under TIHTN semantics.

Proof. (⇒) Let TD be the subsequence of the acyclic progression (sI, tnI, ∅) →∗AP (s, tn∅, ∅) containing all the decompositions performed, TA be the subsequence of task applications, TI be the subsequence of task insertions, and TIA be the subsequence of both task applications and insertions.

Since task application only removes primitive tasks, TD must be a decomposition of tnI to a primitive task network tn′ , specifically one with a partial order ≺′ which is consistent with the order and content of task applications, TA. Then, given that task insertion commutes with decomposition, TI gives us a set of insertions tn′ →∗I tn′′ , and TIA is a witness that tn′′ has an executable ordering.

(⇐) If P is solvable, by Corollary 1 there is an acyclic decomposition sequence tn such that tnI→∗D tn, and a sequence of insertions tn→∗I tn′ such that tn′ = (T ′ , ≺′ , α′ ) has an executable ordering TIA = 〈t1, . . . , tk〉. Insertions commute with both themselves and with decomposition, and decompositions commute with each other so long as one decomposed task is not an ancestor of the other. So the following procedure gives an acyclic progression of P to the empty network. Given that ti is the last task from TIA to be applied to the state (by insertion or application) and the current triple under progression is (sj , tnj , hj ):

• If there is a non-primitive task tj in tnj such that tj is an ancestor of ti+1 in the sequence tn, use the decomposition from tn to decompose tj .
• If ti+1 exists in tnj, progress it out of the task network with task application and move on to ti+2.
• Else, ti+1 was obtained by insertion, and so use insertion to apply α′ (ti+1) to sj and move on to ti+1.

A problem's acyclic progression bound is the size of the largest task network reachable via any sequence of acyclic progressions. Only decomposition can increase the task network size. Since decomposition is required to be acyclic, every problem has a finite acyclic progression bound. Given the tree-like structure of decomposition, if m is the max number of subtasks in any method and n is the number of task names, and T is the set of task symbols in the initial task network, then |T | · mn is an acyclic progression bound of the problem.

If methods are totally ordered (i.e., the ≺ relation in each method is a total order), then we reach a much tighter bound:

Theorem 3. Propositional TIHTN planning for problems with totally-ordered methods is PSPACE-complete.

Proof. Classical planning provides a PSPACE lower bound [Geier and Bercher, 2011]. Here, we provide an upper bound. Let P = (L, O,M, sI , tnI) be a ground TIHTN problem where each method is totally ordered. The initial task network tnI may be partially ordered. Letting tnI = (T,≺, α), there are |T| initial tasks. Since the methods are totally ordered, any sequence of progressions (sI , tnI , ∅)→∗AP (s, tn, h) preserves that tn can be described by the relationship of |T| or fewer totally ordered chains of tasks.

Progression can only affect the unconstrained tasks in the chains. While the acyclic decomposition phase of progression can lengthen a chain by m- 1 tasks (m being the size of the largest method), each of those tasks has a strictly larger set of ancestral task names, and the size of that set is capped. If n is the number of ground task names, each chain can only grow to a length of n · (m- 1). So the acyclic progression bound of problems with totally ordered methods is |T | · n · (m - 1). Since the size of any state is also polynomial, totally ordered proposition TIHTN plan existence is PSPACE-complete.

Theorem 4. TIHTN planning is EXPSPACE-complete for lifted problems with totally-ordered methods.

Proof. Grounding a lifted domain produces a worst-case exponential increase in the number of task names providing EXPSPACE membership. Lifted classical planning provides the EXPSPACE lower bound [Erol et al., 1995].

4 22k Bottles of Beer on theWall

At most 2L tasks need to be inserted between each pair of two consecutive primitive tasks in any acyclic decomposition [Geier and Bercher, 2011]. This provides an upper bound on the number of task insertions needed to show a TIHTN problem is solvable. The song "m Bottles of Beer on the Wall" uses a decimal counter to encode a bound on the number of refrains in space logarithmic to m [Knuth, 1977]. Much like this, we will give transformations of TIHTN operators so that a binary counter ensures strict upper bounds on the number of primitive tasks in any solution. This will limit the length of any sequence of progressions, giving us upper complexity bounds for TIHTN planning.

Clearly, we could just limit acyclic progression to a bounded depth instead. However we will also use the bounding transformation below in the following section to provide a polynomial transformation of acyclic HTN problems which preserves solvability under TIHTN semantics.

Let P be a propositional problem with a set of operators O and language L. Given a bound of the form 2k , we create a language L′ which contains L and the following propositions: counting, count init, and counteri and decrementi for i ∈ {1 . . . k + 1}. We define the operator set O′ to be each operator in O with the added the precondition ¬counting and the additional effect counting ∧ decrement1. We define another set of operators Ocount with the following operators:

• (count init op, ¬count init, count init ∧ counterk), initializing the counter to the value 2k .
• (decrement i 0 op, pre, eff ) for i ∈ {1..k}, where:

pre := count init ∧ decrementi ∧¬counteri eff := ¬decrementi ∧ decrementi+1 ∧ counteri

setting the ith bit of the counter to 1 if it was zero and moves on to the next bit.

· (decrement i 1 op, pre, eff ) for i ∈ {1..k}, where: pre := count init ∧ decrementi ∧ counteri eff := ¬decrementi ∧ ¬counting ∧ ¬counteri

setting the ith bit of the counter to 0 and stops counting.

Then in the problem P ′ with operators O′ ∪ Ocount and the language L′ , any executable sequence consists of an alternating pattern of an operator from O′ followed by a sequence of counting operators from Ocount. Since there is no operator to decrement counterk+1, we can only apply 2k operators fromO′ to the state. Notice that by setting the appropriate counteri propositions in the count init op operator, we could have expressed any bound between 0 and 2k+1 - 1.

We can extend this to doubly-exponential bounds for lifted problems. Let P be a lifted problem with language L and operators O, and let 22k be our bound on operators from O to encode. Let L′ contain L and the following predicates: counting(), count init(), and counter (v1, . . . , vk)

and decrement (v1, . . . , vk), and let 0, 1 be arbitrary distinct constants in L′ .

As with the counteri predicates, the ground counter(. . .) predicates will express a binary counter in the state, with a binary index (the variables) into the exponential number of bits. Let cr1 . . . , crk be predicates such that each cri has the form counter (vk, . . . , vi+1, 0, 1, . . . , 1) and let dec1 . . . , deck be predicates such that each deci has the form decrement (vk, . . . , vi+1, 0, 1, . . . , 1) where each vm is a variable. So:

• dec1 = decrement (vk, . . . , v2, 0)
• dec2 = decrement (vk, . . . , v3, 0, 1)
• deck-1 = decrement (vk, 0, 1, . . . , 1), and
• deck = decrement (0, 1, . . . , 1)

Similarly, let dec′1 , . . . , dec′k be predicates of the form decrement (vk, . . . , vi+1, 1, 0, . . . , 0), so:

• dec′1 = decrement (vk, . . . , v2, 1)
• dec′2 = decrement (vk, . . . , v3, 1, 0)
• dec′k-1 = decrement (vk, 1, 0, . . . , 0)
• dec′k = decrement (1, 0, . . . , 0)

So if v is an assignment of v1, . . . , vk to {0, 1} and we view the proposition deci [v] as an instruction to decrement the jth bit of the counter, then dec′i [v] is for decrementing the bit with index j + 1.

Let O′ consist of each operator in O with the added the precondition ¬counting() and the additional effect counting() ∧ decrement (0, . . . , 0). We define Ocount to be the following operators:

• (count init op(), pre, eff ), where:

which initializes the counter to the value 22k .

• (decrement i 0 op(), pre, eff ) for i ∈ {1..k}, where:

which, if v is an assignment of v1, . . . , vk to {0, 1}, sets cri [v] to 1 if it was zero and moves on to the next bit.

• (decrement i 1 op(), pre, eff ) for i ∈ {1..k}, where:

which, if v is an assignment of v1, . . . , vk to {0, 1}, sets cri [v] to 0 and stops counting.

So after decrement (0, . . . , 0) is set by an operator (and count init op() has been applied in the past), the only legal sequence of operators involves stepping sequentially through the 2j possible counter (. . .) predicates until the decrement operation is finished.

Similar to the propositional transformation, we can start the counter at some number which is a polynomial sum of

2i for i ∈ {1..2k }. These two transformations are the dual of the counting tasks in Theorems 4.1 and 4.2 from Alford et al. (2015). Where the counting tasks gave methods that enforced exactly 2k and 22k repetitions of a given task be in any solution, this transformation ensures that there are no more than the specified number of primitive tasks.

Theorem 5. Propositional TIHTN planning is in NEXPTIME; lifted TIHTN planning is in 2-NEXPTIME.

Proof. Use the appropriate transformation from above to limit the number of primitive operators in any solution to |T| · mn · 2L, where |T| is the number of tasks in the initial network, m is the max method size, n is the number of non-primitive task names in the grounded problem (exponential for lifted problems), and 2L is the total number unique states expressible by L. This ensures every sequence of acyclic progressions ends after an exponential number of steps for propositional problems and a doubly-exponential number of steps for lifted problems. Thus, a depth-first non-deterministic application of acyclic progression until it reaches a solution or can progress no more is enough to prove the existence of a TIHTN solution.

5 Acylic HTN Planning with TIHTN Planners

Theorem 5 provides upper bounds for TIHTN planning. Section 2 describes acyclic decomposition. An acyclic problem is one in which every sequence of decompositions is acyclic [Erol et al., 1996; Alford et al., 2012]. HTN plan existence for propositional partially ordered acyclic problems is NEXPTIME-complete and 2-NEXPTIME-complete for lifted partially ordered acyclic problems.

Theorem 6.1 of [Alford et al., 2015] encodes NEXPTIMEand 2-NEXPTIME-bounded Turing machines almost entirely within the task network of propositional and lifted acyclic HTN problems, respectively. Of particular interest here, though, is that, for a given time bound and Turing machine, every primitive decomposition of the initial task network in these encodings has exactly the same number of primitive tasks. This lets us use the bounding transformation from Section 4 to prevent rogue task insertion under TIHTN semantics:

Theorem 6. Propositional TIHTN planning is NEXPTIMEhard; lifted TIHTN planning is 2-NEXPTIME-hard.

Proof. Let N be a nondeterministic Turingmachine (NTM), let K = 22k be the time bound for N, and let P with operators O be the encoding of N as a lifted acyclic HTN problem.

One can calculate exactly how many primitive tasks are in any decomposition of P, but it is roughly of the form B = c ·K2 +d ·K+1 for constants c and d, which we can express as a polynomial sum of 22i . Let P ′ be the B-task-bounded transformation of P.

From the hardness proof of Theorem 6.1 of [Alford et al., 2015], we know: if N can be in an accepting state after K steps, there is an executable primitive decomposition of P with B tasks from O, and so P ′ has a TIHTN solution.

Let tn be a non-executable primitive decomposition of the initial task network, tnI →∗D tn. Since the bounding transformation does not affect the methods, this decomposition sequence is also legal in P ′ (with operators O′ ∪ Ocount ). Since any insertions of operators from O′ would put tn over the limit B, no sequence of insertions can make this task network executable in P ′ . Thus if no run of N is in an accepting state after K steps, no primitive decomposition of P is executable, and there is no TIHTN solution to P ′ .

Since P ′ has a TIHTN solution iff P has a solution, and P encodes a 22k -bounded NTM, lifted TIHTN planning is 2-NEXPTIME-hard.

The proof is the same for propositional TIHTN problems using the propositional encoding of 2k time-bounded NTMs into acyclic HTN problems, so propositional acyclic TIHTN planning is NEXPTIME-hard.

As a corollary, we obtain NEXPTIME and 2-NEXPTIME completeness for propositional and lifted TIHTN planning, respectively.

6 A comparison with HTN complexity classes

Based on the recursion structure classification for HTN problems [Alford et al., 2012], we now have an extensive classification of HTN problems by structure and complexity:

• Acyclic problems, discussed earlier, where every decomposition is guaranteed to be acyclic.
• Tail-recursive problems, where methods can only recurse through their last task. All acyclic problems are also tail-recursive.
• Arbitrary-recursive problems, which includes all HTN problems.

However, by Corollary 1, non-acyclic (i.e., cyclic) decompositions can be ignored, limiting the impact of recursion structure on the complexity of TIHTN planning.

This is not to say that method structure (outside of ordering) has no effect on the complexity of TIHTN planning. For instance, regular TIHTN problems (defined by Erol et al. (1996) for HTN planning) with a partially ordered initial task network and partially ordered methods are easier than nonregular (partially ordered) problems. Regular problems are a special case of tail-recursive problems, where every method is constrained to have at most one non-primitive task in the method's network, and that task must be constrained to come after all the primitive tasks. Regular problems have a linear progression bound regardless of whether the primitive tasks are totally-ordered amongst themselves. Since acyclic progression is a special case of progression, regular problems have linear acyclic progression bounds, and thus partially ordered regular problems have the same complexity under TIHTN semantics as totally-ordered regular problems:

Corollary 7. TIHTN plan-existence for regular problems is PSPACE-complete when they are propositional, and EXPSPACE-complete otherwise, regardless of ordering.

There are also times when HTN planning is simpler than TIHTN planning. Alford et al. (2014) show that HTN planning for propositional regular problems which are also acyclic is NP-complete. Since an empty set of methods and a single primitive task in the initial network is enough to encode classical planning problems under TIHTN semantics, acyclicregular problems are still PSPACE-hard for propositional domains and EXPSPACE-hard when lifted.

So, while TIHTN planning is not always easier than HTN planning, we have shown that its complexity hierarchy is, in general, both simpler and less sensitive to method structures. In future work, we want to investigate the plan existence problem along the further axis of syntactic restrictions on the task hierarchy and methods: Alford et al. (2015) defines a new restriction on HTN problems, that of constant-free methods, that forbids mixing constants and variables in task names appearing in methods. This significantly reduces the progression bound for lifted partially ordered acyclic and tail recursive problems, and thus may also impact the complexity of those problems under TIHTN semantics.

7 Conclusions

We studied the plan existence problem for TIHTN planning, a hierarchical planning framework that allows more flexibility than standard HTN planning. The complexity varies from PSPACE-complete for the totally ordered propositional setting to 2-NEXPTIME-complete for TIHTN planning where variables are allowed and the methods' task networks may be only partially ordered.

We showed that totally ordered TIHTN planning has the same plan existence complexity as classical planning (both with and without variables). Given that plan existence for both delete-relaxed propositional TIHTN and classical problems is in polynomial time [Alford et al., 2014], we hope that many of the algorithms and heuristics developed for classical planning can be adapted for totally-ordered TIHTN problems.

We also provided a new planning technique for TIHTN planning, called acyclic progression, that let us define provably efficient TIHTN planning algorithms. We hope it inspires the creation of future planners that are both provably and empirically efficient.

Acknowledgment This work is sponsored in part by OSD ASD (R&E) and by the Transregional Collaborative Research Centre SFB/TRR 62 "Companion-Technology for Cognitive Technical Systems" funded by the German Research Foundation (DFG). The information in this paper does not necessarily reflect the position or policy of the sponsors, and no official endorsement should be inferred.