Optimal Delete-Relaxed (and Semi-Relaxed) Planning with Conditional Effects

1 Introduction

In action description languages, a conditional effect is an action effect that takes place only if an additional condition holds when the action is applied, but which does not prevent the action from being applied if this condition is not true. Conditional effects have been part of planning languages dating back at least to ADL [Pednault, 1989], and part of PDDL since its first version [McDermott et al., 1998]. They have been cited, particularly by researchers using classical planners as "black boxes", as an essential feature [Brafman et al., 2012]. The now popular approach of compiling nonclassical planning problems, like planning with uncertainty or temporally extended goals, into classical planning in order to leverage the recent performance gains of classical planners often makes extensive use of conditional effects [Palacios and Geffner, 2007; Bonet et al., 2009; Keller and Eyerich, 2011; Baier and McIlraith, 2006]. Yet, support for conditional effects in planners, particularly cost-optimal planners, is limited: none of the twelve cost-optimal planners that participated in the last IPC had any support for conditional effects.

Conditional effects can be removed by two different problem transformations [Nebel, 2000], but there are problems with both: the compilation that preserves plans exactly is exponential in size, making it infeasible when actions have more than a few conditional effects, while the compact compilation does not preserve the problem delete relaxation, which is the basis of many planning heuristics.

Several efficient methods for optimal delete-free planning have been presented recently [e.g., Robinson et al. 2010; Gefen and Brafman 2012; Haslum et al. 2012; Pommerening and Helmert 2012], but none of them support conditional effects. Here, we introduce an incremental compilation approach through which they can be applied to problems with conditional effects. A subset (initially empty) of effects are compiled out, and the rest treated in a relaxed way; the compiled subset is grown, iteratively, only if needed to obtain a valid plan. This approach can solve problems with large numbers of conditional effects, where full compilation is infeasible, by compiling out only a small fraction.

The recent idea of "semi-relaxation" [Keyder et al., 2012] provides a spectrum of intermediate points between deleterelaxed and fully non-relaxed planning, and is the basis of the h++ anytime lower bound function on plan cost [Haslum, 2012]. Semi-relaxed planning is delete-relaxed planning on a transformed problem. It too can be done in two ways: the P C compilation is exponential in size, while the linear-space P C ce compilation introduces conditional effects into the problem. Having an effective h+ solver for problems with conditional effects enables us to consider using the compact P C ce compilation in h++, reducing the memory requirements drastically; surprisingly, it also improves the function on some problems where memory is not an issue.

2 Background

A planning problem is defined by a set of propositional state variables ("atoms"), a set of actions, a completely specified initial state (s0) and a goal condition (G). Each action a is defined by a precondition (pre(a)) and sets of positive (add(a)) and negative (del(a)) effects; each effect is a pair 〈c, p〉, where c is the effect condition and p the effect atom, made true ("added") by the action if 〈c, p〉 ∈ add(a) and made false ("deleted") if 〈c, p〉 ∈ del(a). Unconditional effects of an action are simply effects with an empty condition. A problem in which all actions have only unconditional effects is called a STRIPS problem. Note that an action may have both (conditional) effects that add and delete an atom p. If effects of both kinds trigger when the action is applied in some state, the add effect takes precedence so the result is to make the atom true. This is in accordance with PDDL semantics [Fox and Long, 2003].

Action preconditions, effect conditions, and the goal are sets of atoms, interpreted as conjunctions. Instead of having negated atoms in conditions we assume that, when needed, each atom p has a complementary atom not-p that plays the role of ¬p, i.e., such that exactly one of p and not-p is true in every reachable state. Such complementary atoms can be added as needed with only a linear increase in problem size [Erol et al., 1991]. As we consider cost-optimal planning, each action has a non-negative cost (cost(a)); the cost of a plan is the sum of the costs of actions in it. The cost of an optimal plan for P is denoted h⋆ (P).

2.1 The Delete Relaxation

The delete relaxation of a planning problem P , denoted P +, is exactly like P except that all negative effects are removed. The cost of an optimal plan for P +, denoted h+, is a lower bound on the cost of an optimal plan for P . Computing h+ is NP-hard [Bylander, 1991].

A plan for a delete-free problem is monotonic, in the sense that any atom once made true never becomes false in a later state. (In P +, it is possible for both atoms p and not-p in a complementary pair to be true in a state.) This means that if P is a STRIPS problem, an optimal (non-redundant) plan for P + does not include any action more than once. This is not true of planning problems with conditional effects, because different sets of conditional effects may need to trigger at different occurrences of the same action. Hence, we define a (sequenced) delete-relaxed plan as a sequence of pairs 〈a1,E1〉, . . . , 〈an,En〉, where ai is an action and Ei ⊆ add(ai) is the subset of conditional add effects of ai that must take place at step i of the plan; we call such a pair a step, and say the effects in Ei are active. A step 〈ai,Ei〉 is applicable in state s if pre(ai) ∪ ⋃〈c,p〉∈Ei c holds in s, and applying it adds {p | 〈∅, p〉 ∈ add(ai)} ∪ {p | 〈c, p〉 ∈ Ei}. In other words, a step may be viewed as an unconditional (STRIPS) action that combines the unconditional effects of ai with the active effects in Ei. Ei does not have to contain all the effects of ai that trigger when ai is applied: triggering more effects can only make more atoms true, which cannot invalidate the remainder of the plan.

In an optimal (non-redundant) delete-relaxed plan, each step is a unique combination of action and effects. Although defined as a sequence, we will often consider a relaxed plan as an unordered set of steps. An unordered relaxed plan is valid iff some sequencing of the steps in it is. Because deleterelaxed execution is monotonic, deciding the validity of an unordered set of steps, and producing a sequencing if it is valid, can be done, in linear time, by greedily applying steps until all are done or no remaining step is applicable.

The relaxed plan dependency graph (RPDG) [Haslum, 2012] is a labelled directed graph that describes necessary ordering constraints in an unordered delete-relaxed plan S. It has one node na for each action a ∈ S, one node nG representing the goal, and an edge na λ -→n′ iff λ ̸= ∅ is the subset of pre(n′ ) that becomes relaxed unreachable if a is removed from the plan (pre(nG) = G). The RPDG of a valid relaxed plan is acyclic, and any sequencing of the plan must be a topological sort of the RPDG. We extend the RPDG to relaxed plans for problems with conditional effects by treating each step as an unconditional (STRIPS) action.

2.2 Semi-Relaxation

A semi-(delete-)relaxation of a planning problem P is a transformation of P into a new problem P ′ such that P ′ has the same optimal plan cost as P but the delete relaxation of P ′ keeps some information about the negative interactions caused by delete effects. Thus, h+(P ′ ) may be greater than h+(P) but remains a lower bound on h⋆ (P). Two semirelaxing transformations have recently been proposed: Both take a parameter, C, which is a set of conjunctions (sets) of atoms, and add to the problem a new atom πc for each c ∈ C. Actions in the compiled problem make πc true only if their application in the original problem makes the condition c true. The P C compilation [Haslum, 2012] produces a STRIPS problem that may be exponentially larger than P. The P C ce compilation [Keyder et al., 2012] instead uses conditional effects to update πc atoms, and therefore grows only linearly. Both compilations are defined only for STRIPS problems.

Both compilations are perfect in the limit, meaning that for some sufficiently large set C, h+(P C ) = h+(P C ce ) = h⋆ (P ). The P C ce compilation is weaker, in the sense that it may require compiling in a larger set of conditions to achieve the same information gain; that is, there are cases where h+(P C ce ) < h+(P C ) when both use the same set C.

2.3 Compilation of Conditional Effects

A planning problem with conditional effects can be compiled into a STRIPS problem in two ways [Nebel, 2000]: The first compilation, denoted Pexp, replaces each action a with one action for each possible "case", meaning a subset of effects that are triggered. As there can be up to 2| add(a)∪del(a)| cases, this compilation can increase the size of the problem exponentially, but it preserves plans exactly. Thus, h+(Pexp) = h+(P). The second compilation, denoted Pseq, breaks each action a into a sequence of actions, including one for each effect in add(a)∪del(a), and through additional control atoms forces each application of a (in the compiled problem) to be followed by the complete sequence. This compilation only increases the size of the problem polynomially, but may increase plan length polynomially. To preserve optimal plan cost, action costs must be set so that the cost of the complete sequence equals the cost of the original action. Inclusion of the complete sequence of separated effects cannot be enforced without the use of negative (delete) effects. Thus, delete relaxation of this compilation results in an additional relaxation, i.e., h+(Pseq) ≤ h+(P).

3 Relaxed Planning with Conditional Effects

We approach optimal delete-relaxed planning for a problem P with conditional effects by incremental compilation: We first apply a transformation, similar to Pseq, to produce a delete-free STRIPS problem that is a relaxation of P +; we call this the floating effects relaxation of P +. The relaxed problem is solved, optimally, using any method for optimal delete-free planning available for STRIPS problems [e.g., Robinson et al. 2010; Gefen and Brafman 2012; Haslum et al. 2012; Pommerening and Helmert 2012]. If the resulting plan can be scheduled into a plan for P +, this plan is optimal and we are done; if not, we apply the exponential compilation to a subset of conditional effects, and the relaxation to the remaining conditional effects, and repeat. We call this procedure h+ce .

In the worst case, this may end up compiling away all conditional effects, thus faring no better than applying the exponential compilation up front and solving the STRIPS problem only once. But in practice, as will be shown, we often need to compile only a small fraction of them, thus making this approach able to solve problems whose exponential compilation is prohibitively large.

3.1 The Floating Effects Relaxation

The idea of making conditional effects into separate actions has been used in delete relaxation-based heuristics since FF [Hoffmann and Nebel, 2001]. Typically, the condition of each effect is augmented with the precondition of its action to ensure the action is (relaxed) applicable when the effect is used.

The floating effects relaxation is based on the same idea, but differs on two points: First, it ensures that whenever a conditional effect appears in the relaxed plan, so does at least one instance of the action that the effect belongs to. This allows setting costs so that the relaxation yields a lower bound, and simplifies scheduling the relaxed plan. Second, a subset of conditional effects (a parameter of the transformation) are compiled out rather than relaxed. This gives a sliding scale, from full relaxation to full exponential compilation of all conditional effects. To keep track of the compiled out effects, we associate with each action a in the relaxation a set ce(a) of conditional effects.

Definition 1 Let P + be a delete-free problem with conditional effects and E a subset of its effects (with non-empty effect conditions). The (partially compiled) floating effects relaxation, denoted P + fe /E, is defined as follows. Atoms in P + fe /E are all atoms of P +, plus one atom done-a for each action a in P +. For each action a in P +, P + fe /E has two types of actions:

• For each A ⊆ (add(a) ∩ E), an action aA with pre(aA) = pre(a) ∪ ⋃〈c,p〉∈A c, add(aA) = {p | 〈∅, p〉 ∈ add(a)} ∪ {p | 〈c, p〉 ∈ A} ∪ {done-a}, and cost(aA) = cost(a). This is called an anchor action (for a). We set ce(aA) = A.
• For each conditional effect 〈c, p〉 ∈ (add(a) -E) (where c ̸= ∅), an action a〈c,p〉 with pre(a〈c,p〉) = c ∪ {done-a}, add(a〈c,p〉) = p and cost(a〈c,p〉) = 0. This is called a floating effect (of a). We set ce(a〈c,p〉) = ∅.

The initial state of P + fe /E is that of P +, with all done-a atoms false, and the goal of P + fe /E is that of P +.

The size of P + fe /E is exponential, but only in the maximum number of effects per action that are compiled out. Note that the size of P + fe /∅ is linear in P.

It is easy to see that P + fe /E is a relaxation of P +: Given a step 〈ai,Ei〉 in an optimal plan for P +, let Ai = Ei ∩E be the subset of Ei that has been compiled out. P + fe /E, by construction, includes an anchor action aiAi with ce(aiAi ) = Ai. The precondition of this action is pre(ai)∪⋃〈c,p〉∈Ai c, which must hold in the state where the step takes place, since ai is applicable and all effects in Ei trigger, and it adds all of {p | 〈c, p〉 ∈ Ai}. Thus, replacing each step 〈ai,Ei〉 with aiAi followed by the floating effect action a〈c,p〉 for each effect 〈c, p〉 ∈ (Ei -Ai) yields a plan for P + fe /E, with equal cost. The converse, however, is not necessarily true (unless E contains all conditional effects in P +). This is shown by the following example.

Example 1 Consider (a simplified version of) the Miconic domain, which involves scheduling the stops of an elevator to serve a queue of waiting passengers. The action (stop ?f), for each floor ?f, has two types of conditional add effects: one effect 〈{(waiting ?p)}, (boarded ?p)〉 for each passenger ?p waiting at ?f and one effect 〈{(boarded ?p)}, (served ?p)〉 for each passenger ?p whose destination is ?f.

Consider a problem with two passengers, A and B, where A wants to go from F1 to F2 and B from F2 to F1. An optimal plan for the floating effects relaxation (with E = ∅) of this problem is (stop F1), 〈{(waiting A)},(boarded A)〉, (stop F2), 〈{(boarded A)},(served A)〉, 〈{(waiting B)},(boarded B)〉, 〈{(boarded B)},(served B)〉, with a cost of 2 (since floating effect actions have cost 0). But this plan cannot be rewritten into a plan for the delete relaxation of the original problem: The last floating effect, 〈{(boarded B)},(served B)〉, belongs to action (stop F1), so must take place at the same time as that action (whereas the relaxation only requires it to happen after the anchor action), but depends on the fact (boarded B) which is only added by an effect of the second action, (stop F2). Swapping the order of the two stops only leads to the same problem with passenger A. Due to the cyclic dependency, any plan for the delete relaxation of the original problem must stop at one floor twice, for a minimum cost of 3.

3.2 Scheduling a Relaxed Plan

A scheduling of a plan S for a partially compiled floating effects relaxation P + fe /E is a plan S′ for P + that has one step for each anchor action a ∈ S, whose active effect set includes ce(a), and where each floating effect in S is included in the effect set of a (not necessarily adjacent) step with the action that the effect belongs to. The cost of S′ is the same as the cost of S; thus, if S is an optimal plan for P + fe /E then S′ is an optimal plan for P +. Example 1 shows it may be impossible to schedule a plan for P + fe /E, but if S contains no floating effect action, then clearly a valid scheduling of S exists; thus for large enough E, scheduling succeeds.

The complexity of deciding if a plan for P + fe /E can be scheduled is an open question. Keyder et al. [2012] show NP-hardness, but for a slightly different scheduling problem; their reduction does not apply when both the set of anchor actions and floating effects is fixed. On the other hand, we also do not have a polynomial-time scheduling algorithm.

To schedule a relaxed plan we use plain depth-first search, with a constraint propagation mechanism for efficiency. With slight abuse of terminology, let S′ be a partially scheduled plan, i.e., a set of steps where some actions are floating effects. Let 〈a′ ,E′ 〉 and 〈a〈c,p〉, ∅〉 be two steps in S′ , where a〈c,p〉 is a floating effect and a′ is an instance of the action that this effect belongs to. Placing a〈c,p〉 with 〈a′ ,E′ 〉 transforms S′ into a new plan S′′ by (i) replacing 〈a′ ,E′ 〉 with 〈a′ , E′ ∪ {〈c, p〉}〉 and (ii) removing 〈a〈c,p〉, ∅〉.

Let S′′ be the result of placing a floating effect a〈c,p〉 with some step 〈a′ , E′ 〉 in S′ : for any valid sequencing of S′′ there is a corresponding valid sequencing of S′ , with a〈c,p〉 applied immediately following the step 〈a′ ,E′ 〉. This implies that the RPDG of S′ , excluding the a〈c,p〉 node, is an edge-labelsubgraph of the RPDG of S′′ , i.e., if n λ -→n′ is an edge in the former, then n λ′ -→n′ , with λ ⊆ λ′ , is an edge in the latter. We exploit this to build a sound approximation (i.e., an edge-label-subgraph) of the RPDG of the final scheduled plan incrementally: Starting from the RPDG of the plan for the relaxation, whenever a floating effect a〈c,p〉 is placed with a step 〈a′ ,E′ 〉, the a〈c,p〉 node is removed and all its incident edges redirccted to the 〈a′ , E′ 〉 node. Because the RPDG of a valid plan is acyclic, a cycle in the approximate graph implies that the current partially scheduled plan cannot be valid.

Scheduling starts from S′ = {〈a, ce(aA)〉 | aA ∈ S} ∪ {〈a〈c,p〉, ∅〉 | a〈c,p〉 ∈ S}. If there is a floating effect a〈c,p〉 in S′ , then for each candidate step 〈a′ ,E′ 〉 in turn, try placing a〈c,p〉 with 〈a′ ,E′ 〉. If the placement causes a cycle in the RPDG, or the new plan S′′ cannot be sequenced, proceed to the next candidate; otherwise try to schedule S′′ . If any placement succeeds, return the plan, else add the effect 〈c, p〉 to a set Failed and backtrack.

If the scheduling procedure returns failure, the set Failed contains at least one conditional effect, and no effect in Failed is in the set E of effects that have been compiled out. In this case, we set E′ = Failed ∪ E, construct P + fe /E′ , call the STRIPS h+ solver to obtain a new relaxed plan, and try again. This repeats until scheduling succeeds, which will happen eventually since the set of compiled out effects grows at each iteration. We then have an optimal plan for P +.

3.3 Evaluation: h+ce in Practice

We compare the effectiveness of h+ce with building the full exponential compilation of the delete-relaxed problem, P + exp , and computing h+ on that. The exponential compilation is optimised so that no redundant actions are generated: when an action has two conditional effects 〈c, p〉 and 〈c′ , p′ 〉 such that c implies c′ , any compiled action that includes 〈c, p〉 also includes 〈c′ , p′ 〉. We make one modification to h+ce , adding at most one conditional effect per action from Failed to the set of compiled effects, E, per iteration. 1 Both methods use the iterative landmarks h+ solver [Haslum et al., 2012].

Of the usual planning benchmark domains only Assembly (from IPC-1) and the "full" version of Miconic (from IPC2), have conditional effects (after grounding). Both of them are easily dealt with by compilation because the maximum number of effects per action is small. Therefore, we also use problems generated by the conformat-to-classical planning compilation (T0) of Palacios and Geffner [2009] and the finite-state controller synthesis compilation (FSC) by Bonet et al. [2009]. These have significantly larger maximum numbers of conditional effects per action.

Table 1 (left) summarises the number of problems solved (i.e., h+ computed) by the two methods, within 1h CPU and 3Gb memory per problem. Assembly and Miconic are easily solved by full compilation, but in the more difficult domains, incremental compilation has a clear advantage. In these, the number of conditional effects per action compiled (the exponent in the size of the compilation) is often a small fraction of the maximum; in about a third of the problems, no effects need to be compiled. The number of h+ce iterations varies from 1 to 101 (median 3, mean 7.9). There is, of course, a time overhead for computing h+ several times: on those problems that can be solved with the full exponential compilation, the median slow-down of h+ce is a factor of 2.4 (mean 309).

4 Incremental Lower Bounds Beyond h+

The h++ incremental lower bound function [Haslum, 2012] uses the P C compilation to iteratively strengthen h+. It computes an optimal delete-relaxed plan, checks if the relaxed plan works for the real, unrelaxed problem, and if not, computes a set of binary conjunctions C, called flaws, and repeats the process with P C , thus creating a series of less and less relaxed problems. Each flaw set is chosen so that the current relaxed plan does not solve the delete relaxation of the next problem. This ensures the process eventually converges to a point where h+((· · · (P C1 )C2 · · · )Ck ) = h⋆ (P). However, because the P C compilation is exponential it may run out of space, or out of time computing h+. The derelaxation is built iteratively, instead of rebuilding P C each time with a larger set C, because flaw extraction finds only binary conjunctions; after the the second iteration, the conjuncts can be πc atoms, which lets it find (implicit) conjunctions of arbitrary size.

1 We also tried a different compilation of relaxed planning with conditional effects, based on time-indexing atoms and actions in a way similar to the relaxed planning graph (Joerg Hoffmann, pers. comm.). Although it is polynomial in size, it was more difficult for the h+ solver, and led to fewer problems solved.

With a method of computing optimal delete-relaxed plans for problems with conditional effects in hand, we can use the linear-space P C ce compilation in place of P C in h++. This may avoid the exponential blow-up, as well as allow its application to problems with conditional effects. There are two obstacles: First, P C ce , as defined by Keyder et al. [2012], is defined only for STRIPS problems. Generalising it to work with conditional effects is straightforward, but the size of the generalised compilation is no longer polynomial in the worst case. Second, the existing flaw extraction method only works for STRIPS problems, and requires substantial revision.

4.1 The P C ce Compilation with Conditional Effects

The P C ce compilation [Keyder et al., 2012] augments the planning problem P with a new atom πc for each conjunction c ∈ C, and modifies actions so that πc is made true only when the conjunction c holds. Here, we define the generalised P C ce compilation only for binary conjunctions.

Let C be a set of (binary) conjunctions, and X any set of atoms: XC denotes the set {πc | c ⊆ X, c ∈ C}. Let a be an action, and {p, q} a binary conjunction. The conditional effects of a on {p, q} are characterised as follows:

• For an atom p, add(a, p) = min⊂{c | 〈c, p〉 ∈ add(a)}; that is, add(a, p) is the set of minimal (w.r.t. subset) conditions which cause action a to add p. Likewise, del(a, p) = min⊂{c | 〈c, p〉 ∈ del(a)}.
• Let del(a, p) = {c1, . . . , ck}: - del(a, p) is the set of minimal conditions in which a does not delete p, and is given by {{not-p1, . . . , not-pk} | p1 ∈ c1, . . . , pk ∈ ck}, i.e., all ways of taking the complement of one atom in each condition that causes a to delete p. Likewise, -- add(a, p) is the set of conditions in which a does not add p and is constructed analogously.
• Finally, add(a, {p, q}) denotes the conditions in which a makes {p, q} true. It is the union of three sets:

• Likewise, del(a, {p, q}) denotes the conditions in which a makes {p, q} false. Because add effects take precedence over deletes, this happens only if a deletes, and does not add, one of the conjuncts: del(a, {p, q}) = {c ∪ c′ | c ∈ del(a, p), c′ ∈ -- add(a, p)} ∪ {c ∪ c′ | c ∈ del(a, q), c′ ∈ -- add(a, q)}.

Definition 2 Let P be a planning problem (with conditional effects) and C a set of binary conjunctions. Atoms in P C ce are all atoms of P, plus one atom πc for each c ∈ C. For each action a in P , P C ce has an action a′ with

• pre(a′ ) = pre(a) ∪ pre(a)C ,
• add(a′ ) = {〈c ∪ (c ∪ pre(a))C , p〉 | 〈c, p〉 ∈ add(a)} ∪{〈c ∪ (c ∪ pre(a))C , π{p,q}〉 | c ∈ add(a, {p, q})},
• del(a′ ) = del(a) ∪ {〈c, π{p,q}〉 | c ∈ del(a, {p, q})}, and cost(a′ ) = cost(a). Each atom πc is initially true iff c is; the initial state of all other atoms in P C ce is as in P. The goal of P C ce is GC , where G is the goal of P.

The size of P C ce is potentially exponential, but only if some actions conditionally add and delete atoms in some c ∈ C, and it is exponential only in the number of minimal conditions which cause the actions to add or delete those atoms.

The key property of P C ce is that in any reachable state, πc is true if and only if c holds. (The proof of this is a straightforward adaptation of the proof for P C [Haslum, 2012].) Since pre-, effect and goal conditions in P C ce include πc only when the condition contains c, it follows that a1, . . . , an is a plan for P if and only if a′1 , . . . , a′n is a plan for P C ce . Thus, since corresponding actions have the same cost, h⋆ (P C ce ) = h⋆ (P ).

4.2 Flaw Extraction

The flaw extraction procedure for STRIPS problems has two steps: First, if a relaxed plan fails when executed in the real problem, it is because some atom, p, required by an action precondition or the goal, was deleted by a previous action. The nodes in the RPDG corresponding to these are identified as the failed node, nf , and the deleter, nd, respectively. Second, the set of flaws is extracted from the edge labels of the RPDG: A dependency closure from n to n′ is a recursively defined subgraph of the RPDG that contains a path from n to n′ , and a path from n to any node that adds an atom that labels an edge in the closure. If nf is a descendant of nd, flaws are pairs {p, q} where q labels an edge in a dependency closure from nd to nf . If not, dependency closures from nd and nf to one of their nearest common descendants are chosen, and flaws are pairs of one atom from each closure, with p added to the second. For a full description of the procedure we must refer to the earlier paper [Haslum, 2012]. Adapting it to relaxed plans with conditional effects requires several changes, which we can only sketch briefly here.

Relaxed Plan Normalisation The relaxed plan is normalised by (1) including in the active effect set of each step 〈a, E〉 all 〈c, p〉 ∈ add(a) that are implied by the combined precondition of the step, i.e., such that c ⊂ pre(ai) ∪ ⋃〈c′ ,p〉∈Ei c′ ; and (2) iteratively removing from each step any redundant non-implied effect, and any redundant step from the plan.

Splitting the RPDG Next, we need to separate active effects from actions, and track their dependencies explicitly. Computing the RPDG on the floating effects relaxation is not sufficient, because this does not reveal all necessary dependencies. Instead, we compute a split RPDG in two steps. Recall that each step 〈ai,Ei〉 in a relaxed plan can be viewed as a STRIPS action; we compute a standard RPDG, G1 , on this plan, and transform it into the split RPDG, Gsplit , as follows: 1. Each node n〈a,E〉 in G1 is split into one node, na, for the action and one node n〈c,p〉 for each active effect 〈c, p〉 ∈ E.

2. For each incoming edge n λ -→n〈a,E〉 in G1 , each label atom q ∈ λ is considered separately: If q ∈ pre(a), redraw the edge n q -→ to each node that n〈a,E〉 was split into (or add q to the label where an edge already exists). If q ̸∈ pre(a), q must belong to the condition of some active effects; redraw the edge only to each node n〈c,p〉 where q ∈ c.

3. For each outgoing edge n〈a,E〉 λ -→n in G1 and each label atom q ∈ λ: If q is an unconditional effect of a, draw the edge q -→n from na (or add q to the label if the edge already exists). Otherwise, q is added by one of the active effects 〈c, q〉 ∈ E; in this case, draw the edge n〈c,q〉 q -→n.

Assigning Failures If a step in the relaxed plan fails only because some of its effects' conditions are unsatisfied, each node n〈c,p〉 corresponding to such an effect is a failed node. If a step fails because the precondition of the action is unsatisfied, the action node, na, and all of its associated conditional effect nodes are failed. Flaws are generated separately for each failed node. In the split RPDG, nodes other than the goal node may have no outgoing edges; these cannot be used to derive flaws. However, due to normalisation, whenever there is a failed node with no outgoing edge, there is also another failed node that has at least one outgoing edge.

Selecting Deleters For each failed node, flaw extraction from the split RPDG proceeds in the same way as for STRIPS plans. However, since the node of the action that deleted the missing atom may have been split, we may have a choice of deleter node. This choice is made to minimise the size of the flaw set, with the restriction that if any candidate deleter node has a path to the failed node, one that does must be chosen.

Convergence The flaw extraction procedure for STRIPS plans returns a set of conjunctions such that compiling those in is guaranteed to rule out the failed relaxed plan. This is not true of flaw extraction, as described above, for conditional effect plans. The difficulty arises in the recursive part of a dependency closure, which must include a path from the root node of the closure to every node that adds an atom that labels an edge in the closure. In the standard RPDG, such a path always exists [Haslum, 2012, Theorem 2, item 5]. In the split RPDG, that path may need to be traced "backwards" from a conditional effect node to the action node of the corresponding step. How to define a closure in the split RPDG to ensure convergence is an open question.

Flaw Extraction for Non-Sequenced Plans The procedure used to compute a small flaw set that covers each sequencing of a partially ordered relaxed plan in the STRIPS version [Haslum, 2012] does not easily generalise to the conditional effects case. However, with the P C ce compilation minimising the size of the flaw set is not as critical. Thus, we adopt the simple enumerate-to-first-failure approach for non-sequenced relaxed plans.

4.3 Evaluation: h++ ce vs. h++

We compare use of the P C ce compilation in h++ (called h++ ce ) with the original procedure, using the P C compilation, on two sets of domains: Airport, 4-ops Blocksworld and Openstacks are domains where the original h++ most often runs out of memory. Here, we want to see if using P C ce instead leads to better lower bounds. APPN, ParcPrinter and Woodworking are among the domains where h++ is at its best, compared to lower bounds based on A* search. Here, we want to see if using the weaker P C ce compilation also leads to weaker bounds.

Both solvers are given 1h CPU time and 3Gb memory per problem. Table 2 shows the number of problems optimally solved, and how often each method proves a lower bound (on h⋆ ) strictly higher than the other. h++ ce , of course, never runs out of memory, and does improve over h++ where it does, but the improvement does not seem directly related to how often that happens. Moreover, h++ ce even fares (slightly) better in some of the domains where h++ already does well. Clearly, more factors than just the size of the compilation determine the effectiveness of this iterative lower bounding approach.

5 Conclusions

Adapting optimal planning techniques to problems with conditional effects is difficult, but important for optimal planners to be applicable in many cases, particularly to problems generated by compilations. The exponential conditional effects compilation is convenient, since it allows such problems to be reduced to the STRIPS case, but infeasible whenever actions have more than a few conditional effects. We have shown that incremental compilation may be a promising approach, though it remains to investigate how this idea can be applied in other contexts than for computing h+.

Having an h+ solver for problems with conditional effects allows us to contemplate using the more space-efficient P C ce construction within the h++ anytime lower bound function. This requires modifications to both the compilation and the original h++ procedure, and establishing the convergence guarantee that holds in the STRIPS case remains an open problem. However, preliminary results suggest that there are more benefits to making this switch than just reducing memory requirements.

Acknowledgements

NICTA is funded by the Australian Government represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.