Delete Relaxations for Planning with State-Dependent Action Costs

1 Introduction

Many extensions have been made to the Planning Domain Definition Language (PDDL), not only to allow for more expressivity but also to achieve a modeling of domains which is closer to the real world. Some of these extensions allow domains with state-dependent action costs (SDAC) [Ivankovic et al., 2014], for example unrestricted numeric PDDL [Fox and Long, 2003] or PDDL3 [Gerevini et al., 2009]. E. g., SDAC allow representation of the fuel consumption of a car that depends on its speed and its weight more compactly than with state-independent costs. Ivankovic et al. [2014] analyze the power supply restoration domain, where the objective is to minimize the unsupplied load at each plan step and the cost is modeled by a finite sum of conditional costs over the state variables. They simplify the problem by assuming minimal constant action costs and compute an optimal plan for the simplified problem. If the assumed minimal cost is unattainable in the original problem, they split the action into two copies and repeat the first step on the modified problem. Unfortunately, they report that the heuristic is not time-efficient, and as a result blind search solves more problems than search with their heuristic. Another class of problems exists in planning with Markov Decision Processes (MDPs), where costs (or rewards) are associated to pairs of actions and states.

In this work we consider action cost functions, representable by simple enumerations of their values, using function terms, or compactly by decision diagrams. For our purposes so-called edge-valued multi-valued decision diagrams (EVMDDs) [Lai et al., 1996; Ciardo and Siminiceanu, 2002] are most convenient, because they allow us to detect, exhibit and exploit structure in the cost function. After introducing the formal background we propose a na¨ıve compilation into tasks with state-independent action costs. This compilation is infeasible, since it generates exponentially many actions, but can serve as a baseline for more sophisticated approaches. Based on the structure of the EVMDD we introduce a novel compilation technique, which greatly reduces the number of additional actions. Finally, we avoid compilation altogether by integrating the structure of the EVMDD in the relaxed planning graph (RPG), and show the correctness of this approach. We apply this procedure to the ACADEMIC ADVISING domain [Guerin et al., 2012] and compare the results with the standard heuristic of the PROST planner [Keller and Eyerich, 2012], a state-of-the-art planning system for MDPs. We conclude with some remarks about future work.

2 Preliminaries

In this section, we introduce planning tasks with SDAC, recall the definition of the additive heuristic in classical planning, and extend it to tasks with SDAC.

2.1 Planning with State-Dependent Action Costs

We extend the definition of SAS+ planning tasks [B¨ackstr¨om and Nebel, 1995] to take SDAC into account.

Definition 1. A planning task with SDAC is a tuple Π = (V,A, s0, s⋆, (ca)a∈A) consisting of the following components: V = {v1, . . . , vn} is a finite set of state variables, each with an associated finite domain Dv = {0, . . . , |Dv| - 1}. A fact is a pair (v, d), where v ∈ V and d ∈ Dv, and a partial variable assignment s over V is a consistent set of facts. If s assigns a value to each v ∈ V, s is called a state. Let S denote the set of states of Π. A is a set of actions, where an action is a pair a = 〈pre, eff〉 of partial variable assignments, called preconditions and effects. The state s0 ∈ S is called the initial state, and the partial state s⋆ specifies the goal condition. Each action a ∈ A has an associated cost function ca : S → N that assigns the application cost of a to all states where a is applicable, and arbitrary values to all other states.

For propositional variables, i.e. variables v with Dv = {0, 1}, we write v and ¬v for (v, 1) and (v, 0), respectively. For states s, we use function notation s(v) = d and set notation (v, d) ∈ s interchangeably. Typically, each cost function ca will be specified as a function term that only depends on a subset of the state variables, which we denote by supp(a) = {va 1 , . . . , va ka} ⊆ V. 1 It will then be convenient to think of ca as a function ca : D1 × · · · ×Dka → N where Dj is the domain of va j , j = 1, . . . , ka . Let Sa be the set of all valuations of the variables occurring in ca, i.e., the set of all possible argument tuples of ca, let Fa = ⋃ˆ s∈Sa ˆ s be the set of all facts (v, d) for v ∈ Sa and d ∈ Dv, and let pvars(a) be the set of variables mentioned in the precondition of action a. Throughout the paper, we assume without loss of generality that supp(a) ∩ pvars(a) = ∅. This assumption is warranted since, whenever a variable v occurs in the precondition of a, its value d is fixed in every application of a and the value d can be plugged into the cost function ca, thus making ca independent of v.

The semantics of planning tasks are as usual: An action a is applicable in state s iff pre ⊆ s. Applying action a to s yields the state s′ with s′ (v) = eff(v) where eff(v) is defined and s′ (v) = s(v) otherwise. We write s[a] for s′ . A state s is a goal state if s⋆ ⊆ s. We denote the set of goal states by S⋆. Let π = 〈a0, . . . , an-1〉 be a sequence of actions from A. We call π applicable in s0 if there exist states s1, . . . , sn such that ai is applicable in si and si+1 = si[ai] for all i = 0, . . . , n - 1. We call π a plan for Π if it is applicable in s0 and if sn ∈ S⋆. The cost of plan π is the sum of action costs along the induced state sequence, i.e., cost(π) = ca0 (s0) + · · · + can-1 (sn-1).

Dealing with SDAC in an explicit-state forward search is straightforward, since upon expansion of a state s, determining the relevant action cost values amounts to a simple function evaluation. However, if the search is guided by a domainindependent distance heuristic h, the action costs should also be correctly reflected by the h values assigned to states. This is where complications arise, at least for delete-relaxation heuristics [Bonet et al., 1997; Bonet and Geffner, 1999; 2001] such as the additive heuristic hadd .

2.2 Delete-Relaxation Heuristics

A delete-relaxation of a planning task ignores delete effects, which translates to allowing state variables to hold several values simultaneously. Thus, in the relaxed version of an SAS+ planning task, state variables accumulate their values rather than switching between them.

1 There can also be variables within supp(a) that have no influence on the cost of a. E.g., for ca = B+A-A2 and DA = {0, 1}, A ∈ supp(a), although A and A2 cancel out and ca is in fact independent of the value of A. We accept this since a more "semantic" definition of the support easily becomes computationally intractable.

Formally, a relaxed planning task with SDAC Π+ consists of the same variables V, the same actions A, and the same goal condition s⋆ as the unrelaxed task Π. A relaxed state s+ now assigns to each v ∈ V a non-empty subset s+(v) ⊆ Dv. The set S+ is the set of all relaxed states, and for s ∈ S, s+ ∈ S+ we say that s+ subsumes s iff for all v ∈ V, s(v) ∈ s+(v). An action a = 〈pre, eff〉 is relaxed applicable in s+ iff pre(v) ∈ s+(v). Applying a in s+ results in s+′ with s+′ (v) = s+(v) ∪ {eff(v)} if eff(v) is defined and s+′ (v) = s+(v) otherwise. The initial state s+0 assigns to each variable v the singleton set {s0(v)}. Relaxed plans are then defined in the obvious way. What is still missing from this definition is the extension of the action cost function to relaxed states. Here, we define the cost of a in s+, ca(s+), in a natural way as the minimal cost ca(s) for any unrelaxed state s that is subsumed by s+. The problem with this definition is not that much a conceptual, but rather a computational one. With n state variables, there can be exponentially many unrelaxed states s subsumed by s+. In this paper we present a representation of cost functions that is typically (although not always) compact and that allows a simple computation of ca(s+) and a simple integration into the RPG.

Delete-relaxation heuristics can be generalized to tasks with SDAC: For h+ , generalization is straightforward: h+ (s) is the cost of a cost-minimal relaxed plan starting in s+. However, the computation of the generalized h+ heuristic is still NP-hard, as it is already for classical planning [Bylander, 1994]. Thus, we also want to generalize approximations to h+ , such as hadd and hmax , to tasks with SDAC. In the following, we discuss hadd and leave a detailed discussion of hmax for future work. For a fact f = (v, d), let A(f) be the set of achievers of f, i.e., the set of actions a = 〈pre, eff〉 ∈ A with f ∈ eff. Then for classical planning, hadd is defined as follows [Bonet et al., 1997; Bonet and Geffner, 1999]:

where sp stands for a partial state, f for a fact, pre(a) for the precondition of a, and ca is the state-independent cost of a. A natural generalization to SDAC should, in case (3), minimize over all achievers a of f and over all possible situations where a is applicable. 2 Thus, cases (1) and (2) remain unchanged, and case (3) is replaced by case (3′ ) below. Then:

2 Consider state s with s(A) = s(B) = 0, actions a1 = 〈∅, B〉 with ca1 = 2 - 2 · A and a2 = 〈∅,A〉 with ca2 = 1. We can achieve B at cost 2 in one step, or at cost 0 + 1 = 1 in two steps if hadd s (A) = 1 and we take this hadd value into account.

The only difference between Equations (3) and (3′ ) is the replacement of the constant ca by the term C a s . Obviously, if ca is a constant function, as in classical planning, C a s = ca(∅) + hadd s (∅) = ca, and for classical tasks, our generalized definition of hadd becomes the standard definition again. The central new challenge is the efficient computation of C a s . Unfortunately, the number of states in Sa is exponential in the number of variables in supp(a), and in general, C a s cannot be additively decomposed by the variables in supp(a). However, we can represent ca and C a s with the help of edgevalued decision diagrams such that ca and C a s are efficiently computable in the size of the decision-diagram representation and that the size of the representation itself is, although exponentiality in the size of supp(a) cannot be avoided in general, compact in many "typical", well-behaved cases.

2.3 Edge-Valued Decision Diagrams

Each action cost function ca : D1 × · · · ×Dn → N over variables V = {v1, . . . , vn} with domains Dv = {0, . . . , |Dv| - 1} can be encoded as an edge-valued multi-valued decision diagram (EVMDD) [Ciardo and Siminiceanu, 2002]. Formally, we use a definition of EVMDDs similar to the EVBDD definition by Lai et al. [Lai et al., 1996].

Definition 2. An EVMDD over V is a tuple E = 〈κ, f 〉 where κ ∈ Z is a constant value and f is a directed acyclic graph consisting of two types of nodes:

1. There is a single terminal node denoted by 0.
2. A nonterminal node v is a tuple (v, χ0, . . . , χk, w0, . . . , wk) where v ∈ V is a variable, k = |Dv| - 1, children χ0, . . . , χk are terminal or nonterminal nodes of E and w1, . . . , wk ∈ Z, w0 = 0.

We refer to the components of v as v(v), χi(v) and wi(v). Edges of E between parent and child nodes are implicit in the definition of the nonterminal nodes of E. The weight of an edge from v to χi(v) is wi(v). The following definition specifies the arithmetic function denoted by a given EVMDD.

Definition 3. An EVMDD E = 〈κ, f〉 denotes the arithmetic function κ + f where f is the function denoted by f . The terminal node 0 denotes the constant function 0, and (v, χ0, . . . , χk,w0, . . . ,wk) denotes the arithmetic function over S given by (I) f(s) = fs(v)(s) + ws(v), where fs(v) is the arithmetic function denoted by child χs(v). We write E(s) for κ + f (s).

In the graphical representation of an EVMDD E = 〈κ, f〉, f is represented by a rooted directed acyclic graph and κ by a dangling incoming edge to the root node of f . The terminal node is depicted by a rectangular node labeled 0. A nonterminal node is a tuple (v, χ0, . . . , χk,w0, . . . ,wk), where v is the node label, χ0, . . . , χk are the subgraphs rooted at v, and w0, . . . ,wk are the weights assigned to the edges of v. Edge labels d are written next to the edges, edge weights wd in boxes on the edges, d = 0, . . . , k. For fixed variable orders, reduced and ordered EVMDDs are unique [Ciardo and Siminiceanu, 2002]. However, in our application, we do not care about uniqueness, and we can even use different, appropriate variable orderings for different cost functions. Notice that, for appropriate variable orders, the encoding size of an EVMDD Ea for cost function ca is polynomial in the number of variables in supp(a) for many types of cost functions: For ∑nj=1 κjvj with natural coefficients κj it is linear, and for general multivariate polynomials over supp(a), it is still only exponential in the size of the largest cluster of variables from supp(a) that are interdependent in ca.

Example 1. Consider the action cost function ca = AB2 + C + 2 with DA = DC = {0, 1}, and DB = {0, 1, 2}.

Depicted is an EVMDD for ca and the variable ordering A,B,C. To see how the EVMDD encodes the cost function ca, consider the valuation s with s(A) = 1, s(B) = 2 and s(C) = 0. Traversing the corresponding edges in the EVMDD from top to bottom and adding up the edge weights, we arrive at the resulting value 6, which is exactly ca(s).

EVMDDs are suitable for the encoding of ca since the evaluation of an EVMDD is straightforward both in unrelaxed and in relaxed states. Let Ea be an EVMDD encoding ca. For an unrelaxed state s, ca(s) can be read from Ea as the path cost of the unique EVMDD path corresponding to s, Ea(s). For a relaxed state s+, ca(s+) can be determined by traversing Ea in a topological order, only following edges "subsumed" by s+, and minimizing over accumulated costs of multiple incoming arcs of the same decision node:

Definition 4. Similar to Definition 3, we can define the arithmetic function denoted by E for relaxed state s+ by replacing Equation (I) with (II) f(s+) = mind∈s+(v)(fd(s+) + wd). We write E(s+) for κ + f(s+).

Theorem 1. Ea(s+) = ca(s+) for action cost function ca, EVMDD Ea for ca, and relaxed state s+ over supp(a).

Proof sketch. States subsumed by s+ correspond to paths in Ea minimized over in the definition of Ea(s+).

This shows that EVMDDs allow an efficient computation of ca values of unrelaxed and relaxed states. In order to show that EVMDDs can also be used to compute C a s , we need to incorporate hadd s values into Ea. To do this correctly, it is necessary that on each path through Ea, each variable in supp(a) is tested, since otherwise the hadd s values of facts for variables skipped on some branch would not be included there. Hence, in the following we assume that Ea includes branches over all variables on all paths, even if this does not affect the value of Ea. In the EVMDD from Example 1, this means that there is also a test branching over variable B instead of the edge from A immediately to C, where all three B branches have weight 0. We call such an Ea quasi-reduced and note that turning a given reduced EVMDD into this form only leads to a polynomial blowup in the worst case.

3 Action Compilations

A simple way of getting rid of SDAC in a principled manner is by translating Π into an equivalent task where action costs are state independent, and then to evaluate h on the compiled task. In this section, we discuss two such compilations.

3.1 Basic Action Compilation

In the basic compilation, each action a is transformed into multiple actions aˆ s , corresponding to the valuations ˆ s of the variables occurring in ca, such that aˆ s is only applicable in ˆ s. Formally, for every assignment ˆ s ∈ Sa, an action aˆ s = 〈pre(a) ∧ ∧f∈ˆ s f, eff〉 with cost c(aˆ s ) = ca(ˆ s) is added to the compiled task, where pre(a) is the precondition of a. We call this the basic compilation scheme (BC). It is not hard to see that this leads to an exponential blowup in the number of variables in supp(a), as discussed by Ivankovic et al. [2014].

Example 2. Consider again action a with ca = AB2 +C+2 as defined in Example 1. Applying BC on a results in

On the other hand, the basic compilation scheme produces the desired hadd values.

Theorem 2. Let Π be a task with SDAC and Π′ its BC compilation. Let s be a state of Π and hadd and hadd orig the generalized and original additive heuristics for tasks Π and Π′ , respectively. Then hadd (s) = hadd orig (s).

Proof sketch. Follows from the original and generalized definitions of hadd and of the BC compilation, as states ˆ s correspond uniquely to actions ˆa in the basic compilation.

Instead of further studying BC, we only treat it as a baseline approach and define a more compact EVMDD-based compilation instead.

3.2 EVMDD-Based Action Compilation

To compute the cost of a state in the EVMDD, one has to sum up the costs of the edges on the path from the root node to the terminal node. The key insight is that the edges in the EVMDD can be thought of as auxiliary actions with stateindependent constant costs that are only allowed to be applied if the tested state variable has the value corresponding to the edge. Based on this observation we compile the structure of the EVMDD into auxiliary actions. To that end, we introduce an additional auxiliary variable auxa for each original action a that keeps track of where we currently stand in the evaluation of the corresponding EVMDD. Let Ea = 〈κ, f 〉 be a quasi-reduced EVMDD for some cost function ca, |f| the number of nodes of Ea, and let idx(v) ∈ {1, . . . , |f|} be a topological ordering of Ea, i.e., a bijective function numbering the nodes of Ea such that for every non-terminal node v and each child χi(v), idx(v) < idx(χi(v)). If v is the terminal node 0, then idx(v) = |f|. The domain of auxa has one value for each node in the EVMDD (plus one start value), i.e., Daux = {0, . . . , |f|}. For each non-terminal node v = (v, χ0, . . . , χk,w0, . . . ,wk) of Ea and each i = 0, . . . , k, we create an action av=i,idx(v) = 〈auxa = idx(v) ∧ v = i, auxa = idx(χi(v))〉 with cav=i,idx(v) = wi. Additionally, we need two actions corresponding to the precondition and the effect: A start action apre = 〈pre ∧ auxa = 0, auxa = 1〉 with cost capre = κ and a stop action aeff = 〈auxa = |f |, eff ∧ auxa = 0〉 with caeff = 0. 3

Example 3. Consider again action a with ca = AB2 + C + 2 encoded in the quasi-reduced form E ′a of the EVMDD Ea from Example 1 with an extra test for B on the (A, 0) branch. Applying the EVMDD compilation to a leads, among others, to the following actions (we write aux for auxa ):

The size of the resulting task depends on the number of edges in the EVMDD. This can lead to a much smaller number of new actions than in the BC compilation. For example, to transform an action with cost function ca = ∑nj=1 vj for propositional variables vj, j = 1, . . . , n, we only need 2n+2 actions, whereas the BC compilation produces 2n new actions. Furthermore, hadd applied on an EVMDD-compiled planning task still results in the desired value:

Theorem 3. Let Π be a task with SDAC and Π′ its EVMDD compilation. Let s be a state of Π and s′ = s ∪ ⋃a∈A{(auxa , 0)} be the corresponding state in Π′ , and let hadd and hadd orig be the generalized and original additive heuristics. Then hadd (s) = hadd orig (s′ ).

Proof sketch. We only need to show that Equations (3) and (3′ ) are equal for s and s′ . By construction, we get one aeff ∈ A′ (f) for each a ∈ A(f). During computation of hadd orig (pre(aeff )) we minimize over all paths from the root to 0 in the EVMDD. Since each path corresponds to one ˆ s ∈ Sa we get hadd orig (pre(aeff )) = hadd s (pre(a)) + C a s . Then we get hadd orig (f) = minaeff∈A′ (f)[hadd s (pre(a)) +C a s ]. Since aeff corresponds to a ∈ A(f) we get hadd (s) = hadd orig (s′ ).

4 EVMDD-Based RPGCompilation

In the following, we will show that we can also use EVMDDs to compute C a s directly, essentially by compiling the EVMDDs as sub-graphs into the RPG. In principle, computation of C a s is easy given a quasi-reduced EVMDD Ea: One can construct from Ea an EVMDD Ga s for ca + hadd s by retaining the graph structure of Ea and incorporating hadd values into the edge weights, and use Ga s for minimization over s+-viable paths. Such a transformation from Ea to Ga s has one drawback: It assumes that, when generating Ga s , all necessary hadd s ((v, d)) values to be hard-coded in Ga s are already known. However, due to the recursive nature of the hadd s computation, this is not the case. This problem can be avoided by adding "input nodes" for all relevant hadd s ((v, d)) values to the EVMDD. Since we will use the resulting "input-node augmented EVMDD" (INADD) as a portion of an RPG later, we do not treat it as an EVMDD any more, but rather as an AND/OR DAG.

3 In an unrelaxed setting, introduction of an additional semaphore variable can help reducing the branching factor of the search.

Definition 5. Let Ea = 〈κ, f〉 be a quasi-reduced EVMDD for some cost function ca with support supp(a) and Fa the set of facts over supp(a). Then the input-node augmented decision diagram (INADD) for Ea is the directed acyclic AND/OR graph Ia = (N∧, N∨, E, W ) with AND nodes N∧, OR nodes N∨, edges E, and node weight function W : N∧ → Z with the following components:

• Input nodes: For each fact f ∈ Fa, there is an input node nf ∈ N∨.
• Variable nodes: For each node v of Ea, there is a node nv ∈ N∨. This includes a node n0 for the terminal node 0 of Ea.
• Fact nodes: For each non-terminal node v = (v, χ0, . . . , χk,w0, . . . ,wk) of Ea and each i = 0, . . . , k, there is a node n(v,χi,wi) ∈ N∧ with weight W(n(v,χi,wi)) = wi. There is a node nκ ∈ N∧ for the additive constant κ with weight W(nκ) = κ.
• AND edges from variable nodes: For each variable node nv ∈ N∨ for non-terminal v = (v, χ0, . . . , χk,w0, . . . ,wk) and each i = 0, . . . , k, there is an edge from nv to n(v,χi,wi).
• AND edges from input nodes: For each input node nf for fact f = (v, d) and each fact node n(v,χd,wd) where v(v) = v, there is an edge from nf to n(v,χd,wd).
• OR edges: For each fact node n(v,χi,wi) ∈ N∧ for v = (v, χ0, . . . , χk,w0, . . . ,wk), there is an edge from n(v,χi,wi) to nχi . There is an edge from nκ to nf , where f denotes the root node of Ea.

This definition is best illustrated with the running example.

Example 4. Consider the EVMDD Ea from Example 1 in its quasi-reduced form E ′a . The INADD Ia for E ′a is depicted in Figure 1. OR nodes are shown as ellipses, AND nodes as rectangles, input nodes are labeled with the input facts, arcs from input nodes are thin, arcs corresponding to EVMDD arcs are solid, and node weights are given as annotations next to the corresponding nodes. The gray portion results from the extension of Ea to E ′a . The red node labels and other red markings will only be of interest in Example 5.

We can now define the evaluation of an INADD for a given input valuation as follows:

Definition 6. Let Ia = (N∧,N∨,E,W) be the INADD for some EVMDD Ea and let ι be a function assigning natural numbers or infinity to input nodes of Ia. Then the node valuation ˆι of all nodes of Ia is recursively defined as follows:

• For input node n ∈ N∨, ˆι(n) = ι(n).
• For variable node n ∈ N∨, ˆι(n) = min(n′ ,n)∈E ˆι(n′ ).
• For fact node n ∈ N∧, ˆι(n) = ∑(n′ ,n)∈E ˆι(n′ )+W(n).

The value of Ia for ι, denoted as Ia(ι), is then the value ˆι(n0) of the INADD node corresponding to the terminal node 0 of Ea. Since Ia is acyclic, this is well-defined.

Example 5. Consider the INADD from Example 4. The red input node labels denote ι(n) for some input valuation ι, and the red interior node labels denote the corresponding valuation ˆι. The highlighted red path of interior nodes is the minimizing path determining Ia, with inputs used on that path also highlighted in red. As we will see formally below, the value Ia = 9 is the same as C a s =minˆ s∈Sa [ca(ˆ s) + hadd s (ˆ s)] if the ι values are interpreted as hadd s values: The highlighted path corresponds to the minimizing ˆ s, ca(ˆ s) is the sum of the node weights 2 + 0 + 4 + 0 = 6 along the path, and hadd s (ˆ s) is the sum of used input node costs, 0 + 1 + 2 = 3.

We can now use Ia to compute C a s by initializing the valuation of input nodes with the hadd values of the corresponding facts. Efficient computability in the size of Ia is obvious.

Lemma 1. Let Ia = (N∧,N∨,E,W) be the INADD for a quasi-reduced EVMDD Ea encoding the action cost function ca of action a, and let v1 ≺ · · · ≺ vk be the variable order of Ea. Let C a s be the function over the variable nodes n = nv in N∨ defined recursively as follows:

• Base case for v(v) = v1 or k = 0 and v = 0: C a s (n) = min(n′ ,n)∈E W (n′ ).
• Inductive case for v(v) = vj, j > 1, or k > 0 and v = 0: C a s (n) = min(n′ ,n)∈E[C a s (n′∨) + hadd s (f) +W(n′ )], where n′∨ ∈ N∨ is the unique OR parent of n′ and f is the fact represented by the input node connected to n′ .

Then we get the following result:

1. C a s (n) = minˆ s∈Sn [ˆ ca(ˆ s) + hadd s (ˆ s)], where Sn is the set of partial states corresponding to paths incoming in n and where ˆ ca(ˆ s) is ca applied to ˆ s ∪ {(vi, 0) | vi ∈ supp(a) not occurring in ˆ s}.
2. C a s (n0) = C a s .

Proof sketch. 1. Induction over recursive definition of C a s (n). In the base case, both sides evaluate to κ. For the inductive case, we can apply the induction hypothesis to C a s (n′∨), use the independence of hadd s (f) and W(n′ ) of the choice of ˆ s ∈ Sn′∨ , construct ˆ sf(n′ ) = ˆ s ∪ {f}, use ˆ ca(ˆ sf(n′ )) = ˆ ca(ˆ s) +W(n′ ) and hadd s (ˆ sf(n′ )) = hadd s (ˆ s) + hadd s (f), and simplify.

1. By part 1 of this lemma, using Sn0 = Sa, which holds since Ea is quasi-reduced.

Theorem 4. Let Ia be the INADD for a quasi-reduced EVMDD Ea encoding the action cost function ca of action a. Let ι(nf ) = hadd s (f) for all facts f ∈ Fa. Then Ia(ι) = C a s .

Proof sketch. For non-input OR nodes n, we show by induction over the distance from n to nκ that ˆι(n) = C a s (n) (with C a s recursively defined as in Lemma 1). Then the claim follows for n = n0 using the definition of Ia(ι) (left-hand side) and part 2 of Lemma 1 (right-hand side). In the base case, again both sides evaluate to κ. In the inductive case, let n ∈ N∨ be a node with distance d. Then ˆι(n) = ˆι(n′ ) where n′ ∈ N∧ is a ˆι-minimizing fact node with (n, n′ ) ∈ E. Now, n′ has two parents, one variable node n′∨ with strictly smaller distance, and one input node nf . Thus, by definition, ˆι(n′ ) = ˆι(n′∨)+ˆι(nf )+W(n′ ). By induction hypothesis and the definition of ˆι for input nodes, this is C a s (n′∨) + hadd s (f)+W(n′ ). Thus, ˆι(n) = min(n′ ,n)∈E[C a s (n′∨) + hadd s (f) +W(n′ )] = C a s (n) by the choice of n′ and recursive definition of C a s .

We can now use the construction of Ia as a portion of the RPG for Π as follows: In each RPG layer, instead of having a single action node for action a, we have an action sub-graph for a that is the "conjunction" of Ia with the precondition facts of a. The input nodes of Ia are the corresponding fact nodes from the previous layer, and the "output" node n0 of Ia is linked to the effect literals of a on the current layer.

5 Experimental Evaluation

To evaluate hadd on planning tasks with SDAC, we have implemented the heuristic in the 2014 version of the PROST planner and compared it against the standard heuristic of PROST on the ACADEMIC ADVISING domain. The reason we chose the probabilistic setting is that planners already have to be able to deal with SDAC, which are part of the last two IPPCs' benchmark sets. ACADEMIC ADVISING is not the only goal-oriented domain, but the others are either very small, based on constant action costs, or require a transformation to positive action costs. Furthermore, it was by far the most challenging domain of the last IPPC, with no participant able to generate a good policy for more than the first four instances. PROST 2014 is based on the UCT⋆ algorithm [Keller and Helmert, 2013], a Trial-Based Heuristic Tree Search algorithm using UCB1 [Auer et al., 2002] action selection, Monte-Carlo simulation of stochastic outcomes, and a partial Bellman backup function to propagate collected information in the search tree. The standard heuristic (IDS) performs a lookahead based on a sequence of iterative deepening searches on the most-likely determinization of the given MDP. If the search uses too much time, it is stopped prematurely. The challenging part for the ACADEMIC ADVISING domain is that the application of good actions only pays off when the goal is reached, which is why it is costly to gain informative goal distance heuristic values. Table 1 shows statistics for different instances of ACADEMIC ADVISING. The first two rows denote the number of variables and the number of actions, while the third row shows the number of variables occurring in the cost function of each action. Note that this number is identical for all actions except for the no-op action. Next we denote the number of actions in the BC compilation, showing clearly that BC is infeasible. Row five denotes the number of nodes plus the number of edges of the resulting INADD 4 . The last three rows show the average results of PROST across 100 runs for each instance, based on different heuristics, with a 1-second timeout for each planning step. Best results (up to insignificant differences) are bold. baseline is based on a policy which always performs the no-op action, IDS is the standard heuristic used by PROST as described by Keller and Eyerich [2012], and hadd is the additive heuristic using the EVMDD-based RPG compilation of Section 4. Both IDS and hadd are applied to the most-likely determinization. For small problems, IDS performs reasonably well, but suffers from uninformative heuristic values as soon as the problem size increases, which leads to results worse than those of the baseline policy, whereas hadd yields good results, even for the most complex instances.

We briefly want to mention some implementation details. Since IPPC domains are modeled in RDDL [Sanner, 2010], we transformed grounded actions of the most-likely determinization into precondition-effect pairs. This transformation leads to more actions (roughly 5 times more), but the generated actions are only used for the computation of the heuristic values. EVMDDs are created by the open source MDD library MEDDLY [Badar and Miner, 2011]. Finally we want to mention that even-numbered instances allow concurrent actions. In this case, PROST generates additional actions for all possible combination of actions. During the computation of hadd , however, we only reason about the original actions, which leads to a small underestimation of the true hadd values but largely reduces the size of the RPG.

4 Note that (i) input nodes are not counted, as they are already part of the RPG anyway, and (ii) the used EVMDDs are not quasireduced. We internally transform them from reduced to quasireduced on the fly.

6 Conclusion and FutureWork

We have shown how action cost functions in planning with SDAC can be compactly encoded using EVMDDs and how a compact compilation to tasks with state-independent action costs can be derived from such an encoding. Moreover, we have introduced a natural extension of the definition of the hadd heuristic to tasks with SDAC, which can be efficiently computed, again using the EVMDD structures of the action cost functions. Finally, we have presented an implementation of the generalized hadd heuristic in the context of probabilistic planning, where SDAC are common. This heuristic gives rise to the first approach able to handle even the hardest instances of the combinatorial ACADEMIC ADVISING domain. For future work, we plan to extend the empirical evaluation to a broader range of benchmark problems, from probabilistic planning as well as from classical planning with SDAC. Furthermore, we will study the usefulness of the EVMDD encoding for other relaxation heuristics such as hmax (which is not as straightforward as it may seem) as well as to other types of heuristics, such as abstractions, and integrate them in the framework of the PROST planner. Finally, we will investigate how to automatically derive suitable EVMDD variable orderings for given cost functions.

Acknowledgements. This work was partly supported by the DFG as part of the SFB/TR 14 AVACS and by BMBF grant 02PJ2667 as part of the KARIS PRO project. We thank the anonymous reviewers for their insightful comments.