Laying the Foundations for Solving FOND HTN Problems: Grounding, Search, Heuristics (and Benchmark Problems)

1 Introduction

Hierarchical Task Network (HTN) planning allows the decomposition of complex tasks into smaller sub-tasks using predefined methods [Ghallab et al., 2016; Bercher et al., 2019]. The hierarchy imposed by the decompositions restricts which tasks can be included in the solutions, and more interestingly, excluded from them. This fine-grain control over the solutions makes HTN planning provably more expressive than the classical goal-satisfying approach [Erol et al., 1996; Geier and Bercher, 2011; Alford et al., 2015].

One of the prevailing assumptions in hierarchical planning systems is that the operating domain will react deterministically to the execution of actions [Erol et al., 1994; Nau et al., 2003; Bercher et al., 2019; H¨oller et al., 2021]; this is, however, rarely the case when dealing with real-world scenarios. While many planning systems in classical setting can deal with non-determinism [Cimatti et al., 2003; Kissmann and Edelkamp, 2009; Mattm¨uller et al., 2010; Fu et al., 2011; Pereira et al., 2022], to the best of our knowledge, there is no system to tackle HTN problems in the context of Fully Observable Non-Deterministic (FOND) environments. While hierarchical planners such as YoYo [Kuter et al., 2005; 2009], and ND-SHOP2 [Kuter and Nau, 2004] permit hierarchy as advice on how to solve the underlying classical FOND planning problems, they do not leverage the inherent expressivity of HTN planning. In other words, plans following their policies are usually not refined according to the task hierarchy. Other treatments of uncertainty in hierarchical planning such as the UPOM planner [Patra et al., 2020; 2021] which extends the Reactive Acting Engine (RAE) [Ghallab et al., 2016] to include learning strategies for online planning in dynamically changing environments, emphasize "acting" [Ghallab et al., 2014]. As a consequence, they use a nonstandard operational model to achieve hierarchy [Patra et al., 2019]. In this work, we aim to bridge this gap by building upon a theoretical framework proposed for solving FOND HTN problems [Chen and Bercher, 2022]. To achieve this goal we lay the entire groundwork necessary:

• A compilation from FOND HTN domains to their alloutcome-determinized relaxation in order to:
• ground lifted FOND HTN domains using existing deterministic HTN planning grounders, and
• derive heuristics from the deterministic planning literature (present and future),
• A heuristic search algorithm to solve (propositional) acyclic FOND HTN planning problems.

As a minor (non-scientific) contribution, we also extend the Hierarchical Domain Definition Language (HDDL) [H¨oller et al., 2020a] to allow the expression of FOND HTN problems, and provide the first set of benchmark problems denoted in this language for our (or future) empirical evaluations.

Overall, we introduce (to the best of our knowledge) the first planning system for HTN planning problems capable of handling some level of uncertainty while strictly adhering to the hierarchy and retaining important features such as the partial ordering of tasks. We would like to note that the AO* algorithm requires acyclic search spaces, which is why we restrict our evaluation to acyclic problems. However, none of our other contributions (i.e., the all-outcomedeterminization, the grounder, and heuristics) requires this restriction. We call our system Koala, and it is accessible at https://github.com/koala-planner/main.

2 Problem Statement

Currently, two formalizations for FOND HTN (under standard HTN semantics) exist [Chen and Bercher, 2021; 2022]. The biggest difference between the solutions put forward in 2021 and those in 2022 is that the former only considers primitive task networks as solutions, i.e., a complete and finite refinement of the initial task network. Its underlying policy just tells when each primitive task is to be executed, based on the observed outcome. This has been called outcome-dependent fixed-method policy [Chen and Bercher,

2021]. The latter version, called method-based policy, differs significantly from this since the choice of methods is postponed until primitive tasks have been executed [Chen and Bercher, 2022]. As a consequence, solutions are complex policies, not fixed task networks. Any primitive action sequence executed is still a refinement of the initial task network, but which plan that is will be decided during runtime after observing non-deterministic action outcomes. For this flexible kind of solution, two variants exist: Strong and strong cyclic policies. Strong solutions guarantee finite execution time since they prohibit cycling. Strong cyclic solutions are allowed to exploit cyclic method definitions. As a consequence, while these plans still guarantee to end up in a primitive and executable refinement eventually, it could take arbitrarily long due to unfortunate action outcomes. The definitions resemble those found in FOND classical planning [Goldman and Boddy, 1996; Pryor and Collins, 1996; Cimatti et al., 2003]. Our work aims at finding strong method-based policies for FOND HTN problems. As such, in this section, we provide the formalization introduced by Chen and Bercher [2022].

A FOND HTN domain contains all objects, relations, and valid operations on them.

Definition 1 (PlanningDomain). AFONDHTNplanning domain D is a tuple D = ⟨F, Np, Nc, δ, M⟩ where:

• F is a finite set of facts, and we define the set of states to be S := 2F ,
• N := Np ∪Nc is a finite set of primitive, Np, and compound, Nc, task names where Np ∩ Nc = ∅,
• δ : Np → A, with A ⊆ S × 22F ×2F a finite set of nondeterministic actions, is the action mapping, and
• M ⊆ Nc ×TN is a finite set of decomposition methods, where TN denotes the set of all possible task networks.

We will sometimes use the term action name and action synonymously (as it is often clear from the context which one is meant), although the former first has to be mapped to the latter via the action mapping δ. Also, note that the terms action and primitive task are used synonymously.

For each primitive task name p ∈ Np, δ defines an action δ(p) = (pre, eff ) where pre ⊆ F is the set of preconditions that must hold in order to execute the action and eff ⊆ 22F ×2F consists of a set of effect pairs of the form (add, del), with add effects add ⊆ F and delete effects del ⊆ F. For convenience, we also write pre(p) and eff (p) to refer to the preconditions and effects of an action p ∈ Np. An action p ∈ Np is executable in state s ∈ S (denoted by τ(p, s) = ⊤) if and only if pre(p) ⊆ s.

The execution of an action p ∈ Np in a state s ∈ S results in a non-deterministic state transition, defined as follows.

The tasks that need to be accomplished and their desired ordering are organized in task networks. The definition is identical to deterministic HTN planning, as it simply organizes the tasks in a partially ordered fashion, which is independent of whether actions are deterministic or not.

Definition 2 (Task Network). A task network is a tuple tn = ⟨T,≺, α⟩ where T is a finite set of task IDs, ≺ is a partial order over T , and α: T → N.

Task IDs are required to differentiate between multiple occurrences of the same tasks. Therefore, the ordering is defined on these IDs, and then α maps those IDs back to the actual tasks. Therefore, it does not matter which concrete identifiers are used for the IDs. This is captured by the definition of isomorphism (i.e., equivalence) of task networks:

Definition 3 (Isomorphism of Task Networks). Let tn1 = ⟨T1,≺1, α1⟩ and tn2 = ⟨T2,≺2, α2⟩ be two task networks. tn1 and tn2 are isomorphic (denoted tn1 ∼= tn2) if there is a bijection σ: T1 → T2 such that for all t, t′ ∈ T1 we have α1(t) = α2(σ(t′ )), and further it holds (t, t′ ) ∈ ≺1 iff (σ(t), σ(t′ )) ∈ ≺2.

Note that our definition does not incorporate so-called method preconditions [Nau et al., 2003], which provide state properties that have to hold in order to be allowed/capable of applying a method in a certain state during progression search. This is for two main reasons: (1) We base on the unaltered formalism by Chen and Bercher [2022] for which a comprehensive complexity investigation has been conducted, and (2) for the sake of simplicity because under a common interpretation of method preconditions, they can easily be compiled away by introducing a new artificial primitive task as the first task into the respective task network with the method's precondition as its precondition [H¨oller et al., 2020a]. However, despite being considered standard, this interpretation is semantically doubtful in a partial order setting (while being perfectly fine in total order), as discussed by H¨oller et al. [2020a]. Existing grounders, such as the one presented by Behnke et al., which has been employed in this paper, eliminate method preconditions.

Definition 4 (Decomposition Method). A (decomposition) method is a tuple m = ⟨c, tn⟩ where c ∈ Nc and tn is a task network.

We now define task decomposition in the context of progression search [H¨oller et al., 2018; 2020b], where only compound tasks without predecessor (in their ordering constraints) can be decomposed.

Definition 5 (Progression Task Decomposition). A method m = ⟨c, tn⟩ decomposes a task network tn1 = ⟨T1, ≺1, α1⟩ into tn2 = ⟨T2,≺2, α2⟩ if there exists an unconstrained task t ∈ T1 (i.e., there is no x ∈ T1 where (x, t) ∈ ≺) such that α1(t) = c and there is a task network tn′ = ⟨T ′ , ≺′ , α′ ⟩ with tn′ ∼= tn where T1 ∩ T ′ = ∅. The task network tn2 is defined as tn2 = ⟨(T1 \ {t}) ∪ T ′ , ≺′ ∪ ≺D, ((α1 \ {(t, c)}) ∪ α′ )⟩ where ≺D is defined as follows.

FOND HTN planning problems are defined as follows.

Definition 6 (FONDHTNProblem). AFONDHTNplanning problem P is a tuple ⟨D, tnI, sI⟩ where D is its planning domain and sI ∈ 2F and tnI are its initial state and task network, respectively.

We still need to define the set of solutions for a planning problem. Whereas in deterministic HTN planning [Geier and Bercher, 2011; Bercher et al., 2019] (or even in FOND HTN planning with fixed-methods [Chen and Bercher, 2021]), a solution is simply a fixed task network, we - for the more flexible method-based FOND solutions - require a more complex data structure, called method-based policy [Chen and Bercher, 2022]. This is a mapping from a current task network plus its state to either a primitive task (the next task to execute) or a compound task and an appropriate method (how to decompose the next compound task). After formally defining this (partial) function, we provide the criteria which of these policies are actually solutions.

Definition 7 (Method-Based Policy). A (method-based) policy π is a partial function π : TN × S → T ×M ′ where T is the union of the sets of (corresponding) tasks in the task networks of TN , and M ′ = M ∪ {ϵ} where ϵ is the reserved symbol for execution of primitive tasks.

For a policy π to be well-defined, we have to impose that for all (tn1, s1) and (tn2, s2) in the domain of π, if s1 = s2 and tn1 ∼= tn2 then tn1 = tn2.

Following a policy we get an execution trace, i.e., a sequence of task networks and states - the search nodes processed by an HTN progression planner. This is formally captured by what was called execution structure [Chen and Bercher, 2022]. In the following definition, for a task network tn = ⟨T,≺, α⟩ we use the shorthand tn \ t to denote ⟨T \ {t}, {(x, y) | (x, y) ∈ ≺ and x, y ̸= t}, α \ {(t, α(t)}⟩. Definition 8 (Execution Structure). Let P be a FOND HTN problem. Let L = ⟨U, V ⟩ be a tuple where U ⊆ TN ×S and V ⊆ (TN ×S)×(T ×M ∪{ϵ})×(TN ×S) be the minimal sets satisfying (tnI , sI ) ∈ U and:

If (tn, s) ∈ U and π(tn, s) = (t, m), then

• if t is primitive, then for all s′ ∈ γ(t, s) we have (tn \ t, s′ ) ∈ U and ((tn, s), (t, ϵ), (tn \ t, s′ )) ∈ V , and
• if t is compound, then we have (tn′ , s) ∈ U and ((tn, s), (t,m), (tn′ , s)) ∈ V , where tn′ is the result of decomposing task t in tn with method m.

The execution structure induced by a policy π is the tuple [L] = ⟨[U], [V ]⟩ where [U] is the set U quotient out by the relation (tn, s) ∼ (tn′ , s) iff tn and tn′ are isomorphic and similarly for [V ] where ((tn1, s), (t, m), (tn2, s)) ∼ ((tn′1 , s), (t,m), (tn′2 , s)) iff tn1 and tn2 are isomorphic and tn′1 and tn′2 are isomorphic.

The execution structure [L] = ⟨[U], [V ]⟩ induced by a policy π can be viewed as a directed graph where each node u ∈ [U] is a FOND HTN (sub-)problem with its own task network and state, and each transition v ∈ [V ] is an instruction on which task (either primitive or compound) must be performed in order to step toward solving the problem - see Fig. 1 for an example. This simply corresponds to all task networks a progression planner would create while following all possible outcomes of a given policy.

Given an execution structure L, we refer to (tnI , sI ) as the initial node, any node that has no outgoing edge as terminal, and terminal nodes (tn, s) where tn contains no task (also denoted by tn∅) as a goal node.

We can now define the solution criteria for FOND HTN problems. Note that we define, purely for the sake of completeness, all three standard kinds of solutions: weak, strong, and strong cyclic ones - but in this paper, we are only concerned with finding strong solutions.

Definition 9 (Weak, Strong, and Strong Cyclic Solutions). Let P be a FOND HTN problem. A policy π with execution structure L = ⟨U, V ⟩ is a weak solution to P if at least one terminal node of L is a goal node, a strong cyclic solution to P if every terminal node of L is a goal node, and a strong (acyclic) solution to P if L is acyclic, finite, and every terminal node of L is a goal node.

For weak solutions, Chen and Bercher [2022] also demand finiteness. Although we are not concerned with weak solutions, we removed this constraint as it would exclude some policies from considered weak although they admit a solution given favorable outcomes.

3 All Outcome Determinization

In this section, we show how a FOND problem can be turned into a deterministic problem serving as problem relaxation, meaning that the set of solutions of the deterministic problem is a superset of the (traces of the) solutions of the nondeterministic one. We believe that this transformation has multiple practical applications in FOND HTN planning, two of which are proposed in this paper. There might also be further theoretical applications as evidenced by one result relying on it already. Chen and Bercher [2021] used it for the less flexible HTN formalization (of fixed-method policies) to prove their Lemma 4.3 which relates this problem relaxation to weak solutions. Since we now build on it in a more significant way we present it in more technical detail and state important theoretical properties.

A core idea behind the transformation is the so-called all-outcome-determinization, which is well known in nonhierarchical planning and has been used, among others, in FF-replan for probabilistic planning problems [Yoon et al.,

2007]. The transformation extends these ideas to make it work in the hierarchical setting.

FOND problems are often represented as an AND/OR graph (also known as a hypergraph) [Bonet and Geffner, 2000], which is a generalization of a canonical graph that allows multiple connections using a single edge.

Definition 10 (Hypergraph). A hypergraph is a tuple G = (V,E) where V is a set of vertices and E ⊆ V × 2V is a set of connectors. A k-connector is a connector in a hypergraph G such that (v, V ′ ) ∈ E where |V ′ | = k.

Intuitively, the transformation converts all k-connectors in a search space to k 1-connectors, thus sacrificing the "AND" semantics and relaxing it into an "OR" semantics.

Formally, for any non-deterministic primitive task p ∈ Np (i.e., we require |eff (p)| ≥ 2) we construct a set of deterministic actions Ap := {(pre(p), add, del) | (add, del) ∈ eff (p))} and redefine p to now be a compound task with |Ap| methods where each method decomposes the task into one of the actions in Ap. We use the notation Nnd to refer to non-deterministic action names in a domain. Formally, Nnd := {p | p ∈ Np, |eff (p)| ≥ 2}. Furthermore, without loss of generality, we assume the existence of an injective labelling function, β : Nnd × (2F × 2F ) → Sym, that, given a non-deterministic action name and one its effects, provides a unique symbol to be used as a name, where Sym ∩ N = ∅. More precisely, if p ∈ Nnd and e ∈ eff (p), then β(p, e) = s for some s ∈ Sym, acting as a new task name.

Given that we now deal with deterministic domains, the definition of action mappings is slightly altered. Now, an action mapping δ : N → 2F × 2F × 2F maps to a 3-tuple.

Definition 11 (All-Outcome-Determinized Relaxation). Let D = ⟨F,Np,Nc, δ,M⟩ be a FOND HTN domain and Nnd be its set of non-deterministic action names. Then, the all-outcome-determinized relaxation of D is D′ = ⟨F, N ′p , N ′c , δ′ , M ′ ⟩, a deterministic HTN domain, where:

• N ′p = (Np \ Nnd) ∪ {β(p, e) | p ∈ Nnd, e ∈ eff (p) }
• N ′c = Nc ∪ Nnd,
• For all n ∈ N we define δ′ (n) = (pre(n), add, del), where e = (add , del ) with e ∈ eff (p), and either n ∈ Np \Nnd (n is already deterministic), or p ∈ Nnd, β(p, e) = n (new action per effect).
• M ′ = M ∪ {(p, ⟨{p}, ∅, {(p, β(p, e))}⟩) | p ∈ Nnd, e ∈ eff (p)}

The corresponding planning problem can be defined without further changes:

Definition 12 (All-Outcome-Determinized Problem). Let ⟨D, sI , tnI⟩ be a FOND HTN problem and D′ be the determinization of D. Then, the all-outcome determinization of P is the (deterministic) problem P ′ = ⟨D′ , sI , tnI ⟩.

As mentioned before, the core idea behind this encoding was introduced before, where polynomial runtime was stated [Chen and Bercher, 2021, Lemma 4.3]. Since this useful problem encoding was a bit "hidden" in a (short) proof, we make aware of its formal properties more prominently, and provide tighter properties as well.

Proposition 1. Let P be a FOND HTN planning problem and P ′ its deterministic version. Then, P ′ can be computed in time linear to the count of non-deterministic effects.

Our definitions are provided, for the sake of simplicity, on a fully propositional level. However, we would like to stress that the transformation also works on a lifted level, and also requires only linear runtime to compute. This is because one can still turn a single non-deterministic action with n effects into n deterministic actions (with its accompanying n methods) - whether these actions are ground or lifted is irrelevant.

We now prove a novel result that will prove useful for several possible applications, such as its usage for heuristics and grounding: The transformation is a problem relaxation.

Theorem 1. Let P be a FOND HTN problem and P ′ be its all-outcome-determinization. Let π be a strong or strong cyclic policy. Then, each execution trace tr1 = ⟨(tn1, s1), (t1,m1)⟩, ..., ⟨(tnk, sk), ∅⟩ with (tn1, s1) = (tnI, sI) and tnk = tn∅ following π corresponds to a sequence of progressions tr2 = ⟨(tn1, s1), (t′1 ,m′1 )⟩, ..., ⟨(tn′k′ , sk′), ∅⟩ with |tr2| = k′ ≥ k = |tr1| for P ′ . More precisely: Let t1 = p1, . . . , pk be the primitive task (name) sequence induced by tr1. Then, the task name sequence t2 = p′1 , . . . , p′k induced by tr2 is a (classical) solution to P ′ and it holds:

• If pi ∈ Np \Nnd, then p′i = pi.
• If pi ∈ Nnd and its effect eji ∈ eff (pi) produced the respective successor state, then p′i = β(pi, eji ).

Proof. By construction, every method for a compound task in P exists in P ′ and is hence still applicable there. The same applies to primitive deterministic actions. The only case to look closely at is the application of a non-deterministic action. If however, the trace contains a progression from a nondeterministic action p to a new state s, then this is due to some specific non-deterministic effect e ∈ eff (p). Then, by construction, the action β(p, e) leads to s.

This implies that whenever there exists a weak, strong, or strong cyclic solution, the all-outcome-determinized problem also has a solution, which enables us to use it as a problem relaxation, as exploited by, e.g., heuristics and a grounder.

4 Grounding Procedure

While most planning systems - both in classical as well as in HTN planning - work on a propositional model, the domains are commonly expressed in a lifted representation with variables to abstract over concrete object instances, such as PDDL for classical models [Fox and Long, 2003] or HDDL for (deterministic) hierarchical ones [H¨oller et al., 2020a]. The extension is conceptually very simple: every fact, task, and method now has a sequence of (typed) variables which may be instantiated by a (type-conforming) constant. An example, provided in the HDDL syntax, is provided in Fig. 2. Examples for valid groundings are provided later.

The process of turning a lifted model into a propositional one is called grounding. A ground domain can be obtained by instantiating all variables. However, in practice, naive instantiation would result in an exponential number of propositions.

Thus, most planners utilize a more sophisticated grounding procedure that exploit reachability analyses and in case of HTN planning further exploit the task hierarchy in a nontrivial manner [Behnke et al., 2020].

In order to ground a FOND HTN problem, instead of creating an entirely new approach to deal with the additional challenges of dealing with non-determinism in the context of HTN planning, we propose to exploit the all-outcomedeterminization and thereby, existing - and future - HTN grounding technology. Our algorithm resembles the approach by Scala and Vallati [2021] that infers a grounding for PDDL+ using classical grounders. The procedure is as follows: First, Compute the all-outcome-determinized relaxation as defined in Def. 11 on the lifted model, then use an existing oracle (i.e., any deterministic HTN problem grounder) to obtain a ground representation of the determinized problem. And finally, re-infer a valid (overapproximation) grounding of the original model based on the grounding of the determinized model. When we say "valid" grounding, then we mean any grounding that (i) is in line with all constraints (this is trivial, e.g., respecting type constraints of variables and constants) and, more importantly, (ii) no grounding is missing, i.e., that any ground instance (of any domain element, like action, method, etc.) that could be part of a solution is part of the grounding.

Before we provide our procedure in pseudo code, we explain it using an illustrative example that also semi-informally introduces the formalization as required for our purposes.

Consider the following non-deterministic action, Lift, expressed in our extension of HDDL (Fig. 2). The new "oneof" keyword allows us to define mutual exclusion on effects, mirroring the approach adopted in extending PDDL for non-deterministic effects [Bertoli et al., 2003].

(:action Lift :parameters (?h - hoist ?c - crate) :precondition (reachable ?h ?c) :effect (oneof (lifting ?h ?c) (not (lifting ?h ?c)) ) )

To go through the grounding process, assume that we have two hoists (h1 and h2) and also two crates (c1, c2). So in total, four groundings exist in the worst-case, leading to the four ground actions Lift[h1, c1], Lift[h1, c2], Lift[h2, c1], and Lift[h2, c2]. The all-outcomedeterminization (run on the lifted model) will create two lifted actions Lift-eff1[?h, ?c] and Lift-eff2[?h, ?c], and so we will get at most eight ground actions for the determinized problem (four for each).

Suppose the black-box grounder (for deterministic planning) rules out two groundings for Lift-eff1[?h, ?c] and even three for Lift-eff2[?h, ?c], resulting in the following remaining ground instances:

• Lift-eff1[h1,c2], Lift-eff1[h2,c2]
• Lift-eff2[h2,c2]
• we also have 2 ground compound tasks (Lift[h1,c2] and Lift[h2,c2]), and 3 ground methods (one for Lift[h1,c2] and two for Lift[h2,c2], one for each reachable effect)

At this point we could stop and use the two identified groundings [h1,c2] and [h2,c2] for the ground nondeterministic action. However, we can do even better.

Notice that the grounding [h1,c2] only appears in one of the two effects of our non-deterministic action. However, according to the definition of strong (or strong cyclic) policies, every outcome must eventually lead to a solution. Due to Thm. 1 we know that the corresponding action would be used in some solution. Since we know that this is not the case (as the respective grounding wasn't computed), we can conclude that Lift[h1,c2] cannot be part of any strong (or strong cyclic) policy. We can hence discard this grounding and identified only a single (of four possible) one: Lift[h2,c2]. The procedure is summarized in Alg. 1.

Algorithm 1: FOND Grounding Procedure

• Input: P , a lifted FOND HTN planning problem; P ′ , its (lifted) all-outcome-determinisation; G′ , a valid grounding of P ′ Output: G, a valid grounding of P 1 Let G be an empty set of groundings. 2 Let Nnd be the set of names of actions with more than one effect in the domain of P. 3 foreach C[o1, o2, ..., ok] in ground compound tasks of G′ do 4 if C ∈ Nnd then 5 If the number of ground methods in G′ that decompose C[o1, o2, ..., ok] is equal to |eff (n)| in the original lifted domain, add [o1, o2, ..., ok] to G as a valid grounding for the non-deterministic action that corresponds to C. 6 else // a "normal" compound task 7 add C[o1, o2, ..., ok] and all of its methods to G. 8 Copy all remaining groundings in G′ (those not covered in the previous loop, i.e., actions) to G. 9 return G

From the arguments above, especially by exploiting Thm. 1, we can conclude:

Proposition 2. The grounding procedure described in Alg. 1 is correct, i.e., no grounding of tasks, methods, etc. that could be part of any strong (or strong cyclic) policy will be missing in its output.

5 Search Algorithm

While there are several algorithms to search for a solution in a hypergraph [Bonet and Geffner, 2005], we propose to use the AO* algorithm [Nilsson, 1982; Edelkamp and Schr¨odl, 2012] to find a strong solution to a FOND HTN problem (cf.

Alg. 2). This heuristic search algorithm explores an acyclic hypergraph gradually extending the best (strong) policy.

Algorithm 2: AO* Search

Input: an acyclic FOND HTN planning problem P = ⟨D, tnI , sI ⟩. Output: a solution to problem P or "No Solution" 1 V ← {⟨tnI, sI⟩}, E ← ∅, G← (V,E) 2 cost(⟨tnI, sI⟩) ← 0, label(⟨tnI, sI⟩) ←"Ongoing" 3 while label(⟨tnI, sI⟩) /∈ {"Solved", "Failed"} do 4 πp ←G 5 if there are markers in G then 6 πp ← the marked subgraph of G 7 n←a random unexpanded node of πp 8 succ(n) ← expand(n) 9 foreach SN i ∈ succ(n) do 10 foreach ⟨tn, s⟩ ∈ SN i do 11 if ⟨tn′ , s⟩ ∈ V for some tn′ ∼= tn then 12 Change the pointer to ⟨tn, s⟩ in SNi to its equivalent search node in V . 13 else 14 cost (⟨tn, s⟩) ← h(⟨tn, s⟩) 15 V ← V ∪ {⟨tn, s⟩} 16 E ←E ∪ {(n, SNi)} 17 W ← {n} 18 while W ̸= ∅ do 19 q ← a node x ∈ W such that x does not have any descendants inW 20 if isTerminal?(q) then 21 label (q) = "Failed" 22 if isGoal ?(q) then label (q) = "Solved" 23 W ←W ∪ predecessors(q) 24 else 25 if all successors of q are terminal then 26 label (q) ← "Failed" 27 if there is a "Solved" successor then 28 label (q) ← "Solved" 29 W ← W ∪ predecessors (q ) 30 best ← argmin({cost(x) | x ∈ succ(q)}) 31 cost (q) ← cost (best) 32 mark(q, best) 33 if label(⟨tnI, sI⟩) = "Solved" then 34 return πp 35 else 36 return "No solution"

The algorithm is a loop consisting of two steps: Lines 516 expand the frontier of the search, and Lines 17-32 do a backward cost revision. Note that, in Line 11 when checking for equivalence between a new search node ⟨tn, s⟩ ∈ SNi and explored nodes V , in the case where states are equal, we have to check for isomorphism between task networks (cf. Def. 8). This is a costly operation (it is not yet known whether a poly-time procedure exists), and in order to avoid a complete search for bijection, we first use the over-approximation algorithm introduced by H¨oller and Behnke [2021] to quickly rule out task networks that cannot be isomorphic. The expansion step performed in Line 8 is presented in Alg. 3.

Algorithm 3: Node Expansion

Input: task network tn, and state s Output: all possible progressions of tn 1 (Up,Uc) ← unconstrained(tn), SN ← ∅ 2 foreach t ∈ Uc do 3 foreach m ∈ t .methods do 4 tn′ ← tn.decompose(t , m) 5 SN ← SN ∪ {{⟨tn′ , s⟩}} 6 foreach t ∈ Up do 7 foreach a ∈ Np do 8 if τ (a, s) = ⊤ then 9 ⟨tn′ , S′ ⟩ ← tn.apply(a) 10 SN ← SN ∪ {{⟨tn′ , s′ ⟩ | s′ ∈ S′ }} 11 return SN

The AO* algorithm is known to terminate with an optimal solution (defined as the minimum sum of transition costs) under the following conditions [Nilsson, 1982]: (i) There is a solution graph from the initial node to a set of goal nodes, (ii) for all search nodes, h(n) ≤ h∗ (n) where h∗ (n) is the actual distance of node n to its nearest goal node (admissibility), and (iii) for all search nodes, h(n) ≤ c + h(n1) + ... + h(nk) where n1, ..., nk are the successors of n (in the same connector) and c is the connector cost (monotonicity).

For the first condition it is known for deterministic HTN planning that a goal node, if one exists, can be reached via a sequence of progressions [Alford et al., 2012; H¨oller et al., 2020b]. Alg. 3 is an adaptation of progression-based expansion to non-deterministic settings where line 10 forces the algorithm to solve for all states that result from executing a non-deterministic action. Criteria (ii) and (iii) would have to be ensured by the deployed heuristic.

6 AGeneric Approach to Use Deterministic HTN Heuristics in FOND HTN Planning

Even in deterministic HTN planning, there are only three heuristics available as of now [Bercher et al., 2017; H¨oller and Bercher, 2021; H¨oller et al., 2020]. Although they are all specifically designed for HTN planning, the most successful approach is one that re-uses existing heuristics for (nonhierarchical) classical planning [H¨oller et al., 2018; 2020b]. It relaxes a given HTN search node into a classical planning problem and then deploys an existing classical heuristic to it. Our proposal for obtaining FOND HTN heuristics bases on the very same idea.

Given a FOND HTN search node, we turn it into a deterministic one by using the all-outcome-determinization put forward in Section 3. Then, instead of developing novel heuristics for FOND HTN planning, we can use any from deterministic HTN planning. By transitivity (i.e., by using the encoding by H¨oller et al., 2018; 2020b), we can even use classical heuristics to guide search in the FOND HTN setting.

Theorem 2. The all-outcome-determinization preserves safety, goal-awareness, and admissibility of deterministic HTN heuristics.

Proof. Let h be a deterministic HTN heuristic, P be a FOND HTN problem, and P ′ be its all-outcome-determinized relaxation. Safety means that if h(n) = ∞, then h∗ (n) = ∞. This follows directly from Theorem 1, as it implies that P ′ is a problem relaxation. Goal awareness means that if n is a solution, we get h(n) = 0. If a FOND search node is a solution, it is by definition empty, in which case the encoding will also be empty. We thus get h(n) = 0 since h is goal-aware by assumption. Admissibility means that h(n) ≤ h∗ (n) for all search nodes n. This also follows from Theorem 1 (combined with h being admissible by assumption).

7 Experimental Results

We evaluated our system using the following configuration: We used our proposed grounding procedure (Alg. 1) with the deterministic HTN grounder by Behnke et al. [2020] as our oracle. For the required heuristic, we again used our proposed approach that makes deterministic hierarchical planning heuristics available to the FOND setting using a cascade of problem relaxations. More precisely, we use the RC Max , RC FF , and RC Add heuristics [H¨oller et al., 2018; 2020b] on the all-outcome-determinization, which in turn relax the respective deterministic HTN problem into a classical problem and then use the classical planning heuristics Max [Bonet and Geffner, 1999], FF [Hoffmann and Nebel, 2001], and Add [Bonet and Geffner, 2001], respectively. We configured our heuristic to use action costs of one for each action from the HTN model (including those encoding method preconditions) and zero for each of the actions compiled by the RC encoding. Heuristics thus estimate final plan length (including method preconditions). Our implementation is a new system, called Koala, implemented in Rust (see Introduction for a link).

For the benchmarks, we have created five novel FOND domains with 15 instances each 1 , all based on the hierarchical track of the International Planning Competition (IPC) 2020. All of them are totally ordered, but only two domains have exclusively totally ordered initial task networks, making the problems totally ordered (namely Childsnack and Depot), so the rest is partially ordered. All domains are acyclic. We use the Agile IPC Score 2 to assess our planner. We ran our experiments on a machine running Ubuntu 22.04 with one CPU core (Intel i7 13700), 8GB of RAM, and a 30 minute cut-off time. A summary of the result is provided in Table 1. All failed instances are a result of timeout. The characteristics (and modifications) of the domains are as follows. In our version of Depots, hoists are human-operated, and junior operators may fail to load/unload a truck. In case of failure, a supervisor must be called to assist in the operation. The main characteristic of this domain is that unfavorable outcomes are fixed in a few steps. In the Satellite domain, the phenomenons of interest may not be stationary. In the latter case, the motion trajectory must be calculated and compensated for by the satellite. This domain illustrates cases where the uncertainty can be eliminated by taking uncertainty-reducing actions such as observing the movement pattern at execution time. ChildSnack is modified so the tray may get dirty and require washing in the kitchen. In the new Rover domain, the camera may not be able to take an image. Thus, the rover must report this incident for new instructions. Finally, we have modified Transport such that the package recipient may not be at home, in which case the truck driver(s) cannot unload the package. Thus, unfavorable outcomes lead to the accumulation of packages in trucks, triggering capacity constraints.

1 All of the problems, and their respective domains are available at https://github.com/koala-planner/domains.

2 Given a maximum of T seconds to solve a problem, the score for a problem that is solved within 1 second is 1, within t seconds (1 < t ≤ T) is 1 - log t logT , and 0 otherwise. The final score for a domain is the sum of scores for all of the problems in that domain.

As for the first step, grounding was always possible within at most 8 seconds (including the time that PANDA's grounder needed for a determinized problem), also for the unsolved ones. As a matter of fact, most problems were grounded in less than a second. More interestingly, the overhead added by our grounding procedure on top of that of the black-box grounder was at most 1 second, which is thus negligible. This is hardly surprising because investigating Alg. 1 shows that its runtime is linear in the number of groundings produced by the deterministic base-grounder. So, in total, we showed that our procedure can successfully make use of deterministic grounders with almost zero overhead.

The next step, i.e., the search, has more interesting results. The performance of the algorithm varies on two axes: the intrinsic difficulty of a problem in a particular domain (i.e., branching factor and solution depth) and the choice of heuristic function for the relaxed problem. The intrinsic difficulty is captured by the IPC Score and the number of solved instances as reported in Table 1. The details of our experimental setup is available online [Yousefi and Bercher, 2024]. The choice of a heuristic function (in our case RC Max , RC FF , and RC Add ) has an impact on the performance of the algorithm. There were cases where the algorithm with one heuristic was able to solve a particular problem, while it could not with the others. This is noticeably reflected in the average solution structure in the transport domain where a particularly difficult instance was solved only with the Add heuristic. However, the total number of solved problems for each domain were almost the same. The time needed to compute the RC Add and RC Max heuristics are significantly less, allowing the algorithm to reach more depth in the search graph and explore more nodes. However, the cost of this property is usually decreased accuracy.

In conclusion, our investigation suggests that even though FOND HTN planning in theory seems intractable (more specifically of higher complexity classes than their deterministic counterparts [Chen and Bercher, 2021; 2022]), a great deal of problems can be solved within the practical constraints of the IPC.

8 Conclusion

We addressed a critical gap in the field of HTN planning by laying the foundational groundwork for tackling problems in non-deterministic domains. Since there was no approach available to solve FOND HTN problems, we had to provide the entire infrastructure, including a grounder, search procedure, and heuristics. Specifically, we provided a problem encoding that relaxes FOND HTN problems to deterministic ones that serves as the basis for using existing deterministic grounders in the FOND setting as well as existing HTN or classical heuristics. Due to non-existing competitors, we could not compare against existing approaches, but our evaluation showed that grounding is efficient and problems of realistic size can be solved within the constraints of the IPC.

Acknowledgements

Pascal Bercher is the recipient of an Australian Research Council (ARC) Discovery Early Career Researcher Award (DECRA), project number DE240101245, funded by the Australian Government.