Abstraction Heuristics for Classical Planning Tasks with Conditional Effects

1 Introduction

Conditional effects allow the modelling of action effects that occur only when specified conditions are satisfied in the current state [Nebel, 2000; Helmert, 2009]. Introduced to classical planning in the context of ADL [Pednault, 1989], they have since become an essential tool for compactly representing complex planning tasks. For example, they underlie recent planning formulations for discovering new algorithms for matrix multiplication [Speck et al., 2023] and for transforming quantum circuits [Shaik and van de Pol, 2024]. Their importance is also reflected in the growing number of International Planning Competition (IPC) domains that feature conditional effects [Taitler et al., 2024].

Since designing optimal planners that natively handle conditional effects remains challenging, a common alternative is to compile them away [Gazen and Knoblock, 1997; Haslum, 2013]. However, Nebel [2000] showed that compiling away conditional effects entails an exponential increase in model size if plan lengths are constrained to grow at most linearly. If polynomial growth of plan lengths is allowed, compilation becomes feasible for certain tasks using techniques that exploit the structure of the conditional effects [Gerevini et al., 2024; Percassi et al., 2024]. Nevertheless, the resulting compiled tasks often overwhelm planners due to a combinatorial explosion in the search space, which usually grows exponentially with the depth of the search [Gerevini et al., 2024].

Given these limitations, developing optimal classical planners that can handle conditional effects natively is paramount. While symbolic search can be extended to support conditional effects simply by encoding the effects in the transition relation [Edelkamp and Helmert, 2001; Kissmann et al., 2014; Speck et al., 2025], the situation is more challenging for informed search techniques that rely on admissible heuristics.

To date, only a few admissible heuristics have been extended to natively support conditional effects, such as the hmax heuristic [Bonet and Geffner, 2001] and the LM-Cut heuristic [Helmert and Domshlak, 2009; R¨oger et al., 2014]. More recently, B¨uchner et al. [2024] showed how to compute abstractions for factored tasks, a restricted class of conditional-effect tasks where each effect condition considers only the effect variable. As for tasks without conditional effects, abstractions of factored tasks are induced, i.e., each abstract transition corresponds to a concrete transition.

To handle arbitrary conditional effects, we overapproximate the abstract transition system and obtain non-induced abstractions. Dropping the requirement that abstractions are induced is necessary for handling conditional effects, because even for projections it is NP-hard to decide whether an abstract transition is induced [B¨uchner et al., 2024]. Adding conditional-effect support requires only minor modifications for projections, the abstractions underlying pattern databases (PDBs) [Edelkamp, 2001; Haslum et al., 2007; Sievers et al., 2012] and merge-andshrink (M&S) abstractions [Sievers and Helmert, 2021].

Our main contribution, however, concerns Cartesian abstractions [Seipp and Helmert, 2018], where extending support for conditional effects requires not only redefining how to decide the presence of abstract transitions but also adapting the counterexample-guided abstraction refinement (CEGAR) algorithm, which remains the only method for constructing Cartesian abstractions. We show that all flaw detection strategies from the literature, forward [Seipp and Helmert, 2018], backward [Pozo et al., 2024b] and sequence flaws [Pozo et al., 2024a], can be adapted to handle conditional effects.

Our experimental results for factored tasks show that the CEGAR algorithm for PDBs designed for this setting is preferable to the general counterpart, but for tasks with arbitrary conditional effects, our techniques solve more tasks than state-of-the-art methods across many benchmark domains.

2 Background

We begin by introducing the necessary background on classical planning, abstractions and the CEGAR algorithm.

2.1 Planning Tasks

We consider finite-domain (FDR) planning tasks with action costs but without axioms and derived variables [Helmert, 2009]. Such planning tasks Π = ⟨V,O, I,G⟩ are defined by a set of finite-domain variables V , a finite-set of operators O, an initial state I and a goal description G. Each variable v ∈ V has a finite domain Dv. A partial state p is a partial variable assignment over some variables vars(p) ⊆ V . A (concrete) state s is a full assignment, i.e., vars(s) = V . We write p[v] for the value assigned to variable v ∈ vars(p) in partial state p. Two partial states p1 and p2 are consistent, p1 ∼= p2, if p1[v] = p2[v] for all v ∈ vars(p1) ∩ vars(p2). We let S denote the set of all states and let �p� ⊆ S be the set of states consistent with p. We often treat (partial) states as sets of atoms v ↦→ x, where x ∈ Dv.

Each operator o = ⟨pre(o), eff (o), cost(o)⟩ ∈ O consists of the partial state pre(o), called its precondition, a finite set of effects eff (o) and a non-negative cost cost(o) ∈ R+0 . Each effect e ∈ eff (o) is a pair ⟨conds(e), atom(e)⟩, where conds(e) is a partial state, called the effect conditions, and v ↦→ x = atom(e) is the effect atom, where v and x are called the effect variable and effect value. Operator o is forwardapplicable or, in short, applicable in state s iff s is consistent with pre(o). In the resulting state s′ = progr(s, o) we have s′ [v] = d for all effects ⟨conds(e), v ↦→ x⟩ with conds(e) ∼= s and s′ [v] = s[v] for all variables v where no effect is triggered. We assume that all operator effects are nonconflicting. Note that conds(e) can be empty, in which case the effect is triggered in all states s ∈ S. We write s o-→ s′ as a shorthand whenever o is applicable in s and s′ = progr (s, o).

2.2 Search in Transition Systems

A task Π = ⟨V,O, I,G⟩ induces the labelled transition system Θ = ⟨S,O, T, I, SG⟩, where SG = {s ∈ S | s ∼= G} is the set of goal states and T = {⟨s, o, s′ ⟩ | s, s′ ∈ S, o ∈ O, s o-→ s′ } is the set of transitions. An s-plan is a sequence of operators ⟨o1, o2, . . . , on⟩, s.t. the trace s o1 -→ s1 o2 -→ . . . on -→ sn reaches a goal state sn ∈ SG. The cost of a plan is the summed-up cost of its operators. An s-plan is optimal if it has the minimum cost among all s-plans. An I-plan is a plan for Π. Regression reasons backwards, starting from a partial state p′ and deriving from which states �p� we can reach some state in �p′ � by applying an operator [Rintanen, 2008; Alc´azar et al., 2013]. We write p o←- p′ as a shorthand.

Heuristics. One of the most successful approaches to find optimal plans is to use A∗ with an admissible heuristic [Dechter and Pearl, 1985]. A heuristic is a function h : S → R+0 ∪{∞}. The perfect heuristic h∗ assigns to each state s the cost of an optimal s-plan, or ∞ if no s-plan exists. A heuristic is admissible if h(s) ≤ h∗ (s) for every state s ∈ S, it is consistent if h(s) ≤ h(s′ ) + cost(o) for all s o-→ s′ ∈ T and it is goal-aware if h(s) = 0 for all goal states s ∈ SG. Consistent and goal-aware heuristics are admissible [Pearl, 1984].

Cost Partitioning. Cost partitioning allows for the combination of several admissible heuristics H into a single heuristic while preserving admissibility [Katz and Domshlak, 2010; Pommerening et al., 2015]. It does so by distributing the cost of each operator among the heuristics, such that the sum of the assigned costs does not exceed the original operator cost. Formally, given a tuple of heuristics H = ⟨h1, . . . , hn⟩ for task Π, the cost functions C = ⟨c1, . . . , cn⟩ form a cost partitioning for H if ∑ni=1 ci(o) ≤ cost(o) for all o ∈ O. The resulting cost-partitioned heuristic is hC (s) = ∑ni=1 hi(ci, s), where hi(ci, s) is the heuristic value of hi for state s evaluated under cost function ci.

2.3 Abstractions

We focus on heuristics based on abstraction [Helmert et al., 2008]. An abstraction is a surjective function α : S → Sα, where Sα is a finite set of abstract states. The abstract transition system Θα = ⟨Sα, O, T α, I α, SαG⟩ is a homomorphism of the concrete transition system, i.e., T α = {(α(s) o-→α(t) | s o-→ t ∈ T)}, I α = α(I), SαG = {α(s) | s ∈ SG}. We also call a homomorphism a conservative abstraction [Sievers and Helmert, 2021]. An abstraction is induced (a strict homomorphism) if each abstract transition corresponds to a concrete transition. Each abstract state sα ∈ Sα is identified with the set of states mapped to it, �sα� = {s ∈ S | α(s) = sα}. Abstraction heuristics are a family of admissible heuristics hα, where hα(s) is the cost of the cheapest α(s)-plan in the abstract transition system.

Projections. The most basic type of abstraction is a projection αP to a subset of variables P ⊆ V . We call P a pattern and projection-based heuristics pattern database (PDB) heuristics [Edelkamp, 2001].

Merge-and-Shrink Abstractions. The most general type of abstraction for classical planning are merge-and-shrink abstractions (M&S) [Sievers and Helmert, 2021]. M&S begins by computing a projection for each variable v ∈ V to obtain its initial factored transition system. Then it iteratively selects two factors and replaces them by their synchronized product (merge). To adhere to a given size limit, in between such merge operations, M&S may shrink a factor by applying an abstraction function on it. The two remaining operations that the M&S framework uses, label reduction and state pruning, are not important for our contributions, so we refer the reader to Sievers and Helmert [2021]. The M&S procedure ends once there is only a single factor left or in case a time limit is reached, in which case we can combine the estimates of the remaining factors with cost partitioning [Sievers et al., 2024].

Cartesian Abstractions. On the generality scale, Cartesian abstractions lie in between projections and M&S abstractions. An abstract state sα is Cartesian if �sα� has the form A1 × A2 × · · · × An, where Ai ⊆ Dvi for all vi ∈ V . (We treat V as a tuple where it simplifies notation.) If all states in an abstraction are Cartesian, we call the abstraction Cartesian [Seipp and Helmert, 2018]. Given a Cartesian set a, we denote by a[vi] the set of values that vi can take in a, i.e., a[vi] = Ai ⊆ Dvi . The intersection of two Cartesian sets a and b is the Cartesian set c, with c[v]=a[v] ∩ b[v] for all v ∈V . We write a ∼= p for (partial) state p if there is a state s ∈ �a� with s ∼= p. Also, for any such p, we can build a Cartesian set C(p) = b such that �b�=�p�, by setting b[v]={p[v]} if v ∈ vars(p) and b[v]=Dv otherwise.

Algorithm 1: CEGAR loop for a task Π.

1 Θα ←TrivialAbstraction(Π) 2 while not TerminationCondition() do 3 τ α ← FindOptimalTrace(Θα) 4 if τ α = "no trace" then 5 return task is unsolvable 6 φ←FindFlaw(Π, τ α) 7 if φ = "no flaw" then 8 return plan extracted from τ α 9 Θα ←Refine(Θα, φ) 10 return Θα

2.4 Cartesian Abstraction Refinement

Currently, the only way to build Cartesian abstractions is via counterexample-guided abstraction refinement (CEGAR) [Clarke et al., 2000; Seipp and Helmert, 2013; Seipp and Helmert, 2018], shown in Algorithm 1. This iterative procedure starts from the trivial abstraction, which consists of a single abstract state a0 such that a0[v]=Dv for all v ∈V . Then, the abstraction is refined until finding a plan, proving the task unsolvable or hitting a termination condition like a time or memory limit.

In each iteration, an optimal abstract plan trace τ α=a0 o1 -→ . . . on -→ an is executed in the concrete state space, resulting in a trace s0 o1 -→ . . . om --→ sm,m ≤ n (line 6). An abstract plan trace τ α = a0 o1 -→ . . . on -→ an is mappable to a concrete plan trace τ = s0 o1 -→ . . . on -→ sn iff α(si) = ai for all i ∈ [0, n]. If τ α is mappable and sn = sm ∈ SG, then it is an optimal plan for the task (line 8). If it fails at some step i, this is a flaw and the abstraction is refined by splitting the abstract state ai into two, in such a way that the same flaw cannot happen again (line 9). A flaw is a pair ⟨si, c⟩ of a concrete state si ∈ S and a Cartesian set c.

There are three causes for a flaw, which correspond to different reasons that can cause the execution of τ α to fail at step i: (1) precondition flaw: si is the first state in which oi+1 is inapplicable and c is the set of states consistent with ai in which oi+1 is applicable, i.e., c = ai ∩ C(pre(oi+1)); (2) deviation flaw: si is the first state where oi+1 is applicable but its successor is not consistent with ai+1, and c is the set of states consistent with ai from which ai+1 is reached when applying oi, i.e., c = ai ∩ regr(ai+1, oi+1); 1 and (3) goal flaw: the sequence can be executed but sn is not a goal state, which results in the flaw ⟨sn, an ∩ C(G)⟩.

3 Abstractions for Conditional-Effect Tasks

Heuristics based on (conservative) abstractions are admissible because all concrete plans are preserved, which guarantees that abstract plans cannot be more expensive than their concrete counterparts. To preserve admissibility in the presence of conditional effects, we need to ensure that the abstraction remains conservative. We have to give up on inducedness, though, and instead over-approximate the set of

1 The regression of a Cartesian set is not Cartesian for operators with conditional effects. We deal with this in Section 4.2.

1 if pre(o) ≇ a then 2 return ∅ 3 forall v ∈ P do 4 post[v]←{x | ⟨C, v ↦→x⟩∈eff (o),C|P ∼= a}∪{a[v]} 5 forall ⟨C, v ↦→x⟩∈eff (o) | C|P ∼=a, vars(C)⊆P do 6 post [v] ← {x} 7 return {a o-→ b | b ∈×v∈P post[v]}

abstract transitions, since even for the basic class of projections, it is NP-hard to test whether an abstract transition is induced [B¨uchner et al., 2024].

3.1 Projections

We define the projection of a (partial) state s to a set of variables P as the partial state s|P that contains only the atoms of s for the variables in P. Algorithm 2 shows how to compute the over-approximation of outgoing transitions from abstract state a induced by operator o in a projection to P. If the precondition of o projected to P is not satisfied in a, we return the empty set. Otherwise, we compute for each variable v in P the set post[v] of possible values for v after applying o, accounting for the possibility that no effect is triggered for v and v keeps the value it has in a. We set post[v] to {x} for v ∈ P if there is an effect ⟨C, v ↦→ x⟩ that is guaranteed to be triggered. Finally, we compute the Cartesian product of all sets post[v] for v ∈ P to obtain the set of successor states b.

Theorem 1. Projection heuristics computed with Algorithm 2 for tasks with conditional effects are admissible.

Proof Sketch. Abstractions computed by Algorithm 2 are conservative, since the algorithm considers all subsets of effects that could be triggered.

3.2 Merge-and-Shrink Abstractions

Since merge-and-shrink abstractions start from (atomic) projections, we can use Algorithm 2 to over-approximate them.

Theorem 2. Merge-and-shrink heuristics that use Algorithm 2 for computing the initial factors are admissible for tasks with conditional effects.

Proof Sketch. M&S is compositional. If the initial factors are conservative and only conservative transformations are applied, the resulting abstraction is also conservative.

4 Cartesian Abstractions for Tasks with Conditional Effects

We now describe how to adapt Cartesian abstractions and the CEGAR algorithm to tasks with conditional effects. Of the five subroutines in Algorithm 1, TrivialAbstraction, TerminationCondition and FindOptimalTrace are not related to conditional effects, so no modification is needed. FindFlaw retrieves the next flaw and Refine repairs it by splitting the abstract state and rewiring transitions. We first explain the rewiring of transitions, and then describe the modifications needed for finding the different types of flaws.

Algorithm 3: Compute outgoing transitions from abstract state a via operator o in Cartesian abstraction α.

1 if pre(o) ≇ a then 2 return ∅ 3 post ← a ∩ C(pre(o)) 4 forall ⟨C, v ↦→ x⟩ ∈ eff (o) with C ∼= a do 5 post[v] ← post[v] ∪ {x} 6 forall ⟨C, v ↦→ x⟩ ∈ eff (o) do 7 if a[w] ={y} for all w ↦→ y ∈ C then 8 post [v] ← {x} 9 return {a o-→ b | b ∈ Sα, b ∩ post ̸= ∅}

4.1 Rewiring Transitions

A flaw ⟨s, c⟩ is repaired by splitting the abstract state α(s) into two child abstract states d and e with s∈d and c⊆e. Such a split is always possible and is done by partitioning the abstract domain α(s)[v] into d[v] and e[v] for a suitable split variable v ∈ V . After such a split, the transitions adjacent to α(s) must be rewired for d and e.

Algorithm 3 shows how to compute the outgoing transitions from a Cartesian state a via operator o ∈ O. If the precondition of o is not satisfied in a, we return the empty set. Otherwise, we use three steps to compute the possible values post[v] for each variable v ∈ V after applying o in a. First, we intersect a with the Cartesian partial state pre(o) to obtain the subset �post � ⊆ �a� of states in a in which o is applicable. Second, we iterate over the effects ⟨C, v ↦→ x⟩ ∈ eff (o) that might be triggered in a and add x to post[v]. Third, we iterate over the effects ⟨C, v ↦→ x⟩ ∈ eff (o) that are guaranteed to be triggered in a and replace post[v] with {x}. There is a transition a o-→ b if b ∈ Sα contains at least one value from post [v] for each variable v ∈ V .

Example 1. Briefcase [Pednault, 1988] is a domain with three types of operators: store puts an object into the briefcase, takeout leaves an object from the briefcase at the current location, and move moves all objects in the briefcase and the briefcase itself between two given locations. In our example task from this domain, a worker who is initially at work (W) has forgotten an important document (D) and must return home (H), take it and return to work (the only goal is to have the document at work). The variables for this task are the location of the briefcase vB, with domain {H,W}; the location of the document vD, with domain {H,W}; and whether the document is in the briefcase, vI, with domain {⊥,⊤}. The move operators are defined as move(ℓ,m) = ⟨pre = {vB ↦→ ℓ}, eff = {⟨{v ↦→ ℓ}, v ↦→ m⟩ | v ∈ V }, cost = 1⟩. Figure 1 shows the rewiring after splitting abstract state a into d and e. Since vI is abstracted in all states, the store and takeout operators only induce self-loops. After the split, the transitions that were adjacent to a are rewired to e, as e is the only new state that contains the effect atom and precondition vB ↦→H. Moreover, the move self-loops for a become transitions between d and e.

d

b

Figure 1: For an abstraction of the task in Example 1, we split a for atom vB ↦→ H, yielding states d and e. Self-loops are omitted and the variable order is vB, vD, vI .

Proof Sketch. The refinement loop maintains a conservative abstraction at all steps, by considering all effects that could be triggered.

Theorem 4. Cartesian CEGAR with Algorithm 3 may yield non-induced abstractions for tasks with conditional effects.

Proof. Consider planning task Π = ⟨V,O, I,G⟩, with V={v0, v1, v2}, Dv0 =Dv1 =Dv2 ={0, 1}, O={o}, o = ⟨pre = {}, eff = { ⟨{v0 ↦→ 0}, {v1 ↦→ 1}⟩, ⟨{v0 ↦→ 1}, {v2 ↦→ 1}⟩ } , cost = 1⟩, I = {v0 ↦→ 0, v1 ↦→ 0, v2 ↦→ 0}, and G = {v2 ↦→ 1}. After separating the values of v1 and v2 in all abstract states, we obtain an abstract transition system that has the four states a0 = {0, 1} × {0} × {0}, a1 = {0, 1} × {1} × {1}, a2 = {0, 1}×{0}×{1}, and a3 = {0, 1}×{1}×{0}, with an optimal plan trace τ α =⟨a0 o-→ a1⟩. Transition a0 o-→ a1 has no counterpart in the concrete transition system, as both states mapped to a0 satisfy only one of the effect conditions.

4.2 Progression Flaws

Having discussed how to rewire the transition system after a given split, we now focus on deciding which splits to perform in the first place. Out of the three flaw causes-precondition flaws, deviation flaws and goal flaws-conditional effects impact only deviation flaws, as operator applicability only depends on operator preconditions (not their effects) and the goal status of a state does not depend on any operator. There are three main strategies for finding (deviation) flaws in CEGAR: progression flaws, regression flaws and sequence flaws, and we now discuss how to adapt them to tasks with conditional effects, beginning with progression flaws.

A deviation exists for a transition a o-→ b in an abstract plan trace τ α = a0 o1 -→ . . . oi -→ a o-→ b ok -→ . . . on -→ an, if s∈�a� and t /∈�b� for the state s=progr(I, o1, . . . , oi) and the state t=progr(s, o). In such a case, the deviation flaw is ⟨s, c⟩ with c = a ∩ regr(b, o). An obstacle here is that regression is not Cartesian for operators with conditional effects. However, we only need to know the possible values for each variable to detect deviations. Therefore, we over-approximate the regression of a Cartesian state b over operator o with conditional effects as the Cartesian set regr (b, o). For each variable v ∈ V , we define the set of possible values before applying o as regr(b, o)[v] =

where we always use the first case that applies. We omit the case where regr(b, o)[v] is empty, as it cannot happen during the CEGAR loop.

It is often the case that multiple variables are the cause for a single deviation. Fixing all causes simultaneously would require to modify the CEGAR algorithm to apply multiple splits in the same iteration of the refinement loop. However, it is simpler to split only for a single variable in each iteration, and to account for the rest of the flaw in later iterations. A similar situation already occurs for tasks without conditional effects when several preconditions are not satisfied by a concrete state. Here, existing methods refine for only one of the preconditions in each iteration.

Example 2. A deviation flaw exists in state e of the bottom abstraction shown in Figure 1, because move(H,W) does not change the location of the document if the document is not inside the briefcase. Thus, vD ↦→H continues to hold after applying move(H,W) in the concrete state {vB ↦→H, vD ↦→H, vI ↦→⊥}, but not in the abstract state b. This flaw can be fixed by splitting off vI ↦→ ⊤ from e.

Theorem 5. Let τ α = a0 o1 -→ a1 o2 -→ . . . on -→ an be an abstract plan trace of a task Π with conditional effects. Then, τ α is mappable iff τ α has no progression flaw.

Proof Sketch. (⇒) If τ α is mappable, then there is a concrete trace τ without deviation flaws. Since those are the only flaws that can be caused by conditional effects, we know that τ has no flaws at all. (⇐) If there are no flaws, then there are also no deviation flaws, which means that τ α is mappable.

4.3 Regression Flaws

Regression flaws are found by executing an abstract plan in regression from the goals [Pozo et al., 2024b]. Given a transition a o-→ b ∈ τ α =a0 o1 -→ . . . oi -→ a o-→ b ok -→ . . . on -→ an, a deviation exists if p ∼= b and q ≇ a for the Cartesian state p=C(regr(G, on, . . . , ok)) and the Cartesian state q=C(regr(p, o)). Handling deviation flaws in regression is easier than in progression because effect conditions are not evaluated in the abstract state b that will be split, but in a. Therefore, the way to find deviations is the same as without conditional effects except that the effect is possibly not triggered, so a deviation may happen in an atom v ↦→ x only if p[v] = x and |b[v]| > 1.

Regression flaws are found in an optimal abstract plan by applying the plan from G to I in a Cartesian state space. Again, the obstacle here is that regression over operators with conditional effects is not Cartesian. Therefore, representing the regression of a Cartesian state b over an operator o requires a disjunction of up to cf Cartesian sets, where f is the number of effect atoms of o that hold in b and c is the highest number of conditions of those effects. To avoid this blow-up, we apply regression as the Cartesian over-approximation in Equation 1. But this over-approximation comes with a compromise: regressed Cartesian sets are supersets of the actual regression, so they may not find all regression flaws.

Theorem 6. Let τ α = a0 o1 -→ . . . on -→ an be an abstract plan trace for a task Π. Then, although τ α has no regression flaw with regression by Cartesian over-approximation, the sequence ⟨o1, o2, . . . , on⟩ may not be a plan for Π.

Proof. Let Π be the planning task from the proof of Theorem 4. The trace a0 o-→ a1 has no regression flaw with Cartesian over-approximation because I ∈ �regr(G, o) = {0, 1} × {0, 1} × {0, 1}� but ⟨o⟩ is not a plan for Π because progr(I, o) = {v0 ↦→ 0, v1 ↦→ 1, v2 ↦→ 0} /∈ SG.

Given an abstract plan trace τ α = a0 o1 -→ . . . on -→ an and a backward plan trace τ = pm om+1 ←--- . . . on ←- pn, m ∈ [0, n), we mitigate this issue with two adjustments. The first one is to intersect each pi with ai, that is, we start the search of flaws from an instead of G and intersect each regr(pi, oi) with ai-1. However, this does not guarantee finding a flaw when ⟨o1, o2, . . . , on⟩ is not a plan for the task [Pozo et al., 2024b], so the CEGAR algorithm may finish before finding a solution or reaching the termination condition. The second adjustment addresses this issue by searching for a progression flaw as a fallback when no regression flaw is found.

Theorem 7. Let τ α = a0 o1 -→ . . . on -→ an be an abstract plan trace for a task Π. Then, τ α is mappable iff τ α has no regression flaw with the progression flaw fallback.

Proof Sketch. A progression flaw is searched if no regression flaw is found, so the proof of Theorem 5 applies.

4.4 Sequence Flaws

Sequence flaws allow finding flaws in the middle of a plan by continuing the search for flaws "behind" a progression flaw or "before" a regression flaw in an abstract plan trace [Pozo et al., 2024a]. This is achieved by two sequence relaxations: allowing to apply an inapplicable operator o by assigning unmet preconditions to variables v /∈ vars(eff (o)); and the undeviation of a successor Cartesian state r by setting r[v] =a[v] for all v ∈V where r[v] ∩a[v]=∅.

The deviation of sequence flaws in progression and regression is exactly the same as their "first-flaw" counterparts, since these relaxations do not affect deviations. Nevertheless, an important difference exists compared to sequence flaws for tasks without conditional effects: given a successor abstract state b and a Cartesian state r′ , intersecting them as in previous work [Pozo et al., 2024a] is not sufficient to guarantee that there is no deviation flaw. This is the case because the absence of deviation requires that the set of outgoing transitions from r′ is a subset of outgoing transitions from b. This is true for the intersection without conditional effects but not for an operator o with an effect e∈eff (o) s.t. conds(e)∼=r′ , conds(e)≇b. However, there is a sufficient condition that guarantees the absence of deviation flaws for operators with conditional effects: r′ ⊆b. If this condition holds, then we do not need to check for deviation flaws. Otherwise, we perform the deviation check.

5 Experiments

We implemented our algorithms in the Scorpion planning system [Seipp et al., 2020a], which is an extension of Fast Downward [Helmert, 2006]. For all configurations we use the h2 preprocessor [Alc´azar and Torralba, 2015] and limit time and memory for each planner run to 30 minutes and 8GiB, respectively. We use Downward Lab [Seipp et al., 2017] and run experiments on Xeon Gold 6130 processors.

As our benchmark set, we use the domains with conditional effects from the last two IPCs, the domains used by R¨oger et al. [2014], the matrix multiplication domain [Speck et al., 2023], and the domain for transforming quantum circuits into CNOT-only layouts [Shaik and van de Pol, 2024]. This benchmark set consists of 1963 tasks from 21 domains. All code, benchmarks, and experiment data is available online [Pozo and Seipp, 2025].

We evaluate our techniques in four subsections: computing a single abstraction, multiple abstractions of the same abstraction type, combinations of multiple abstraction types, and a comparison versus baselines. Table 1 shows coverage results.

5.1 Single Abstraction

We begin by comparing a single merge-and-shrink (M&S) to a single Cartesian abstraction. For M&S, we use the recommended values for all parameters [Sievers, 2018] and up to 100 000 abstract states. For Cartesian abstractions, we use incremental search to find abstract plans [Seipp et al., 2020b] and a time limit of 900 seconds for the CEGAR loop.

We focus on the "M&S" and "Single Cartesian" columns in Table 1 for now. Among these algorithms, hMS solves the highest number of tasks overall, mainly due its high coverage for CNOT tasks. Cartesian abstractions with regression flaws and progression flaw fallback (B) yield the highest coverage among Cartesian abstractions, and they dominate hMS in all domains with general conditional effects except for Miconic and the CNOT domains because refining closer to goal states yields more informative heuristics. However, Cartesian abstractions using sequence flaws (S) solve the most tasks in all factored domains and Briefcase, where fewer regression flaws are found and the progression flaw fallback is needed often.

5.2 Multiple Abstractions

We compare saturated cost partitioning (SCP) over Cartesian abstractions for landmark and goal subtasks 2 [Seipp and Helmert, 2018] with SCP over M&S abstractions (hMS SCP ) [Sievers et al., 2020], and Sys-SCP PDBs combined by SCP (hPDB SCP ) [Seipp, 2019].

Again, regression flaws with the progression flaw fallback (B) obtain the highest coverage for Cartesian abstractions for all domains except the FSC Domains. However, SCP over Cartesian abstractions solves fewer tasks than a single abstraction in Rubik′s Cube, CNOT domains and factored domains, where the interaction between goals is more intricate and not captured by subtasks. PDBs solve many Miconic tasks and hMS SCP has its strength in factored tasks and CNOT domains.

2 We do not compute domain abstractions for subtasks because they do not support conditional effects [Seipp and Helmert, 2018].

5.3 Combinations of Abstractions

Finally, we combine abstractions of different types via saturated cost partitioning. As the base ingredient, we use PDBs, because they proved to be complementary to Cartesian abstractions. To this, we add different collections of Cartesian abstractions (see caption of Table 1). We use at most 100 seconds to compute PDBs and at most 50 million non-looping transitions in total for Cartesian abstractions. Table 1 shows that C fBS B is the strongest among the combinations in all domains. It combines multiple Cartesian abstractions over subtasks using regression flaws, a single Cartesian abstraction over the full task using regression flaws and a single Cartesian abstraction over the full task using sequence flaws. In total, this configuration solves 39 more tasks than the secondbest combination, CB, mainly because repairing flaws for the full task refines parts of the abstract state space that are kept coarse for individual landmark and goal subtasks, especially in CNOT domains and factored tasks.

5.4 State of the Art

As baselines, we use LM-Cut with context splitting (hLMC ) [R¨oger et al., 2014] and symbolic bidirectional search (Sym) [Speck et al., 2025]. For factored tasks, we use a single Cartesian abstraction (hCart fact ) and multiple PDBs (hPDBs fact ) [B¨uchner et al., 2024] as our baselines.

hLMC is very good for Miconic-where delete-relaxation works well because each operator appears at most once in optimal plans-but it solves even fewer tasks than a single Cartesian abstraction in the other domains. Sym is the strongest baseline, especially for factored tasks, but it is still weaker than hPDBs fact for these tasks. However, C fBS B dominates all baselines in 9 domains, solving 59 more tasks in total than Sym. hMS SCP is the best technique for CNOT domains, but it struggles in Miconic. Finally, for factored tasks the dedicated algorithm that computes PDBs is the clear winner in all domains, solving 51 more tasks than C fBS B . Figure 2 shows that the heuristic quality of C fBS B is higher than hMS SCP except in CNOT domains, but lower than hPDBs fact for factored tasks.

6 Conclusions

We showed how to support conditional effects in PDBs, M&S, and Cartesian abstractions, including support for regression and sequence flaws. Our strongest algorithm, which combines PDBs and Cartesian abstractions, solves many more tasks than symbolic search, the previous state of the art.

CEGAR is also suitable for domain abstractions, which fall in between projections and Cartesian abstractions on the generality scale [Kreft et al., 2023]. Future work could extend them to support conditional effects.

Acknowledgments

We thank Malte Helmert for his valuable feedback on the implementation of conditional-effect support for merge-andshrink abstractions.

This work was partially funded by grant PID2021127647NB-C21 from MICIU/AEI/10.13039/501100011033, by the ERDF "A way of making Europe", and by the Madrid Government under the Multiannual Agreement with UC3M in the line of Excellence of University Professors (EPUC3M17) in the context of the V PRICIT (Regional Programme of Research and Technological Innovation). This work was also supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.