Hierarchical Planning: Relating Task and Goal Decomposition with Task Sharing

1 Introduction

Hierarchical Task Network (HTN) planning [Erol et al., 1994] is a task planning formalism that is widely used in real-world applications [Nau et al., 2005]. HTN planners use methods as recipes to recursively decompose tasks into primitive action sequences. We focus on two hierarchical formalisms, the Action Notation Markup Language (ANML) [Smith et al., 2008] and Hierarchical Goal Network (HGN) planning [Shivashankar et al., 2012], and their relationship with the more widely known HTN planning. All these formalisms now have systems that implement subsets of their features, yet little research examines the differences between them, either in terms of their computational complexity or their semantics.

HGN planning bridges classical planning and totally ordered task networks by operating over sequences of goals with methods that decompose goals with further subgoals. By attaching goals to methods, HGN planning adds explicit semantics to methods, making it easy to adapt classical heuristics to HGN planning [Shivashankar et al., 2016].

The Action Notation Markup Language (ANML) is a temporal planning framework with a hierarchical component [Smith et al., 2008], designed to address common challenges faced when modeling problems that require sophisticated temporal or resource reasoning within a single language that combines generative and hierarchical task planning [Smith and Cushing, 2008]; an essential feature of ANML is its ability to embed complex procedures as tasks. A translation from ANML to a variant of PDDL [Bonasso et al., 2009] and the planning system FAPE [Dvorak et al., 2014] have implemented subsets of ANML.

One of the unique features of ANML is that it allows subtasks to be shared between multiple tasks. For example, let us assume an ANML planner is considering two tasks t1 and t2 that are unordered with respect to one another which decompose into the same setup task; so, t1 decomposes into hsetup↪ a1i (read "do setup, then do a1"), while t2 decomposes into hsetup↪ a2i. According to standard HTN planning semantics, the only solution would involve two setup tasks. ANML, however, also allows for sharing the same setup task across both task-decompositions, and can therefore generate a solution with a single setup task.

Traditional HTN planners strictly follow the method hierarchy when composing a plan. This rigidity is a liability in dynamic environments when actions may fail and the plan needs to be repaired [Ayan et al., 2007]. Task Insertion semantics modifies HTN semantics to allow planners to insert actions whenever they are useful, regardless of methods [Geier and Bercher, 2011]. Task insertion is also used in the HTN literature to capture plan repair and partial method knowledge. These semantics are also implemented as part of HGNs [Shivashankar et al., 2013] and are explicitly supported in ANML. It is not known how task insertion interacts with task sharing.

Contributions. The central aim of this paper is to unify these various families of hierarchical planning and their semantics as summarized in Figure 1. In particular,

• ÷ A Unified Formalism: We define Goal-Task Network (GTN) planning that models partially ordered HTN planning and extends HGN planning with partially-ordered sets of subgoals. We present standard semantics for GTN that extends HTN semantics with goals. We then extend these semantics with the addition of task insertion semantics, denoted GTNI, with the addition of task sharing GTNS, and finally, with the combined semantics of GTNIS.
• ÷ Expressivity Results: We show that every GTN problem with any combination of the above semantics can be translated in a solution preserving manner to HTN planning with standard semantics, which is in general semidecidable.
• ÷ Membership Results: For certain classes of GTN planning, we improve the semi-decidable upper bound by proving that HGNI is in PSPACE, while GTNIS and GTNI planning are in NEXPTIME.

2 AUnified Hierarchical Planning Formalism

To precisely describe the relationship between HTN and HGN planning, we model both in a single framework called GoalTask Network (GTN) planning 1 . GTN planning has already been extremely useful in formalizing goal reasoning [Roberts et al., 2016]. We augment the set-theoretic notation of Geier and Bercher [2011] with goal decomposition from HGN planning [Shivashankar et al., 2012] and with SHOP2-style method preconditions [Nau et al., 2003]. After formalizing GTNs, we clarify their operations before discussing GTN problems and their solutions.

1 GTN was partly inspired by conversations with Ghallab et al. following their paper [Ghallab et al., 2014] and upcoming book [Ghallab et al., in press] wherein they argued for use of a hybrid task-planning formalism for Planning and Acting.

2.1 Preliminaries

Let L be a propositional language and T be a set of task names represented as propositional symbols not appearing in L with L \ T = ;, and let O and C be a partition of T (O [ C = T , O \ C = ;). O will correspond to primitive tasks, or actions that can be executed directly, while C represents Compound or non-primitive tasks which need to be recursively decomposed into primitive tasks before they can be executed.

Then HTN planning is over partially-ordered multisets of task names in T representing activities to accomplish, while HGN planning is over totally-ordered subgoals in L which must be met in sequence. GTNs elegantly models both, and in addition extends the scope of HGN planning to allow for partially-ordered sets of subgoals.

2.2 Goal-Task Networks (GTNs)

A goal-task network is a tuple (I↪≺↪ ↵) where I is a set of instance symbols which are placeholders for task names and goals, ≺⇢ I ⇥ I is a partial order on I, and ↵ : I !L[T maps each instance symbols to a goal or task name.

Some symbol instances are special because they occur first or last in a network. An instance symbol i is unconstrained if no symbols are constrained before it (8i02Ii0 ⌃ i) and last if it constrained after all other symbols (8i02Ii0 ≺ i). We refer to i as a task if ↵(i) 2 T and as a subgoal if ↵(i) 2 L; recall that L and T are disjoint.

Two goal-task networks, (I1↪ ≺1↪ ↵1) and (I2↪ ≺2↪ ↵2) are isomorphic if there exists a bijection f : I1 ! I2 such that: (1) (i↪ i0 ) 2≺1 iff (f(i)↪ f(i0 )) 2≺2 and (2) ↵1 (i) = ↵2 (f(i)) for all i 2 I1.

Methods. We distinguish the methods for GTNs by the kind of symbol they decompose. A task method mt is a tuple (n↪ χ↪ gtn) where n 2 C is a non-primitive task name, χ 2 L is mt's precondition, and gtn is a goal-task network over L and T . A task method is relevant to a task i in a goal-task network (I↪≺↪ ↵) if n = ↵(i). The method mt is a specific decomposition of a task n into a partially-ordered set of subtasks and subgoals, and there may be many such methods.

A goal method mg, similarly, is a tuple (g↪ χ↪ gtn) where g↪ χ 2 L are the goal and precondition of mg and gtn is a goal-task network. A goal method is relevant to a subgoal i in a goal-task network (I↪≺↪ ↵) if at least one literal in the negation-normal form (NNF) of g matches a literal in the NNF of ↵(i) (e.g., accomplishing g ensures that at least part of ↵(i) is true). By convention, the goal-task network gtn = ((I↪≺↪ ↵) has a last instance symbol i 2 I with ↵(i) = g to ensure that mg accomplishes its own goal.

Task and goal methods are respectively identical to methods in HTN and HGN planning.

Operators. An operator o is a tuple (n↪ χ↪ e) where n 2 O is a primitive task name (assumed unique to o), χ is a propositional formula in L called o's precondition (or prec(o)), and e is a set of literals from L called o's effects. We refer to the set of positive literals in e as add(o) and the negated literals as del(o). An operator is relevant to primitive task it if n = ↵(it) and to a subgoal ig if the effects of o contain a matching literal from the NNF of ↵(ig).

States. A state s ⇢ Lsym is any subset of Lsym, the propositional symbols of L; the set of all states is 2Lsym . A set of operators O forms a transition (partial) function γ : 2Lsym ⇥ O ! 2Lsym as follows: γ (s↪ o) is defined iff s ♣= prec(o) (the precondition of o holds in s), and γ (s↪ o) = (s ∩ del(o)) [ add(o).

2.3 GTNNodes and Node Operations

A node is a (state, goal-task network) pair N = (s↪ gtn). GTN planning allows four operations on nodes, described below.

We use the term progression as an umbrella term for the various GTN node operations. We write N -!P N 0 if any of the operations can make that transition between nodes. For progression sequences from N to N 00 , we write N -!⇤P N 00 .

Operator application of an operator o to a node (s↪ gtn), with gtn = (I↪≺↪ ↵), written as (s↪ gtn) i↪o -!A (s0 ↪ gtn0 ), is defined if s ♣= prec(o) and o is relevant to an unconstrained instance symbol i in gtn. If i is a primitive task with task name n, then this corresponds to primitive task application in HTNs; the result of application is given by s0 = γ(s↪ o) and gtn0 = (I ∩ ¶i♦ ↪ ¶(i1↪ i2) 2≺♣ i1 6= i♦ ↪ ¶(i0 ↪ n) 2 ↵ ♣ i0 6= i♦), transitioning the state and removing the instance symbol from the network. If i is a relevant goal task instead, this corresponds to primitive task application in HGNs; in this case, gtn0 = gtn, and the subgoal remains while the state changes.

Goal release for an unconstrained subgoal i, written (s↪ gtn) i-!G (s↪ gtn0 ), is defined whenever s ♣= ↵(ig). Goal release can remove a subgoal whenver it is satisfied by s, and so gtn0 is given by (I ∩ ¶i♦ ↪ ¶(i1↪ i2) 2≺♣ i1 6= i♦ ↪ ¶(i0 ↪ n) 2 ↵ ♣ i0 6= i♦), just as in operator application.

Task decomposition for an unconstrained task i by a relevant task method m = (c↪ χ↪ gtnm), written (s↪ gtn) i↪m --!D (s↪ gtn0 ), is defined whenever s ♣= χ. Task decomposition expands i in gtn, replacing it with the network gtnm. Let (I↪≺↪ ↵) = gtnm and (Im↪≺m↪ ↵m) = gtnm, assuming without loss of generality that I \ Im = ;. Then the result of task decomposition, gtn0 = (I 0 ↪ ≺0 ↪ ↵0 ) is given by:

Goal decomposition for an unconstrained subgoal i by a relevant goal method m = (gm↪ χ↪ gtnm), also written (s↪ gtn) i↪m --!D (s↪ gtn0 ), is defined whenever s ♣= χ. Goal decomposition prepends i with gtnm, leaving the subgoal in place, so that gtn0 is given by (I [ Im↪ ≺ [ ≺m [ ¶(im↪ i) 2 Im ⇥ ¶i♦♦ ↪ ↵ [ ↵m).

3 GTN Planning Problems and Solutions

A problem is a tuple P = (L↪ O↪M↪ N0) where L is propositional language for defining the set of operators (O), the set of goal and task methods (M), and N0 is the initial node consisting of the the initial goal-task network gtn0, and the initial state s0. O and C are implicitly defined by O and M. Nodes are isomorphic if their goal-task networks are isomorphic and their states are identical.

We say P is solvable under GTN semantics iff there is a progression N0 -!⇤P Nk, where Nk = (sk↪ gtn;), sk is any state, gtn; is the empty network. The subsequence of operator applications of that progression is a plan for P.

Whenever all networks (method and initial) in a problem P contain only tasks, we call it an HTN problem since goal release and goal decomposition are irrelevant, and so the semantics are identical to HTN planning under progression [Alford et al., 2012]. Whenever all networks contain only subgoals, we call it an HGN problem, since the semantics are identical to HGN planning with a straightforward extension to partially-ordered networks [Shivashankar et al., 2012].

3.1 Task-Insertion Semantics

Formally, task insertion of an operator o is defined whenever o's precondition is supported by the state, and is written (s↪ gtn) o-!I (s0 ↪ gtn), where s0 = γ (s↪ o). Note that this combines two operations, insertion of o and operator application of o.

If a node (s0 ↪ gtn0 ) is reachable from another node (s↪ gtn) via any sequence of progressions and insertions, we write (s↪ gtn) -!⇤PI (s0 ↪ gtn0 ). We say that a problem P is solvable under GTN semantics with task insertion (GTNI semantics) iff (s0↪ gtn0) -!⇤PI (s↪ gtn;) where s is any state and gtn; is the empty goal-task network. HTNI planning is NEXPTIMEcomplete [Alford et al., 2015b].

3.2 Task-Sharing Semantics

We formalize task sharing here using a task merging oper-

ation that takes two task symbols in the goal-task network that map to the same task name and merges them into one task symbol. Formally, task merging of two unconstrained tasks i1↪ i2 in a network gtn = (I↪ ≺↪ ↵) is applicable whenever the tasks share a task name (↵(i1) = ↵(i2)). The operation, written (s↪ gtn) i1↪i2 ---!M (s↪ gtn0 ), is given by gtn0 = (I ∩ ¶i2♦ ↪ ≺0 ↪ ↵0 ), where:

We say a problem P with initial node (s↪ gtn) is solvable under GTN semantics with task sharing (GTNS) if there is any sequence of progression and merging to a node (s0 ↪ gtn;), written (s↪ gtn) -!⇤PM (s0 ↪ gtn;). Solvability under both task insertion and sharing (GTNIS semantics) is defined similarly, with the sequence denoted as (s↪ gtn) -!⇤PIM (s0 ↪ gtn;).

4 Plan-preserving translations

We can study the computational complexity of GTN planning by reductions, which are transformations between problems and/or formalisms. In this section, we use a special kind of reduction we call plan-preserving translations, which preserve the solution set of the problem across translation. For example, we can trivially use a GTN planner to solve a GTNI

problem P by adding a new task to the initial node along with methods that decompose it into any sequence of operators. Since this transformation preserves the set of plans, (1) an optimal plan from the GTN planner is an optimal plan P, and (2) when creating GTNI planners, the transformation is a procedure for using any admissible GTN heuristic as a GTNI heuristic. Further, we know that GTN planning is at least as expressive as GTNI planning, since the (possibly infinite) set of solutions for any problem under GTNI semantics can be exactly expressed as the solutions of the translated problem under GTN semantics.

Same-semantic translations from GTNs to HTNs

In this section, we provide a plan preserving translation from GTN problems to HTN problems that preserves plans under like semantics (GTN to HTN, GTNI to HTN with task insertion, etc.). This establishes that GTN planning is no harder in the general case than HTN planning across all the semantic variants we discuss.

Construction 4.1. Let P be a problem. We iteratively construct an HTN problem P 0 as follows:

Let g be a subgoal appearing in the initial network or any method network. Let tg be a fresh task name, and let mg = (tg↪ g↪ gtn;), which will act as the goal release operation for tg. Let N 00 and M0 be the P's initial node and set of methods where each instance of g in a network is replaced by tg. Let MOg be a set methods of the form mog = (tg↪ true↪ gtnog ) for each operator o relevant to g, where gtnog contains the task o preceding the task tg. Finally, let MMg be a set of methods of the form mmg = (tg↪ χ↪ gtnmg ) for each goal method (g0 ↪ χ↪ gtn) 2 M0 relevant to g, where gtnmg is gtn with a new task for tg constrained to come after all other instance symbols. Then P 0 = (L↪O↪M0 [MOg [MMg [ ¶mg♦ ↪N 00 ). Iterate until no goal appears in a network, and remove all goal methods.

Theorem 4.2. For a problem P with initial node N0, use Construction 4.1 to construct an HTN problem P 0 . Then, under GTN semantics, a sequence of actions is a plan for P iff it is a plan for P 0 . The same result holds under GTNI semantics.

Proof. We prove this theorem by showing that for each iteration of Construction 4.1, after replacing g with tg, P and P 0 have the same set of plans.

()) Let N0 -!⇤P Nk be a derivation of a plan p for P, where N1 ▷ ▷ ▷Nk-1 are the intermediate nodes. Construct N 00 -!⇤P N 0k as follows: N 00 is isomorphic to N0 with g replaced with tg. Suppose N 0 i is isomorphic to Ni with g replaced with tg. The following cases ensure the same for N 0 i+1 and Ni+1:

If Ni i↪o -!A Ni+1 is an application of o to goal task g, then decompose the corresponding i in N 0 i with mog and immediately apply o (N 0 i i↪mog ---!D N 00 i i0 ↪o --!A N 0 i+1 ). If Ni i-!G Ni+1, then g is satisfied in Ni's state (identical to the state of N 0 i ), so decompose the corresponding i from N 0 i with mg, removing i, to get the corresponding N 0 i+1 . If Ni i↪m --!D Ni+1 corresponds to goal-method decomposition, then N 0 i i↪mmg ----!D N 0 i+1 is applicable and produces the corresponding N 0 i+1 . Otherwise, the operation does not involve g, so apply it directly to N 0 i . Since this preserves operator applications in the derivation, p is also a plan for P 0 .

(() Let N 00 -!⇤P N 0k be a derivation of a plan p for P 0 . Note that decomposition with any mog can be push back in the derivation until it is immediately before the application of o. Then the inverse of the above procedure can produce a derivation of p for P .

Since the set of GTN problems includes all HTN problems and HTN planning is semi-decidable [Erol et al., 1996], by the above theorem, GTN planning is also semi-decidable:

Corollary 4.3. Deciding whether a solution exists for a problem under GTN semantics is semi-decidable.

We know by Alford et al. [2015b] that HTN planning with task insertion is NEXPTIME-complete, so by the above, the same result extends to GTNI planning:

Corollary 4.4. Deciding whether a solution exists for a problem under GTNI semantics is NEXPTIME-complete.

We can also show that Construction 4.1 preserves plan sets under GTNS semantics:

Theorem 4.5. For a problem P, let P 0 be the resulting HTN problem from Construction 4.1. Then, under GTNS semantics, a sequence of actions is a plan for P iff it is a plan for P 0 . The same result holds under GTNIS semantics.

Proof. Again, we show that for each iteration of Construction 4.1, after removing g, P and P 0 have the same set of plans.

()) Task merging does not involve goals, so given a derivation N0 -!⇤PM Nk of a plan p for P, extend the ()) procedure of Theorem 4.2 with merging so that Nj i1↪i2 ---!M Nj+1 maps to N 0 j i1↪i2 ---!M N 0 j+1 .

(() Once g is replaced by tg, there are two threats to inverting the above procedure to find a derivation of a plan p for P from p's derivation from P 0 : (1) two tasks for tg may be merged, and (2) a primitive task for an operator o may be merged with another task for o.

For (1), if there is a merge Nj i1↪i2 ---!M Nj+1 where ↵(i1) = tg in the derivation of p, then there must also be an Nq (q > j) where the method corresponding to goal release is applied (meaning g holds in the state of Nq). Then, since i1 and i2 are not ordered with respect to each other, another derivation of p is to skip the merge of i2, and decompose i2 with mg immediately after Nq, since g must hold in that node's state.

For (2), assume WLOG that the task i2 (↵(i2) = o) was inserted via decomposition with mog of a task i3. The derivation of p must include a decomposition of i3 with mog, which replaces i3's task for tg with the tasks o preceding tg. Later in the derivation, the task for o is merged with another task, and later applied, all before any further decomposition of tg. Then another derivation of p is just to skip the first decomposition of i3 and subsequent merge.

Since we can eliminate any merging of tg or its related primitive tasks, we can invert ()) to find a derivation of p for As a special case, consider that HGN problems have the same plan set under GTNS semantics as under GTN semantics, as there are no tasks to merge. So by the above theorem, Construction 4.1 is a plan-preserving translation of HGN problems to HTNS planning:

Corollary 4.6. For any HGN problem P, let P 0 be the resulting HTN problem from Construction 4.1. Then a sequence of actions is a plan for P under GTN semantics iff it is a plan for P 0 under GTNS semantics. The same result holds under GTNIS semantics.

So HGN planning is neither harder nor more expressive than HTN planning with sharing.

Translating from GTNS to GTN

In this section, we give a plan preserving translation from GTNS semantics to standard GTN semantics as part of our proof that GTNS planning is semi-decidable. To start, we note that, at least as far as solvability goes, GTNS semantics are equivalent to a sharing semantics that only allows merging of primitive operators.

Lemma 4.7. Let N0 -!⇤PM Nk be the derivation of a plan p for a problem P . Then there is another derivation N0 -!⇤PM Nk that any merging only happens for primitive tasks.

Proof. We can iteratively remove merging of non-primitive tasks from N0 -!⇤PM Nk as follows: Let Nj i1↪i2 ---!M Nj+1 be the first merge of any two non-primitive tasks i1↪ i2 in the derivation p. Since i1 is a non-primitive task, there is a subsequent decomposition Nk i1↪m ---!D Nk+1. Let Ni -!⇤PM N 0k+1 be the same sequence of progressions above with the initial merge omitted (including the decomposition of i1). Then decompose i2 with the same method as i1 and merge all its resulting tasks with those from the decomposition of i1. The resulting node is isomorphic with Nk+1.

We can now reduce GTNS planning to GTN relying on operators asserting in the state when they have been applied:

Construction 4.8. Let P = (L↪O↪M↪N0) be a GTN problem. We iteratively construct a new GTN problem P 0 as follows: For each primitive task name o, we introduce a new non-primitive task symbol to, as well as a new propositional symbol fino. Let L0 = L [ ¶fino ♣ o 2 O♦. Let O0 be the set of operators of O modified so that each operator o asserts fino and retracts fino0 for all o0 6= o. Let N 00 and M0 be N0 andMwith all primitive tasks in their networks replaced with the corresponding to. Finally, letMO contain two methods for each operator o: moa = (to↪ true↪ gtno), where gtno contains only the task o, and mom = (to↪ fino↪ gtn;), which can remove to from a network immediately after o is applied. Then P 0 = (L0 ↪O0 ↪M0 [MO↪N 00 ).

There are two important points to note in the above construction. First, fino is set up in such a way that it is true iff o was the last operator applied. Second, we use fino to simulate task-sharing under GTN semantics by providing two methods moa and mom for each o. These respectively introduce and don't introduce a new instance of o after one instance of o has already been applied; mom thus simulates the task-sharing option. Below, we formally prove that this construction indeed simulates task-sharing under GTN semantics:

Theorem 4.9. Let P 0 be the result of applying Construction 4.8 to a problem P . Then a sequence of operators p is a plan for P under GTNS semantics iff p is a plan for P 0 under GTN semantics. This also holds for P under GTNIS semantics and P 0 under GTNI semantics.

Proof. ()) By Lemma 4.7, there is a derivation of P under GTNS semantics that only merges primitive operators. We can also assume WLOG that merging comes immediately before operator application. For a derivation of p from P 0 under GTN semantics, replace each sequence of merges then application of an operator o with decomposition by moa, application of o, and decomposition with mom for the remaining merges.

(() Since moa has no precondition, we can always move it back in a derivation of p until just before the application of o. Similarly, we can move forward any mom before any intervening decompositions until they come just after application of o. Then invert ()) to obtain the appropriate merging.

The only threat to this step under task insertion is that there an insertion of o followed by applications of mom. If this happens, then there must be at least one unconstrained task for o in the current network. We can replace the insertion and first mom with decomposition by moa and o's application.

Since we have a plan-preserving polynomial translation of GTNS planning into HTN planning, GTNS planning is not computationally harder nor more expressive than HTN planning.

5 Encoding HTNs as HGNs

Although there are a wide array of complexity classes for specific restrictions of HTN planning [Alford et al., 2015a], HTN planning in general is semi-decidable [Erol et al., 1996]. Erol et al.'s proof of undecidability encodes the intersection of context free grammars (CFGs) as an HTN problem with totally-ordered methods and two partially-ordered initial tasks. The two tasks function as producer and consumer - one producing a sequence of symbols from one CFG, and the other consuming them in the order of another. The reachable tasks from both initial tasks are disjoint. Thus, any progression of the initial problem leads to a task network composed of two totally-ordered sets of tasks. Under GTNS semantics, no task within one of the sets can be merged (they are all ordered with respect to each other), and no task between sets can be merged (the two sets have distinct task names). Thus, Erol et al.'s construction has the same set of solutions under GTN semantics as GTNS semantics.

For HGNs, Shivashankar et al. [2012] gave a bidirectional encoding of totally-ordered HGNs and HTNs, encoding task names as new goals. This easily extends to encode Erol et al.'s construction in partially-ordered HGN planning:

Theorem 5.1. Deciding whether a solution to an HGN or GTNS problem exists under GTNS semantics is semidecidable.

These results do not easily extend to task insertion with sharing. In particular, the proof that HTNI planning is NEXPTIME-hard encodes a Turing machine into the task network where an exponential number of partially-ordered tasks are synchronized through the state. In the following lemma and construction, we show that if there is a plan where two mergeable tasks were not merged, we can always merge the two tasks and replace the lost task's primitive descendants with task insertion.

In a derivation N0 -!⇤P Nk, we say that an instance symbol

i0 in a node Nj is a child of a symbol i in node Nj-1 iff (1) i = i0 and was not otherwise involved in the progression or (2) i0 was introduced in a decomposition Nj-1 i↪m --!D Nj . A descendant symbol of i is any child in the subsequent node, or a descendant of those children in following nodes, while the reverse holds for ancestors.

Lemma 5.2. Let N0 -!⇤PIM Nk be a derivation of a plan p for a problem P under GTNIS semantics, and let Nj be a node in that sequence with two mergeable tasks i1 and i2. Then there is a progression N 0 j -!⇤PIM Nk which preserves the remain sequence of operator application after merging i1 and i2.

Proof. Assume WLOG that i1 constrains some instance symbol i0 , and i0 is progressed before any other instance symbol constrained by i1 or i2 in the derivation Nj -!⇤PIM Nk, or that i1 and i2 constrain no tasks. Modify the derivation as fol-

lows: Let Nj i1↪i2 ---!M N 0 j . Drop any decomposition or goal release of descendant symbols of i2. For any operator application to a descendant of i2, replace with task insertion.

Construction 5.3. Let P be an HTN problem (by Construction 4.1 if necessary). Alford et al. [2015b] extends the work of Geier and Bercher [2011] to show that any solvable taskinsertion problem can be solved with acyclic progression, which never decomposes a task's ancestor of the same task name. We modify it for merging as follows: Where acyclic progression maintains a history of ancestral task names, instead associate each task with a counter, starting the counters in the initial node with ♣C♣ (the number of non-primitive task names). Decompose only tasks with a positive counter, and associate a decremented counter with the resulting children. When merging two tasks, the new task receives the greater of the two counters. Finally, after every decomposition or action application, all mergeable task names are merged.

So GTNIS planners can merge all mergeable tasks after every operation, leaving at most ♣C♣ unconstrained tasks, which is incompatible with HTNI's hardness proof. This leaves us with a looser bound for GTNIS planning:

Theorem 5.4. Deciding whether a problem is solvable under GTNIS semantics is PSPACE-hard and in NEXPTIME.

Meanwhile, HGNI planning is trivially in PSPACE: with insertion, one only needs to guess a totally-ordered sequencing of the initial subgoals, and solve it as a series of sequential propositional planning problems [Bylander, 1994]:

Theorem 5.5. Deciding whether an HGN problem is solvable under GTNI semantics is PSPACE-complete.

6 Conclusion and FutureWork

A number of hierarchical planning formalisms modify the standard HTN semantics in different ways; HGN planning uses goals in lieu of tasks, while ANML uses both tasks and goals as well as task insertion and sharing. Despite increased interest in using these planners in practice, there is little insight on how these modifications change the theoretical properties of HTN planning, both in terms of expressivity or computational complexity. Our key contributions against this are:

• ÷ We formalized GTN planning, a hybrid formalism that supports both task and goal decomposition. We also formalized task insertion and task-sharing semantics under this formalism, capturing features of HGNs and ANML.
• ÷ We provided plan-preserving translations from GTN problems with any combination of task insertion and sharing semantics to standard HTN semantics, thus showing that they are no more expressive than HTN planning, which in general is semi-decidable.
• ÷ We showed that HGN planning is also semi-decidable. In fact, we showed that HGN, HTN, and HTNS planning are all equivalent complexity-wise.
• ÷ We provided plan-preserving translations from HGN problems to HTN problems with task sharing semantics, thus showing than HGN is no more expressive than HTNS.
• ÷ Finally, we provided new upper bounds for subsets of GTN planning, showing that that HGNI is in PSPACE, and that GTNIS and GTNI planning are in NEXPTIME.

While we show that HGNs and GTNs (with and without task sharing and insertion) can be compiled to HTN planning, we do not claim that this is a superior method of planning. Goals, sharing, and insertion all provide explicit semantics that are obscured by the compilation process. This reduces both the ability to analyze the domain for correctness and the applicability of some heuristic search techniques [Shivashankar et al., 2016].

Future Work. There are several avenues to extend this work, some of which are:

• ÷ We showed only that GTNIS belong in NEXPTIME. We conjecture GTNIS planning may be PSPACE-complete.
• ÷ For HGN planning, we derived a semi-decidability result for partially ordered problems, which complements a known EXPTIME-completeness result [Shivashankar et al., 2012]. A more nuanced classification of HGN planning (similar to the classification of HTN planning [Alford et al., 2012]) would also extend to GTN planning.
• ÷ We provided plan preserving translations only in one direction, e.g. HGN! HTNS, GTNS! GTN, and GTN! HTN. We suspect some of the inverse plan-preserving translations are possible and others are not. Proving the non-existence of any of these translations would provide a firm separation in expressivity [H¨oller et al., 2016].
• ÷ Given the partially-ordered nature of GTN planning, it seems natural to extend it to planning with concurrent actions. Even PDDL 3 semantics [Gerevini and Long, 2005]

for trajectory constraints assume linear planning, which does not appear to increase complexity; it is not clear if partial order planning plus trajectory constraints increases complexity.

Acknowledgment This work is sponsored in part by OSD ASD (R&E). Ron Alford performed part of this work as an ASEE postdoc at NRL; affiliation with MITRE is provided for identification purposes only. The information in this paper does not necessarily reflect the position or policy of the sponsors nor MITRE, and no official endorsement should be inferred.