On Guiding Search in HTN Planning with Classical Planning Heuristics

1 Introduction

Planning is the task of finding a course of action that achieves the goal(s) of an agent when it is executed. In its simplest form, the model underlying the task contains a description of the relevant parts of the environment the agent is planning for and a set of actions that describe how he/she can change it. The environment is usually described by using a (finite) set of propositional variables; the definition of an action contains a description of preconditions that need to be fulfilled to be able to apply it and a set of effects (changes to the system it causes). The objective is to find a sequence of actions transforming the system into a state where certain state features hold. This is often done using heuristic search.

Two of the most popular approaches to planning are classical planning (that is equal to the abstract description given above) and hierarchical planning [Bercher et al., 2019]. In Hierarchical Task Network (HTN) planning, the most common hierarchical formalism, the model as given above is complemented by a hierarchy on the things to do, the tasks. The planning process is started with one or more so-called abstract tasks. Abstract tasks can not be executed directly (like actions), but need to be decomposed into other tasks until all remaining tasks are actions. Inserting actions apart from this decomposition hierarchy is (usually) not allowed. Interestingly, the objective in HTN planning is not to reach a state with certain properties, but to find a decomposition that can be executed. The process is very similar to the derivation of a word from a formal grammar, but with two differences: the symbols may be partially ordered, and the terminal symbols are actions with preconditions and effects. It has been shown that HTN planning models can describe much more complex behavior than possible in classical planning [Erol et al., 1996; H¨oller et al., 2014; H¨oller et al., 2016].

∗This paper was invited for the Best Papers from Sister Conference Track. It describes content of the paper "A Generic Method to Guide HTN Progression Search with Classical Heuristics" [H¨oller et al., 2018] from the International Conference on Automated Planning and Scheduling (ICAPS).

When a domain is modeled, the designer may introduce knowledge about the domain itself as well as advice for the planner on how to find a plan. Having less advice decreases the modeling effort and allows a simple adaptation of planning systems to new domains, but planners need to rely (even more) on their search techniques to find a plan. Systems that are designed to find plans without any advice are called to be domain-independent. In HTN planning, such systems have been developed based on heuristic search (e.g. our system or Bercher et al.'s [2017]), or on translation techniques, e.g. to propositional logic [Behnke et al., 2019b]. However, compared to classical planning, the solving techniques in HTN planning are less sophisticated, especially domainindependent heuristics to guide search. Therefore hierarchical systems often rely on advice encoded in the problem.

Using the more sophisticated techniques from classical planning in HTN planning seems appealing, but it is not straightforward due to several reasons:

• The hierarchy determines which actions are reachable, i.e. which actions may be in a plan.
• All tasks need to be decomposed and the resulting actions need to be integrated into the plan, i.e. the hierarchy also determines which actions have to be in a plan.
• The goal in classical planning is defined by a set of state features that shall be achieved. Therefore classical heuristics are designed to estimate the distance from a given state to a goal state. In HTN planning the "goal" is an abstract task to perform; no state-based goal is given.

In this paper we describe a generic way to use heuristics from classical planning to guide the search in HTN planning that overcomes the challenges given above.

2 Formal Framework

A classical planning problem is a tuple P = (L, A, s0, g, δ), where L is a set of propositional environment variables. A state s of the system is defined by the subset of state variables that is fulfilled in this state, i.e. s ⊆ L. s0 is the initial state that holds in the beginning of the planning process; g ⊆ L is the goal definition that specifies which state features shall be fulfilled in a goal state. A is a set of action names; δ is a triple (prec, add, del) of functions that define the preconditions and effects of the actions, each mapping actions to a set of state variables f : A → 2L. An action a is applicable when its preconditions are contained in the current state s, i.e. when prec(a) ⊆ s. When it is applicable, the state resulting from the application is defined by the function γ : A× 2L → 2L with γ(a, s) = (s \ del (a)) ∪ add(a). The objective in classical planning is to find a sequence that transforms the initial state into one that includes the goal conditions g; more formally, a sequence 〈a0a1 . . . al〉 of actions where ai is applicable in si and si is defined as γ(ai-1, si-1) for i > 0.

An HTN planning problem is defined as a tuple P = (L,C,A,M, s0, tnI, δ). L, A, s0, and δ are defined as before. C is a set of abstract (also called compound) task names. During the planning process, the tasks to accomplish are maintained in so-called task networks. A task network combines a (multi-)set of task names with the definition of ordering relations between these tasks. Formally, it is defined as a triple (T,≺, α), where T is a set of (unique) identifiers, α : T → A ∪ C is a function that maps these ids to task names, and ≺ ⊆ T × T is a strict partial order on the ids.

As given in the introduction, abstract tasks are decomposed until only primitive tasks are left. The rules on how to decompose these tasks are given by the set of decomposition methods M. Each method m ∈ M is defined as a pair (c, tn) of a task name c ∈ C that may be decomposed by the method and a task network tn that specifies how the task is decomposed. When a task is decomposed, it is removed from the task network, the tasks in the method's task network are added and inherit the ordering relations from the decomposed task. Formally, a method (c, tn) decomposes a task network tn1 = (T1,≺1, α1) into a task network tn2 = (T2,≺2, α2) if there is a task t ∈ T1 with α1(t) = c and a task network tn ′ = (T ′ ,≺′ , α′ ) that is equal to tn but using ids not contained in the decomposed network (i.e. T1 ∩ T ′ = ∅). The task network tn2 is defined as follows:

The planning process starts with the initial task network tnI and the objective is to find a task network tn such that the following conditions hold.

• tn can be reached by decomposing the initial task network tnI .
• All task names in tn are primitive.
• There is a sequence of the tasks in tn that is in line with its ordering relations and applicable in s0.

3 Using Classical Heuristics in HTN Planning

As given in the introduction, a common way to solve planning problems is heuristic search. In HTN planning, there are two common search algorithms: plan space search and progression search. The former maintains a partial ordering between the tasks and selects the next modification to do based on the so-called flaw selector, a kind of heuristic. The latter searches in a forward manner, processing the tasks next that have no predecessors in the ordering. It commits to a total order of the tasks in the prefix of the generated plan. This makes the representation less compact (because there may be many totally ordered linearizations of a single partial ordering), but the system can apply the state transition during search and is thus informed about the current state. This may be beneficial to calculate heuristics that depend on the state.

We introduced an improved progression algorithm [H¨oller et al., 2018] not given here due to the limited space. Instead, we want to focus on our method to guide the search with classical heuristics. In progression search, the distance to the next goal node is equal to the sum of decompositions and action applications necessary to transform a search node into a solution. To guide the search we need to estimate this number.

We want to do this using arbitrary and unchanged heuristics from classical planning. Our overall approach is illustrated in Figure 1. Before search, the HTN model is relaxed to a classical model. A relaxation is necessary because it has been shown that such a transformation is (in general) impossible [Erol et al., 1996; Geier and Bercher, 2011]. During search, the HTN planning system updates the initial state and the goal definition of the classical model. Based on the updated model, a classical heuristic is calculated and the resulting heuristic value is used to guide the search.

The transformation needs to overcome the challenges discussed in the introduction: 1. the reachability is restricted by the hierarchy, 2. the hierarchy enforces actions to be integrated into the plan, and 3. there is no state-based goal definition that can be used to calculate the heuristic.

From a top-down view the hierarchy represents a tree with AND nodes and OR nodes: for each task, a single method needs to be selected (an OR node). A method introduces new tasks that all need to be decomposed/executed (an AND node) and thus imply new OR nodes. This is illustrated in a simple transport domain in Figure 2. First consider its right side: The root of the tree is a single deliver task: a package p shall be delivered to position d (this is an OR node). There are several methods to decompose it (AND nodes) using different vehicles vi, the planner has to select one. In the figure, the method using vehicle v2 is selected. It leads to several new task nodes (denoted t1 to tm). These form new OR nodes. The leaves of the tree are actions (indicated by the boxes) that form the solution. The planner has to select methods that lead to an executable sequence of actions (in line with the ordering definitions induced by the HTN model).

We want a classical planner to do this selection, or, more precisely, a classical heuristic to estimate the minimum number of methods and actions necessary to build the tree. Therefore we encode the problem in a bottom-up approach into a classical planning problem: we start with the state and action definition of the HTN problem. For every (abstract and primitive) task n in the problem we add a new state feature un indicating whether it is part of the tree. Each action a gets a new add effect ua that achieves the corresponding state feature. For each method m = (c, tn) of the HTN model a new action am is introduced. It has as many preconditions as the method has subtasks: for every subtask n, the newly introduced state feature un is part of the precondition set. As single effect, am adds the fact uc (the fact corresponding to the decomposed task). The goal of the transformed problem is to achieve the state features corresponding to the task(s) in the current task network, i.e., the tree is built in a bottom-up manner. Since it thus somehow applies the decomposition methods in a backward manner, composing the tasks, we call our heuristics Relaxed Composition (RC) heuristics.

Consider the method m-del (?p, ?l1, ?l2, ?v) given in Figure 3 that decomposes the abstract task t -deliver (?p, ?l2) that defines how to deliver a package ?p to a location ?l2. To do so, a vehicle ?v needs to get to the current location of the package, pick it up, get to its final location, and drop it.

The method is translated into an action am-del(?p,?l1,?l2,?v) with the precondition set containing the four state features {ut-get-to(?v,?l1), upickup(?v,?l1,?p), ut-get-to(?v,?l2), udrop(?v,?l2,?p)} and a single add effect ut-deliver(?p,?l2).

A classical planner applied to that domain builds a plan representing the tree discussed above. Such a plan is shown on the left side of Figure 2. It starts at the bottom of the figure with the initial state s0. The actions in the model correspond to 1. actions or 2. methods of the HTN problem. The former are those that also appear in solutions of the HTN problem. The classical system needs to select an executable sequence. The latter represent the decisions at the OR nodes. When we apply a classical heuristic (instead of a planner), we can estimate the size of the tree.

This solves challenges 2 and 3: we have a meaningful statebased goal; to reach it, the classical system needs to integrate the actions enforced by the hierarchy into the plan. However, there are several relaxations made:

• The ordering relations given in the HTN are ignored.
• Every task needs to be done only once (regardless how often it is enforced by the HTN).
• To make enforced actions applicable, other actions may be inserted.

The third point is harmful to challenge 1: we should restrict the actions in a plan to those reachable via the hierarchy. Though we need to relax the problem to make it tractable, we can fix this issue to a certain extent. When there are two methods for a certain task, one decomposing it into the action a, the other one into b, a solution can only contain one action out of a and b. We can not encode this easily into the problem. However, we can encode which actions are reachable from the current task network at all and exclude these that are not. The heuristic may, however, still insert actions that can not appear together due to the hierarchy, e.g. because they are part of different methods for the same task (as given above). The set of reachable tasks can be preprocessed before search.

To restrict the set of all actions in the RC model to reachable actions, we could adapt the heuristic function(s) so check it. However, instead we added an additional precondition to every action that encodes whether it is reachable. Reachability is then set in the initial state and excludes those actions from a solution that can not be reached via the hierarchy. That way we can use unchanged heuristics.

Formally, our transformation is defined as follows:

Definition 1 (Relaxed Composition Model). Given an HTN planning problem P = (L, C, A, M, s0, tnI, (prec, add, del)) with tnI = (TI,≺I, αI), we define our RC model as the following classical planning problem P ′ :

The functions prec ′ , add ′ , and del ′ are defined as follows: For actions a ∈ A:

For actions am ∈ AM with m = (c, (T , ≺, α)):

An interesting theoretical property of our encoding is that for each HTN solution, there is a classical plan in the transformation that has costs equal to the number of nodes in the decomposition tree of the HTN solution. This especially holds for the optimal plan. This makes it possible to create safe, goal-aware, and admissible HTN heuristics, i.e. those that never return a heuristic value of ∞ if there still is a solution reachable (enabling pruning without becoming incomplete), that return 0 for goal nodes, and that never overestimate goal distance, respectively. The later can be used to find costoptimal plans (for details see Behnke et al. [2019c], Sec. 4).

During search, 1. the current state, 2. the set of reachable tasks, and 3. the tasks in the current search node change. These HTN elements are represented in the initial state and the goal definition of the encoding. This enables an efficient update of the model without a full recreation.

In principle our encoding can be combined with any heuristic from classical planning. However, the used heuristic should allow for a "cheap" change of the goal definition (not all do). We tested our approach with the Add [Bonet and Geffner, 2001], FF [Hoffmann and Nebel, 2001], and LMCut [Helmert and Domshlak, 2009] heuristic.

4 Discussion

We first want to discuss related work. Alford et al. [2009; 2016] introduced an approach to translate HTN planning problems into classical planning problems to solve them with classical planners. To make this possible, they use a bound to restrict the size of task networks in the translated problem. To solve arbitrary HTN planning problems, this bound must be increased while no solution is found (and in general there is no technique to determine when this can be stopped without potentially getting an incomplete search). In principle, their translation could also be integrated as heuristic model into the overall process depicted in Figure 1. However, when increasing the bound, the model grows very fast (while ours is linear in the size of the input model), and when the bound is chosen too low, the search may become incomplete because it marks search nodes as dead ends that are none.

FAPE [Bit-Monnot et al., 2016] uses blind search and a computation-intensive pruning technique. For pruning, it transforms the hierarchical model - which is essentially an acyclic HTN - into a temporal planning problem. Abstract tasks are represented using temporal actions, following an idea similar to our encoding: preconditions enforcing subtasks, which are temporally arranged according to their ordering relation, and an effect marking the abstract task as fulfilled at the end. Using a temporal reachability analysis, it determines whether a delete-relaxed plan exists, while still incorporating some of the problem's ordering information.

The maybe most closely related heuristics from the literature are those by Bercher et al. [2017] (that are also included in the evaluation). They are based on the so-called Task Decomposition Graph (TDG), a finite graph representing the task hierarchy. Heuristic calculation is started by assigning each action its costs as heuristic value. The heuristic value of each method is then set to the sum of the costs of its subtasks, and the costs of abstract tasks are set to the minimum of all applicable methods. The costs of abstract tasks and methods need to be updated until they converged (however, this can be done efficiently as described in the paper). The value has been further improved by including a state-based reachability analysis. The resulting heuristic includes the minimum effort induced by the hierarchy to reach a plan executable using task insertion. There are two main differences between the two approaches: First, our encoding as classical planning problem enables the combination with any classical heuristic (defining a family of heuristics instead of a single one). Second, our approach includes the costs of added actions into the heuristic value (what is not done by the TDG heuristics).

Figure 4 shows coverage results of several search-based HTN planning systems. We included our system using the Add, FF, and LM-Cut heuristic; plan space search with two TDG-based heuristics [Bercher et al., 2017]; and the translation approach as described by Alford et al. [2016] in combination with the classical planner JASPER [Xie et al., 2014]. For our system and the one of Bercher et al. the results are those for Greedy A∗ search with a weight of 2 (that has the highest coverage). The DFS data compares the uninformed Depth First Search of the original progression algorithm and our improved version (both implemented in our system). The JSHOP2 [Nau et al., 2003] planning system also relies on DFS. The data given here is its combination with our grounding and preprocessing [Behnke et al., 2019a] that increases its performance. Our system has the highest coverage. Our novel progression algorithm (not described in this paper) increases the coverage by 1 instance in DFS.

5 Conclusion

Domain-independent planning systems do not depend on advice modeled into a planning model. This makes models more compact and decreases the effort to create them. However, due to the lack of advice, such systems must rely on their solving techniques to find a solution. Though there has been progress in that direction in hierarchical planning, the used solving techniques - especially search heuristics - are less evolved than in classical planning. Due to the different problem classes, the adaptation of classical techniques to the setting of HTN planning is not straightforward. In this paper, we introduced an approach to use arbitrary classical heuristics to guide search in HTN planning. We have shown that it can be used to create HTN heuristics with interesting theoretical properties and that - when combined with our new progression search algorithm - it outperforms the state of the art in search-based HTN planning.

Acknowledgements

This work was partly funded by the technology transfer project "Do it yourself, but not alone: Companion-Technology for DIY support" of the SFB/TRR 62 funded by the German Research Foundation (DFG). Industrial project partner is the Corporate Research Sector of the Robert Bosch GmbH.