Most practical work on At planning systems during the last fifteen years has been based on Hierarchical Task Network (HTN) decomposition, but until now, there has been very little analytical work on the properties of HTN planners. This paper describes how the complexity of HTN planning varies with various conditions on the task networks, and how it compares to STRIPS-style planning. In AI planning research, planning practice (as embodied in implemented planning systems) tends to run far ahead of the theories that explain the behavior of those systems. There is much recent analysis of the properties of total-and partial-order planning systems using STRIPS-style planning operators. STRIPS-style planning systems, however, were developed more than twenty years ago, and most of the practical work on AI planning systems during the last fifteen years has been based on Hierarchical Task Network (HTN) decomposition (e.g., NOAH [1 I], NONLIN [12], DEVISER [13], and SIPE [14] ). Until now, there has been very little analytical work on the properties of HTN planners. One of the primary obstacles impeding such work has been the lack of a clear theoretical framework explaining what a HTN planning system is, although two recent papers [9, 15] have provided important first steps in that direction. A primary goal of our current work is to define, analyze, and explicate features of the design of HTN planning systems. Our work has progressed far enough to do complexity analyses of HTN planning similar to analyses which Bylander [2], Erol et al. [5] performed for planning with STRIPS-style operators. In particular, We have examined how the complexity of determining whether a plan exists depends on the following factors: (1) restrictions on the existence and/or ordering of non-primitive tasks in task networks, (2) whether " This work was supported in part by NSF Grant NSFD CDR-88003012 to tile Institute for Systems Research, and NSF grant IR19306580 and ONR grant N00014-91-J-1451 to the Computer Science Department. I~) J.C. Baltzer AG, Science Publishers 70 K. Erol et al.. Complexi O, resuhs for HTN planning the tasks in task networks are required to be totally ordered, and (3) whether variables are allowed. The paper is organized as follows. Section 2 contains an overview of HTN planning and our formalization of HTN planning. Section 3 contains the complexity results, and section 3.3 investigates the relation between HTN planning and STRIPSstyle planning. Basics of HTN planning This section contains an informal description of HTN planning, intended to provide an intuitive feel for HTN planning. The precise description is presented in the sections 2.2 through 2.4. HTN planning can be described best by contrasting it with its predecessor, STRIPS-style planning I The representations of the world and the actions in HTN planning are very similar to those of STRIPS-style planning. Each state of the world is represented by the set of atoms true in that state. Actions correspond to state transitions, that is, each action is a partial mapping from the set of states to set of states. However, actions in HTN planning are usually called primitive tasks. The difference between HTN planners and STRIPS-style planners is in what they plan for, and how they plan for it. STRIPS-style planners search for a sequence of actions that would bring the world to a state that satisfies certain conditions, i.e., attainment goals. Planning proceeds by finding operators that has the desired effects, and by asserting the preconditions of those operators as subgoals. On the other hand, one of the motivations for HTN plalming was to close the gap between AI planning techniques and operations-research techniques for project management and scheduling [12] . HTN planners search for plans that accomplish task networks, and they plan via task decomposition and conflict resolution, which we shall explain shortly. A task network is a collection of tasks that need to be carried out, together with constraints on the order in which the tasks are carried out, the way variables are instantiated, and what literals must be true before or after each task is performed. For example, Fig. 1 contains a task network for a trip to Las Vegas. Constraints allow the user to specify how he desires the tasks to be performed. For instance, in the Las Vegas example, the user might desire to get rich before seeing a show, which can be represented as an ordering constraint. Unlike STRiPS-style planning, the constraints may or may not contain conditions on what must be true in the final state. We use the term "STRIPS-style" planning to refer io any planner (eilher total-or partial-order) in which the planning operators are STRIPS-style operators (i.e., operators consisting of three lists of atoms: a precondition list, an add list, and a delete list). These atoms are normally assumed to contain no function symbols. K. Erot et af,, Complexit3, results .[br HTN plamffng A task network that contains only primitive tasks is called a primitive task network. Such a network might occur, for example, in a scheduling problem. In this case, an HTN planner would try to find a schedule (task ordering and variable bindings) that satisfies all the constraints. In the more general case, a task network can contain non-primitive tasks. Nonprimitive tasks are those that cannot be executed directly, and the planner needs to figure out how to accomplish them. They represent activities that involve perfbrming multiple tasks. For example, consider the task of travelling to New York. There are sevemI ways to accomplish it, such as flying, driving or taking the train. Flying would involve tasks like making reservations, going to the airport, buying ticket, boarding the plane, and it would only work under certain conditions such as availability of tickets, being at the airport on time, having enough money for the ticket, etc, Ways of accomplishing non-primitive tasks are represented using constructs called methods. A method is of the form (c~, d) where a, is a non-primitive task, and d is a task network. It states that one way to accomplish the task ct is to achieve all the tasks in the task network d without violating the constraints in d. Figure 2 presents a (simplified) method for accomplishing Go(X,Y). Planning proceeds by starting with the the initial task network d, and doing the following steps repeatedly, until no non-primitive tasks are left: pick a non-primitive task (t in d and a method (n:, dr). Then modify d by "decomposing" ct (i.e., replace a: with the tasks in d ~, and incorporate the constraints of d ~ into d), Figure 3 demonstrates how to do a decomposition on the task network presented in Fig. I Fig. 2 . Once no non-primitive tasks are left in d, the next problem is to find a totally-ordered ground instantiation cr of d that satisfies all of the constraints. If this can be done, then cr is a successful plan for the original problem. In practice, HTN planning also has several other aspects. In particular, functions are often provided which can "debug" partially reduced task networks to eliminate potential problems. These "critic" functions are used to handle constraints, resource limitations, and to provide domain-specific guidance. The formalization described in [6] explains critics and the relationship between these and the constraints described above. For the purposes of this paper, the critics do not affect worst-case behavior, and thus we will omit this detail. Here are some examples to further clarify the distinctions between different types of tasks and STRIPS-style goals. Building a house requires many other tasks to be performed (laying the foundation, building the walls, etc.), thus it is a compound task. It is different from the goal task of "having a house", since buying a house would achieve this goal task, but not the compound task of building a house (the agent must build it himself). As another example, the compound task of making a round trip to New York cannot easily be expressed as a single goal task, because the initial and final states would be the same. Goal tasks are very, similar to STRIPS-style goals. However, in STRIPS-style planning, any sequence of actions that make the goal expression true is a valid plan, where as in HTN planning, only those plans that can be derived via decompositions are considered as valid. This allows the user to rule out certain undesirable sequences of actions that nonetheless make the goal expression true. For example, consider the goal task of "being in New York", and suppose the pIanner is investigating the possibility of driving to accomplish this goal, and suppose that the agent does not have a driver's licence. Even though learning how to drive and getting a driver's licence might remedy the situation, the user can consider this solution unacceptable, and while writing down the methods for be-in(New York), she can put the constraint that the method of driving succeeds only when the agent already has a driver's licence. There appears to be some general confusion about the nature and role of tasks in HTN planning. This appears largely due to the fact that HTN planning emerged, without a formal description, in implemented planning systems [11, 12] . Many ideas introduced in HTN planning (such as nonlinearity, partial order planning, etc.) were formalized only as they were adapted to STRIPS-style planning, and only within that context. Those ideas not adapted to STRiPS-style planning (such as compound tasks and task decomposition) have been dismissed as mere efficiency hacks. In our formalism, we have tried to fill the gaps, and replace informal descriptions with precise definitions, without omitting HTN planning constructs. Our formalism is mostly shaped after NONLIN [t2] and the works of Yang and Kambhampati [9, 15] o11 hierarchical planning. However, our terminology for K. Erol et al., Complexi O, results for HTN plannh~g 73 referring to non-primitive tasks is slightly different from theirs, which instead uses the term "high level actions" [11, 15]. Although this term has some intuitive appeal, we prefer not to use it, in order to avoid any possible confusion with STRIPS-style actions. STRIPS-style actions are atomic, and they always have the same effect on the world; non-primitive tasks can be decomposed into a number of primitive tasks, and the effect of accomplishing a non-primitive task depends not only on the methods chosen for doing decompositions, but also on the interleavings with other tasks. Compound tasks are also different from STRIPS-style goals. As we have discussed earlier, compound tasks represent activities for which the final state might be totally irrelevant, or in the case of round-trip example, the final state might be the same as the initial state. Yet another view of HTN planning totally discards compound tasks, and views methods for goal tasks as heuristic information on how to go about achieving the goals (i.e., which operator to use, in which order achieve the preconditions of that operator, etc.). Although this is a perfectly coherent view, we find it restrictive, and we believe there is more to HTN planning, as we try to demonstrate in our formalism and in the section on expressive power. Our language £ for HTN planning is a first-order language with some extensions, and it is fairly similar to the syntax of NONLIN [12] . The vocabulary of/; is a tuple IV, C, P, F, T, N), where V is an infinite set of variable symbols, C is a finite set of constant symbols, P is a finite set of predicate syrnbols, F is a finite set of primitive-task symbols (denoting actions), T is a finite set of compound-task symbols, and N is an infinite set of symbols used for labeling tasks. All these sets of symbols are mutually disjoint. A state is a list of ground atoms. The atoms appearing in that list are said to be tree in that state and those that do not appear are false in that state. A primitive task is a syntactic construct of the form do [f(zl,..., z~,:)], where f E F and :el,... ,:c~: are terms. A goal task is a syntactic construct of the form achieve [l], where l is a literal. A compound task is a syntactic construct of the form perJorm [t(:cl,..., :c~)], where ~ C T and zi,..., zk are terms. We sometimes refer to goal tasks and compound tasks as non-primitive tasks. A task network is a syntactic construct of the form [(lzl : ctl) and n., 'n; E N 3 Intuitively (finis will be formalized m the <°Operational Semantics" section), (,~. -~ ';7') means that the task labeled with .n must precede the one labeled with r~/: (n, l), (l, ;;) and (71,, l, r~/) mean that l must be tree in the state immediately after 'fT., immediately before <ft., and in all states between -r~. and 'n/, respectively. Both negation and disiunction are allowed in the constraint formula. A task network containing only primitive tasks is called a primitive task network. As an example, Fig. 4 shows a blocks-world task network and its graphical representation. In this task network there are three tasks: clearing ~l, clearing v2, and moving vi to t?2. The task network also includes the constraints that moving vi must be done last, that Vl and '~> must remain clear until we move Vl, that ./Jl,'t~2,'v3 are different blocks, and that on(vt, v3) be true immediately before vi is moved. Note that on(~q, v3) appears as a constraint, not as a goal task. The purpose of the constraint (on(vi, '~)3), 7z3) is to ensure that v3 is bound to the block under ~)i immediately before the move. Representing on('~q,.~)3) as a goal task would mean moving '~)i onto some block v3 before we move it onto v2, which is not what is intended. A plan is a sequence cr of ground primitive tasks. An ope,ato," is of the form [ope,ato," f('vi .... ,va:) (p,e:l,,... ,l,,) A metDod is a constrtlct of the form (cx, d) where ~. is a non-prmlitive task, and d is a task network. As we will define formally in the "Operational Semantics" section, this construct means that one way of accomplishing the task ct is to accomplish the task network d, i.e., to accomplish all the subtasks in the task network without 2 We also allow n, r~' to be of tile form first[n/, nO,...] or last[hi, 7L~,...] so that we can refer to the task thai starts first and to the task that ends last among a set of tasks, respectively. 75 violating the constraint formula of the task network. For example, a blocks-world method for achieving on (vl, v2) would look like (achieve (on(vt, v2)), d), where d is the task network in Fig. 4 . To accomplish a goal task (achieve [l]), I needs to be tree in the end, and this is an implicit constraint in all methods for goal tasks. If a goal is ah-eady true, then an empty plan can be used to achieve it. Thus, for each goal task, we (implicitly) have a method (achieve [t], [(r,. : do[f]), (/,'n.)]) which contains only one dummy primitive task f with no effects, and the constraint that the goal / is tree immediately before do [f]. Each primitive task has exactly one operator for it, where as a non-primitive task can have an arbitrary number of methods. A planning domain is a pair "D = (Op, Me), where Op is a set of operators, and Me is a set of methods. A plamling problem instance is a triple P = (d, I,'D), where D is a planning domain, I is the initial state, and d is the task network we need to plan for. The language of P is the HTN language £ generated by the constant, predicate, and task symbols appearing in P, along with an infinite set of variables and an infinite set of node labels. Thus, the set of constants, predicates and tasks are all part of the input. Next, we define some restrictions on HTN-planning problems. P is primitive if the task network d contains only primitive tasks. This corresponds to the case where the planner is used only for scheduling. P is regular if all the task networks in the methods and d contain at most one non-primitive task, and that non-primitive task is ordered with respect to all the other tasks in the network. Surprisingly, this class of HTN-planning problems is closely related to STRiPS-style planning, as we shall see in section 3.3. P is propositional if no variables are allowed. P is rotalh, ordered if all the tasks in any task network are totally ordered. PLAN EXISTENCE is the following problem: given P = (d, I, D), is there a plan that solves P? In this section, we give a fixed point definition for the set of solutions for a given HTN-planning problem. Description of an equivalent model-theoretic semantics appear in [6] . First, we define how primitive tasks change the world when executed. Similar to the way it is done in STRiPS-style planning, we verify that the primitive task is executable and then update the input state based on the effects of the prmfitive task. More precisely, Let s be a state, and f E F be a primitive task symbol with the corresponding operator [.] '(vl ..... v/,:) 3 All variables and node labels in the method must be renamed with variables and node labels that do not appear anywhere else. K. EIvl et al., Complexi O, results for HTN planning • replace (n < ~,j) with (last[r~ll,...,n'k] < "n,j), as 'n.j must come after every task in the decomposition of n; l . • replace (n,j < n.) with (~,j <first['n/t • replace (~., I) with (last ['n,'l,...,n,'k], l), as l must be true immediately after the last task in the decomposition of 'n.; • replace (~,, l, 7z.  and me is a method in 70 for that task}.  Intuitively, sol,, (d, I, 70) is the set of plans that can be derived in n, steps, and sol (d, I, 70) is the set of plans that can be derived in any finite number of steps. In [6], we prove that the set of solutions according to the model-theoretic semantics coincide with sol (d, I, 70). Our complexity results are summariz6d in Table 1 . In the following sections, we state the theorems and discuss their implications.  K. EIvl et al., Complexi O, results for HTN plamzing It is easy to show that we can simulate context-free grammars within HTN planning by using primitive tasks to emulate terminal symbols, compound tasks to emulate non-ten'ninal symbols, and methods to encode grammar rules. More interesting is the fact that we can simulate any two context-free grammars, and with the help of task interleavings and constraints, we can check whether these two grammars have a common string in the languages they generate. Whether the intersection of the languages of two context-free grammars is non-empty is a semi-decidable problem [8] . Thus: Theorem 1. PLAN EXISTENCE is strictly semi-decidable, even if P is restricted to be propositional, to have at most two tasks in any task network, and to have only totally ordered methods. This result might seem surprising at first, since the state space (i.e., the number and size of states) is finite. If the planning problem were that of finding a path from the initial state to a goal state (as in STRIPS-style planning), indeed it would be decidable, because, for that problem, whenever there is a plan, there is also a plan that does not go through any state twice, and thus we need to examine only a finite number of plans. On the other hand, HTN planning can represent compound tasks accomplishing which might require going through the same state many times, and thus we have the undecidability result. Instead of encoding each context-free grammar rule as a separate method, it is possible to encode these rules with predicates in the initial state, and to have a method containing variables and constraints such that only those decompositions corresponding K. Etvl et al., Complexi O, results for HTN planning 79 to the grammar rules encoded in the initial state are allowed. Hence, even when the domain description (i.e., the set of operators and methods) is fixed in advance, it is possible to find planning domains for which planning is undecidable, as stated in the following theorem: Theorem 2. There are HTN planning domains that contain only totally ordered methods each with at most two tasks, for which PLAN EXISTENCE is strictly semi-decidable. One way to make PLAN EXISTENCE decidable is to restrict the methods to be acyclic. In that case, any task can be expanded up to only a finite depth, and thus the problem becomes decidable. To this end, we define a L:-level-mapping to be a function level() from ground instances of tasks to the set {0 ..... k:}, such that whenever we have a method that can expand a ground task a to a task network containing a ground task a', level(a) > level(a'). Furthermore, level(a) must be 0 for every primitive task a. Intuitively, level 0 assigns levels to each ground task, and makes sure that tasks can be expanded into only lower level tasks, establishing an acyclic hierarchy. In this case, any task can be expanded to a depth of at most k. Therefore, Theorem 3. PLAN EXISTENCE is decidable if P has a k-level-mapping for some integer ~:. Examples of such planning domains can be found in manufacturing, where the product is constructed by first constructing the components and then combining them together. Another way to make PLAN EXISTENCE decidable is to restrict the interactions among the tasks. Restricting the task networks to be totally ordered limits the interactions that can occur between tasks. Tasks need to be achieved serially, one after the other; interleaving subtasks for different tasks is not possible. Thus interactions between the tasks are limited to the input and output state of the tasks, and the "protection intervals", i.e., the literals that need to be preserved, which are represented by state constraints of the form (7~, l, fT.'). Under the above conditions, we can create a table with an entry for each task, input/output state pair, and set of protected literals, that tells whether it is possible to achieve that task under those conditions. Using dynamic programming techniques we can compute the entries in the table in DOUBLE-EXPTIME, or in EXPTIME if the problem is further restricted to be propositional. As shown in the next section, STRIPS-style planning can be modeled using HTNs that satisfy these conditions, so we can use the complexity results on STRIPS-style planning in [2, 5] to establish a lower bound on the complexity of HTN planning. Thus: 80 Theorem 4. PLAN EXISTENCE is EXPSPACE-hard and in DOUBLE-EXPTIME if P is restricted to be totally ordered. PLAN EXISTENCE is PSPACE-hard and in EXPTIME if P is further restricted to be propositional. If we restrict our planning problem to be regular, then there will be at most one non-primitive task in any task network (both the initial input task network, and those we obtain by expansions). Thus, subtasks in the expansions of different tasks cannot be interleaved, which is similar to what happens in Theorem 4. But in Theorem 4, there could be several non-primitive tasks in a task network, and we needed to keep track of all of them (which is why we used the table). If the planning problem is regular, we only need to keep track of a single non-primitive task, its input/final states, and the protected literals. Since the size of a state is at most exponential, the problem can be solved in exponential space. But even with regularity and several other restrictions, it is still possible to reduce an EXPSPACE-complete STRiPS-style planning problem (described in [5] ) to the HTN framework. Thus: Theorem 5. PLAN EXISTENCE is EXPSPACE-complete if P is restricted to be regular. It is still EXPSPACE-complete if P is further restricted to be totally ordered, with at most one non-primitive task symbol in the planning language, and all task networks containing at most two tasks. When we further restrict our problem to be propositional, it is still possible to define a reduction from propositional STRiPS-style planning, which is proven to be PSPACE-complete [2]. Thus the complexity goes down one level: Theorem 6. PLAN EXISTENCE is PSPACE-complete if P is restricted to be regular and propositional. It is still PSPACE-complete if P is further restricted to be totally ordered, with at most one non-primitive task symbol in the planning language, and all task networks containing at most two tasks. If we allow variables but instead fix the planning domain "D (i.e., the set of methods and operators) in advance, then the number of ground atoms and ground tasks is polynomial in the length of the input to the planner. Hence the complexity of regular HTN planning with a fixed planning domain with variables is no harder than the complexity of regular propositional HTN planning, which is shown to be PSPACE-complete in Theorem 6 4 In the proof of Theorem 5.17 in [5] a set of three STRIPS operators with variables for which planning is PSPACE-complete is presented. The reduction described in the proof of Theorem 5 transforms this set of operators into a regular HTN planning domain (with variables) for which planning is PSPACg-complete. Hence: 4 In a related result, [2] shows that propositional STRIPS-style planning is also PSPACE-complete. We investigate the relation between regular HTN planning and STRIPS-style planning in section 3.3. K. Erol et al., Complexit 3, results for HTN planning Theorem 7, If P is restricted to be regular and 71) is fixed in advance, then PLAN EXISTENCE is in PSPACE. Furthermore, there exists a fixed regular HTN planning domain D for which PLAN EXISTENCE is PSPACE-complete, Suppose a planning problem is primitive, and either propositional or totally ordered. Then the problem's membership in NP is easy to see: once we nondeterministicalty guess a total ordering and variable binding, we can check whether the constraint formula on the task network is satisfied in polynomial time. Furthermore, unless we require the planning problem to be both totally ordered and propositional, our constraint language enables us to represent the satisfiability problem, and thus we get NP-hardness. Hence: Theorem 8. PLAN EXISTENCE is NP-complete if P is restricted to be primitive, or primitive and totally ordered, or primitive and propositional. However, PLAN EXISTENCE can be solved in polynomial time if P is restricted to be primitive, totally ordered, and propositional. There has not been a clear consensus on what HTNs can and cannot represent. It was generally believed that although HTNs are more flexible compared to STRIPSstyle planning, anything that can be done in HTN planning can be also done in STRIPS-style planning. Due to the lack of a formalism for HTN planning, such claims could not be proved or disproved. We address this question using the formalism in this paper. When we compare HTNs and STRIPS, we observe that the HTN approach provides all the concepts (states, actions, goals) that STRIPS has. In fact, given a domain encoded as a set of STRIPS operators, we can transform it to an HTN planning domain, in low-order polynomial time. A straightforward transformation would be to declare one primitive task symbol for each STRIPS operator, and for every effect of each operator, to declare a method similar to the one in Fig. 4 . Each such method contains the preconditions of the operator as goal tasks, and also the primitive task corresponding to the operator itself. Below is a more instructive transformation, which demonstrates that the relationship between STRIPS-style planning and HTN planning is analogous to the relationship between right Iinear (regular) grammars and context-free grammars. We summarize the transformation below; for details see the proof of Theorem 5. In this transformation, the HTN representation uses the same constants and predicates used in the STRIPS representation. For each STRIPS operator o, we declare a primitive task f with the same effects and preconditions as o. We also use a durnmy primitive task .t'rt with no effects or preconditions. We declare a single compound task symbol L For each primitive task f, we construct a method of the form 82 K. Eml et al., Complexi O, results for HTN plamffng f ..1 We declare one last method [pel~[ornl[l;,J] [(Tz :per[brm[t]), ('n., GI) A... A ('lz, Gm)] where GI,... ,Gin are the STRIPS-style goals we want to achieve. Note that the transformation produces regular HTN problems, which has exactly the same complexity as STRIPS-style planning. Thus, just as restricting context-free grammars to be right linear produces regular sets, restricting HTN methods to be regular produces STRIPS-style planning. The next question is whether there exists a transformation in the other direction, that is whether it is possible to encode HTN planning problems as STRIPS-style planning problems. Intuitively, such a transformation cannot exist, because STRIPSstyle planning lacks the concept of compound tasks, and its notion of goals is more restrictive than in HTN planning. For example, it does not provide means for declaring goals/constraints on the intermediate states as HTNs do. A more formal argument can be made as follows. From Theorem 1, HTN planning with no t\mction symbols (and thus only finitely many ground terms) is semi-decidable. Even if we require the domain description 7) to be fixed in advance (i.e., not part of the input), Theorem 2 tells us that there are HTN planning domains for which planning is semi-decidable. However, with no function symbols, STRIPS-style planning is decidabIe, regardless of whether or not the planning domain 5 is fixed in advance [5] . Thus: Theorem 9. There does not exist a computable function '(~ from the set of HTN planning problem instances to the set of STRIPS-style planning problem instances such that for any HTN-planning problem instance P, and any plan o', cr solves P iff (a(~) solves '(.,(P) 6 Showing whether a polynomial or computable transformation exists is one way of comparing the expressivity of two languages. The lack of a computable transformation from HTN planning to STRIPS-style planning means that for some planning problems, the problem representation in STRIPS-style planning will be exponentially (or in some cases, even infinitely!) larger than in HTN planning. However, there are also some other ways in which one might want to compare expressivity. For example, for comparing the expressive power of knowledge representation languages, Baader [1 ] has developed an approach based on model-theoretic semantics. According to Baader's definition, a knowledge-representation language L2 is as expressive as Lq iff there exists a function ,O (which does not have to be computable) that maps each set of sentences from Ll to a set of sentences from L2, such that the following property is satisfied whenever */J(FI) = F2: s Since STRIPS-style planning does not include medmds, a STRIPS-style planning domain is simply a set of operators. a In proving this theorem, we use the standard assumption that the STRIPS operators do not contain function symbols, nor do the HTN operators. To adapt Baader's definition to planning languages, there are two possible approaches: develop a model-theoretic semantics for planning, or use the operational sernantics presented in section 2.4. As we discuss in [6], these two approaches yield different (non-equivalent) definitions of the expressivity of planning languages. However, HTN planning is more expressive than STRiPS-style planning according to both of these definitions. In [6] we prove this for the model-theoretic definition; below we present a definition of expressivity based on operational semantics, and we use this definition to prove that HTN planning is more expressive than STRIPS-style planning. We define a planning language Li to be as e.vpressive as a planning language L2 iff there exists a function '/~, from the set of planning problem instances in L2 to the set of planning problem instances in L~ such that for any planning problem instance P in L2, P and .t/~(P) have the same set of solutions (plans) modulo symbol renaming. .~/, need not be computable. In the proofs of the undecidability theorems, we have shown that the set of sohltions for an HTN-planning problem instance can be any context-free set, or even the intersection of any two context-free sets. In general, such a set cannot be expressed as the set of solutions to a STRIPS-style planning problem, because the set of solutions to a STRIPS-style planning problem correspond to a regular set (where the states in the planning domain correspond to the states of a finite automata, and the actions conespond to state transitions). Hence there does not exist a function .~/J from the set of HTN-planning problem instances to the set of STRIPS-style planning problem instances that preserves the set of solutions. On the other hand, we have presented a transformation that maps each STRIPS-style planning problem instance to an HTNplanning problem instance with the same set of solutions. Thus we can conclude Theorem 10. HTN planning is strictly more expressive than STRIPS-style planning. The power of HTN planning comes from two things: (1) allowing multiple tasks and arbitrary constraint formulas in task networks, (2) compound tasks. Allowing multiple tasks and arbitrary formulae provides flexibility -but if alI tasks were either primitive or goal (STRIPS-style) tasks, these could probably be expressed with STRIPS-style operators (albeit clumsily and using an exponential number of operators/predicates). Compound tasks provide an abstract representation for sets of primitive task networks, similar to the way non-terminal symbols provide an abstract representation for sets of strings in context-free grammars. We have presented a formal description of HTN planning, and we have done a complexity analysis based on this formalism. From our results we can draw the following conclusions: 84 K. Erol et al., Complexit 3, results for HTN plamting 1. HTN planners can represent a broader set of planning domains than STRIPSstyle planners. The transformations from HTN planning problems to STRIPSstyle planning problems have revealed that STRiPS-style planning is a special case of HTN planning, and that the relation between them is analogous to the relation between context-free languages and regular languages. This contradicts the idea, held by some researchers, that HTNs are just an "efficiency hack". 2. Handling interactions among non-primitive tasks ix the most difficult part of HTN planning. In particular, if subtasks in the expansions for different tasks can be interleaved, then planning is undecidable, under even a very severe set of restrictions. However restricting the planning problems to be totallyordered or regular reduced the complexity significantly, because that limited the interactions among tasks. 3. In general, what restrictions we put on the non-primitive tasks has a bigger effect on complexity than whether or not we allow variables, or require tasks to be totally ordered. 4. If there are no restrictions on non-primitive tasks, then whether or not we require tasks to be totally ordered has a bigger effect (namely, decidability vs. undecidability) than whetlaer or not we allow variables. But in the presence of restrictions on non-primitive tasks, whether or not we allow variables has a bigger effect than whether or not we require tasks to be totally ordered. Currently, we are investigating how to use constraint satisfaction techniques such as tree search versus repair, value ordering and variable ordering heuristics to increase the efficiency of HTN planning. We are also investigating how to extend the action representation of HTNs to allow conditional, probabilistic and future effects.
that motivation, the complexity of HTN planning is substantially worse than planning with just primitive actions REF .
Complexity results for HTN planning
Annals of Mathematics and Artificial Intelligence
Annals of Mathematics and Artificial Intelligence
Computer Science