On the Decidability of HTN Planning with Task Insertion

1 Introduction

Planning is known to be intractable in general. This holds both for classical state-based planning and for hierarchical planning. For the former, the complexity of the plan existence problem ("Is there a plan that solves the given planning problem?") reaches from constant time over EXPSPACE-complete to undecidable [Erol et al., 1995] depending on various restrictions. The most expressive "configuration" of classical planning that is still decidable 1 is thus intractable. Hierarchical task network (HTN) planning was created to mitigate this complexity problem by introducing a hierarchy over operators and thereby including search control knowledge into the planning process. Contrary to the intuition that the introduced hierarchy makes planning easier, it introduced undecidability even for the case in which classical planning is "only" PSPACE-complete2 ; this result was proved by Erol et al. [1996] for their formalization of HTN planning [Erol et al., 1994].

1 Datalog (no function symbols and finitely many constant symbols); operators are given in the input; allow delete lists and negated preconditions [Erol et al., 1995].

2 Propositional; operators are given in the input; allow delete lists and negated preconditions [Erol et al., 1995].

The hierarchical aspect in HTN planning is achieved by introducing the concept of compound tasks in addition to the operators known from classical planning, which we call primitive tasks in this context. Compound tasks can be decomposed into predefined partial plans using so-called decomposition methods. The goal is to find an executable plan that was obtained by decomposing compound tasks in the initial plan until all tasks are primitive. Although the provision of decomposition methods can speed up the search process, they introduced undecidability. However, several restrictions can be imposed on methods which make the plan existence problem decidable: for instance if the initial task network and all methods are totally ordered or if all methods are acyclic [Erol et al., 1996]. In this work, we show how decidability can be achieved without restricting methods by altering the solution criterion of HTN planning problems.

We investigate the decidability of the plan existence problem for HTN planning with task insertion, a planning formalism that lies between classical and HTN planning and is therefore often referred to as hybrid planning: the idea is to have an initial task network that needs to be decomposed, but to allow the insertion of tasks without requiring them to be inserted by the decomposition of compound tasks. This particular variant of fusing classical with HTN planning has been addressed before by Estlin et al. [1997], Schattenberg and Biundo [2006], and Gerevini et al. [2008]. The most important argument for this planning paradigm is that it overcomes a main criticism of HTN planning: "HTN planning reduces the flexibility of an agent to respond to situations that are not anticipated by the writer of the task reduction schemas" [Kambhampati et al., 1998]. This argument is also the main motivation for Kambhampati et al.'s formalization of hybrid planning. There, compound tasks also show preconditions and effects like primitive ones and they can be inserted like operators in classical planning (which is also true for the work of Schattenberg and Biundo [2006]). However, Kambhampati et al. do not specify an initial task network. Hence, there is no need to insert and decompose compound tasks and therefore, they are only an efficiency boost for solving classical planning problems.

In the following sections we will first introduce our formalization of HTN planning with task insertion. We explain why our formalism, although stripped of many technical aspects, is still susceptible to the original proof of undecidability for HTN planning when disallowing insertion of tasks. We then present a result that yields an upper bound on the length of shortest solutions and derive from it an upper complexity bound for the plan existence decision problem. In the end we conclude our paper with a discussion of the presented results.

2 Formalism

In this section, we introduce our notion of HTN planning with task insertion (or hybrid planning, for short). For the sake of simplicity, we base our formalism on a ground state representation. That is, there exist only boolean propositions. The choice effects only the final complexity class but not the decidability, as long as a potential first-order representation does not introduce undecidability on its own, e.g., by the use of functions.

During the rest of the paper, we consider relations and functions as sets of tuples. We use the bar notation for restricting relations and functions. Given a set of tuples Q ⊆ R × R, we define Q|X :={(q1, q2) ∈ Q | q1, q2 ∈ X} and for a function f : R → S, we define f |X :={(r, s) ∈ f | r ∈ X}.

We begin by describing a task network, which represents a generalization of a task sequence in that it is only partially ordered.

Definition 1 (Task Network). A task network tn = (T, ≺, α) over a set of task names X is a tuple, where

• T is a finite and non-empty set of tasks
• ≺ ⊆ T × T is a strict partial order on T (irreflexive, asymmetric, and transitive)
• α : T → X labels every task with a task name

We write TNX for the set of all task networks over the task names in X. Given a task network tn = (T, ≺, α) and a set of tasks T ′ , we define its restriction tn|T ′ :=(T ∩T ′ , ≺|T ′ , α|T ′ ). Also we write T (tn) to refer to the tasks of tn.

Tasks serve the purpose of unique identifiers because task names (like "move" or "open door") may occur multiple times in the same task network. This leads us to the next definition: two task networks are isomorphic if they describe the same arrangement of task names despite using different identifiers.

We define two task networks tn = (T,≺, α) and tn′ = (T ′ , ≺′ , α′ ) as being isomorphic, written tn ∼= tn′ , if and only if there exists a bijection σ : T → T ′ , such that for all t, t′ ∈ T it holds that (t, t′ ) ∈ ≺ if and only if (σ(t), σ(t′ )) ∈ ≺′ and α(t) = α′ (σ(t)).

Definition 2 (Planning Problem). A planning problem is a 6-tuple P = (L, C, O, M, cI , sI ) and

• L, a finite set of proposition symbols
• C, a finite set of compound task names
• O, a finite set of primitive task names with C ∩ O = ∅
• M ⊆ C ×TNC∪O, a finite set of decomposition methods
• cI ∈ C, the initial task name
• sI ∈ 2L, the initial state

For each o ∈ O, (prec(o), add(o), del(o)) ∈ 2L × 2L × 2L is called the operator of o and consists of a precondition, an add-, and a delete list. By tnI := ({tI }, ∅, {(tI , cI )}) we denote a fixed initial task network which consists only of the initial task tI mapping to the initial task name cI .

HTN planning formalizations usually feature an initial task network instead of only a single initial task name. We would like to note that our choice does not reduce the class of problems that can be expressed.

Both compound and primitive task names will be used to label the elements of task networks. We refer to tasks that are labeled with elements from C and O as compound tasks and primitive tasks, respectively. We refer to a task network over O as a primitive task network.

As during the rest of this paper there is always exactly one planning problem under consideration, we do not write out "P = (L, C, O, M, cI , sI )" each time. Thus, whenever any of the symbols L, C, O, M, cI , and sI are used, then they are part of the planning problem P.

After we have defined the basic components of a planning problem, we continue by describing how an initial task network can be transformed into a solution by decomposition and task insertion.

The decomposition of a compound task results in its removal from the task network, followed by an insertion of a copy of the method's task network. The ordering constraints on the removed task are inherited by its replacement tasks (cf. the set ≺X in the next definition).

Definition 3 (Decomposition). A method m = (c, tnm) decomposes a task network tn1 = (T1, ≺1, α1) into a new task network tn2 by replacing task t, written tn1 --→ t,m tn2, if and only if t ∈ T1, α1(t) = c, and there exists a task network tn′ = (T ′ , ≺′ , α′ ) with tn′ ∼= tnm and T ′ ∩ T = ∅, and 3

Given a planning problem P, we write tn1 →∗D tn2, if tn2 can be decomposed from tn1 by an arbitrary number of decompositions using methods from M.

Note that →∗D is reflexive and transitive. Also note that the constructed set of ordering constraints ≺1 ∪≺′ ∪≺X is again a strict partial order.

Other formalizations of hybrid planning complement decomposition with the insertion of both primitive and compound tasks, where compound tasks also show preconditions and effects [Kambhampati et al., 1998; Schattenberg and Biundo, 2006]. Since the result of inserting a compound task can be simulated by inserting a decomposed version directly, we only allow the insertion of primitive tasks.

Definition 4 (Task Insertion). Given a task network tn1 = (T1, ≺1, α1) and a primitive task name o, then a task network tn2 can be obtained from tn1 by insertion of o, if and only if tn2 = (T1 ∪ {t}, ≺1, α1 ∪ {(t, o)}) for some t /∈ T1.

3 For correctness, ordering and labeling of tn2 must be restricted to (T1 \ {t}) ∪ T ′ ; omitted for better readability.

A task network tn2 = (T1,≺2, α1) can be obtained from tn1 by insertion of an ordering constraint (t, t′ ), if and only if t, t′ ∈ T1 and ≺2 is minimal and a strict partial order such that ≺1 ∪ {(t, t′ )} ⊆ ≺2.

Given a planning problem P, we say that tn2 can be obtained from tn1 via task insertion, written tn1 →∗I tn2, if tn2 can be obtained from tn1 by an arbitrary number of insertions of orderings and primitive task names from O.

Note that →∗I is reflexive and transitive.

Definition 5 (Executable Task Network). Given a planning problem P, then a task network tn = (T, ≺, α) is executable in state s ∈ 2L, if and only if it is primitive and there exists a linearization of its tasks t1, . . . , tn that is compatible with ≺ and a sequence of states s0, . . . sn such that s0 = s and prec(α(ti )) ⊆ si-1 and si = (si-1 \del(α(ti )))∪add(α(ti )) for all 1 ≤ i ≤ n. We call sn the state generated by tn.

Definition 6 (Solution). A task network tnS is a solution to a planning problem P, if and only if (1) tnS is executable in sI and (2) tnI →∗D tnS for tnS being an HTN solution to P or (2') there exists a task network tnB such that tnI →∗D tnB →∗I tnS for tnS being a hybrid solution to P. SolHTN(P) and SolHYBRID(P) denote the set of all HTN and hybrid solutions of P, respectively.

For the purpose of this paper, we refer to hybrid solutions as solutions and use the term HTN solutions if necessary.

Note that the presented hybrid formalism is capable of capturing ground classical planning. The only missing piece in comparison to classical planning is the goal condition. This can be simulated by having an initial task network that forces an artificial final task, carrying the goal condition in its precondition as the last task in every solution.

3 On the (Un-)Decidability of HTN Planning

When using the HTN solution criterion, we talk about HTN planning, rather than hybrid planning. Although our formalization of HTN planning is inspired by Erol et al.'s formalization [1994], it is still a simplification of the latter. As we are going to show the decidability of our hybrid planning formalism, the question arises whether this is due to these simplifications or due to the addition of task insertion. To address this question we reproduce Erol et al.'s proof of the undecidability of the plan existence problem for HTN planning [Erol et al., 1996] using our formalization, which requires only minor adaptations. In particular, their proof relies on the usage of truth constraints, which are not available in our formalization. And it turns out that they are not necessary for the proof.

We begin by defining the plan existence problem for HTN planning as the set of planning problems that possess an HTN solution, i.e., PLAN-EXISTENCEHTN := {P | P is a planning problem and SolHTN(P) ̸= ∅}.

Theorem 1. PLAN-EXISTENCEHTN is undecidable

The proof bases on the fact that one can imitate the production rules of context-free grammars (CFGs) by using decomposition methods. We reduce the undecidable question of whether the languages of two CFGs have a non-empty intersection [Hopcroft et al., 2000, page 407] to the plan existence problem. The idea is to start with a task network that contains the start symbols from both grammars in parallel. These are decomposed into words from the respective grammar's language. The pre- and postconditions of the primitive tasks enforce a final plan in which the symbols of both words are mixed together like the teeth of a zipper. This allows us to ensure that the decomposed task network is executable if and only if the produced words are equal.

Proof. Let G1,G2 be two CFGs in Chomsky normal form (each rule has either the form X→Y Z or X→a, where X, Y , and Z are non-terminals and a is a terminal) defined over the same set of terminal symbols Σ. For i ∈ {1, 2}, we denote by Γi the non-terminal symbols of Gi with Si ∈ Γi being the start symbol of Gi. We assume Γ1 ∩ Γ2 = ∅ and define Γ := Γ1 ∪ Γ2. By L(Gi ) we denote the language generated by Gi and assume ε /∈ L(G1) ∪ L(G2). We refer to the grammar rules of Gi by Ri and set R:=R1∪R2. We construct P = (L, C, O, M, cI , sI ) with cI /∈ Γ as follows:

• L := {turnG1 , turnG2 } ∪ Σ
• C := Γ ∪ {cI }, O := {Gai | a ∈ Σ, i ∈ {1, 2}} ∪ {F}
• M

• sI := {turnG1 }

The operator of Ga1 ∈ O is defined as ({turnG1 }, {turnG2 , a}, {turnG1 }) and that of Ga2 ∈ O as ({turnG2 , a}, {turnG1 }, {turnG2 , a}), respectively. This construction ensures strict turn-taking and a matching of the produced words. The operator of F is defined as ({turnG1 }, ∅, ∅); it ensures that the plan finishes with an operator of the second grammar. By construction, there is a word ω ∈ L(G1)∩L(G2) if and only if P has a solution.

We have shown that one can express the CFG intersection problem within our HTN formalization, thus proving the undecidability of our planning formalism without insertion. Please note that a solution to the same planning problem using the hybrid solution criterion can produce solutions which do not correspond to words in the intersection of L(G1) and L(G2) due to the the arbitrary insertion of tasks.

4 On the Decidability of HTN Planning with Task Insertion

We now present our proof that yields an upper bound on the length of shortest solutions to a given planning problem. The following paragraph summarizes its main idea.

Suppose there exists a solution tnS. This solution features a decomposition tnB of the initial task network. In analogy to the pumping lemma for CFGs [Hopcroft et al., 2000, page 274 ff.], we show that there exists also a "short" decomposition tn′B . It is obtained by "pumping-down" tnB, removing all parts that were produced by cycles in the decomposition process. We show that tn′B can be developed into tnB by task insertion, which in turn can be developed into tnS.

Further we provide an upper bound on the number of tasks that must be inserted in order to turn a given task network into a solution, if possible. Applying this result to the short decomposition tn′B , we can prove the existence of a short solution tn′S . So in order to decide whether a solution to a planning problem exists, it suffices to check all task networks of a certain size.

4.1 Representing Task Decomposition

This section transfers the idea of a parse tree from formal grammars to the area of task network decompositions, where we call it a decomposition tree. It is a representation of how the initial compound task can be decomposed into a primitive task network.

Definition 7 (Decomposition Tree). Given a planning problem P, then a decomposition tree g = (T,E,≺, α, β) is a five-tuple with the following properties. (T,E) is a tree with nodes T and directed edges E pointing towards the leafs. There is a strict partial order defined over the nodes, given by ≺. The nodes are labeled with task names by α : T → C∪O. Additionally β : T → M labels inner nodes with methods.

We write T (g) to refer to the tasks of g and ch(g, t) to refer to the direct children of t ∈ T (g) in g.

The following definition states under which circumstances a decomposition tree encodes a decomposition of the initial compound task. Note that a task network resulting from such a decomposition is not necessarily executable.

Definition 8 (Validity of Decomposition Tree). A decomposition tree g = (T,E,≺, α, β) is valid with respect to a planning problem P, if and only if the root node of g is labeled with the initial task name cI and for any inner node t, where (c, tnm) := β(t), the following holds:

1. α(t) = c
2. the task network induced in g by ch(g, t) and tnm are isomorphic, i.e., (ch(g, t), ≺|ch(g,t), α|ch(g,t)) ∼= tnm
3. for all t′ ∈ T and all c′ ∈ ch(g, t) it holds that
4. (a) if (t, t′ ) ∈ ≺ then (c′ , t′ ) ∈ ≺
5. (b) if (t′ , t) ∈ ≺ then (t′ , c′ ) ∈ ≺
6. there are no ordering constraints in ≺ other than those demanded by either 2. or 3.

The first criterion ensures the applicability of the methods, the inner nodes are labeled with; the second criterion ensures that the method's task networks are correctly represented within the decomposition tree; and the third criterion ensures the inheritance of ordering constraints as demanded by Definition 3. Please note that every task is uniquely used by g, as we require (T, E) to be a tree.

Definition 9 (Yield of Decomposition Tree). The yield of a decomposition tree g = (T,E,≺, α, β), written yield(g), is a task network defined as follows. Let T ′ ⊆ T be the set of all leaf nodes of g. Then, yield(g) := (T ′ , α|T ′ , ≺|T ′ ).

Proposition 1. Given a planning problem P, then for any task network tn ∈ TNC∪O the following holds. There exists a valid decomposition tree g with yield(g) = tn, if and only if tnI →∗D tn.

Proof Sketch. For the forward implication, make an induction over the number of inner nodes of g. Note that each inner node corresponds to one method application. As base case, we have the valid decomposition tree without inner nodes, that must consist of only one task that is labeled with cI and hence its yield is the initial task network tnI. For the inductive step, fix a valid decomposition tree g with n + 1 inner nodes. Let t be an inner node, for which all children ch(g, t) are leafs. Then consider the tree g′ which has all children of t removed. Show that g′ is valid based on the validity of g. Then show that yield(g′ ) ---→ t,β(t) yield(g).

For the backward implication, make an induction over the length of the decomposition sequence. The base case holds due to the reflexivity of →∗D . In the inductive step, construct the tree by adding newly inserted tasks as children of the replaced task.

Given a decomposition tree g = (T, E, ≺, α, β) and a node t ∈ T , we define the subtree of g induced by t, written g[t], as g[t] := (T ′ , E′ , ≺|T ′ , α|T ′ , β|T ′), where (T ′ ,E′ ) is the subtree in (T, E) that is rooted at t. We now define the operation of replacing a subtree by another subtree.

The result of this operation as defined by us is only reasonable for our particular use-case. A general subtree substitution operation would have to create an isomorphic copy of the inserted subtrees, which we have omitted for simplicity.

Definition 10 (Subtree Substitution). Let g = (T,E,≺, α, β) be a decomposition tree and ti, tj ∈ T be two nodes of g. If ti is the root node of g, then we define the result of the subtree substitution on g that substitutes ti by tj, written g[ti ← tj ], as g[ti ← tj ] := g[tj ]; otherwise, g[ti ← tj ] := (T ′ , E′ , ≺|T ′ , α|T ′ , β|T ′ ) with

• T ′ := (T \ T (g[ti ])) ∪ T (g[tj ])
• E′ := E|T ′ ∪ {(p, tj )}, where p is the parent node of ti

The following proposition states that the result of a subtree substitution still describes decompositions if applied under the right circumstances. Also refer to Figure 1 for an illustration of the operation.

Proposition 2. Given a valid decomposition tree g = (T, E, ≺, α, β) with respect to a planning problem P and two nodes ti ∈ T, tj ∈ T (g[ti ]) with α(ti ) = α(tj ), then g[ti ← tj ] is also a valid decomposition tree with respect to P.

Proof Sketch. We have to show that g′ := g[ti ← tj ] = (T ′ , E′ , ≺′ , α′ , β′ ) is still a tree, its root node is labeled with cI, and that ≺ is minimal such that the first three criteria of Definition 8 hold for all inner nodes of g′ . For the remainder, let p ∈ T be such that (p, ti ) ∈ E.

For the special case of the subtree substitution, in which ti is the root node of g, there is nothing to show, since g′ = g[tj ] is clearly a valid decomposition tree with respect to P. Thus, let ti be different from the root node. It is also easy to see that g′ is a tree and its root node is labeled with cI .

Criterion 1 holds for all inner nodes of g′ as both α′ and β′ are defined on the same nodes and α′ ⊆ α and β′ ⊆ β.

For criterion 2, we fix some inner node t ∈ T ′ and consider the two cases that either t ̸= p or t = p. The case in which t ̸= p is straight forward as the task network induced by ch(g, t) in g is the same as the one induced by ch(g′ , t) in g′ . If t = p, the induced task network in g′ is still isomorphic to the one in g, because we substituted ti by tj and α(ti ) = α(tj ).

To show criterion 3 (considering only 3a, as 3b is analogous), take some ordering constraint (t, t′ ) in ≺′ . It must also occur in ≺ and thus (c′ , t′ ) ∈ ≺ for all children c′ of t. Show (c′ , t′ ) ∈ ≺′ if c′ ̸= ti and (tj, t′ ) ∈ ≺′ , otherwise.

Proving the minimality of ≺′ is the most difficult part. We have to show for each (t1, t2) ∈ ≺′ that it is required by criterion 2 or 3. Consider the cases that (t1, t2) ∈ ≺ is originally produced by criterion 2 (case I) or 3 (case II).

For case I, show that as a consequence (t1, t2) is required in ≺′ because of criterion 2 with special treatment for t1, t2 ∈ ch(g′ , p). Intuitively all decompositions in g′ have counterparts in g and they produce the same ordering in both trees.

For proving case II (again, we consider only 3a), let (c′ , t′ ) := (t1, t2). We know that there exists a node t ∈ T with (t, c′ ) ∈ E and (t, t′ ) ∈ ≺, as this is the antecedent of criterion 3a. Now consider the cases of t ∈ T ′ (case IIa) and t ̸∈ T ′ (case IIb). The proof for case IIa is straight forward. For case IIb, we can conclude that c′ = tj since tj is the only node in g′ that has lost its parent in g. Show that (p, t′ ) ∈ ≺′ and use this as premise to apply criterion 3a in order to show that (c′ , t′ ) must be in ≺′ .

4.2 Bounding Solution Sizes by Eliminating Cycles

In order to prove our main theorem, which establishes a size limit on the smallest solution of a planning problem, we first need to prove three lemmas. The first one allows us to shorten a decomposition sequence that contains a cycle over compound task names. When doing so, we remain able to recreate via task insertion what has been removed. This result is used by the second lemma to give an upper bound on the size of shortest task networks originated from decomposition that can possibly be developed to a solution. Then the third lemma allows us to find a limit to the number of tasks that have to be inserted in order to turn a given task network into a solution.

The proof of the first lemma uses the idea of the proof of the pumping lemma for CFGs to claim the existence of a shorter version of a given decomposition.

Lemma 1. Given a planning problem P and a primitive task network tn with valid decomposition tree g, for which there exists a path t1, . . . , tn in g with α(ti ) = α(tj ) for some i and j with i < j ≤ n (the path contains a cycle). Then it holds that tnI →∗D yield(g[ti ←tj ]) →∗I tn.

Proof. Fix the premises from the lemma. We notice that the conditions for applying Proposition 2 are given. Thus, we can state that g[ti ← tj ] is valid. Therefore it generates a task network, name it tn′ = (T ′ , ≺′ , α′ ), that can be obtained from tnI by decomposition. It remains to show that tn′ →∗I tn. Since tn′ consists of the leafs of g[ti ← tj ] and tn = (T,≺, α) is induced by the leafs of g, and the substitution only takes away nodes and ordering constraints from g and does not create new leaf nodes, clearly T ′ ⊆ T and ≺′ ⊆ ≺ and also α|T ′ = α′ . We can thus obtain tn from tn′ by adding additional tasks and ordering constraints.

By using this result repeatedly, we are now able to remove all cycles from a decomposition tree. This makes it possible to formulate an upper bound on the size of the tree and thus of the generated task network.

Lemma 2. Given a planning problem P, then for every task network tn with tnI →∗D tn, there exists a task network tn′ with tnI →∗D tn′ →∗I tn and |T (tn′ )| ≤ b|C| , where b is the number of tasks inside the largest task network of the methods from M.

Proof. Fix a planning problem P and a task network tn with tnI →∗D tn. Fix a decomposition tree g of tn. If g contains a cycle on one of its paths (i.e., two nodes labeled with the same compound task symbol), then Lemma 1 allows us to remove it, obtaining a new decomposition tree g1 and corresponding task network tn1 = yield(g1) with tnI →∗D tn1 →∗I tn.

As long as the new decomposition tree still contains a cycle, we can repeat the procedure. By doing so, we obtain a sequence of decomposition trees g1, . . . , gn and corresponding task networks tn1, . . . , tnn. The last decomposition tree gn does not contain a cycle on any of its paths. The sequence is finite, since every subtree substitution removes at least one task, thus n ≤ |T (g)|. For the sequence of task networks, it holds that tnI →∗D tnn →∗I tnn-1 →∗I . . . →∗I tn1 →∗I tn and by the transitivity of task insertion we get tnI →∗D tnn →∗I tn. We choose tnn as the tn′ from the lemma. It remains to show the size bound |T (tnn )| ≤ b|C| .

The size of tnn is limited because its decomposition tree gn contains no cycle on any of its paths and is thus bounded in depth by |C|. Taking the maximal branching factor b of g, we get an upper bound of b|C| of the number of leaf nodes of tnn and thus on the number of tasks of tnn = yield(g).

While the first two lemmas have somehow tamed the decomposition aspect of the solution criteria, we still need to care for executability. The idea is to take the tasks that have been introduced by decomposition and connect them in an executable way by using task insertion. Thus we obtain one classical planning problem for each task inside the decomposed task network.

Proposition 3. Let P be a planning problem and s, s′ ∈ 2L. If there exists a task network tn which is executable in s and generates s′ , then there is also a task network tn′ which is executable in s, generates s′ , and |T (tn′ )| ≤ 2|L| .

Proof. As the size of the state space induced by P is 2|L| , each task network longer than this value must traverse at least one state twice and hence must contain a cycle in the task sequence which can simply be omitted.

Lemma 3. Given a planning problem P and a task network tn, that can be developed into a solution tnS ∈ SolHYBRID(P) via task insertion tn →∗I tnS, then there exists a solution tn′S ∈ SolHYBRID(P) with |T (tn′S )| ≤ |T (tn)| (2|L| + 1).

Proof. Since tnS is a solution to P, there exists an executable linearization LinS of its tasks. Let Lin := t1, t2, . . . , tn be the tasks of tn ordered as they appear inside LinS. Let si and s′i be the states before and after the execution of ti when applying LinS to the initial state sI .

In order to develop Lin into an executable task sequence, we need to find the n -1 task networks tni that transform s′i into si+1 for 0 < i < n - 1 and the task network tn0 that transforms sI into s1. Proposition 3 tells us that we can find such task networks containing at most 2|L| many tasks each, if these problems are solvable at all. And we can use LinS as a witness, that they are solvable.

Putting it all together, we can construct a solution task network illustrated by the sequence tn0t1tn1t2 . . . tnn-1tn. This task network contains at most n2|L| + n many tasks and can be constructed from tn via task insertion.

Theorem 2. Given a planning problem P with SolHYBRID(P) ̸= ∅, then there exists a solution tn∗S ∈ SolHYBRID(P) with |T (tn∗S )| ≤ b|C| (2|L| + 1), where b is the number of tasks inside the largest task network of the methods fromM.

Proof. A graphical presentation of this proof is given in Figure 2. Fix a solution tnS ∈ SolHYBRID(P). There exists a task network tnB with tnI →∗D tnB and tnB →∗I tnS because of the solution criteria. This task network marks the boundary between the decomposition part and the insertion part of the planning process. By Lemma 2 there exists a (not necessarily different) task network tn′B with tnI →∗D tn′B →∗I tnB and |T (tn′B )| ≤ b|C| . Because of transitivity of task insertion, from tn′B →∗I tnB →∗I tnS, it follows that tn′B →∗I tnS .

Using Lemma 3, from tn′B →∗I tnS, it follows that there exists a solution tn∗S with |T (tn∗S )| ≤ |T (tn′B )| (2|L| + 1) and thus |T (tn∗S )| ≤ b|C| (2|L| + 1).

4.3 Complexity Results

In this section we will put the previous results to use in order to obtain an upper complexity bound of EXPSPACE for the plan existence problem for propositional, hybrid planning.

First we are going to define two decision problems. As usual, these are represented by subsets of words over a given alphabet Σ. We do not deal with the problem of encoding the syntactical structures, such as task networks or problems, into words over Σ. It is assumed that this process and the rejection of malformed inputs is feasible and does not add to the complexity of the problem. We denote the length of the description of an object X in Σ by |X|Σ. As a remark about task networks, note that the description of a task network tn is bounded by O(|T (tn)|2 ) because of the possible number of ordering constraints.

We define the decision problem SOLUTIONHYBRID as all tuples of a planning problem and a corresponding hybrid solution, i.e., SOLUTIONHYBRID := {(P, tn) | P is a planning problem and tn ∈ SolHYBRID(P)}. Then we can state the following proposition.

Proposition 4. SOLUTIONHYBRID ∈ PSPACE.

Proof. Take as input the tuple (P, tn). Since we demand that a task network may not be empty, the application of a decomposition to a task network never decreases its number of tasks |T (tn)|. This means that during a decomposition tn1 →∗D tn2, the intermediate task networks never exceed pol(|tn2|Σ). Obviously the same holds for a sequence of insertions. We can thus state the following nondeterministic algorithm, that runs in polynomial space in the size of |(P, tn)|Σ and thus in PSPACE. (1) Check if tn is executable in sI; reject if not. (2) The following works in-place: non-deterministically decompose tnI into a primitive task network tn′ with size of at most pol(|tn|Σ); then, non-deterministically insert tasks and ordering constraints not violating this size bound; check if tn was produced; accept if so, otherwise reject.

We define the plan existence problem for hybrid planning as the set of planning problems that possess a hybrid solution, i.e., PLAN-EXISTENCEHYBRID := {P | P is a planning problem and SolHYBRID(P) ̸= ∅}.

Corollary 1. PLAN-EXISTENCEHYBRID ∈ EXPSPACE.

Proof. Let the input be P and let n = |P|Σ be the length of this input. Theorem 2 states that there exists a solution tn∗S with |T (tn∗S )| ≤ b|C| (2|L| + 1), if and only if P has a solution at all. From the bound on the number of tasks and by substituting b, |C|, and |L| by n, we can estimate |tn∗S |Σ ≤ pol(nn (2n + 1)) . Thus, |tn∗S |Σ ≤ 2pol(n) and the following non-deterministic algorithm runs in exponential space. (1) Non-deterministically guess a task network tn with |T (tn)| ≤ b|C| (2|L| + 1). (2) Check whether (P, tn) ∈ SOLUTIONHYBRID using only space polynomial in |(P, tn)|Σ ≤ n + 2pol(n) ; accept if the check returns true, otherwise reject. The given algorithm decides PLAN-EXISTENCEHYBRID using only space exponential in the input length.

And as a direct consequence, we conclude:

Corollary 2. PLAN-EXISTENCEHYBRID is decidable.

5 Conclusion and Discussion

We have formalized a simplified, propositional version of HTN planning with task insertion (or hybrid planning) that allows for the insertion of tasks and ordering constraints. We have established EXPSPACE as an upper complexity bound of the corresponding plan existence problem. We have also shown that plan existence is undecidable given our formalization without insertion. We conclude that the possibility to insert tasks as an addition to task decomposition greatly reduces the computational complexity of HTN planning.

A direct application of the result to the established HTN formalism by Erol et al. [1994] might not be possible, since undecidability could have been "reintroduced" by a feature that is not captured by us, like the formulation of truth constraints. But even then we would have eliminated at least one source of undecidability.

Schattenberg and Biundo [2006] solve hybrid planning problems close to the ones defined in this paper. However, the initial task network and the decomposition methods may contain causal links, thereby further restricting the set of possible solutions. Thus, it is not clear, whether our decidability result also applies to their formalization.

However, our result seems to apply to the problems solved by the Duet planning system [Gerevini et al., 2008]. It processes problems as defined in this paper, but uses a lifted state representation and features preconditions for decomposition methods. Duet could be extended to prune plans that exceed a certain size and achieve guaranteed termination without sacrificing completeness. Note that the complexity result is not directly transferable, since the step from a propositional state representation to a lifted one will most likely result in an exponential increase in complexity.

Since the focus of the paper lies on showing decidability, we did not attempt to provide tight complexity bounds for the plan existence problem. We have shown EXPSPACE membership and can state PSPACE-hard as a trivial lower bound. This is the case, because our formalization captures ground, classical planning with negative effects and operators given in the input, which has been proved to be PSPACE-complete.

Acknowledgements

We want to thank our reviewers for their insightful questions and suggestions that helped us improving this paper.

This work is done within the Transregional Collaborative Research Centre SFB/TRR 62 "Companion-Technology for Cognitive Technical Systems" funded by the German Research Foundation (DFG).