A Structural Complexity Analysis of Hierarchical Task Network Planning

1 Introduction

Automated Planning is a core research topic whose goal is to devise computational methods capable of finding solutions to prominent planning tasks. In this work, we consider automated planning in the context of Hierarchical Task Networks (HTNs), which have received significant attention in the artificial intelligence research community. HTNs are capable of incorporating the compound, hierarchical structure of realworld tasks, as opposed to the fine-grained view of classical planning that operates directly on the state space of the system under consideration, and are one of the best-established planning formalisms in the literature [Tsuneto et al., 1996; Li et al., 2009; Sohrabi et al., 2009; Geier and Bercher, 2011; Alford et al., 2015b; Xiao et al., 2017; Behnke et al., 2019; H¨oller et al., 2019; Lin and Bercher, 2023].

On a high level, HTNs can be informally described and illustrated as follows: at the top level of the task hierarchy is a set of tasks that is to be executed in a (partially specified) order. For instance, the task of going to work may be decomposed into three subtasks: leaving the house, going the actual distance, and getting set up at the office. Now, each of these tasks can in turn be decomposed into a set of smaller tasks, like climbing the stairs or taking a bus, which again can be decomposed, and so forth. This continues until we reach an elementary level of tasks that are no longer decomposable, which correspond to single executable actions.

The crucial feature of the model is that it separates the userfacing description of a task (what we want to do) from its internal implementation (how to do it). For instance, leaving the house needs to be done before going the actual distance, regardless of how it is done. However, in an HTN, we may have several options of how to decompose this task: the agent can, e.g., either climb the stairs or take the elevator.

Perhaps the most natural problem associated with HTNs is PLAN VERIFICATION: can the tasks in a given network be decomposed and then ordered to match a given, executable sequence of actions? A second fundamental problem is PLAN EXISTENCE: can the tasks in a given network be decomposed and then ordered in any way that yields an executable sequence of actions? The literature has investigated the complexity of several variants of the aforementioned problems [Erol et al., 1996; Geier and Bercher, 2011; Alford et al., 2015b; Behnke et al., 2015; Lin and Bercher, 2023]. Moreover, we also consider the question of whether a specified target state can be reached, formalized as the STATE REACHABILITY problem. This is the typical goal in classical planning [Fikes and Nilsson, 1971; Chapman, 1987; B¨ackstr¨om and Nebel, 1995], and has also been considered in the HTN setting [H¨oller and Bercher, 2021; Olz et al., 2021].

It is well-established that problems on HTNs such as those listed above remain computationally intractable even in severely restricted settings. These results usually depend on restricting the decompositions, e.g., requiring acyclicity [Alford et al., 2015a; Chen and Bercher, 2021], restricting the impact of actions on the state space (e.g., delete-relaxed HTN planning) [Alford et al., 2014; H¨oller et al., 2020], or by allowing the insertion of tasks at arbitrary positions [Geier and Bercher, 2011; Alford et al., 2015b].

In this article, we take a different approach and instead focus on structural restrictions of the task network. While there are some complexity results known for the extreme cases of a total ordering or no ordering of the tasks [Geier and Bercher, 2011; Alford et al., 2014; Behnke and Speck, 2021], other restrictions received little to no attention so far. Building on these first results, we identify interesting and natural special cases where pockets of polynomial-time solvability show themselves. Moreover, we prove that these pockets give rise to a surprisingly rich complexity-theoretic landscape.

Our Contributions. We first consider primitive task networks, i.e., HTNs in which there are no compound tasks.

While this may seem restrictive, it is a natural place to start from a complexity-theoretic perspective: all three of the considered problems remain NP-hard on primitive task networks. In fact, PLAN VERIFICATION is known to be NP-hard even if the network forms a collection of disjoint stars [Lin and Bercher, 2023]. Moreover, unlike PLAN VERIFICATION, the latter two problems remain NP-hard even on trivial (in particular, edgeless) networks when the state space is not of fixed size [Bylander, 1994; Erol et al., 1996]. Thus, in line with previous related works, we henceforth consider PLAN EXISTENCE and STATE REACHABILITY exclusively in the setting of constant-sized state spaces [Kronegger et al., 2013; B¨ackstr¨om et al., 2015]. Even in this setting, we establish the NP-hardness of the three considered problems on networks consisting of a collection of independent chains.

While these initial results may seem discouraging, it turns out that all three problems are polynomial-time solvable on networks which are chains (i.e., totally-ordered networks) [Erol et al., 1996; Behnke et al., 2015] or antichains (Theorems 3 and 4). We generalize and unify these tractability results by showing that all three considered problems are polynomial-time solvable on networks of bounded "generalized partial order width", that is, the partial order width of the network when ignoring isolated elements (Theorems 5 and 6).

Building on the above results for the primitive case, in the second part of the paper, we establish an algorithmic metatheorem that allows us to precisely describe the conditions under which polynomial-time tractability for primitive task networks can be lifted to the compound case (Theorem 8). Crucially, we prove that this result is tight in the sense that all of the required conditions are necessary (Theorem 9).

In the final part of the paper, we push beyond classical complexity and analyze the considered problems from the perspective of the more fine-grained parameterized complexity paradigm [Cygan et al., 2015]. There, one analyzes problems not only w.r.t. the input size n, but also w.r.t. a specified parameter k ∈ N, where the aim is to obtain algorithms which run in time at most f(k)·nO(1) for some computable function f (so-called fixed-parameter algorithms); problems admitting such algorithms are called fixed-parameter tractable (FPT).

The natural question from the parameterized perspective is whether the aforementioned tractability results for HTNs with constant-sized structural measures (Theorems 5 and 6) can be lifted to fixed-parameter tractability when parameterized by the same measures. While analogous questions have been thoroughly explored-and often answered in the affirmative-in many other areas of artificial intelligence [Eiben et al., 2021; Ganian and Korchemna, 2021; Froese et al., 2022; Heeger et al., 2023], here we prove that the generalized partial order width does not yield fixedparameter tractability for any of our problems on primitive task networks, under well-established complexity assumptions. Moreover, the aforementioned hardness of the problems on forests of stars already rules out fixed-parameter tractability for essentially all standard structural graph parameters, except for the vertex cover number (vcn) [Blazej et al., 2023; Bodlaender et al., 2023; Chalopin et al., 2024]. We complement these lower bounds by designing highly nontrivial fixed-parameter algorithms for all three considered problems on primitive task networks w.r.t. the vertex cover number of the network. For compound HTNs, we then adapt our general algorithmic meta-theorem for polynomial-time solvability to the fixed-parameter paradigm (Theorem 12), allowing us to also extend these results to the non-primitive setting. See Fig. 1 for a schematic overview of our results.

Related Work. HTN planning has been extensively studied in artificial intelligence research and has applications in areas such as healthcare [Gonz´alez-Ferrer et al., 2013b], business processes [Gonz´alez-Ferrer et al., 2013a], humanrobot interaction [Hayes and Scassellati, 2016], emergency response [Liu et al., 2016; Zhao et al., 2017], and visualization [Padia et al., 2019]. For an overview of the current state of HTN planning, see the works by Bercher, Alford, and Hoeller [2019] and Georgievski and Aiello [2015].

Questions on the complexity and even computability of many tasks associated with HTNs have been treated in the literature [Erol et al., 1994; Erol et al., 1996; Geier and Bercher, 2011; Alford et al., 2015a; Olz et al., 2021; Lin and Bercher, 2023; Lin et al., 2024a; Lin et al., 2024b]. Albeit carried out in a different context, the work of Kronegger, Pfandler, and Pichler [2013] on propositional STRIPS with negation (PSN) studies a problem (k-PSN) which is related to STATE REACHABILITY. The main difference is that while PSN includes a broader definition of actions, it does not consider any primitive or hierarchical network structure. Finally, the computational complexity of planning has also been studied in settings beyond HTNs [Bylander, 1994; B¨ackstr¨om et al., 2012; B¨ackstr¨om et al., 2013; B¨ackstr¨om et al., 2015].

2 Preliminaries

For n ∈ N, let [n] = {1, . . . , n}. We use standard graph terminology [Diestel, 2012]. The partial order width w of a partial order ≲ over a set S is the maximum number of pairwise-disjoint maximal chains contained in ≲ or, equivalently, the size of its largest antichain. An element s ∈ S is isolated under ≲ if it is incomparable to all other elements of S. We define the generalized partial order width of ≲ as the partial order width of ≲ after removing isolated elements from S.

Hierarchical Task Networks. Our formalization of HTNs follows the terminology employed in recent works [Olz et al., 2021; Lin and Bercher, 2023]. The domain of a planning problem is a tuple (F,A, C, δ,M), where F is a finite set of propositions, A is a set of actions (or primitive task names), and C is a set of compound task names such that A ∩ C = ∅. The function δ : A → 2F ×2F ×2F maps each action to a set prec(a) of preconditions, a set del(a) of propositions to be removed, and a set add(a) of propositions to be added to the current state. Here, a state is a subset of the propositions in F . An action a is executable in a state s ⊆ F if prec(a) ⊆ s. If executed, it changes the state s to s′ = (s \ del(a)) ∪ add(a). A plan is a sequence of actions and is executable in a state s if its actions can be executed consecutively starting from s. Lastly, M represents the decomposition methods. M is a mapping that assigns to each c ∈ C a set M(c) of task networks (defined below) which c can be decomposed into.

A task network in such a domain is a tuple (T, ≺+, α) consisting of a set T of task identifiers (or simply tasks) with a partial order ≺+ ⊆ T × T and a function α: T → A ∪ C.

The usual representation of a task network is its cover graph D≺ = (T,≺), where ≺ is the cover of ≺+ (in particular, (a, b) ∈≺ if and only if a ≺+ b and there is no c such that a ≺+ c ≺+ b). We denote the underlying undirected graph by G≺. We include two examples to illustrate these definitions. In Fig. 2, the high-level interplay of the components of the formalism is shown, without an explicit state transition function. The latter is shown in a smaller example in Fig. 3. A subset T ′ of tasks is a chain if ≺+ defines a total order on T ′ , and an antichain if all of its tasks are pairwise incomparable. A task t is primitive if α(t) ∈ A, and compound otherwise. A task network is primitive if it contains no compound tasks. For a primitive task network, a total order ¯ t on T such that t ≺ t′ implies that t precedes t′ in ¯ t is called a linearization. Enumerating the actions α(t) in order of ¯ t defines an action sequence α(¯ t). Non-primitive task networks can be decomposed into primitive ones via the methods in M; decomposing a task t into a subnetwork tnm ∈ M(α(t)) means replacing t by tnm and modifying ≺ such that for all tasks t′ in tnm and t1 ∈ T -{t}, we have t′ ≺ t1 or t1 ≺ t′ if and only if t ≺ t1 or t1 ≺ t were true originally, respectively.

The input of an HTN problem contains a domain D = (F, A, C, δ,M), an initial task network tn in that domain, and an initial state s0 ⊆ F. 1 In a generalization of the literature, we consider a primitive task network tn′ = (T ′ ,≺+′ , α′ ) to be a solution to a triple (D, tn, s0) if tn′ has a linearization ¯ t such that α′ (¯ t) is executable in s0 and tn decomposes into a primitive task network (T ∗ ,≺+∗ , α∗ ) with T ′ ⊆ T ∗ , for each (t, t′ ) ∈ ≺+∗ with t′ ∈ T ′ we have that t ∈ T ′ and (t, t′ ) ∈ ≺+′ , and α′ (t) = α∗ (t) for all t ∈ T ′ . The literature usually considers the case where tn can be decomposed into tn′ , that is, T ∗ = T ′ , in which we call tn′ a full solution. Intuitively, non-full solutions respect δ and ≺+, but do not need to execute all tasks. We now define our problems of interest.

PLAN VERIFICATION

Input: A task network tn = (T,≺+, α) in a domain D = (F,A, C, δ,M), an initial state s0 ⊆ F, and a plan p over A.

Question: Is there a full solution to (D, tn, s0) with a linearization ¯ t such that α(¯ t) = p?

PLAN EXISTENCE

Input: A task network tn in a domain D = (F, A, C, δ, M) and an initial state s0 ⊆ F .

Question: Is there a full solution to (D, tn, s0)?

In addition to the problems mentioned in the introduction, we also define the corresponding problem of constructing a plan executing (at least) a specified set of actions. This ACTION EXECUTABILITY problem is closely related to PLAN EXISTENCE and, in fact, all results that we prove for one of the problems will also hold for the other.

1 Some works refer to the triple (D, tn, s0) as an HTN problem, while we use that term for the considered algorithmic problems.

ACTION EXECUTABILITY

Input: A task network tn in a domain D = (F,A, C, δ,M), an initial state s0 ⊆ F, and a multiset S of actions in A.

Question: Is there a solution to (D, tn, s0) with a linearization ¯ t such that α(¯ t) covers S?

ACTION EXECUTABILITY can be seen as a generalization of PLAN EXISTENCE: any PLAN EXISTENCE instance can be easily reduced to ACTION EXECUTABILITY, e.g., by adding a new task t with new action a, letting S = {a}, and adapting ≺+ or δ to ensure that all other tasks are executed before t. Such direct reductions can be used to transfer algorithmic and hardness results in the respective directions; in our setting, we establish all of our hardness results for the "simpler" PLAN EXISTENCE, while all of our algorithms can deal with the "harder" ACTION EXECUTABILITY.

Finally, as motivated in the introduction, we consider the following natural problem on HTNs.

STATE REACHABILITY

Input: A task network tn in a domain D = (F,A, C, δ,M), an initial state s0 ⊆ F, and a target state sg ⊆ F.

Question: Is there a solution to (D, tn, s0) with a linearization yielding a state s ⊇ sg?

While the considered problems are stated in their decision variants for complexity-theoretic purposes, all of our obtained algorithms are constructive and can output a solution and a corresponding linearization as a witness. Further, for primitive networks, all the problems are clearly in NP. In some results, we use the state transition graph, i.e., the multigraph whose vertices are the states reachable from the initial state s0 by any sequence of actions, and a transition from one state to another via an action a is represented by an arc labeled a.

3 Primitive Task Networks

Our first set of results focuses on the classical complexity of the targeted problems on primitive task networks. Before proceeding with our analysis, we make a general observation about the state space in our instances.

The State Space. As a basic precondition for solving our problems on more sophisticated task networks, we need to ensure tractability on trivial primitive task networks where ≺+= ∅ (antichains). Unfortunately, all but the first of our problems of interest are intractable even on these degenerate networks, as the hardness of PLAN EXISTENCE in STRIPS planning [Bylander, 1994] transfers to HTN planning by an HTN-to-STRIPS translation [Alford et al., 2016]; see also the related work of Nebel and B¨ackstr¨om [1994] and Erol et al. [1996]. As discussed above, the hardness of ACTION EXECUTABILITY follows from the hardness of PLAN EXISTENCE. The hardness of STATE REACHABILITY follows as well: there is a trivial reduction from PLAN EXISTENCE that adds a special task tg and adapts all actions and sg such that sg is only reachable if tg is executed, and tg is only executable after all other tasks have been executed.

A requirement for the above reductions is that the state space (i.e., the number of states in the state transition graph) can be large, and in particular not bounded by any constant. Hence, we hereinafter analyze the affected problems (STATE REACHABILITY, PLAN EXISTENCE, and ACTION EXECUTABILITY) in the bounded state-space setting. The drop in complexity from PSPACE with unbounded state sets (see [Bylander, 1994]), to NP in the bounded state space setting is abstractly explained as follows: unbounded state sets capture the full tape contents of a non-deterministic Turing machine (NTM) during execution, while bounded state sets can only model the fixed-size set of states that define an NTM.

The Intractability of Tree-likeHTNs. We beginwith a series of lower bounds which rule out polynomial-time algorithms even for simple "tree-like" networks (unless P = NP). PLAN VERIFICATION is known to be NP-complete on primitive networks such that D≺ consists of disjoint stars, even when prec(a) = del(a) = add(a) = ∅ for all actions a ∈ A [Lin and Bercher, 2023, Theorem 3]. As our first result of this section, we show that our problems remain intractable even if ≺+ describes a set of total orders that are independent from one another (i.e., D≺ is a disjoint union of paths). We reduce from SHUFFLE PRODUCT, which asks, given words u, c1, . . . , cw over an alphabet Σ, to decide if u can be generated by interlacing c1, . . . , cw while preserving the order of the letters as they appear in each ci, i ∈ [w]. This problem is NP-hard even if |Σ| = 2 [Warmuth and Haussler, 1984].

Theorem 1. PLAN VERIFICATION is NP-complete, even when restricted to primitive task networks such that ≺+ is a collection of chains, |A| = 2, and prec(a) = del(a) = add(a) = ∅ for all actions a ∈ A.

Proof. We reduce from SHUFFLE PRODUCT with the alphabet Σ = {a, b}. Let A = Σ. Construct a task for each letter in the words c1, . . . , cw; let the task ti,j refer to the j th letter of the word ci, i ∈ [w]. Let ≺+ be such that the tasks for each word form a chain in the respective order, i.e., let ≺ consist of the edges (ti,j, ti,j+1), for all i ∈ [w] and j ∈ [|ci| - 1]. Then, ≺+ partitions T into w chains (LEFT side of Fig. 4). Now, set α(ti,j) to the action representing the j th letter of ci. Let the input plan p be such that p = u.

The correctness of the reduction follows since verifying whether the tasks can be arranged to match the input plan corresponds to interlacing the words to form u.

Theorem 2. STATE REACHABILITY and PLAN EXISTENCE are NP-complete, even when restricted to primitive task networks such that ≺+ is a collection of chains, |A| ≤ 5, and the state transition graph has at most 4 states.

Proof Sketch. We use a similar reduction as for Theorem 1, (see Fig. 4), but encode u as a separate chain and adapt the actions so that executable plans must alternate between LEFT and RIGHT tasks, and executed RIGHT tasks must be preceded by executed LEFT tasks of the same color.

Chains and Antichains. Given the seemingly discouraging lower bounds obtained so far, one might wonder whether there are natural structural restrictions on the network which can be exploited to obtain polynomial-time algorithms. Here, we chart the route towards identifying these by first establishing the tractability of the considered problems (under the state-space restrictions justified in Sec. 3) in the extremes of ≺+, where T is a chain (total order) or antichain (≺+ = ∅).

When T is a primitive chain, it is easy to observe that all of our problems are polynomial-time solvable (see, e.g., [Erol et al., 1996; Behnke et al., 2015]). PLAN VERIFICATION restricted to primitive antichains is also trivial, as it suffices to check whether the plan is executable in the initial state and the multiset of actions defined by the tasks in the network matches the actions in the plan. Handling antichains for the other problems requires more effort, and no tractability results exist that only assume the state space to be bounded.

Theorem 3. STATE REACHABILITY is polynomial-time solvable on primitive antichain task networks with constantly many states in the state transition graph.

Proof. Let I be an instance of STATE REACHABILITY, k the number of states, s0 the initial state, and sg the target state. We first compute the state transition graph G of I in quadratic time. In G, if there are more than k edges between any pair of states, select any k of them and discard the rest. Then, consider all simple edge paths from s0 to sg. Note that there are O(2k · kk-1 ) such paths, as there are O(2k ) simple vertex paths, each of length at most k - 1, and each step might choose between up to k different edges. For each simple edge path, check whether there is any action that is used more times in the path than there are tasks of that action in T. If there exists a simple edge path for which the number of required tasks does not exceed the number of available ones, then give a positive answer, and otherwise reject.

If such a path is found, the instance is indeed a yes-instance as there is a task sequence that results in a path to sg in G. For the other direction, let there be a task sequence that leads to the state sg. Consider the subsequence obtained by exhaustively removing cycles in G from that sequence. The resulting task sequence describes a simple edge path from s0 to sg. It might employ edges that were discarded from G by the algorithm. However, in this case there are k other edges connecting the respective states in G. Thus, one can choose to replace deleted edges by existing ones in such a way that each replacement action occurs at most once in the path, which ensures that there are enough tasks to actually walk this path. Hence, there is a path from s0 to sg that only uses edges that are present in G after the deletion, and for which the number of required tasks does not exceed the number of available ones. As the algorithm will find this path, it will correctly give a positive output. Finally, the overall running time can be upper-bounded by O(|I|2 + |A|k + |T | + 2k · kk ).

To obtain an analogous result for ACTION EXECUTABILITY, a more sophisticated approach is necessary, since a solution may be required to visit a state multiple times.

Theorem 4. ACTION EXECUTABILITY is polynomial-time solvable on primitive antichain task networks with constantly many states in the state transition graph.

Proof Sketch. ACTION EXECUTABILITY on primitive antichains can be expressed by deciding whether there is a walk in the state transition graph such that each action is used in the path at least as many times as required by S and at most as many times as there are respective tasks in T. We bound the number of actions by a function of the number k = O(1) of states by identifying equivalent actions that have the same impact on the states in the state transition graph. Now we enumerate all possible types of walks in constant time by branching on a "main-path" from s0 to any s ⊇ sg and which sets of simple cycles the walk uses. For all branches where the main-path and all selected cycles are connected, it remains to determine the number of times each cycle is traversed. We do so by solving an Integer Linear Program (ILP) where there are variables stating the number of traversals of each of the O(1) selected cycles, and a constraint for each action requiring that the number of times it is executed (as defined by the variables and the number of times it occurs in the main-path and the respective cycles) is admissible w.r.t. S and T .

Generalized Partial Order Width. We have seen that the considered problems are polynomial-time solvable on primitive chains and antichains. Here, we unify and extend these results by establishing tractability for primitive HTNs of constant generalized partial order width (chains and antichains have generalized partial order width 1 and 0, respectively).

Theorem 5. PLAN VERIFICATION is polynomial-time solvable on primitive task networks of constant generalized partial order width.

Proof Sketch. We use dynamic programming to decide, for each index i in the plan and all combinations of indices h1, . . . , hw in the w = O(1) many chains partitioning the non-isolated tasks, whether there is a solution matching the first i actions in the plan and using exactly the first h1, . . . , hw tasks of each chain, respectively. Clearly, this is possible for i = h1 = . . . = hw = 0 and we iteratively add a next admissable task from a chain or the isolated tasks.

Theorem 6. STATE REACHABILITY and ACTION EXECUTABILITY are polynomial-time solvable on primitive task networks with constantly many states in the state transition graph and constant generalized partial order width.

Proof Sketch. We note that the number |E| of action equivalence classes that have the same impact on the state graph is constant. We use this in a dynamic programming approach similar to the one used for Theorem 5. Here, we decide for each state s, indices hj , j ∈ [w] in the w chains, and numbers of actions ri, i ∈ [|E|]| in the equivalence classes, whether there is a solution with a linearization that uses exactly the first hj tasks of each chain cj, results in state s, and uses exactly ri tasks of each action equivalence class ei. We initialize all variables to be FALSE except for the one with s = s0 and all hj and ri are 0. When a variable is set to TRUE (including the initial one), for each next index in a chain and each equivalence class for which the hj and ri imply that there is still an unused isolated task, we test whether this task can be appended to a sequence witnessing the TRUE variable. If so, the corresponding variable is set to TRUE as well.

We recall that Theorem 6 also immediately implies the analogous result for PLAN EXISTENCE.

4 Hierarchical Task Networks

Considering HTNs with compound tasks adds another, seemingly opaque layer of difficulty to the considered planning problems. In this section, we show that-at least in terms of classical complexity-we can cleanly characterize the jump from primitive to compound through three measures on compound task networks: we obtain an algorithmic meta-theorem that allows to lift polynomial-time solvability from primitive to compound task networks if all three of these measures are bounded. Moreover, this result is tight in the sense that none of the three measures can be dropped. The three measures we need are C#, Cs, and Cd:

Definition 1. For an initial task network tn = (T, ≺+, α) in a domain D = (F, A, C, δ, M), we refer to the number of compound tasks in tn by C#(tn) = |{t ∈ T | α(t) ∈ C}|. The maximum size of a network that a task can be decomposed into is Cs(D) = max{|Tm| | (c, (Tm,≺+m, αm)) ∈M}. The maximum depth Cd(tn) of a network is defined recursively: Cd(tn) = 0 for primitive task networks, and a compound task network tn′ has Cd(tn′ ) = i if i is the smallest integer such that every decomposition of all compound tasks in the initial network T results in a new network tn′′ where Cd(tn′′ ) ≤ i - 1. We let Cd(tn) = ∞ if no such i exists (cyclic decomposition).

For our later considerations, it will be useful to additionally define the maximum number of pairwise non-isomorphic networks that a task can be decomposed into; we denote that by Cc(D) = maxc∈C |{tnm | (c, tnm) ∈M}|. The next technical lemma shows how these measures help us bound the "decomposition complexity" of compound HTNs. We drop the references to tn and D in these parameters when they are clear from context.

Lemma 7. If Cd ̸=∞, then a task network tn = (T,≺+, α) can be decomposed into at most Cc∑Cd-1 i=0 C#·Cs i pairwise non-isomorphic primitive task networks tn′ = (T ′ , ≺+′ , α′ ). For each of these, |T ′ | ≤ |T | + C# · (CsCd - 1).

Proof. We first show the second part of the statement. The |T |-C# primitive tasks in tn are still present in any network tn′ that tn can be decomposed into. A compound task in tn can be decomposed into at most Cs compound tasks in one decomposition step and there are at most Cd decomposition steps. Thus, each compound task in tn can create at most CsCd tasks in tn′ . Hence, |T ′ | ≤ |T| -C# +C# · CsCd .

For the first statement, note that decomposing each of the C# compound tasks once in a task network of depth Cd can result in at most CcC# pairwise non-isomorphic task networks of depth at most Cd - 1. Further, each of these resulting networks has at most C# · Cs compound tasks. Thus, tn can be decomposed into at most

Having defined our measures of interest, we proceed to formalize the set of problems our meta-theoremwill capture. Intuitively, the aim is to formalize the set of all problems which deal with compound HTNs by decomposing them.

Definition 2. Let PR be an arbitrary HTN problem. Then, PR is decomposable if and only if, for all non-primitive initial task networks tn, PR on tn is a yes-instance if and only if there is a primitive task network tn′ such that tn can be decomposed into tn′ and tn′ is a yes-instance of PR.

Note that all problems discussed in this work are decomposable. Next, in order to capture the general notions of "tractability" for various HTN problems on networks where certain measures are bounded, we need to slightly restrict the measures in question to avoid entirely degenerate measures.

Definition 3. Let κ be any numerical measure of HTNs in a domain D, i.e., a mapping that assigns each HTN a nonnegative number. We say that κ is stable if there exists a computable function f with the following property: for each primitive HTN tn∗ consisting of c tasks and each HTN tn containing some compound task t, the HTN tn′ obtained from tn by decomposing t into tn∗ satisfies κ(tn′ ,D) ≤ f (κ(tn, D), c).

The computability of f is a mild technical requirement relevant for the fixed-parameter setting later on. We say that a stable measure κ is a stable tractability measure for a decomposable HTN problem PR if, for each constant c, PR can be solved in polynomial time on all primitive HTNs tn such that κ(tn,D) ≤ c. Notably, the (generalized) partial order width measure fits in that definition, where its stability is due to the fact that the addition of c vertices to a graph can only increase its (generalized) partial order width by at most c.

Observation 1. (Generalized) partial order width is a stable tractability measure for PLAN VERIFICATION. The sum of the (generalized) partial order width and the number of states in the state space is a stable tractability measure for ACTION EXECUTABILITY and STATE REACHABILITY.

We are now ready to establish the first meta-theorem.

Theorem 8. Let PR be a decomposable HTN problem and κ a stable tractability measure. Then, PR is polynomialtime solvable when restricted to any initial network tn in domain D where Cd, C#, Cs, and κ(tn, D) are constants.

Proof. Let I have task network tn = (T,≺+, α). If there are no compound tasks in T , then we apply an algorithm for primitive networks. Thus, assume Cd ≥ 1. Then, PR in tn can be solved by listing all the primitive instances tn can be decomposed into and solving PR in each of these. By Lemma 7, there are at most Cc g(Cd,C#,Cs) ≤ |I|g(Cd,C#,Cs) such instances Ip for g(Cd,C#,Cs) = ∑Cd-1 i=0 C# · Cs i and, for each of these, |Ip| ≤ |I| + f ′′ (Cd,C#,Cs) for some computable function f ′′ . Furthermore, for each initial task network tnp of an instance Ip, we have κ(tnp,D) ≤ f ′′′ (κ(tn,D),Cd,C#,Cs), for some computable function f ′′′ as κ is a stable measure and tnp is obtained from tn by sequentially decomposing C# compound tasks into a total of f ′′ (Cd,C#,Cs) primitive tasks. Thus, if primitive instances Ip can be solved in time at most |Ip|f(κ(tnp,D)) , then the total runtime (for some computable function f ′ ) is

We complement Theorem 8 via lower bounds which show that bounding Cd, C#, and Cs is necessary. Specifically, we prove that if any one of these measures is not bounded by a constant, then some of the considered problems become NPhard on compound networks, even for settings that were easily solvable on primitive networks. While other reductions show the hardness deriving from decomposing non-primitive networks (see, e.g., [Erol et al., 1996; Alford et al., 2015a; Behnke et al., 2015]), our reduction is stronger in the sense that it bounds all but any one of the parameters Cd, C#, Cs.

Theorem 9. For each ι ∈ {Cd,C#,Cs}, PLAN EXISTENCE, ACTION EXECUTABILITY, and STATE REACHABILITY remain NP-hard when restricted to instances which have (generalized) partial order width at most 1 and where {Cd, C#, Cs, Cc} \ {ι} are upper-bounded by a constant.

Proof Sketch. We reduce from MULTICOLORED-CLIQUE, which is NP-hard and asks whether a given properly kvertex-colored graph G contains a k-clique [Fellows et al., 2009]. The reduction creates a compound task for each vertex and edge of G. These can all either be decomposed into a primitive vertex- or edge-task, or an empty "dummy" network. The actions and state space of the output instance are set up in a way which ensures that, for each color class, only a single primitive vertex task can be executed. The vertices for which we execute the corresponding primitive vertex task are considered as "chosen", and a primitive edge task can only be executed if both of its incident vertices are chosen. Based on the targeted HTN problem, we ensure the instance admits a solution if and only if it is possible to execute (k2) primitive edge tasks, matching each of the (k2) pairs of colors.

The above completes the reduction for the case where ι = C#. For the case where ι = Cs, we slightly adapt the construction by having the whole network (as described above) be the result of decomposing a single initial compound task t0. Finally, when ι = Cd we build on the case of ι = Cs by making the decomposition from t0 "gradual" as opposed to only occurring in a single step.

5 A Parameterized Analysis of HTNs

In this final section, we ask whether-and for which parameterizations-our problems on primitive HTNs admit fixed-parameter algorithms. While there are many graph-theoretic parameters typically used to achieve fixedparameter tractability, none of the "usual suspects" in that regard will help with our problems due to the hardness on forests of stars [Lin and Bercher, 2023] and sets of chains (Theorems 1 and 2). Indeed, this applies to treewidth [Robertson and Seymour, 1986], the feedback edge number [Ganian and Korchemna, 2021], and similar measures defined on digraphs [Ganian et al., 2016].

On the other hand, our problems are polynomial-time solvable for constant generalized partial order width and so we need a more refined notion of hardness to rule out fixed-parameter tractability in this case. In particular, hardness w.r.t. a parameter k for the complexity classes W[1] or W[2] rules out any fixed-parameter algorithm under the wellestablished assumption that W[1] ̸= FPT. As the SHUFFLE PRODUCT problem is W[2]-hard when parameterized by the width w [van Bevern et al., 2016], Theorems 1 and 2 also imply the W[2]-hardness of the considered problems.

Fixed-Parameter Tractability via Vertex Cover. We contrast these lower bounds with a fixed-parameter algorithm for primitive networks that exploits a different parameterization, namely the vertex cover number (vcn) of G≺. A vertex cover of G≺ is a subset of tasks V ⊆ T such that, for all t ≺ t′ , t ∈ V and/or t′ ∈ V ; the vcn of G≺ is the minimum size of a vertex cover of G≺. While the vcn has been used to obtain fixed-parameter algorithms for many other problems [Balko et al., 2022; Blazej et al., 2023; Bodlaender et al., 2023; Chalopin et al., 2024], the techniques from previous works do not easily translate to HTN problems. Instead, our algorithms use a delicate branching routine whose correctness requires a careful analysis of the state space.

Theorem 10. PLAN VERIFICATION is fixed-parameter tractable on primitive task networks parameterized by the vcn of G≺.

Proof Sketch. We must order the tasks so that they respect ≺ and correspond to the input plan p. We branch over all orderings of the tasks in a minimal vertex cover V and discard those which do not respect ≺. Let the priority of a task be higher the earlier one of its out-neighbors in V is placed in the ordering. Tasks in V have priority just below the last of their in-neighbors, and tasks outside V with no out-edges have no priority. We iterate through p and, at each step, select a task for that position that has the respective action and has all of its predecessors in ≺ already selected. If there are multiple candidates, we choose a task with highest priority, ensuring that order constraints are met as early as possible.

Theorem 11. STATE REACHABILITY and ACTION EXECUTABILITY on primitive networks are fixed-parameter tractable when parameterized by the vcn of G≺ plus the number of states in the state transition graph.

Proof Sketch. We branch over the order of vertices in the vertex cover as in Theorem 10, but need more involved arguments for constructing the task sequence. Inspired by the proof of Theorem 4, we carefully branch on which paths and cycles the sequence takes in the state transition graph in between visiting the tasks of the vertex cover, and use an ILP to determine the number of times each cycle is traversed.

A Meta-Theorem for Fixed-Parameter Tractability. As our final contribution, we show that the algorithmic metatheorem for polynomial-time solvability can be lifted to the setting of fixed-parameter tractability if we also restrict the maximum "breadth" of a compound task, i.e., Cc. To do this, we first need to define a suitable notion of stability. We call κ a stable fixed-parameter tractability measure for a decomposable HTN problem PR if κ is a stable measure and PR is fixed-parameter tractable on primitive task networks parameterized by κ. The vcn is an example of this notion as the addition of c vertices to a graph increases its vcn by at most c.

Observation 2. The vcn is a stable fixed-parameter tractability measure for PLAN VERIFICATION. The sum of the vcn and the number of states in the state space is a stable fixedparameter tractability measure for ACTION EXECUTABILITY and STATE REACHABILITY.

We now establish the parameterized analog of Theorem 8, which extends Theorems 10 and 11 to compound networks:

Theorem 12. Let PR be a decomposable HTN problem and κ a stable fixed-parameter tractability measure. If Cd ̸= ∞, then PR is fixed-parameter tractable by the combined parameters Cc, Cd, C#, Cs, and κ(tn, D) for the initial network tn.

Proof. Let tn = (T,≺+, α). If there are no compound tasks

in T, i.e., Cd = 0, the statement immediately holds by applying an algorithm for primitive networks. Thus, assume Cd ≥ 1. Then, PR in tn is solved by listing all primitive instances tn can be decomposed into and solving PR in each of these. By Lemma 7, there are at most Cc∑Cd-1 i=0 C#·Cs i such instances Ip and, for each of these, |Ip| ≤ |I| + f ′′ (Cd,C#,Cs) for some computable function f ′′ . Further, for each initial task network tnp of an instance Ip, we have κ(tnp,D) ≤ f ′′′ (κ(tn,D),Cd,C#,Cs), for some computable function f ′′′ as κ is a stable measure. Thus, if primitive instances Ip can be solved in time f(κ(tnp,D))|Ip|O(1) , then the total running time can be upper-bounded by O(Cc g(Cd,C#,Cs) · f ′ (κ(tn,D),Cd,C#,Cs) · |I|O(1)) for computable functions g and f ′ .

6 Concluding Remarks

This article provides a comprehensive understanding of the complexity-theoretic landscape of several fundamental problems on HTNs. Our results include strong algorithmic lower bounds and complementary positive results-not only for specific problems, but also in the form of meta-theorems that can be used for other HTN problems. For further work, while we have provided lower bounds justifying all the restrictions applied in the algorithmic meta-theorem for polynomial-time solvability (Theorem 8), in the more refined fixed-parameter tractability setting we leave it open whether the "hierarchical breadth" Cc needs to be part of the parameterization in order to establish Theorem 12.

Let us close with a brief discussion of the practical relevance of the results contained in this article. One indicator for the existence of practical algorithms is whether efficient algorithms should even be possible from a theoretical point of view. Our work provides such indicators, which may guide the development of algorithms that are efficient in practice as well. This is an exciting direction for future work, but it lies beyond the scope of this paper. That said, we deem it plausible that real-world planning problems exhibit some of the structural restrictions for which we have theoretically efficient algorithms. For example, the fixed-parameter algorithms in Theorems 10 and 11 could be applied to instances where only a few central tasks have precedence over others, while the remainder are essentially independent of each other. Moreover, the polynomial-time algorithms from Theorems 5 and 6 could be applied to instances where the tasks can be partitioned into isolated tasks and a small number of sets with internally predefined orders. For a concrete example, consider airport maintenance scheduling. Here, one may need to schedule a sequence of tasks for a small number of aircraft (where, for each aircraft, the order is predefined by FAA standards), while also dealing with a potentially large number of auxiliary tasks which are all pairwise independent.

Acknowledgements

This work was funded by the Austrian Science Fund (FWF) [10.55776/Y1329 and 10.55776/COE12], the WWTF Vienna Science and Technology Fund (Project 10.47379/ICT22029), and the EU Horizon Europe project TaRDIS (grant agreement 101093006).