From Qualitative to Quantitative Dominance Pruning for Optimal Planning

1 Introduction

Most classical planners focus on reducing the search space. Their success greatly depends on their ability to exploit the structure of the problem in the form of heuristics or pruning methods. Pruning methods reduce the search effort by eliminating redundant states [Pochter et al., 2011] or avoiding the application of some actions [Wehrle and Helmert, 2012] while preserving at least one optimal plan. Dominance pruning methods automatically construct a relation that compares states, to eliminate those that are dominated by others. Previous approaches define a qualitative relation, ⪯, in which t is said to dominate s (s ⪯ t) if it is at least as close to the goal [Hall et al., 2013]. In that case, s may be safely pruned if its g-value is not lower than that of t.

We generalize the label-dominance (LD) simulation method originally devised to compute qualitative dominance [Torralba and Hoffmann, 2015] to a quantitative version. Instead of a relation, we define a function D : S ×S → R ∪ {-∞} that measures "by how much" does t dominate s. A positive value D(s, t) > 0 means that t is strictly closer to the goal than s. Negative values bound the difference in goal distance between t and s.

Theoretically, quantitative dominance has several advantages. First, it may find coarser relations, hereby strengthening previous dominance pruning methods. Second, and more importantly, novel pruning methods may take advantage of the additional information. One way is to trade-off dominance and g-value. If D(s, t) > 0 we may prune s even if its g-value is lower. If D(s, t) < 0 there is no qualitative dominance but, we can still prune s if its g-value is large enough. Another way is to use quantitative dominance to prove that an action a starts an optimal plan from a given state s, whenever the successor dominates s by an amount equal to the action cost. We introduce a novel type of pruning, which we call action selection pruning, that prunes any other successor reducing the branching factor to one.

Empirically, we show that quantitative dominance can greatly reduce the search space in many benchmark domains, even when compared to the qualitative version. However, there is a big overhead to perform as much pruning as possible so approximation methods may be desirable. Action selection, on the other hand, achieves an impressive amount of pruning with very low overhead. Moreover, it is complementary to previous dominance pruning methods and it greatly improves their performance in many domains.

2 Background

A planning task is a tuple Π = 〈V,A, I, G〉. V is a finite set of variables v, each with a finite domain Dv. A partial state is a function s on a subset V(s) of V, so that s(v) ∈ Dv for all v ∈ V(s); s is a state if V(s) = V. I is the initial state and the goal G is a partial state. A is a finite set of actions. Each a ∈ A is a tuple 〈prea, eff a, c(a)〉 where prea and eff a are partial states, called its precondition and effect, and c(a) ∈ R+0 is its cost. An action a is applicable in a state s if s(v) = prea(v) ∀v ∈ V(prea). In that case, the result of applying a in s, denoted sJaK, is another state s.t. sJaK(v) = eff a(v) if v ∈ V(eff a), and sJaK(v) = s(v) otherwise.

A labeled transition system (LTS) is a tuple Θ = 〈S,L, T, sI , SG〉 where S is a finite set of states, L is a finite set of labels each associated with a label cost c(l) ∈ R+0 , T ⊆ S×L×S is a set of transitions, sI ∈ S is the start state, and SG ⊆ S is the set of goal states. A planning task defines a state space, which is an LTS where: S is the set of all states; sI = I; s ∈ SG iff G ⊆ s; L = A, and s a-→ sJaK ∈ T if a is applicable in s. We will use s ∈ Θ to refer to states in Θ and s a-→ t to refer to their transitions.

A plan for a state s is a path from s to any sG ∈ SG. We denote h∗ (s) (g∗ (s)) to the cost of a cheapest plan for s (path from I to s). A plan for s is optimal iff its cost equals h∗ (s) and is strongly optimal if its number of 0-cost actions (denoted h∗0 (s)) is minimal among all optimal plans for s.

We consider a representation of the planning task as a set of LTSs on a common set of labels, {Θ1, . . . ,Θk} [Helmert et al., 2007; 2014]. Whenever it is not clear from the context, we will use subscripts to differentiate states in the state space, Θ (s, s′ , t) and in the individual components Θi (si, s′i , ti). The synchronized product of two LTSs Θ1 ⊗ Θ2 is another LTS with states S = {(s1, s2) | s1 ∈ Θ1 ∧ s2 ∈ Θ2}, transitions T = {(s1, s2) l-→ (s′1 s′2 ) | s1 l-→ s′1 ∧ s2 l-→ s′2 }, s.t. (s1, s2) ∈ SG iff s1 ∈ SG 1 and s2 ∈ SG 2 .

3 Simulation-Based Qualitative Dominance

This section describes the label-dominance (LD) simulation method we build upon [Torralba and Hoffmann, 2015]. Given a planning task with states S, a dominance relation is a relation ⪯⊆ S × S where s ⪯ t implies h∗ (t) < h∗ (s) or h∗ (t) = h∗ (s) and h∗0 (t) ≤ h∗0 (s). Such relation can be used to prune states during the search: A search node ns (representing state s) can be pruned at any point if there exists a

node nt ∈ open ∪ closed s.t. g(nt) ≤ g(ns) and s ⪯ t. A relation ⪯ is goal-respecting if whenever s ⪯ t, t ∈ SG ∨ s ̸∈ SG. ⪯ is a simulation relation if, whenever s ⪯ t, for all s l-→ s′ , there exists t l-→ t′ s.t. s′ ⪯ t′ . A costsimulation allows the transition from t to use a different label of lower or equal cost, i.e., whenever s ⪯ t, for every s l-→ s′ , there exists a transition t l′-→ t′ s.t. s′ ⪯ t′ and c(l′ ) ≤ c(l). In a compositional approach, we take as input a set of LTSs {Θ1, . . . ,Θk} and compute a relation ⪯i on each Θi to obtain a goal-respecting cost-simulation of the whole state space Θ1 ⊗ . . . ⊗Θk. LD simulation computes all of them simultaneously, using label dominance to ensure that the property still holds after merging every Θi.

Definition 1 (LD Simulation) A set {⪯1, . . . ,⪯k} of relations ⪯i⊆ Si × Si is a label-dominance (LD) simulation for {Θ1, . . . ,Θk} if all ⪯i are goal-respecting and, whenever s ⪯i t, for all s l-→ s′ ∈ Θi, there exists a transition t l′-→ t′ in Θi s.t. s′ ⪯i t′ , c(l′ ) ≤ c(l), and for all j ̸= i, l′ dominates l in Θj given ⪯j. We say that l′ dominates l in Θj given ⪯j if for all s l-→ s′ ∈ Θj there exists s l′-→ t′ ∈ Θj s.t. s′ ⪯ t′ .

A typical example is a logistics task where a single truck must transport n packages from location A to B. Figure 1

Intuitively, t dominates s in Θi if, for every outgoing transition from s, t has an at least as good transition where the targets are compared according to ⪯i and the labels are compared in all other Θj to ensure that there is no negative side effect. For any LD simulation {⪯1, . . . , ⪯k}, we can define a relation ⪯ s.t. s ⪯ t iff si ⪯i ti for each Θi. This relation is a goal-respecting cost-simulation and hence, a valid dominance relation for the state space Θ ≡ Θ1 ⊗ . . . ⊗ Θk.

shows the LTSs of the case with a single package. In this example, LD simulation finds a relation where PA ⪯ PT ⪯ PB, i.e., having a package at its destination is at least as good as having it in the truck, which is at least as good as having it anywhere else. This holds independently of the position of the truck or the other packages in case there are any. This allows to prune, for example, state 〈TA, PA〉 if 〈TA, PT 〉 has lower or equal g-value. This is quite useful, as it prunes away any state in which a package has been unloaded in any location other than its destination. However, in the next sections we see that quantitative dominance can do much more.

4 Quantitative Dominance

First, we generalize the definition of dominance relations.

Definition 2 (Quantitative Dominance Function) A function D : S × S → R ∪ {-∞} is a quantitative dominance function for an LTS Θ iff D(s, t) ≤ h∗ (s) - h∗ (t) and, if h∗ (s) = h∗ (t) and h∗0 (s) < h∗0 (t), then D(s, t) < 0.

Intuitively, if D(s, t) > 0, then t is strictly closer to the goal than s; if D(s, t) = 0 then t is at least as close to the goal as s; and if -∞ < D(s, t) < 0, t can get as close to the goal as s by paying a price of -D(s, t). Finally, if D(s, t) = -∞, we did not discover any dominance of t over s. The second part of the definition ensures that the pruning is safe in domains with 0-cost actions, where s should not be dominated by t if it is in the path from t to the goal. Given a function D, we can define dominance relations based on it.

Definition 3 (Quantitative Dominance Relation) Let D be a quantitative dominance function on an LTS Θ and let C ∈ R be a constant. We define the C-dominance relation as s ⪯CD t iff D(s, t) ≥ C.

This generalizes qualitative dominance, since ⪯0D is a qualitative dominance relation. For any other ⪯CD , we distinguish between positive and negative dominance relations depending on whether C > 0 or C < 0. For unspecified C, s ⪯CD t serves as a shorthand for D(s, t) > -∞.

4.1 Quantitative Compositional LD Simulation

We follow a compositional approach. Given a set of LTSs {Θ1, . . . ,Θk}, we define a quantitative dominance for each of them so that their aggregation is a quantitative dominance function of the state space of the planning task, Θ1⊗. . .⊗Θk.

To operationalize this definition, we draw upon LD simulation relations. Let s and t be two states for which s ⪯ t. Then, in the standard notion of simulation any plan πs for s must also be a plan for t. As this is too restrictive for deriving useful dominance relations, LD simulation allows to use different labels in the plan πt from t and, if a noop action is considered, πt can be shorter than πs. A limitation is that it still requires the plan for t not to be longer than that from s. This is fine in qualitative dominance because there is usually a strong correlation between plan cost and length [Radzi, 2011]. However, it is an impediment to infer negative dominance since if there exists a path t →∗ s of cost c we would like to infer that D(s, t) ≥ -c. Consider the position of the truck in our example. In an LD simulation, TA ̸⪯1 TB because of the transition TA lA -→ TA for which TB does not have any counterpart (noop or lB do not dominate lA in the other LTSs). However, since the movements of the truck do not depend on any other variable, D1(TA, TB) = -1 because from TB we can always reach TA without having any side effects on other variables.

We avoid this restriction by considering weak simulation relations [Hennessy and Milner, 1985]. Weak simulations consider a set of internal τ-labels that are not relevant to describe the behavior of the system. Therefore, each transition s l-→ s′ can be simulated by a path t τ-→∗u l-→ u′ τ-→∗ t′ s.t. s′ ⪯ t′ . In our case, τ-labels are those that do not have any preconditions or effects in other LTSs, like dr for the position of the truck in our example.

Definition 4 (τ-label) Let {Θ1, . . . ,Θk} be a set of LTSs. Label l is a τ-label forΘi iff s l-→ s ∈ Θj ∀Θj ̸= Θi, s ∈ Θj.

The actions in a τ -path are not relevant, only its cost is. We model this by defining the τ -distance between any two states. Definition 5 (τ -distance) Let s and t be two states in an LTS Θ. The, τ-distance from s to t, written hτ (s, t), is the cost of a minimum-cost path from s to t in Θ using only transitions with τ labels or ∞ if no such path exists. 0-cost transitions are considered to have an infinitesimal cost ϵ.

We define goal-respecting functions so that non-goal states can only dominate goal states if they have a τ -path to the goal.

Definition 6 (Goal-respecting function) A function D is goal-respecting for Θ iff for all s ∈ SG and t ∈ S, D(s, t) ≤ maxsg∈SG -hτ (t, sg).

Finally, we extend the definition of label dominance to the quantitative case, by defining a function DL(l, l′ ) that captures the relation between labels.

Definition 7 (Label-dominance function) Let D be a function for Θ, we define its corresponding label-dominance function as DL(l, l′ ) = mins l-→s′∈Θ maxs l′-→s′′∈Θ D(s′ , s′′ )

If DL(l, l′ ) > 0, then whenever l is applicable in any state s, applying l′ will lead to a better state. If -∞< DL j (l, l′ ) < 0, we can reach an at-least-as-good state by paying the corresponding price.

Definition 8 (QLD Simulation) Let DF = {D1, . . . ,Dk} be a set of goal-respecting functions for T = {Θ1, . . . ,Θk}. DF is a quantitative label-dominance (QLD) simulation for T if for all Θi ∈ T and s, t ∈ Θi, Di(s, t) ≤ fQLD(T , DF , i, s, t) where fQLD(T , DF , i, s, t) :=

⪯C1

Intuitively, we compare all transitions from s (s l-→ s′ ), against the best alternative from t (t τ-→∗u l-→ u′ ) 1 by summing up the difference in goal-distance of the targets (Di(s′ , u′ )), the cost of the transition from s (c(l)), minus the cost of the path from t (hτ (t, u) + c(l′ )). Finally, ∑j̸=i DL j (l, l′ ) estimates the benefit or penalty for using l′ instead of l in the other LTSs. Applying this definition to our example, we now find some dominance for the truck D1(TA, TB) = D1(TB, TA) = -1. For the package, we find that D2(PA, PT ) = 1, D2(PT , PB) = 1 so D2(PA, PB) = 2. This is similar to the result of LD simulation PA ⪯ PT ⪯ PB, but with the additional information that is strictly closer instead of at least as close to the goal.

Theorem 1 A unique maximal QLD simulation exists.

Proof Sketch: The "identity" function (Di(si, ti) = -∞ if si ̸= ti and 0 otherwise) is always an QLD simulation. Given any two QLD simulations, their maximum is also an QLD simulation so a unique maximal QLD simulation exists. □

Theorem 2 Let {D1, . . . ,Dk} be an QLD simulation on {Θ1, . . . , Θk}. Then, D1 + · · · + Dk is a quantitative dominance function on Θ1 ⊗ . . . ⊗ Θk.

Proof Sketch: If there is a single LTS, it can be proved that D(s, t) ≤ h∗ (s) - h∗ (t) for all s, t ∈ Θ by induction on the length of a shortest optimal plan for s. If there are multiple LTSs, it can be proved that QLD simulation is invariant under merge, i.e., the result of replacingΘ1 andΘ2 byΘ1⊗Θ2 and D1 and D2 by D1 +D2 is still a QLD simulation. The key is to show that for any transition s = (s1, s2) l-→ (s′1 , s′2 ) = s′ , there exists a transition (u1, u2) l′-→ (u′1 , u′2 ) s.t. (*) D(s, t) ≤ D(s′ , u′ ) + c(l) - hτ (t, u) - c(l′ ) + ∑j∈3,...,k DL j (l, l′ ). Figure 2 illustrates the following steps. In Θ1, since s1 ⪯CD1 t1, there must exist u1 la -→ ta1 s.t. (E1) D1(s1, t1) ≤ D1(s′1 , ta1 ) - hτ (t1, u1) + c(l) - c(la ) + ∑j∈2,...,k DL j (l, la ). This implies that l ⪯L2 la . In Θ2, since l ⪯L2 la and s2 l-→ s′2 , there must exist s2 la -→ sa2 s.t. (E2) DL 2 (l, la ) ≤ D2(s′2 , sa2 ). Now, since s2 ⪯CD2 t2 there must exist u2 l′-→ u′2 s.t. (E3) D2(s2, t2) ≤ D2(sa2 , u′2 ) - hτ (t1, u1) + c(la ) - c(l′ ) + ∑j∈2,...,k DL j (la , l′ ). This implies that la ⪯L1 l. Going back toΘ1, since la ⪯L1 l, theremust exist u1 l′-→ u′1 such that (E4) DL 1 la , l′ ≤ D1(ta , u′1 ). To prove that the inequality (*) holds, we substitute the inequalities (E1-E4) in the left part. A full proof is included in an extended version [Torralba, 2017] □

1 The path u′ τ-→∗ t′ is implicitly considered by D(s′ , u′ ).

Algorithm 1: Quantitative LD simulation

Input: LTSs: T = {Θ1, . . . , Θk}, Limit: K ∈ N Output: Dominance Function DF = {D1, . . . , Dk} 1 Di[s, t] ←maxsg∈SG i -hτ (t, sg) ∀t ∈ Θi, s ∈ SG i 2 Di[s, t] ← h∗ (s) - h∗ (t) ∀t ∈ Θi, s ̸∈ SG i 3 while ∃i ∈ [1, k], s, t ∈ Θi s.t. Di[s, t] > fQLD(T , DF , i, s, t) 4 if fQLD(T , DF , i, s, t) > -K then 5 Di[s, t] ← fQLD(T , DF , i, s, t) 6 else 7 Di[s, t] ← -hτ (t, s) 8 return {D1, . . . ,Dk}

4.2 Computing Quantitative LD Simulations

Algorithm 1 shows how to compute an QLD simulation for a set of LTSs T , given a parameter, K. Each Di is initialized as the maximal goal-respecting function. Then, at each iteration it checks whether the property Di(s, t) ≤ fQLD(T ,DF, i, s, t) is violated for some Di(s, t). In that case, it updates the value and repeats until the result is a valid QLD simulation. For sufficiently large K (e.g., if K is greater than the maximum cost of any plan of the task, which can be easily bounded by |Θ1 ⊗ . . . ⊗ Θk|(maxl∈L c(l))), Algorithm 1 will find the maximal QLD simulation.

Theorem 3 Algorithm 1 has a worst-case running time polynomial in |Θ1|× . . . × |Θk|×|L|×maxsi∈Θi (h∗ (si) + K) × gcd({cl | l ∈ L}).

In practice we set K to a lower value. While this diminishes the power to infer negative dominance below -K, those are of little use anyway, since they will only be useful to prune states with very large g-value. Note that, even though the algorithm does not run in polynomial time (since h∗ (si) may be exponential in the size of the input, depending on the labels' cost), this is not a major inconvenience in practice. Other pruning techniques, like symmetry pruning [Pochter et al., 2011; Domshlak et al., 2012], also rely on non-polynomial algorithms in their precomputation phase. This is not a problem, as soon as the algorithm finishes in a reasonable amount of time for tasks that are solvable without any pruning.

Proof Sketch: Each iteration takes polynomial time in the size of the input, i.e., the LTSs and L. At each iteration the value of some Di(s, t) decreases by at least gcd({cl | l ∈ L}), so the number of iterations is polynomially bounded by the number of times the number can decrease. The maximum value in the initialization is bounded by maxsi∈Θi h∗ (si), and the minimum by -K. □

4.3 Advantages of Quantitative LD Simulation

Qualitative dominance pruning methods prune a node ns if there exists another nt s.t. g(nt) ≤ g(ns) and s ⪯ t. An advantage of quantitative dominance is that, even when restricted to this type of pruning, QLD simulations will find coarser relations.

Theorem 4 Let ⪯ and D be the coarsest qualitative and maximal quantitative LD simulation, respectively. Then, ⪯⊆⪯0D and there are cases where ⪯⊂⪯0D .

Proof Sketch: For ⪯⊆⪯0D . Define D(s, t) = 0 if s ⪯ t and -∞ otherwise. Then, D is an QLD simulation.

For ⪯⊂⪯0D , consider our example where no qualitative dominance can possibly be found for states that differ in the position of the truck. However, TBPA ⪯0D TAPT , since D(TA, TB) = -hτ (TB, TA) = -1, and D(PA, PT ) = 1, we can compensate the truck being at a different location if we have picked up or delivered more packages. □

Moreover, we can trade off dominance and g-value to further increase the amount of pruning.

Theorem 5 Let D be a dominance function. Let ns be a search node with state s. If there exists nt ∈ open ∪ closed s.t. Dϵ (s, t)+g(ns)-g(nt) ≥ 0 where Dϵ (s, t) = D(s, t)-ϵ if D(s, t) < 0 and D(s, t) otherwise. Then, pruning ns preserves completeness and optimality of the algorithm.

Proof Sketch: Since g(nt) + h∗ (t) ≤ g(ns) + h∗ (s), if an optimal plan from I to G goes through ns, then g(ns) = g∗ (s) and there is another optimal plan through nt. If s is in the path from t to the goal, then D(s, t) < 0. This means that g(nt) + h∗ (t) + ϵ = g∗ (s) + h∗ (s) + ϵ ≤ g(ns) + h∗ (s), so g∗ (s) < g(ns), reaching a contradiction. □

Theorem 5 generalizes the qualitative pruning condition. For nodes ns, nt s.t. g(ns) = g(nt) nothing changes, since ns is pruned iff s ⪯0D t. However, if g(ns) ̸= g(nt) we can leverage quantitative dominance to get more pruning:

• If g(ns) < g(nt), qualitative dominance cannot prune ns. Now, ns may still be pruned if D(s, t) is high enough. This is specially relevant in A∗ . If there is some nt in the closed list with a higher g-value than that of ns, nt was preferred by the heuristic, so there are chances of D(s, t) > 0, assuming that dominance and the heuristic are correlated.
• If g(nt) < g(ns), we replace the relation ⪯0D by the coarser ⪯g(nt)-g(ns)+ϵ D . This may be useful in practice because the successors of t do not necessarily dominate s or its successors according to ⪯0D .

5 Action Selection Pruning

Instead of pruning states that are deemed worse than others, we may use quantitative dominance to perform action selection. Upon expansion of a node ns, if there exists an applicable action a s.t. s ⪯c(a) D sJaK, then only that successor needs to be generated, reducing the branching factor to 1. This is safe because a starts an optimal plan from s if one exists.

Theorem 6 Let D be a dominance function. Let s be a state and a an applicable action on s. If D(s, sJaK) ≥ c(a), then a starts an optimal plan from s to the goal if one exists.

Proof Sketch: As D(s, sJaK) ≥ c(a), then h∗ (s) ≥ h∗ (s[a]) + c(a). If c(a) > 0, sJaK is strictly closer to the goal. If c(a) = 0, then h∗ (s) = h∗ (t). By the definition of dominance function, h∗0 (sJaK) ≤ h∗0 (s). Therefore, s[a] has a path to the goal that does not go through s. □

In our running example, this is extremely powerful. Whenever a package may be loaded into the truck or unloaded at its destination this is automatically done. Since the state resulting of unloading a package in any other location is dominated by its parent, combining both types of pruning the search will only branch over driving actions.

Action selection pruning is related to other heuristic or learning methods that detect useless actions [Wehrle et al., 2008] or even directly decide what action(s) to apply in certain states [Leckie and Zukerman, 1998; de la Rosa et al., 2011; Krajnansky et al., 2014]. Contrary to our pruning, these methods do not preserve completeness and optimality. Partial-order reduction techniques like strong stubborn sets [Wehrle and Helmert, 2012; Wehrle et al., 2013; Wehrle and Helmert, 2014] also reduce the branching factor. However, they are based on a different notion of action interference, and indeed they do not apply in our running example because (un)load actions interfere with driving actions.

6 Experiments

We run experiments on all the optimal-track STRIPS planning instances from the international planning competitions (IPC'98 - IPC'14). All experiments were conducted on a cluster of Intel Xeon E5-2650v3 machines with time (memory) cut-offs of 30 minutes (4 GB). Our main objective is to compare quantitative and qualitative dominance. We run A∗ with the blind heuristic and LM-cut [Helmert and Domshlak, 2009]. We use the same initial set of LTSs for all configurations, derived by running M&S with the merge DFP strategy [Dr¨ager et al., 2006; 2009; Sievers et al., 2014], without label reduction nor any shrinking, and with a time limit of 10 000 abstract transitions and 300 seconds. We use K = 10. 2 These limits are adequate to finish the precomputation phase in a reasonable time (under 30s in most domains, though it runs out of time in a few cases). For comparison against other pruning methods, we include partial-order reduction (POR) based on strong stubborn sets [Wehrle and Helmert, 2014].

2 Larger values for K are possible, but they were not observed to significantly affect the results during our preliminar experiments.

6.1 Pruning power

We start by analyzing the potential of action selection (AS) and dominance pruning based on comparing each node against previously expanded states. Table 1 shows the ratio of expansions until the last f-layer of each configuration compared to the baseline without pruning. We consider multiple variants, ranging from qualitative pruning (⪯) to full quantitative pruning (D). In the middle, we consider several approximations to analyze where the gain comes from. ⪯0D and ⪯0D perform the same pruning as ⪯, constructing a qualitative relation out of the quantitative dominance function. ⪯0D defines each ⪯i as si ⪯i ti iff Di(si, ti) ≥ 0 and then composes them. ⪯0D is always stronger since it trades negative dominance in one Di by positive dominance in another. Quantitative dominance methods use the full strength of the quantitative function by comparing against states with different g value. Dτ disables τ-labels to measure their relevance.

To implement all of the above, we adapt the BDD-based method used by [Torralba and Hoffmann, 2015] in which for each possible g-value they generate a BDD with all the states dominated by any state expanded with that g-value. For quantitative dominance, every time a state t is expanded, we insert the sets of states dominated by it in the corresponding g(t) -D(s, t) bucket. This has an important computational overhead in the qualitative case, which often becomes prohibitive with quantitative dominance. To obtain a more practical method, we use an approximation ⪯pD that prunes any state that is dominated by its parent. This greatly reduces the overhead since it ignores all previously expanded states.

Obs. 1: Quantitative dominance is applicable in the same domains as qualitative dominance, but has a larger pruning potential. The only exception is Scanalyzer where qualitative dominance does not achieve any pruning, but positive dominance has synergy with the LM-cut heuristic. However, among the domains where both techniques apply, quantitative dominance reduces the number of states in one or two orders of magnitude more than qualitative dominance. The gain comes from difference sources. In some domains, ⪯0D is already stronger than ⪯, showing the ability of QLD simulation to find coarser relations. Trading off negative and positive dominance to construct a relation (⪯0D ) already achieves most of the pruning in several domains, specially in blind search. Trading off dominance and g-value (D) is more relevant with heuristics (e.g., NoMystery). The potential of quantitative dominance is also reflected in the comparison against POR, since it is able to achieve stronger pruning in most domains. Finally, the consideration of τ labels can be seen important in around half of the domains, sometimes increasing the pruning in one order of magnitude.

Obs. 2: Action selection pruning is highly complementary to previous dominance pruning methods. In most domains, the combination of both methods is stronger than any of them. Moreover, since the overhead of action selection is quite low, it is almost always worth to use it whenever a quantitative dominance function has been computed.

6.2 Overall Performance

Table 2 compares the coverage of our two best methods, AS with pruning against the parent or against previously expanded nodes, against qualitative dominance and POR. For a fair comparison, we include qualitative pruning with the same input LTSs as our approach (D) and the configuration used by Torralba and Hoffmann[2015] (⪯TH ) which uses exact label reduction [Sievers et al., 2014], bisimulation shrinking [Nissim et al., 2011] and a larger LTS size (100k). All configurations except ⪯pD use the "safety belt" that disables the method if no pruning has been achieved after 1000 expansions.

Obs. 3: AS + ⪯pD has huge pruning power and low overhead, greatly increasing the capabilities of heuristic search planners. It obtains the best overall coverage, solving 128

Search time (s) LM-cut

Figure 3: Expansions until last f-layer and search time of AS + ⪯pD against the baseline with LM-cut.

instances over the baseline in blind search and 61 with LMcut, much higher than POR or qualitative dominance. Some domains like NoMystery that are hard even when using good heuristics, become simple under the analysis of quantitative dominance, which even with blind search is able to solve all tasks. Figure 3 directly compares the number of expanded nodes and search time of AS + ⪯pD against the baseline. It obtains reductions of several orders of magnitude in the number of expansions with little overhead. Note that this ignores the precomputation time (which can be of up to 300s to compute the LTSs plus the computation of the QLD simulation), but, as the coverage improvement shows, the precomputation time is highly compensated by the search space reduction in instances that are not quickly solved by the baseline.

Obs. 4: The overhead of current methods for exploiting the full potential of quantitative dominance (D) is too high to pay off. The D configuration did not improve the other methods anywhere and was excluded from the table. This contrasts with the results of Table 1 that show a great potential. However, there are a few domains where the additional pruning when using ⪯0D to complement AS pays off like Driverlog, Openstacks or VisitAll. Further exploring this trade-off between pruning power and overhead (e.g., using dominance-based methods for irrelevance pruning [Torralba and Kissmann, 2015]) is an interesting topic for future work.

7 Conclusion

We have introduced the notion of quantitative dominance for optimal planning, which extends previous approaches of qualitative dominance. This extension is more effective at analyzing the structure of the task, which leads to stronger pruning. More importantly, the quantitative information enables new ways of pruning. We introduced action selection pruning, a novel pruning method that applies a single action on a state if the action starts an optimal plan from the state according to the quantitative dominance function. Our experiments show that action selection is highly complementary to previous dominance pruning methods, greatly extending the capabilities of heuristic search planners.

Acknowledgments

Work supported by the German Federal Ministry of Education and Research (BMBF) CISPA, grant no. 16KIS0656. Thanks to Rosa Moreno and Daniel Gnad for helpful discussions concerning this work.