Hierarchical Task Network Planning with Task Insertion and State Constraints

1 Introduction

Hierarchical task network (HTN) planning [Erol et al., 1994] is an approach for building plans via step-wise refinement of high-level tasks into lower-level tasks in a top-down manner. A task network may contain both compound (high-level) and primitive tasks. Primitive tasks correspond to STRIPS-like actions that can be applied in states where their preconditions are met, while compound tasks are abstractions: for every compound task, the domain features a set of decomposition methods, each mapping the task to a task network. The complexity of the plan-existence problem for HTN planning ranges up to undecidability even for propositional HTN planning [Erol et al., 1994]. Even so, hierarchical planning approaches are often chosen for real world application scenarios [Lin et al., 2008; Biundo et al., 2011]. On the other hand, it is usually a challenge to provide a complete domain which includes all possible methods for all compound tasks, while defining only a partially hierarchical domain is not sufficient to produce all desired solutions. Several HTN researchers have investigated how partially hierarchical domain knowledge can be exploited during planning without relying on the standard HTN formalism [Kambhampati et al., 1998; Biundo and Schattenberg, 2001; Geier and Bercher, 2011; Shivashankar et al., 2013]. Among them, hierarchical task network with task insertion (TIHTN) planning [Geier and Bercher, 2011] relaxes the restriction on solutions and allows solutions generated not only by the decomposition of compound tasks, but also by the insertion of primitive tasks from outside the decomposition hierarchy.

Unfortunately, only ordering constraints are considered in propositional TIHTN planning [Geier and Bercher, 2011] and lifted TIHTN planning [Alford et al., 2015b]. In contrast, state constraints are taken into account in the conventional HTN planning [Erol et al., 1994], but there is few work on considering them in TIHTN planning.

In this paper, we investigate the extension of TIHTN with state constraints, noted TIHTNS for short. We first prove that, just as for the TIHTN planning problem, all solutions of the TIHTNS problems can be obtained by acyclic decomposition and task insertion, entailing that it is decidable without any restrictions on decomposition methods. We then show that the extension by state constraints does not cause an increase in complexity of the plan-existence problem, which stays 2NEXPTIME-complete, based on an acyclic progression operator. We also show that TIHTNS planning includes lifted TIHTN planning. As under task insertion semantics, hierarchical goal network (HGN) planning [Shivashankar et al., 2013] and goal-task network (GTN) planning [Alford et al., 2016] can be translated to lifted TIHTN, our framework, TIHTNS, actually covers the two kinds of planning approaches. In addition, we give an alternative embedding of hierarchyrelaxed HGN (HR-HGN) [Shivashankar et al., 2017] in TIHTNS without introducing fresh operators.

State constraints State constraints can capture the pre- and postcondition of compound tasks, though in the standard HTN planning there is no notion of pre- and postcondition of compound tasks. A compound task is considered as accomplished if its subtasks are accomplished. With a state constraint, a formula, as a postcondition, can be required to hold after accomplishing a compound task.

Ordering constraints cannot fully represent state constraints. The 'immediate' state constraint, which requires a formula holds immediately before or after a compound task, can be simulated via introducing a virtual subtask to check whether the formula holds. However, the 'maintenance' state constraints (also called trajectory constraints in the Planning Domain Definition Language 3 (PDDL3) [Gerevini and Long, 2005]) cannot be represented easily. For instance, suppose a robot is required to always keep 10% battery for emergency. Its initial compound task is to "clean a room", decomposed into "clean the ground" (t1) and "clean the table" (t2). Suppose that "clean the ground" requires the full battery. Then there is no solution for the TIHTNS planning problem with such a state constraint. 1

Furthermore, state constraints are introduced into PDDL3 [Gerevini and Long, 2005] to support hard constraints over state properties of a trajectory and the specification of preferences. Later [Sohrabi et al., 2009] extends PDDL3 into HTN planning where state constraints are used to capture user preferences. State constraints are also necessary in real-world applications, such as in web service composition where state constraints are used to describe user preferences [Lin et al., 2008] and to additionally capture the enforcement of regulations [Sohrabi and McIlraith, 2009].

The rest of the paper is structured as follows. Section 2 presents the definition of TIHTNS. Section 3 presents how to embed lifted TIHTN and HR-HGN into TIHTNS. Section 4 presents the complexity results of TIHTNS. Section 5 concludes and discusses the future work.

2 Extended TIHTN Planning

In this section we adapt the original TIHTN planning formalism of [Geier and Bercher, 2011; Alford et al., 2015b]. First, we define a function-free first order language L from a set of variables and a finite set L0 of predicates and constants. Next we take parts of variables in L as task symbols to identify tasks. Every task is associated with an action (task name), which is syntactically a first-order atom in L. That is, every action typically is associated with an arity and contains variables that can be eliminated via grounding. For example, by grounding the action "openDoor(X)" where X is quantified as a door, we can obtain a set of ground actions "openDoor(a)", "openDoor(b)", etc. Those actions which can be executed directly are called operators, noted O, while others are called compound actions, 2 noted C. Each operator o ∈ O is represented as a triple of formulas: precondition pre(o), positive effect add(o), and negative effect del(o) where add(o), del(o) are finite sets of atomic formulas. The variables in add(o) and del(o) should be associated with the variables in the operator so that they are instantiated simultaneously. For example, the positive effect of "openDoor(X)" being "Opened(X)", after grounding "openDoor(a)" has positive effect "Opened(a)" but not "Opened(b)". The positive and negative effect of an operator should not conflict, i.e., add(o) ∩ del(o) = ∅ for every o ∈ O. We suppose that O contains the 'empty' primitive operator skip where pre(skip) = ⊤ and add(skip) = del(skip) = ∅.

For a function f : R → S, its restriction to a subset X of its domain is f|X = {(r, s) ∈ f | r ∈ X}. Given a binary relation Q ⊆ R × R, we define its restriction to X ⊆ R by Q|X = Q ∩ (X × X); similarly for ternary relations. We extend the set union operator ∪ to tuples: (Q1,Q2) ∪ (Q′1 ,Q′2 ) = (Q1 ∪ Q′1 ,Q2 ∪ Q′2 ) and extend functions to sequences: f(〈t1, . . . , tn〉) = 〈f(t1), . . . , f(tn)〉.

1 For the original TIHTN planning, there is an intuitive attempt to simulate that constraint: introducing a virtual primitive task pt whose precondition is "more than 10% battery" and introducing two ordering constraints t1 ≺ pt and pt ≺ t2. Assume "charge" means to charge the battery, then the plan 〈t1;"charge";pt;t2〉 is a solution of the original TIHTN planning problem. But it is counter-intuitive and the state constraint is still violated.

2 In the original HTN, "non-primitive or compound task name" is used to distinguish from STRIPS-like actions, i.e., operators.

2.1 HTN Problems

Task networks A task network tn = (T,∆, α) is a tuple, where

• T is a finite and non-empty set of task symbols;
• ∆ ⊆ (T∪{nil}) × L × (T∪{nil}) is a set of constraints over T
• α : T → C ∪ O labels every task with an action.

With Function α, we allow multiple instances of an action in a task network. Compared to the ordering constraints in [Geier and Bercher, 2011] which are in form of task-task pairs, we use a triple (ti, ϕ, tj) to denote a state constraint which intuitively means that formula ϕ must be true in all states between ti and tj. Specially, we introduce an idle task symbol nil which designates a task that is accomplished immediately: (nil, ϕ, tj) and (ti, ϕ, nil) mean formula ϕ holds immediately before tj and after ti, respectively. We suppose nil only occurs in constraints. When ϕ is the truth constant ⊤ then the state constraint (ti, ϕ, tj) becomes an ordering constraint that just requires that ti is before tj. A task is primitive if it is associated to an operator, otherwise compound. A task network is primitive if it only contains primitive task.

We say that two task networks tn = (T,∆, α) and tn′ = (T ′ ,∆′ , α′ ) are isomorphic, noted tn ∼= tn′ , if there exists a bijection δ : T → T ′ where for all t, t′ ∈ T it holds that α(t) = α′ (δ(t)) and (t, ϕ, t′ ) ∈ ∆ iff (δ(t), ϕ, δ(t′ )) ∈ ∆′ .

Methods Non-primitive task networks contain compound tasks which cannot be executed directly by the agent, and decomposition methods tell us how to decompose these hierarchically. Each decomposition method m is a tuple (c, tnm), where c is a compound action, called the method's head, and tnm is a task network, whose inner tasks are called the method's subtasks. The intuition is that compound action c can be reduced by the subtask network tnm.

HTN problems TIHTNS problems only differ HTN problems in the solution criterion and share the syntactical problem description. An HTN domain is a tuple D = (L, C, O,M) where M is a set of methods and C ∩ O = ∅. An HTN problem is a tuple P = (D, sI , tnI) where sI is the ground initial state and tnI is the initial task network.

The semantics of HTN planning is given through grounding. According to [Alford et al., 2015a], it is easy to translate a lifted HTN problem into a ground (or propositional) HTN problem as the set of relations and constants L0 is finite. For an HTN problem (L, C,O,M, sI, tnI), we use P = (L,C,O,M, sI, tn′I ) to denote the ground (or propositional) problem obtain from it.

A ground state is a subset of the ground atoms in L0. A set of ground operators O determines a state-transition function γ : 2L0 × O -→ 2L0 , where:

• γ(s, o) is defined iff s |= pre(o);
• γ(s, o) = (s \ del(o)) ∪ add(o) if γ(s, o) is defined.

A sequence of 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.

Example 1. Suppose we have an initial compound action goMC for "go to Melbourne center", operator o1 for "fly to Melbourne", and operator o2 for "take a taxi to the center". We use At(Mc)and At(Ma) to denote "being at Melbourne center" and "being at Melbourne airport". The primitive operators are:

• o1 = (⊤, {At(Ma)}, ∅)
• o2 = (At(Ma), {At(Mc)}, {At(Ma)})

and the method is:

· m = (goMC, tnm), where tnm = (t2, ∅, (t2, o1)) Then the HTN problem P is (L, goMC, {o1, o2}, m, sI , tnI ) with sI = ∅ and tnI = (t1, (t1, At(Mc), nil), (t1, goMC)). 3

2.2 Task Decomposition

Next we borrow the notion of decomposition in [Geier and Bercher, 2011] and define how to decompose a compound task into a task network. In order to indicate the starting point and the end point of a compound task t, we introduce a pair of 'dummy' primitive tasks, noted ∗t and t∗. As nil only occurs in constraints, we suppose the restriction of constraint set ∆ to a set of tasks T is ∆|T = ∆∩((T∪{nil})×L×(T∪{nil})).

Definition 1 (Decomposition). Given an HTN domain D = (L, C, O,M), let tn = (T, ∆, α) be a task network and t ∈ T be a compound task. Let m = (α(t), (Tm,∆m, αm)) and Tm ∩ T = ∅. The decomposition of task t by method m is tn′ = (T ′ , ∆′ , α′ ) where

We write tn --→ t,m tn′ when tn′ is the decomposition of t bym.

In the resulting task network, the decomposed compound task is replaced with subtasks defined by the method applied and its corresponding starting and terminating tasks. The latter two are dummy tasks and are mapped to the action skip. All state constraints about the decomposed task t are propagated by ∗t and t∗ in ∆′ . More precisely, if ϕ holds before t then it also holds before ∗t and if ϕ′ holds after t then it also holds after t∗. Subtasks should satisfy the inner constraints introduced by the decomposition method and should be performed between ∗t and t∗.

Example 2 (Example 1 continued). We apply the method m in tnI to decompose t1, i.e., tnI ---→ t1,m tn′ , where tn′ is:

3 We will sometimes omit the braces of singleton sets.

Decomposition tree The hierarchical procedure of task decomposition can be viewed as a tree. Given an HTN domain D = (L, C, O,M), a decomposition tree is a five-tuple Tr = (T,E,∆, α, β) where (T,E) is a tree, rooted in t0 which is a fresh task symbol, with nodes T and with directed edges E pointing towards the leaves; ∆ is a set of constraints over T ; function α : T → C∪O links tasks and actions where α(t0) = c0 such that c0 is a fresh compound action with an intuition "to achieve the initial task network". β : T → M ′ labels inner nodes with methods where M ′ = M∪{(c0, tn0)} and tn0 is some task network.

We write τ(Tr) for the nodes (tasks) of the decomposition tree Tr and ch(Tr, t) for the direct children of t ∈ τ(Tr) in Tr. Hereafter sub(t) denotes the set of subtasks of t. The leaf nodes of Tr together with the constraints about these nodes define a task network, denoted by ϑ(Tr).

Definition 2 (valid decomposition tree). A decomposition tree Tr is valid w.r.t. an HTN problem P = (L,C,O,M, sI, tnI) iff the root node of Tr is t0 where β(t0) = (c0, tnI) and for any inner node t where β(t) = (c, tnm), the followings hold:

2. if t = t0 then ch(Tr, t) = sub(t), otherwise ch(Tr, t) = sub(t) ∪ {∗t, t∗} such that

• (sub(t),∆|sub(t), α|sub(t)) ∼= tnm
• for every t′ ∈ sub(t), (t′ ,⊤, t∗), (∗t,⊤, t′ ) ∈ ∆
• for every t′ ∈ τ(Tr) ∪ {nil}:
• if (t, ϕ, t′ ) ∈ ∆ then (t∗, ϕ, t′ ) ∈ ∆
• if (t′ , ϕ, t) ∈ ∆ then (t′ , ϕ, ∗t) ∈ ∆

4. there are no constraints in ∆ except for those demanded by criterion 2. and 3.

When tn′ is reachable from tn by a finite sequence of decompositions then we write tn -→∗D tn′ .

The decomposition tree focuses on the whole procedure of decomposition and records all intermediate tasks and constraints during the procedure. In contrast, in a task network the application of a decomposition method abandons the decomposed task. However, they are compatible as the following proposition states.

Proposition 1. Given an HTN problem P, tnI -→∗D tn iff there exists a valid decomposition tree Tr with respect to P where ϑ(Tr) = tn.

2.3 Solutions

A solution of an HTN problem is a sequence of primitive tasks which is also called a plan of the problem.

Consistency with constraints Given a primitive task network tn = (T, ∆, α) where |T | = n, let σ : T → {1, . . . , n} be a bijection. We use σ to form a total ordering, noted σ(tn), of tasks in T as: 〈σ-(1), . . . , σ-(n)〉 where σ- is the inverse function of σ, i.e., σ-(σ(t)) = t. Suppose α(σ(tn)) is executable in s0, i.e., there exists a sequence s1, . . . , sn such that γ(si-1, α(ti)) = si for every i such that 1 ≤ i ≤ n. We say that σ(tn) is consistent with ∆ in s0 if for every σ-(i), σ-(j) ∈ T the following hold:

• for every (nil, ϕ, σ-(j)) ∈ ∆, sj-1 |= ϕ;

• for every (σ-(i), ϕ, nil) ∈ ∆, si |= ϕ;
• for every (σ-(i), ϕ, σ-(j)) ∈ ∆, i < j and sk |= ϕ for every i ≤ k<j.

Intuitively, a 'maintenance' state constraint (t, ϕ, t′ ) is satisfied if all states between t and t′ satisfy ϕ. An 'immediate' state constraint (nil, ϕ, t) is satisfied if ϕ holds in the state right before ∗t occurs (or t if t is a primitive task), in other words right before all subtasks of t. Finally, an 'immediate' state constraint (t, ϕ, nil) is satisfied if ϕ holds right after the state where ∗t (or t if t primitive task) occurs, in other words right after all subtasks of t. Note that it is impossible to satisfy (t, ⊥, t′ ) because there is no state s such that s |= ⊥.

Executability A task network tn is primitive iff it contains only primitive tasks. A primitive task network tn is executable in a state s iff there exists a total ordering σ(tn) of the tasks in tn that is consistent with ∆ in s. We called such a σ(tn) a plan of tn in s, noted σtn,s.

It is possible that the task network is not executable in a state. For instance, the primitive task network tn′ in Example 2 is not executable in sI because apart from skip it only involves the operator o1 and it is impossible to satisfy At(Mc). However, if we extend the task network by inserting some tasks, then we can make it executable.

Insertion Let tn = (T,∆, α) and tn′ = (T ′ ,∆′ , α′ ) be two task networks where tn′ is primitive. Inserting tn′ into tn results in the task network tn1 = tn ∪ tn′ .

Note that it is not required that T ′ ∩ T = ∅ because the insertion can involve some constraints about tasks in tn.

Solutions With respect to some initial tn, if tn′ is reachable by a finite sequence of decompositions and an insertion we write tn -→∗DI tn′ . The plan obtained only by decomposition is called an HTN solution while the plan obtained additionally by insertion is called a TIHTNS solution:

Let tn be a primitive task network such that there exists a plan of tn in sI . Given an HTN problem P, we call σtn,sI an HTN solution of P if tnI →∗D tn; we call σtn,sI a TIHTNS solution of P if tnI →∗DI tn.

Example 3 (Example 2 continued). The plan 〈∗t1, t2, t3, t1∗〉 where α(t3) = o2 is a TIHTNS solution of P.

When considering whether an HTN problem P has a TIHTNS solution, we call P a TIHTNS problem.

The next proposition states that the state constraints about compound tasks are satisfied in the solutions of the problem.

Proposition 2. Given a TIHTNS problem P, suppose Tr is a valid decomposition tree with respect to P and tn′ is the final primitive task network obtained from ϑ(Tr) by insertion and σtn′ ,sI is a solution of P. Then all constraints in Tr are satisfied by σtn′ ,sI .

Sketch of proof. Suppose there are two compound tasks ti and tj in Tr and tn′ = (T ′ , ∆′ , α′ ). For every (ti, ϕ, tj) ∈ ∆, we have (ti∗, ϕ, ∗tj) ∈ ∆′ and then all states sk such that σ(ti∗) ≤ k < σ(∗tj), sk |= ϕ. For every (ti, ϕ, nil) ∈ ∆, we have (ti∗, ϕ, nil), (st,⊤, ti∗) ∈ ∆′ for all subtasks st ∈ sub(ti) and then sσ(ti∗) |= ϕ and σ(st) < σ(ti∗) for all st ∈ sub(ti). The case of (nil, ϕ, tj) is similar. If one or both of ti, tj are primitive then just consider ∗tj and ti∗ as tj and ti, respectively. Then all constraints in Tr are satisfied.

Remark 1. The state constraint here we define is weaker than that in the original HTN planning [Erol et al., 1995]. Their semantics considers every compound task starts by its first 'real' subtask and terminates by its last 'real' subtask instead of the virtual starting and terminating tasks. The distinction between two semantics stands on whether it is allowed to insert tasks between ∗t and the first real subtask of t (between the last real subtask and t∗). Our weaker semantics can capture the pre- and postcondition of compound actions better. In Example 1, after the subtask t2 of goMC is accomplished, the agent's desirable goal "being in the center" does not hold while by allowing the insertion of t3, the goal is achieved.

3 Embedding TIHTN and HGN

Recently HTN researchers work on enhancing the semantics of HTN planning and have proposed variants of HTN planning. Propositional TIHTN was first proposed in [Geier and Bercher, 2011] and later was extended into lifted TIHTN in [Alford et al., 2015b]. Hierarchy goal network (HGN) planning [Shivashankar et al., 2012] operates over a hierarchy of goals with methods that decompose goals with further subgoals. [Shivashankar et al., 2017] relaxes the hierarchy of HGN planning and translates the variant which is called HRHGN planning into classical planning. Hereafter, we detail that how lifted TIHTN and HR-HGN planning can be easily encoded in our framework in polynomial time.

Embedding TIHTN Let us now translate lifted TIHTN into our extended TIHTNs. By replacing all occurrences of ti ≺ tj in lifted TIHTN problem P with (ti,⊤, tj), we obtain a TIHTNS problem, noted ΓT (P). The following proposition shows that the two problems are equivalent.

Proposition 3. For a lifted TIHTN problem P, P has a solution iff ΓT (P) has a solution.

Sketch of proof. Under the lifted TIHTN semantics, consider the decomposition of t by m, the new ordering constraint set is obtained as: (1) keep the constraints not involving t; (2) introduce the constraints about the subtasks; (3) if t is before t′ then all subtasks are before t′ ; (4) if t is after t′ then all subtasks are after t′ . Under the extended semantics, according to Definition 1, the change of state constraints includes (1) and (2) and is analogous to (3) and (4). If t is before t′ , i.e., (t,⊤, t′ ), there will be (t∗,⊤, t′ ) introduced. As (tm,⊤, t∗) for all subtasks tm are introduced, it entails that (tm,⊤, t′ ) which means tm is before t′ . Then (3) is simulated and the case of (4) is similar. The proposition follows.

Alford et al. [2016] combine HTN and HGN planning into goal-task network (GTN) planning where an element of the network consists of a goal and a task. They also show that allowing task insertion, HGN and GTN planning problems can be translated polynomially into lifted TIHTN problems. Therefore, our extension TIHTNS actually also covers them. Embedding HR-HGN Hierarchical goal network planning is a formalism which extends classical planning to include hierarchical decomposition using methods.

HGN planning talks about goal network gn = (G,≺) where G is a set of formulas in disjunctive normal form over ground literals, called goal formulas, and ≺⊆ G × G is a strict partial order on G. Similar with HTN problems, an HGN problem is a tuple P = (L, O, M, sI , gnI ) where M is a set of HGN methods and gnI is an initial goal network. For an HR-HGN problem, M is a empty set and omitted. The solutions of HR-HGN are defined as the set of all operators sequences that are executable in the initial state sI and that achieve all initial goals according to the order. In [Shivashankar et al., 2017], by introducing fresh operators with the number of |gnI |, an HR-HGN problem can be translated into a classical planning problem. Now, we translate HR-HGN planning into our framework without introducing any fresh operators. Allowing task insertion, state constraints simulate a goal formula by requiring that the formula holds immediately before an empty task. Formally, given an HRHGN problem P = (L,O, sI, gnI), we define a TIHTNS problem ΓG(P) = (L, ∅, O, ∅, sI , tn) as:

• for every g ∈ GI, λg ∈ tn and (nil, g, λg) ∈ ∆ and α(λg) = skip
• for every gi ≺ gj, (λgi ,⊤, λgj )

Next we show that the translation ΓG is correct.

Proposition 4. For an HGN problem P, P has a solution iff ΓG(P) has a solution.

Sketch of proof. Suppose σtn′ ,sI is a solution of ΓG(P). Then tn′ is obtained from tn by an insertion. It forms a sequence s0, . . . , sn where s0 = sI . For every g ∈ GI , we have λg ∈ T ′ and (nil, g, λg) ∈ ∆′ then si |= g where σ(λg) = i; for every gi ≺ gj, we have (λgi ,⊤, λgj )∆′ then i′ < j ′ and si′ |= gi, sj ′ |= gj,where σ(λgi ) and σ(λgj ).

4 Complexity

In this section, we show that the solutions of TIHTNS can be obtained by acyclic decomposition and it does not increase the complexity, staying 2-NEXPTIME-complete.

Substitution Now we adapt the notion of subtree substitution initially proposed in [Geier and Bercher, 2011] which replaces a subtree with another subtree. Given a decomposition tree (T,E,∆, α, β) and a node t ∈ T, we define the subtree of Tr induced by t, as Tr[t] = (T ′ , E′ , ∆|T ′ , α|T ′ , β|T ′ ) where (T ′ , E′ ) is the subtree in (T, E) which is rooted in t.

Let Tr = (T,E,∆, α, β) be a decomposition tree and ti, tj ∈ T be two nodes of Tr where ti is an ancestor of tj . We define the result of the subtree substitution on Tr that substitutes ti by tj , written Tr[ti ← tj ] = (T ′ , E′ , ∆′ , α|T ′ , β|T ′ ), where

Compared to [Geier and Bercher, 2011], the substitution operator here requires to remove tj corresponding starting and terminating tasks before replacement because they are generated from tj's parent which will be dropped. The following proposition states that the resulting tree is still valid.

Proposition 5. Let Tr = (T,E,∆, α, β) be a valid decomposition tree with respect to TIHTNS problem P and two nodes ti ∈ T, tj ∈ τ(Tr[ti]) with α(ti) = α(tj). Then Tr[ti ← tj] is also a valid decomposition tree w.r.t. P.

Acyclic decomposition The sequence of decompositions is acyclic if for every node t in its corresponding tree Tr, the ancestors of t have different actions.

The insertion of tasks allow us to break the loop of generating same compound tasks during the decomposition procedure and find a shortcut to generate the solution. The following theorem states that we only need to consider the acyclic sequences of decompositions to compute the solution.

Theorem 1. A TIHTNS problem P has a solution iff P has a solution which is generated by an acyclic sequence of decompositions and an insertion.

Proof. The right-to-left direction is straightforward. Nowwe prove the left-to-right direction.

Suppose σtn,sI is a TIHTNS solution of P where tnI →∗D tn1 and tn is obtained from tn1 by insertion. Then tn1 is a primitive task network. If the sequence of decompositions from tnI to tn1 is acyclic, then it is proved. Now suppose the sequence is not acyclic. Then in its corresponding tree Tr, there exist two ancestors ti, tj of some t such that α(ti) = α(tj). By Proposition 5, the tree Tr[ti ← tj] is valid with respect to P. By Proposition 1, there exists a primitive task network tn2 such that tn2 = ϑ(Tr[ti ← tj]) and tnI →∗D tn2. As the substitution does not introduce any new node, the leaf nodes of Tr[ti ← tj] are a subset of the leaf nodes of Tr. The only state constraints about leaf nodes which are introduced by the substitution are (tj∗, ϕ1, t1) and (∗tj, ϕ2, t2). Now we replace all occurrences of tj∗ with ti∗, ∗tj with ∗ti in Tr[ti ← tj]. Then except for those constraints between subtasks of tj and either tj∗ or ∗tj, in form of (∗tj,⊤, t) and (t,⊤, tj∗), the constraints in tn2 are a subset of the constraints of tn1. Because ti is an ancestor of tj in Tr, there must be some tasks t′ , t′′ , . . . , t(k) such that (∗ti,⊤, t′ ), (t′ ,⊤, t′′ ), . . . , (t(k) ,⊤, ∗tj). Thus, in the plan σtn,sI , ∗ti is before ∗tj and then before all subtasks of tj. Then those constraints (∗tj , ⊤, t) are satisfied; the case of tj∗ is similar. So σtn,sI includes all tasks in tn2 and is consistent with all constraints in tn2 and then tn can be obtained from tn2 by inserting an appropriate task network.

The next lemma allows us to only check whether there is a solution with an upper bound on length.

Lemma 1. If TIHTNS problem P = (L, C,O,M, sI, tnI) has a solution then P has a solution with a length of at most |TI |×(k+2)|C|×cm ×2p×cn , where k is the maximal number of subtasks in one method, c and p are the number of constants and predicates respectively, m and n are the maximal arity of compound actions and predicates respectively.

Sketch of proof. A valid decomposition tree generated by acyclic decomposition has at most |TI |×(k+2)|C| leaf nodes where |C| is the number of ground compound actions that is |C| × cm. As the number of states is bounded by 2|L0| where |L0| is the number of ground atoms that is p × cn , at most 2|L0| tasks can be inserted between two neighbor tasks.

As the state-transition function γ satisfies the frame axiom, before performing an operator we can check whether a formula is true in the next state. Given a formula ϕ, we use ϕ-o to denote the formula obtained from ϕ by replacing p with ⊤ and q with ⊥ where p ∈ add(o) and q ∈ del(o). As all variables outside the effect of operator o keep their truth value, we can check whether a formula ϕ holds in the next state before operator o is performed, as the following lemma states:

Acyclic progression We adapt the acyclic progression operator proposed in [Alford et al., 2015b] to TIHTNS. To capture the 'maintenance' state constraints we introduce a set Σ of pairs (ϕ, t) of formula and task which means ϕ should be satisfied until performing task t. We use Fml(Σ) to denote the conjunction of all formulas in Σ. To forbid the recursion of tasks, when decomposing a compound task t by method m, its subtasks cannot contain t's ancestors denoted by h(t), where h : T -→ 2C . Formally, we use a tuple (s, tn, Σ, h) to represent that task network tn still needs to be accomplished at the current state s. Given a tuple (s, tn, Σ, h), we define its acyclic progression is (s′ , tn′ , Σ′ , h′ ) with tn′ = (T ′ , ∆′ , α′ ), which is obtained from three possible options:

• Task insertion: if s |= pre(o) ∧ Fml(Σ)-o then s′ = γ(s, o) and tn′ = tn, Σ′ = Σ, h′ = h

The task inserted should satisfy the state constraints.

• Task performing: for a primitive task t ∈ T, if s |= pre(α(t)) ∧ Fml(Σ-t)-α(t) where Σ-t = Σ ∩ (L × (T \ {t})) and the followings hold:
• there is no t′ such that t′ ̸= nil and (t′ , ϕ, t) ∈ ∆
• for every (nil, ϕ, t) ∈ ∆, s |= ϕ
• for every (t, ϕ, t′ ) ∈ ∆, s |= ϕ-α(t)

then

• T ′ = T \ {t}, ∆′ = ∆|T ′ , α′ = α|T ′
• Σ′ = Σ-t ∪ {(ϕ, t′ ) | (t, ϕ, t′ ) ∈ ∆ and t′ ̸= nil}
• h′ = h|T ′ and s′ = γ(s, α(t))

A primitive task is chosen only if its all predecessors have been accomplished, its precondition is satisfied and the state constraints in Σ, except for those constraints ending with the primitive task, will hold after performing it. The 'maintenance' state constraints starting from the primitive task will be added into Σ.

• Task decomposition: for a compound task t ∈ T and a method (α(t), (Tm, ∆m, αm)) ∈ M, if h(t) ∩ Tm = ∅, then tn --→ t,m tn′ and
• h′ = h|T ′ ∪ {(tm, h(t) ∪ {α(t)}) | tm ∈ Tm}
• Σ′ = Σ|T ′ ∪ {(ϕ, ∗t) | (ϕ, t) ∈ Σ}

For a compound task, the method chosen to decomposed cannot contain an action which is its ancestor in order to avoid the recursion of tasks.

Note that the cardinality of Σ may be exponential on size but Fml(Σ) is polynomial which is restricted by the constraints in M. It entails that applying a step of acyclic progression is in P.

If all tasks can be eliminated by the acyclic progression, then the TIHTNS problem has a solution:

Lemma 3. Given a TIHTNS problem P, P has a solution iff there is a sequence of acyclic progressions from (sI , tnI , ∅, hI) to (s, tn∅, ∅, ∅) where hI = αI and tn∅ is the empty task network.

As TIHTNS can cover lifted TIHTN whose plan-existence problem is 2-NEXPTIME-complete [Alford et al., 2015b], the plan-existence problem for TIHTNS is 2-NEXPTIMEhard. The next theorem states its completeness by proving the upper bound.

Theorem 2. Deciding whether a TIHTNS problem has a solution is 2-NEXPTIME-complete.

Proof. Theorem 1 reduces deciding the problem into checking all solutions generated by acyclic decomposition and Lemma 1 reduces further deciding the problem into checking solutions with an upper bound on length. By introducing a counter on operators according to [Alford et al., 2015b], the length of a solution can be restricted with a polynomial translation on the problem. As the number of decomposing compound tasks is bounded double exponentially, it can ensure that every sequence of acyclic progression terminates after a double exponential number of steps of insertion, performing and decomposition. Therefore, by applying nondeterministically acyclic decomposition, either it can reach a solution or it cannot progress any more which entails that the problem has no solution.

5 Conclusion

In this paper, we extended TIHTN so that state constraints can be captured. We have shown that this extension does not increase the complexity while it can represent cover planning frameworks: lifted TIHTN and HR-HGN.

State constraints are written as linear temporal logic (LTL) formulas in PDDL3. It seems not difficult to adapt the notion of consistency with constraint to LTL formulas.

The experimental results in [Shivashankar et al., 2013] show that the completeness of methods can contribute to the performance of the HGN planners. It is also interesting to extend TIHTNS again with allowing method insertion. A promising reference is [Herzig et al., 2016] which provides a dynamic view of HTN planning and models decomposition in propositional dynamic logic.

Acknowledgments

We wants to appreciate the reviewers for their insightful comments. Zhanhao Xiao is partially supported by CSC (Chinese Scholarship Council) and Hai Wan is partially supported by National Natural Science Foundation of China under grants 61573386, Natural Science Foundation of Guangdong Province under grant 2016A030313292 and Guangdong Province Science and Technology Plan projects under grant 2016B030305007. Laurent Perrussel is partially supported by ANR-11-LABX-0040-CIMI within the program ANR-11IDEX-0002-02.