Pattern Selection for Optimal Classical Planning with Saturated Cost Partitioning

1 Introduction

A∗ search [Hart et al., 1968] with an admissible heuristic [Pearl, 1984] is one of the most successful methods for solving classical planning tasks optimally. An important building block of some of the strongest admissible heuristics are pattern database (PDB) heuristics. A PDB heuristic precomputes all goal distances in a simplified state space obtained by projecting the task to a subset of state variables, the pattern, and uses these distances as lower bounds on the true goal distances. PDB heuristics were originally introduced for solving the 15-puzzle [Culberson and Schaeffer, 1996] and have later been generalized to many other combinatorial search tasks [e.g., Korf, 1997; Felner et al., 2004] and to the setting of domain-independent planning [Edelkamp, 2001].

Using a single PDB heuristic of reasonable size is usually not enough to cover sufficiently many aspects of challenging planning tasks. It is therefore often beneficial to compute multiple PDB heuristics and to combine their estimates admissibly [Holte et al., 2006]. The simplest approach for this is to choose the PDB with the highest estimate in each state. Instead of this maximization scheme, we would like to sum estimates, but this renders the resulting heuristic inadmissible in general. However, if two PDBs are affected by disjoint sets of operators, they are independent and we can admissibly add their estimates [Korf and Felner, 2002; Felner et al., 2004]. Haslum et al. [2007] later generalized this idea by introducing the canonical heuristic for PDBs, which computes all maximal subsets of pairwise independent PDBs and then uses the maximum over the sums of independent PDBs as the heuristic value.

Cost partitioning [Katz and Domshlak, 2008; Yang et al., 2008] is a generalization of the independence-based methods above. It makes the sum of heuristic estimates admissible by distributing the costs of each operator among the heuristics. The literature contains many different cost partitioning algorithms such as zero-one cost partitioning [Edelkamp, 2002; Haslum et al., 2007], uniform cost partitioning [Katz and Domshlak, 2008], optimal cost partitioning [Katz and Domshlak, 2008; Karpas and Domshlak, 2009; Pommerening et al., 2015] and post-hoc optimization [Pommerening et al., 2013].

In previous work [Seipp et al., 2017a], we showed experimentally for the benchmark tasks from previous International Planning Competitions (IPC) that saturated cost partitioning (SCP) [Seipp and Helmert, 2014; Seipp and Helmert, 2018] is the cost partitioning algorithm of choice for PDB heuristics. Saturated cost partitioning considers an ordered sequence of heuristics. Iteratively, it gives each heuristic the minimum amount of costs that the heuristic needs to justify all its estimates and then uses the remaining costs for subsequent heuristics until all heuristics have been served this way.

Before we can compute a saturated cost partitioning over pattern database heuristics, we need to select a collection of patterns. The first domain-independent automated pattern selection algorithm is due to Edelkamp [2001]. It partitions the state variables into patterns via best-fit bin packing. Edelkamp [2006] later used a genetic algorithm to search for a pattern collection that maximizes the average heuristic value of a zero-one cost partitioning over the PDB heuristics.

Haslum et al. [2007] proposed an algorithm that performs a hill-climbing search in the space of pattern collections (HC). HC evaluates a collection C by estimating the search effort of the canonical heuristic over C based on a model of IDA∗ runtime [Korf et al., 2001].

Franco et al. [2017] presented the Complementary PDBs Creation (CPC) method, that combines bin packing and genetic algorithms to create a pattern collection minimizing the estimated search effort of an A∗ search [Lelis et al., 2014].

Rovner et al. [2019] repeatedly compute patterns using counterexample-guided abstraction refinement (CEGAR): starting from a random goal variable, their CEGAR algorithm iteratively finds solutions in the corresponding projection and executes them in the original state space. Whenever a solution cannot be executed due to a violated precondition, it adds the missing precondition variable to the pattern.

Finally, Pommerening et al. [2013] systematically generate all interesting patterns up to a given size X (SYS-X). Experiments showed that cost-partitioned heuristics over SYS-2 and SYS-3 yield accurate estimates [Pommerening et al., 2013; Seipp et al., 2017a], but using all interesting patterns of larger sizes is usually infeasible.

We introduce SYS-SCP, a new pattern selection algorithm based on saturated cost partitioning that potentially considers all interesting patterns, but only selects useful ones. SYS-SCP builds multiple pattern sequences that together form the resulting pattern collection. For each sequence σ, it considers the interesting patterns in increasing order by size and adds a pattern P to σ if P is not part of an earlier sequence and the saturated cost partitioning heuristic over σ plus P is more informative than the one over σ alone.

2 Background

We consider optimal classical planning tasks in a SAS+-like notation [B¨ackstr¨om and Nebel, 1995] and represent a planning task Π as a tuple 〈V,O, s0, s⋆〉. Each variable v in the finite set of variables V has a finite domain dom(v). A partial state s is defined over a subset of variables vars(s) ⊆ V and maps each v ∈ vars(s) to a value in dom(v), written as s[v]. We call the pair 〈v, s[v]〉 an atom and interchangeably treat partial states as mappings from variables to values or as sets of atoms. If vars(s) = V, we call s a state. We write S(Π) for the set of all states in Π.

Each operator o in the finite set of operators O has a precondition pre(o) and an effect eff(o), both of which are partial states, and a cost cost(o) ∈ R+0 . An operator o is applicable in a state s if pre(o) ⊆ s. Applying o in s leads into state s′ = sJoK with s′ [v] = eff(o)[v] for all v ∈ vars(eff(o)) and s′ [v] = s[v] for all variables v ∈ V \ vars(eff(o)). The state s0 is called the initial state and s⋆ is a partial state, the goal. Transition systems assign semantics to planning tasks.

Definition 1 (transition systems). A transition system T is a labeled digraph defined by a finite set of states S(T ), a finite set of labels L(T ), a set T(T ) of labeled transitions s ℓ-→ s′ with s, s′ ∈ S(T ) and ℓ ∈ L(T ), an initial state s0(T ), and a set S⋆(T ) of goal states.

A planning task Π = 〈V,O, s0, s⋆〉 induces a transition system T with states S(Π), labels O, transitions {s o-→ sJoK | s ∈ S(Π), o ∈ O, pre(o) ⊆ s}, initial state s0 and goal states {s ∈ S(Π) | s⋆ ⊆ s}.

Separating transition systems from cost functions allows us to evaluate the same transition system under different cost functions, which is important for cost partitioning.

Definition 2 (cost functions). A cost function for transition system T is a function cost : L(T ) → R ∪ {-∞,∞}. It is finite if -∞ < cost(ℓ) < ∞ for all labels ℓ. It is nonnegative if cost(ℓ) ≥ 0 for all labels ℓ. We write C(T ) for the set of all cost functions for T .

Note that we assume that the cost function of the planning task is non-negative and finite, but as in previous work we allow negative [Pommerening et al., 2015] and infinite costs

[Seipp and Helmert, 2019] in cost partitionings. The generalization to infinite costs is necessary to cleanly state some of our definitions.

Definition 3 (weighted transition systems). A weighted transition system is a pair 〈T , cost〉 where T is a transition system and cost ∈ C(T ) is a cost function for T .

The cost of a path π = 〈s0 ℓ1 -→ s1 , . . . , sn-1 ℓn -→ sn 〉 in a weighted transition system 〈T , cost〉 is defined as cost(π) = ∑ni=1 cost(ℓi). It is∞if the sumcontains both+∞and-∞. If sn is a goal state, π is called a goal path for s0 .

Definition 4 (goal distances and optimal paths). The goal distance of a state s ∈ S(T ) in a weighted transition system 〈T , cost〉 is defined as infπ∈Π⋆(T ,s) cost(π), where Π⋆(T , s) is the set of goal paths from s in T . (The infimum of the empty set is ∞.) We write h∗T (cost, s) for the goal distance of s. If h∗T (cost, s) = ∞, we call s unsolvable. A goal path π from s is optimal if cost(π) = h∗T (cost, s).

Optimal classical planning is the problem of finding an optimal goal path from s0 or showing that s0 is unsolvable.

We use heuristics to estimate goal distances [Pearl, 1984].

Definition 5 (heuristics). A heuristic for a transition system T is a function h : C(T ) × S(T ) → R ∪ {-∞,∞}. Heuristic h is admissible if h(cost, s) ≤ h∗T (cost, s) for all cost ∈ C(T ) and all s ∈ S(T ).

Cost partitioning makes adding heuristics admissible by distributing the costs of each operator among the heuristics.

Definition 6 (cost partitioning). Let T be a transition system. A cost partitioning for a cost function cost ∈ C(T ) is a tuple 〈cost1, . . . , costn〉 ∈ C(T )n whose sum is bounded by cost: ∑ni=1 costi(ℓ) ≤ cost(ℓ) for all ℓ ∈ L(T ). A cost partitioning 〈cost1, . . . , costn〉 ∈ C(T )n over the heuristics 〈h1, . . . , hn〉 for T induces the cost-partitioned heuristic h(cost, s) = ∑ni=1 hi(costi, s). If the sum contains +∞ and -∞, it evaluates to the leftmost infinite value.

One of the cost partitioning algorithms from the literature is saturated cost partitioning [Seipp and Helmert, 2018]. It is based on the insight that we can often reduce the amount of costs given to a heuristic without changing any heuristic estimates. Saturated cost functions formalize this idea.

Definition 7 (saturated cost function). Consider a transition system T , a heuristic h for T and a cost function cost ∈ C(T ). A cost function scf ∈ C(T ) is saturated for h and cost if

1. scf(ℓ) ≤ cost(ℓ) for all labels ℓ ∈ L(T ) and
2. h(scf, s) = h(cost, s) for all states s ∈ S(T ).

A saturated cost function scf is minimal if there is no other saturated cost function scf′ for h and cost with scf(ℓ) ≤ scf′ (ℓ) for all labels ℓ ∈ L(T ).

Whether we can efficiently compute a minimal saturated cost function depends on the type of heuristic. In earlier work [Seipp and Helmert, 2018], we showed that this is possible for explicitly-represented abstraction heuristics [Helmert et al., 2007], which include PDB heuristics.

Definition 8 (minimum saturated cost function for abstraction heuristics). Let 〈T , cost〉 be a weighted transition system and h an abstraction heuristic for T with abstract transition system T ′ . The minimum saturated cost function mscf for h and cost is

Given a sequence of abstraction heuristics, the saturated cost partitioning algorithm iteratively assigns to each heuristic only the costs that the heuristic needs to preserve its estimates and uses the remaining costs for subsequent heuristics.

Definition 9 (saturated cost partitioning). Consider a transition system T and a sequence of abstraction heuristics H = 〈h1, . . . , hn〉 for T . For all 1 ≤ i ≤ n, saturatei : C(T ) → C(T ) receives a cost function rem and returns the minimum saturated cost function for hi and rem. The saturated cost partitioning 〈cost1, . . . , costn〉 of a function cost ∈ C(T ) over H is defined as:

rem0 = cost costi = saturatei(remi-1) for all 1 ≤ i ≤ n remi = remi-1 - costi for all 1 ≤ i ≤ n,

where the auxiliary cost functions remi represent the remaining costs after processing the first i heuristics in H.

We write hSCP H for the saturated cost partitioning heuristic over the sequence of heuristics H. In this work, we compute saturated cost partitionings over pattern database heuristics.

A pattern for task Π with variables V is a subset P ⊆ V. By syntactically removing all variables from Π that are not in P, we obtain the projected task Π|P inducing the abstract transition system TP . The PDB heuristic hP for a pattern P is defined as hP (cost, s) = h∗TP (cost, s|P ), where s|P is the abstract state that s is projected to in Π|P . For the pattern sequence 〈P1, . . . , Pn〉 we define hSCP 〈P1,...,Pn〉 = hSCP 〈hP1 ,...,hPn 〉 .

One of the simplest pattern selection algorithms is to generate all patterns up to a given size X [Felner et al., 2004] and we call this approach SYS-NAIVE-X. It is easy to see that for tasks with n variables, SYS-NAIVE-X generates ∑Xi=1 (ni ) patterns. Usually, many of these patterns do not add much information to a cost-partitioned heuristic over the patterns. Unfortunately, there is no efficiently computable test that allows us to discard such uninformative patterns. Even patterns without any goal variables can increase heuristic estimates in a cost partitioning [Pommerening, 2017].

However, in the setting where only non-negative cost functions are allowed in cost partitionings, there are efficiently computable criteria for deciding whether a pattern is interesting, i.e., whether it cannot be replaced by a set of smaller patterns that together yield the same heuristic estimates [Pommerening et al., 2013].

The criteria are based on the causal graph CG(Π) of a task Π [Helmert, 2004]. CG(Π) is a directed graph with a node for each variable in Π. If there is an operator with a precondition on u and an effect on v ̸= u, CG(Π) contains a precondition arc from u to v. If an operator affects both u and v, CG(Π) contains co-effect arcs from u to v and from v to u.

Algorithm 1 SYS-SCP: Given a planning task with states S(T ), cost function cost and interesting patterns SYS, select a subset C ⊆ SYS.

1: function SYS-SCP(Π) 2: C ←∅ 3: repeat for at most Tx seconds 4: σ ← 〈〉 5: for P ∈ ORDER(SYS) and at most Ty seconds do 6: if P /∈ C and PATTERNUSEFUL(σ, P) then 7: σ ← σ ⊕ P 8: C ← C ∪ {P } 9: until σ = 〈〉 10: return C 11: function PATTERNUSEFUL(σ, P) 12: return ∃s ∈ S(T ) : hSCP σ (cost, s) < hSCP σ⊕P (cost, s) < ∞

Definition 10 (interesting patterns). A pattern P is interesting if

1. CG(Π|P ) is weakly connected, and
2. CG(Π|P ) contains a directed path via precondition arcs from each node to some goal variable node.

The systematic pattern generation method SYS-X generates all interesting patterns up to size X. We let SYS denote the set of all interesting patterns for a given task. On IPC benchmark tasks, SYS-X often generates much fewer patterns than SYS-NAIVE-X for the same size limit X. Still, it is usually infeasible to compute all SYS-X patterns and the corresponding projections for X > 3 within reasonable amounts of time and memory. Also, we hypothesize that even when considering only interesting patterns, usually only a small percentage of the systematic patterns up to size 3 contribute much information to the resulting heuristic.

For these two reasons we propose a new pattern selection algorithm that potentially considers all interesting patterns, but only selects the ones that it deems useful.

3 SYS-SCP Pattern Selection Algorithm

Our new pattern selection algorithm repeatedly creates a new empty pattern sequence σ and only appends those interesting patterns to σ that increase any finite heuristic values of a saturated cost partitioning heuristic computed over σ.

Algorithm 1 shows pseudo-code for the procedure, which we call SYS-SCP. It starts with an empty pattern collection C. In each iteration of the outer loop, SYS-SCP creates a new empty pattern sequence σ and then loops over the interesting patterns P ∈ SYS in the order chosen by ORDER (see Section 3.2) for at most Ty seconds. SYS-SCP appends a pattern P to σ and includes it in C if there is a state s for which the saturated cost partitioning over σ extended by P has a higher finite heuristic value than the one over σ alone. Once an iteration selects no new patterns or SYS-SCP hits the time limit Tx, the algorithm stops and returns C.

We impose a time limit Tx on the outer loop of the algorithm since the number of interesting patterns is exponential in the number of variables and therefore SYS-SCP usually cannot evaluate them all in a reasonable amount of time. By imposing a time limit Ty on the inner loop, we allow SYS-SCP to periodically start over with a new empty pattern sequence.

The most important component of the SYS-SCP algorithm is the PATTERNUSEFUL function that decides whether to select a pattern P . The function enumerates all states s ∈ S(Π), which is obviously infeasible for all but the smallest tasks Π. Fortunately, we can efficiently compute an equivalent test in the projection to P .

Lemma 1. Consider a planning task Π with non-negative cost function cost and induced transition system T . Let s ∈ S(T ) be a state, P be a pattern for Π and σ be a (possibly empty) sequence of patterns 〈P1, . . . , Pn〉 for Π. Finally, let rem be the remaining cost function after computing hSCP σ for cost.

Proof. hSCP σ (cost, s) < hSCP σ⊕P (cost, s) < ∞

Step 1 substitutes 〈P1, . . . , Pn〉 for σ and Step 2 uses the definition of saturated cost partitioning heuristics. For Step 3 we need to show that x = ∑ni=1 hPi (costi, s) is finite.

The inequality states x < ∞. We now show x ≥ 0, which implies x > -∞. Using requirement 1 for saturated cost functions from Definition 7 and the fact that rem0 = cost is non-negative, it is easy to see that all remaining cost functions are non-negative. Consequently, hPi (costi, s) = hPi (remi-1, s) ≥ 0 for all s ∈ S(T ), which uses requirement 2 from Definition 7 and the fact that goal distances are non-negative in transition systems with non-negative weights.

The final step (4) uses the definition of PDB heuristics.

Theorem 1 (computing PATTERNUSEFUL on projections). Consider a planning task Π with non-negative cost function cost and induced transition system T . Let P be a single pattern and σ be a (possibly empty) sequence of patterns. Finally, let rem be the remaining cost function after computing hSCP σ for cost.

Proof. Follows directly from Lemma 1 and the fact that projections are induced abstractions: for each abstract state s′ in an induced abstraction there is at least one concrete state s which is projected to s′ .

We use Theorem 1 in our SYS-SCP implementation by keeping track of the cost function rem, i.e., the costs that remain after computing hSCP σ . We select a pattern P if there are any goal distances d with 0 < d < ∞ in TP under rem.

Theorem 1 also removes the need to compute hSCP σ⊕P from scratch for every pattern P. This is important since we want to decide whether or not to add P quickly and this operation should not become slower when σ contains more patterns.

3.1 Dead Ends

To obtain high finite heuristic values for solvable states it is important to choose good cost partitionings. In contrast, cost functions are irrelevant for detecting unsolvable states. This is the underlying reason why Lemma 1 only holds for finite values and therefore why SYS-SCP ignores unsolvable states.

However, we can still use the information about unsolvable states contained in projections. It is easy to see that each abstract state in a projection corresponds to a partial state in the original task. If an abstract state is unsolvable in a projection, we call the corresponding partial state a dead end. Since projections preserve all paths, any state in the original task subsuming a dead end is unsolvable. We can extract all dead ends from the projections that SYS-SCP evaluates and use this information to prune unsolvable states during the A∗ search [Pommerening and Seipp, 2016].

3.2 Ordering Patterns

We showed in earlier work that the order in which saturated cost partitioning considers the component heuristics has a strong influence on the quality of the resulting heuristic [Seipp et al., 2017b]. Choosing a good order is even more important for SYS-SCP, since it usually only sees a subset of interesting patterns within the allotted time. To ensure that this subset of interesting patterns covers different aspects of the planning task, we let the ORDER function generate the interesting patterns in increasing order by size.

This leaves the question how to sort patterns of the same size. We propose four methods for making this decision. The first one (random) simply orders patterns of the same size randomly. The remaining three assign a key to each pattern, allowing us to sort by key in increasing or decreasing order.

Causal graph. The first ordering method is based on the insight that it is often more important to have accurate heuristic estimates near the goal states rather than elsewhere in the state space [e.g., Holte et al., 2006]. We therefore want to focus on patterns containing goal variables or variables that are closely connected to goal variables. To quantify "goal-connectedness" we use an approximate topological ordering ≺ of the causal graph CG(Π). We let the function cg : V → N+0 assign each variable v ∈ V to its index in ≺. For a given pattern P , the cg ordering method returns the key 〈cg(v1), . . . , cg(vn)〉, where vi ∈ P and cg(vi) < cg(vj) for all 1 ≤ i < j ≤ n. Since the keys are unique, they define a total order. Sorting the patterns by cg in decreasing order (cg-down), yields the desired order which starts with "goalconnected" patterns.

States in projection. Given a pattern P, the states ordering method returns the key |S(Π|P )|, i.e., the number of states in the projection to P . We use cg-down to break ties.

Active operators. Given a pattern P, the ops ordering method returns the number of operators that affect a variable in P . We break ties with cg-down.

4 Experiments

We implemented the SYS-SCP pattern selection algorithm in the Fast Downward planning system [Helmert, 2006] and conducted experiments with the Downward Lab toolkit [Seipp et al., 2017c] on Intel Xeon Silver 4114 processors. Our benchmark set consists of all 1827 tasks without conditional effects from the optimization tracks of the 1998-2018 IPCs. The tasks belong to 48 different domains. We limit time by 30 minutes and memory by 3.5 GiB. All benchmarks 1 , code 2 and experimental data 3 have been published online.

To fairly compare the quality of different pattern collections, we use the same cost partitioning algorithm for all collections. Saturated cost partitioning is the obvious choice for the evaluation since experiments showed that it is preferable to all other cost partitioning algorithms for HC, SYS-2 and CPC patterns in almost all evaluated benchmark domains [Seipp et al., 2017a; Rovner et al., 2019]. As in previous work, we maximize over multiple diverse saturated cost partitioning heuristics [Seipp et al., 2017b].

More concretely, for a given pattern collection C, we start with an empty family of saturated cost partitioning heuristics F and a set ˆ S of 1000 sample states obtained with random walks [Haslum et al., 2007]. Then we iteratively sample a new state s and compute a greedy order ω of C that works well for s [Seipp, 2017]. If hSCP ω has a higher heuristic estimate for any state s′ ∈ ˆ S than all heuristics in F, we add hSCP ω to F. We stop this diversification procedure after 200 seconds and then perform an A∗ search using the maximum over the heuristics in F.

Before we compare SYS-SCP to other pattern selection algorithms, we evaluate the effects of changing its parameters in four ablation studies. We use at most 2M states per PDB and 20M states in the PDB collection for all SYS-SCP runs.

4.1 Time Limits

Table 1 shows that a time limit for the outer loop is more important than one for the inner loop, but for maximum coverage we need both limits. The combination that solves the highest number of tasks is 10s for the inner and 100s for the outer loop. We use these values in all other experiments.

4.2 Dead Ends

All configurations from Table 1 store the dead ends from all projections evaluated by SYS-SCP and use them to prune unsolvable states during the A∗ search. For the best configuration from Table 1, coverage decreases from 1168 to 1153 tasks if we ignore the dead ends. Therefore, we use dead ends for pruning unsolvable states in all other experiments.

1 Benchmarks: https://doi.org/10.5281/zenodo.2616479

2 Code: https://doi.org/10.5281/zenodo.3233330

3 Experimental data: https://doi.org/10.5281/zenodo.3233326

4.3 Pattern Orders

Table 2 compares the different methods for ordering patterns of the same size. For all of states, ops and cg, at least one ordering direction (up or down) is preferable to using random orders. The ops-up method is preferable to ops-down for 11 domains, but there are also 7 domains where the opposite is the case. The relation between states-down and states-up is similar. The only ordering method where one direction is clearly preferable to the other is cg: cg-down solves more tasks than cg-up in 12 domains, while the opposite is the case in only 3 domains. Since cg-down also has the highest overall coverage, we use it in all other experiments.

4.4 Using Pattern Sequences for Diversification

Instead of discarding the computed pattern sequences when SYS-SCP finishes, we can turn each pattern sequence σ into a full pattern order by randomly appending all SYS-SCP patterns missing from σ to σ and pass the resulting order to the diversification procedure.

Feeding the diversification exclusively with such orders leads to solving 1130 tasks, while using only greedy orders for sample states [Seipp, 2017] solves 1156 tasks. We obtain the best results by diversifying both types of orders, solving 1168 tasks, and we use this variant in all other experiments.

4.5 Systematic Patterns With Limits

In the next experiment, we evaluate the obvious baseline for SYS-SCP: selecting all (interesting) patterns up to a fixed size. Table 3 holds coverage results of SYS-NAIVE-X and SYS-X for 1 ≤ X ≤ 5. We also include variants (*-LIM) that use at most 100 seconds, no more than 2M states in each projection and at most 20M states per collection. For the *- LIM variants, we sort the patterns in the cg-down order.

The results show that interesting patterns are always preferable to naive patterns, both with and without limits, which is why we only consider interesting patterns in SYS-SCP. Imposing limits is not important for SYS-1 and SYS-2, but leads to solving many more tasks for X ≥ 3. Overall, SYS-3-LIM has the highest total coverage (1088 tasks).

4.6 Comparison of Pattern Selection Algorithms

In Table 4 we compare SYS-SCP to the strongest pattern selection algorithms from the literature: HC, SYS-3-LIM, CPC and CEGAR. We run each algorithm with its preferred parameter values, which implies using at most 900s for HC and CPC and 100s for the other algorithms.

HC is outperformed by all other algorithms. Interestingly, already the simple SYS-3-LIM approach is competitive with CPC and CEGAR. However, we obtain the best results with SYS-SCP. It is preferable to all other pattern selection algorithms in per-domain comparisons: no algorithm has higher coverage than SYS-SCP in more than three domains, while SYS-SCP solves more tasks than each of the other algorithms in at least 21 domains. SYS-SCP also has the highest total coverage of 1168 tasks, solving 70 more tasks than the strongest contender. This is a considerable improvement in the setting of optimal classical planning, where task difficulty tends to scale exponentially.

4.7 Comparison to IPC Planners

In our final experiment, we evaluate whether Scorpion [Seipp, 2018], one of the strongest optimal planners in IPC 2018, benefits from using SYS-SCP patterns. Scorpion computes diverse saturated cost partitioning heuristics over HC and SYS-2 PDB heuristics and Cartesian abstraction heuristics (CART) [Seipp and Helmert, 2018]. We abbreviate this combination with COMB=HC+SYS-2+CART. In Table 5 we compare the original Scorpion planner, three Scorpion variants that use different sets of heuristics and the top three optimal planners from IPC 2018, Delfi 1 [Sievers et al., 2019], Complementary 1 [Franco et al., 2018] and Complementary 2 [Franco et al., 2017]. In contrast to the configurations we evaluated above, all planners in Table 5 prune irrelevant operators in a preprocessing step [Alc´azar and Torralba, 2015].

The results show that all Scorpion variants outperform the top three IPC 2018 planners in per-domain comparisons. We also see that Scorpion benefits from using SYS-SCP PDBs instead of the COMB heuristics in many domains. Using the union of both sets is clearly preferable to using either COMB or SYS-SCP alone, since it raises the total coverage to 1261 by 56 and 44 tasks, respectively. For maximum coverage (1265 tasks), Scorpion only needs SYS-SCP PDBs and Cartesian abstraction heuristics.

5 Conclusion

We introduced a new pattern selection algorithm based on saturated cost partitioning and showed that it outperforms all other pattern selection algorithms from the literature. The algorithm selects a pattern if it is useful for any state in the state space. In future work, we would like to evaluate whether it is beneficial to restrict this criterion to a subset of states, such as all reachable states or a set of sample states.

Acknowledgments

We thank the anonymous reviewers for their helpful comments. We have received funding for this work from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 817639).