# saturated_posthoc_optimization_for_classical_planning__1fc7b0a8.pdf

Saturated Post-hoc Optimization for Classical Planning

Jendrik Seipp,1,2 Thomas Keller,1 Malte Helmert1

1University of Basel, Switzerland 2Link oping University, Sweden jendrik.seipp@liu.se, tho.keller@unibas.ch, malte.helmert@unibas.ch

Saturated cost partitioning and post-hoc optimization are two powerful cost partitioning algorithms for optimal classical planning. The main idea of saturated cost partitioning is to give each considered heuristic only the fraction of remaining operator costs that it needs to prove its estimates. We show how to apply this idea to post-hoc optimization and obtain a heuristic that dominates the original both in theory and on the IPC benchmarks.

Introduction Methods for admissibly combining admissible heuristics signiﬁcantly improved the state of the art in optimal classical planning. Early work that exploits the additivity of heuristics (Felner, Korf, and Hanan 2004; Edelkamp 2006) led to the development of the canonical heuristic (Haslum et al. 2007), which computes all maximal subsets of pairwise independent pattern database (PDB) heuristics and then uses the maximum of all sums over these subsets as the heuristic value. The additivity criterion has been replaced by a more general theory with the introduction of cost partitioning (Katz and Domshlak 2008), which ensures that admissible heuristic estimates can be summed up admissibly as long as the sum of the operator costs that are used to compute the heuristics does not exceed the original cost function. The computation of optimal cost partitionings (Katz and Domshlak 2010) has despite its polynomial time complexity proven to be too costly in practice (Pommerening, R oger, and Helmert 2013; Seipp, Keller, and Helmert 2017b). Suboptimal cost partitionings that are efﬁciently computable both in theory and practice have therefore received much attention. The underlying observation of saturated cost partitioning (Seipp and Helmert 2014, 2018) is that we can often reduce operator costs without affecting heuristic estimates. The saturated cost partitioning algorithm considers a set of heuristics in a given order. For the ﬁrst heuristic h, it computes all heuristic values of h under the original cost function, computes the minimum cost function that preserves the heuristic values, that is, the saturated cost function, and continues with the next heuristic with the remaining costs until all heuristics have been considered.

Copyright 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

The post-hoc optimization heuristic (Pommerening, R oger, and Helmert 2013) uses a linear program (LP) to determine a real-valued factor for each heuristic in a set of pattern database (PDB) abstractions (Edelkamp 2001), and the cost partitioning is derived by multiplying the costs of all operators that affect an abstraction with that factor. Operators that only induce self-loops in an abstraction are assigned costs of zero. In the (equivalent) operator counting version of the dual LP (Pommerening et al. 2014), there is a constraint for each PDB that speciﬁes that the total contribution of all operators in a heuristic multiplied with the operator cost must at least sum up to the heuristic estimate. The fact that every plan for the original problem must also be a plan for each PDB allows us to use the same operator counting variables for all abstractions. In this paper, we strengthen the post-hoc optimization constraints by combining them with the central idea of saturated cost partitioning. We observe that an operator never contributes more than its saturated cost to the heuristic value of an abstraction because all heuristic values remain the same even if we were to reduce its cost to the possibly lower saturated cost. We show that the resulting saturated posthoc optimization heuristic dominates post-hoc optimization theoretically and conﬁrm that the theoretical superiority carries over into practice in an experimental evaluation on the domains of the International Planning Competitions.

A classical planning task induces a transition system and solving the task optimally implies ﬁnding a shortest path from the initial state to a goal state. Formally, a transition system T is a directed, labeled graph deﬁned by a ﬁnite set of states S(T ), a ﬁnite 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 of goal states S (T ). A goal path from s S(T ) is a sequence of transitions from s to any goal state s S (T ). Goal paths are also called plans. A cost function for transition system T is a function cost : L(T ) R. A cost function cost is non-negative if cost(ℓ) 0 for all labels ℓ. We write C(T ) for the set of all cost functions for T . Our input planning tasks use nonnegative cost functions, but following Pommerening et al.

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

s1,s2 s3 s4,s5

s1 s2,s3,s4 s5

Figure 1: Example abstraction heuristics h1 (left) and h2 (right) from Seipp, Keller, and Helmert (2017a). The cost function is cost = {o1 7 4, o2 7 1, o3 7 4, o4 7 1}. The si are concrete states, the rounded rectangles are abstract states, abstract goal states use double borders and dotted lines depict abstract self-loops.

(2015) we allow negative costs in cost partitionings.1 By combining a transition system T and a cost function cost, we obtain a weighted transition system T , cost . The cost of a goal path in a weighted transition system is the sum of its transition weights and a goal path is optimal if its cost is minimal among all goal paths. The goal distance h T (cost, s) of a state s in T is the cost of an optimal goal path from s under the cost function cost or if there is no goal path from s. A heuristic is a function h : C(T ) S(T ) R { , } that estimates the distance of a given state to a goal state under a given cost function (Pearl 1984). It is admissible if h(cost, s) h T (cost, s) for all cost functions cost C(T ) and all states s S(T ). A heuristic h is costmonotonic if h(cost, s) h(cost , s) for all states s S(T ) whenever cost cost (that is, making transitions more expensive cannot decrease heuristic estimates). In this paper, we focus on abstraction heuristics (e.g., Edelkamp 2001; Helmert, Haslum, and Hoffmann 2007; Katz and Domshlak 2008, 2010). An abstraction heuristic for a transition system T is deﬁned by a transition system T called the abstract transition system and a function α : S(T ) S(T ) called the abstraction function. The abstraction function must preserve goal states and transitions; we refer to the literature for details (Helmert, Haslum, and Hoffmann 2007). Heuristic values are computed by mapping states of T (concrete states) to states of T (abstract states) and computing the goal distance in the abstract transition system: h(cost, s) = h T (cost, α(s)). Abstraction heuristics are cost-monotonic. Cost partitioning is the preferable mechanism for combining multiple admissible heuristics. It preserves admissibility by distributing the costs of a task among the component heuristics (Katz and Domshlak 2008, 2010). A cost partitioning for a transition system T and a cost function cost C(T ) is a tuple cost1, . . . , costn C(T )n whose sum is bounded by cost: Pn i=1 costi(ℓ) cost(ℓ) for all ℓ L(T ). It induces the cost-partitioned heuristic h(cost, s) = Pn i=1 hi(costi, s).

1To cleanly state some deﬁnitions concerning saturated cost partitioning, it is useful to allow costs of positive and negative inﬁnity. However, to simplify the presentation here, we only consider ﬁnite cost functions and refer to Seipp, Keller, and Helmert (2020) for details on the more general case.

Saturated Cost Partitioning One of the strongest algorithms for computing cost partitionings is saturated cost partitioning (Seipp and Helmert 2014; Seipp, Keller, and Helmert 2020). At the heart of the algorithm lies the concept of saturated cost functions, which capture the insight that heuristic estimates often remain the same even if we evaluate the heuristic under a reduced cost function. Deﬁnition 1 (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 ). We can compute a saturated cost function for any given heuristic h and cost function cost, since cost itself satisﬁes the criteria of Deﬁnition 1. Ideally, however, we want to ﬁnd a saturated cost function that uses lower costs than the original cost function (to save costs for other heuristics). For some classes of heuristics, there is a unique minimum saturated cost function and we can compute it efﬁciently (Seipp, Keller, and Helmert 2017a, 2020).2 This is the case for explicitly represented abstraction heuristics (Helmert et al. 2014) such as the pattern database heuristics (Haslum et al. 2007; Pommerening, R oger, and Helmert 2013) and Cartesian abstractions (Seipp and Helmert 2013) we consider below, and landmark heuristics (Karpas and Domshlak 2009). Example 1. Consider the abstraction heuristic h1 in Figure 1. Under the original cost function cost, h1 yields the following estimates: h1(s1) = h1(s2) = 5, h1(s3) = 1, h1(s4) = h1(s5) = 0. Reducing the costs to the minimum saturated cost function scf = {o1 7 4, o2 7 0, o3 7 1, o4 7 1} does not change any heuristic estimates. Saturated cost partitioning iteratively computes saturated cost functions for a sequence of heuristics. Deﬁnition 2 (saturated cost partitioning). Consider a weighted transition system T , cost and an ordered sequence of heuristics ω = h1, . . . , hn for T . The saturated cost partitioning cost1, . . . , costn of the cost function cost for ω is deﬁned as: rem0 = cost costi = saturate(hi, 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 ﬁrst i heuristics in ω and saturate(hi, remi 1) computes a cost function that is saturated for hi and remi 1. In this work, saturate always refers to the unique minimum saturated cost function for a given abstraction heuristic and cost function. We write h SCP ω for the heuristic that is cost-partitioned by saturated cost partitioning for order ω.

2Strictly speaking, this is only true if we allow costs of to account for labels that a heuristic detects as dead , i.e., not part of any goal path. We again refer to Seipp, Keller, and Helmert (2020) for details. Later on, we discuss a way to deal with such dead labels outside the cost partitioning mechanism.

Example 2. Consider the two abstraction heuristics h1 and h2 in Figure 1. If we compute a saturated cost partitioning for the order h1, h2 , we obtain the saturated cost function cost1 = {o1 7 4, o2 7 0, o3 7 1, o4 7 1} as in Example 1. Thus, we have remaining costs rem1 = {o1 7 0, o2 7 1, o3 7 3, o4 7 0}. Under this cost function, we have h2(rem1, si) = 3 for 1 i 4 and h2(rem1, s5) = 0. Computing the saturated cost function for h2 under rem1 reveals that we can reduce rem1(o2) = 1 to cost2(o2) = 0, and could use its cost for hypothetical subsequent heuristics. The functions cost1 and cost2 form a cost partitioning, which means that we can sum their estimates admissibly to obtain h SCP h1,h2 (s1) = h1(cost1, s1) + h2(cost2, s1) = 5 + 3 = 8.

Post-hoc Optimization The second cost partitioning algorithm we consider in this paper is post-hoc optimization (Pommerening, R oger, and Helmert 2013). The post-hoc optimization heuristic h Ph O dominates the canonical heuristic h CAN (Haslum et al. 2007), even though computing h Ph O takes polynomial time, whereas computing h CAN is NP-equivalent. Originally, posthoc optimization has been applied to pattern database heuristics, but it has also been used for Cartesian abstractions and landmark heuristics since (Seipp, Keller, and Helmert 2017a). Like optimal cost partitioning, post-hoc optimization is based on linear programming (LP), but since the post-hoc optimization LPs are much smaller than LPs for optimal cost partitioning over the same set of heuristics, the former are much faster to solve in practice. Consequently, in contrast to optimal cost partitioning, it is possible to compute a cost partitioning based on post-hoc optimization for each evaluated state during an A search and obtain competitive performance. A central concept for post-hoc optimization is the distinction whether or not a given label affects a given heuristic. We follow the deﬁnition by Seipp, Keller, and Helmert (2017a):

Deﬁnition 3 (affects). A label ℓaffects a heuristic h for a transition system T if there exists a state s S(T ) and two non-negative cost functions cost and cost differing only on ℓwith h(cost, s) = h(cost , s).

Note the restriction to non-negative cost functions in this deﬁnition. If negative cost functions were considered, the deﬁnition would trivialize in many cases, failing to capture the traditional notion of labels affecting a heuristic in the literature on which post-hoc optimization is based. In particular, every label with negative cost that induces a self-looping transition along any goal path in an abstract transition system would force the abstraction heuristic value to , and hence all these self-loop-inducing labels would have to be considered as affecting the heuristic. This is not in the spirit of the post-hoc optimization approach and would lead to inferior heuristic estimates. Note also that the deﬁnition is purely semantic: it is based on heuristic values under different cost functions, without regard to how the heuristic is computed or how the property can be evaluated. To make computations based on affecting labels practically efﬁcient, this purely semantic notion is generally relaxed. In the following, we write A(h) to de-

note an overapproximation of the set of all labels that affect the heuristic h. For abstraction heuristics h, which are the only heuristics we experimentally evaluate in this paper, we set A(h) to the set of all labels ℓsuch that there exists a

transition s ℓ s with s = s in the abstract transition system. This set is guaranteed to include all labels that affect the heuristic, but may also include some labels that do not affect the heuristic. The post-hoc optimization heuristic is admissible with any overapproximation of affecting labels, but tighter sets can improve the quality of the heuristic. We can now describe the linear program deﬁning the posthoc optimization heuristic. All linear programs can be written in primal and dual form. We call the following LP the primal post-hoc optimization LP and refer to it as Ph O-LP:

Deﬁnition 4 (h Ph O). Let T , cost be a weighted transition system with labels L, and let H be a set of admissible heuristics for T . The post-hoc optimization heuristic h Ph O(cost, s) for state s S(T ), T and H is the objective value of the Ph O-LP:

ℓ L cost(ℓ) Yℓs.t.

ℓ A(h) cost(ℓ) Yℓ h(cost, s) for all h H (1)

Yℓ 0 for all ℓ L (2)

The Ph O-LP uses the operator counting formulation of post-hoc optimization (Pommerening et al. 2014). We can transform this formulation into the equivalent original formulation by Pommerening, R oger, and Helmert (2013) if we replace cost(ℓ) Yℓby Xo, where Yℓcounts the number of times label ℓis used and Xo stands for the induced costs by operator o. By converting the Ph O-LP into its dual formulation Ph O-Dual, we can see the relationship to cost partitioning more clearly:

h H h(cost, s) wh s.t.

h H:ℓ A(h) cost(ℓ) wh cost(ℓ) for all ℓ L (3)

wh 0 for all h H. (4)

In the resulting post-hoc optimization cost partitioning, each heuristic h H is assigned the cost function costh, where costh(ℓ) = cost(ℓ) wh if ℓ A(h) and costh(ℓ) = 0 otherwise. Due to the Ph O-Dual constraints, all such cost functions costh are non-negative.3

3Note that we could simplify Constraint 3 to the inequality P

h H:ℓ A(h) wh 1 by dividing both sides by cost(ℓ) and omitting the constraint for zero-cost labels, for which it is trivially satisﬁed. Intuitively, if a label affects multiple heuristics, then the total weight we assign to these heuristics cannot exceed 1. This ensures that we do not account for a higher cost contributed by the label than it actually contributes.

Saturated Post-hoc Optimization

The main observation we exploit in this paper is that it is impossible that an operator contributes more than its saturated cost to the heuristic value of an abstraction, which implies that we can use the saturated cost of an operator in Constraint 1 rather than the (original) cost of the operator.

Deﬁnition 5 (h SPh O). Let T , cost be a weighted transition system with labels L, and let H be a set of admissible heuristics for T . The saturated post-hoc optimization heuristic h SPh O(cost, s) for state s S(T ), T and H is the objective value of the SPh O-LP:

ℓ L cost(ℓ) Yℓs.t.

ℓ L scfh(ℓ) Yℓ h(cost, s) for all h H (5)

Yℓ 0 for all ℓ L, (6)

where scfh is a saturated cost function for h and cost.

Of course, different choices of scfh lead to different heuristics. In the following, we focus on heuristics h for which a unique minimum saturated cost function exists and the case where scfh is this function. As discussed earlier, this is the case for abstraction heuristics and more generally all heuristics to which the concepts of post-hoc optimization or saturated cost functions have been applied in the literature. In cases where a heuristic function detects that a label ℓ cannot be part of any goal path, scfh(ℓ) could be set arbitrarily low (to if we considered inﬁnite cost functions). Because linear programs require ﬁnite coefﬁcients, we instead add the constraint Yℓ= 0 in such cases and omit terms for Yℓin Constraint 5, which is mathematically equivalent to dealing with such inﬁnities directly. There are two notable differences between the SPh O-LP and the Ph O-LP (and indeed these are the only differences). Firstly, Constraint 5 uses the saturated cost function scfh, while Constraint 1 uses the original cost function cost. Secondly, the SPh O-LP does not require a notion of affecting labels: the sum in Constraint 5 is over all labels, where Constraint 1 is restricted to (possibly an overapproximation of) the labels affecting the given heuristic. Indeed, this restriction is critical for the utility of h Ph O: it is not difﬁcult to see from the dual formulation that, if we replaced A(h) with the set of all labels, h Ph O degenerates to the maximum of the component heuristics. Saturated post-hoc optimization can work without knowledge of which labels affect which heuristics because the same (and more) information is already implicit in the saturated cost function, as we will see in the following. Before comparing h SPh O to h Ph O, we ﬁrst establish that h SPh O is admissible.

Theorem 1. h SPh O is admissible. This result holds for all possible choices for the saturated cost functions scfh.

Proof. Consider SPh O-Dual, the dual of the SPh O-LP:

h H h(cost, s) wh s.t.

h H scfh(ℓ) wh cost(ℓ) for all ℓ L (7)

wh 0 for all h H. (8)

By the duality theorem (e.g., Schrijver 1998), the objective value of the SPh O-Dual is equal to the objective value of the SPh O-LP, so it is sufﬁcient to show that the objective value of SPh O-Dual is an admissible estimate. Consider any solution for SPh O-Dual. Because h(scfh, s) is an admissible heuristic value under the cost function scfh and because wh 0, h(scfh, s) wh is an admissible heuristic value under the cost function scfh wh. Constraint 7 is exactly the cost partitioning constraint under these (scaled by wh) heuristics, and the objective value of the LP is exactly the cost-partitioned heuristic value, taking into account that h(cost, s) = h(scfh, s) by the properties of saturated cost functions. Admissibility thus follows from the admissibility of cost partitioning (Katz and Domshlak 2010; Pommerening et al. 2015).

The advantage of saturated post-hoc optimization over regular post-hoc optimization is that the saturated cost of an operator can be signiﬁcantly smaller than its cost. It can even be negative. This means that Constraint 5 can be signiﬁcantly tighter than Constraint 1, leading to a higher admissible heuristic estimate. However, this presupposes that the information about affecting labels in Constraint 1 is indeed automatically captured by saturated post-hoc optimization as claimed above. We now show that this is the case if scfh is the unique minimum saturated cost function for h and cost.

Theorem 2. With unique minimum saturated cost functions, h SPh O dominates h Ph O, i.e., h SPh O(cost, s) h Ph O(cost, s) for all cost functions cost and states s.

Proof. Comparing Deﬁnitions 4 and 5, the linear programs that deﬁne the two heuristics are identical except for the difference in coefﬁcients in Constraint 1 and Constraint 5. For heuristic h and label ℓ, the coefﬁcient in Constraint 5 ( SPh O coefﬁcient ) is scfh(ℓ), while the corresponding coefﬁcient in Constraint 1 ( Ph O coefﬁcient ) is cost(ℓ) if ℓ A(h) and 0 (the corresponding term does not appear) otherwise. We show that the SPh O coefﬁcient is always less than or equal to the corresponding Ph O coefﬁcient. From this it follows that Constraint 5 is at least as tight as Constraint 1, and consequently the set of feasible solutions for the SPh O-LP is a subset of the set of feasible solutions for the Ph O-LP. For a minimization LP, this proves that the objective value for the SPh O-LP is greater or equal to the objective value of the Ph O-LP, proving the theorem. It remains to show the relationship between the coefﬁcients for every heuristic h and label ℓ. If ℓ A(h), we need to show scfh(ℓ) cost(ℓ), which holds because it is one of the deﬁning properties of saturated cost functions.

If ℓ/ A(h), we must show scfh(ℓ) 0. We know that ℓdoes not affect h because A(h) is a superset of the set of labels that affect h. Let cost be the (non-negative) cost function which is like cost except that cost (ℓ) = 0. From the deﬁnition of affects and ℓnot affecting h, we obtain h(cost , s) = h(cost, s) for all states s. Moreover, we have cost (ℓ ) cost(ℓ ) for all labels ℓ from the deﬁnition of cost . These two properties show that cost is a saturated cost function for h and cost. Because scfh is the unique minimum saturated cost function for h and cost, it never exceeds cost . We obtain scfh(ℓ) cost (ℓ) = 0, which concludes the proof.

We note that the example in Figure 1 shows that there are cases where the dominance is strict: we have h SPh O(cost, s1) = 8 > 5 = h Ph O(cost, s1). From the proof, we see that we do not necessarily need a unique minimum saturated cost function to establish dominance. It is sufﬁcient to consider any saturated cost function that assigns a cost of at most 0 to all labels outside of A(h), and such a saturated cost function always exists by iterating the construction of cost in the proof over all labels ℓ/ A(h).

Other Cost Partitioning Algorithms

Saturated post-hoc optimization is the latest addition to an extensive collection of cost partitioning algorithms. Seipp, Keller, and Helmert (2017a) compare cost partitioning algorithms both theoretically and experimentally. They show for cost-monotonic heuristics that saturated cost partitioning dominates greedy zero-one cost partitioning (Haslum, Bonet, and Geffner 2005; Edelkamp 2006) and that by saturating costs in a uniform cost partitioning (Katz and Domshlak 2008) we obtain an opportunistic version of uniform cost partitioning that dominates the original. Up until now, post-hoc optimization was the last cost partitioning algorithm without a direct connection to cost saturation. As we show above, the two ideas can indeed be combined into saturated post-hoc optimization, which dominates post-hoc optimization. Finally, since post-hoc optimization dominates the canonical heuristic (Haslum et al. 2007; Pommerening, R oger, and Helmert 2013), we can infer that saturated post-hoc optimization dominates the canonical heuristic as well. This leaves the question of how h SPh O compares to the other cost partitioning algorithms that are not already known to be dominated, i.e., saturated cost partitioning (h SCP) and opportunistic uniform cost partitioning (h OUCP). We already know that h SCP and h OUCP do not dominate each other (Seipp, Keller, and Helmert 2017a), and we show that there are no dominance relations between h SPh O and h SCP or h OUCP either.

Theorem 3. For each of the following pairs of cost partitioning algorithms there exists a weighted transition system T , cost and a set of cost-monotonic heuristics H for T

s1 s2, s3 s4

s1, s2 s3 s4

Figure 2: Example abstraction heuristics h3 (left) and h4 (right) used in the proof of Theorem 3. All operators cost 1. The si are concrete states, the rounded rectangles are abstract states, abstract goal states use double borders and dotted lines depict abstract self-loops.

h SCP ω (cost, s) > h SPh O(cost, s) (9)

h SPh O(cost, s) > h SCP ω (cost, s) (10)

h OUCP ω (cost, s) > h SPh O(cost, s) (11)

h SPh O(cost, s) > h OUCP ω (cost, s) (12)

for a state s S(T ) and an order ω of H.

Proof. Consider the abstraction heuristics h1 and h2 in Figure 1 for a weighted transition system T , cost . For state s2 we have h SCP h1,h2 (cost, s2) = 8 > h SPh O(cost, s2) = 7.2 > h SCP h2,h1 (cost, s2) = 7 > h OUCP h1,h2 (cost, s2) = 6, showing (9), (10) and (12). As an example for (11), consider the abstraction heuristics h3 and h4 in Figure 2 for a weighted transition system T , cost . For both heuristic orders ω, h OUCP ω (cost , s1) = 3 > h SPh O(cost , s1) = 2.

Experiments We implemented saturated post-hoc optimization in the Fast Downward planning system (Helmert 2006) and used the Downward Lab toolkit (Seipp et al. 2017) for running experiments on Intel Xeon Silver 4114 processors. Our benchmark set consists of all 1827 tasks without conditional effects from the optimal sequential tracks of the International Planning Competitions 1998 2018. We limit time by 30 minutes and memory by 3.5 Gi B. All benchmarks, code and experiment data are published online (Seipp, Keller, and Helmert 2021). In our experiments we compute cost partitionings over four different sets of abstraction heuristics: pattern databases found by hill climbing (HC, Haslum et al. 2007), systematic pattern databases of sizes 1 and 2 (SYS, Pommerening, R oger, and Helmert 2013), Cartesian abstractions of landmark and goal task decompositions (CART, Seipp and Helmert 2018) and the combination of these three heuristic sets (COMB=HC+SYS+CART). Table 1 compares the number of solved tasks by h Ph O and h SPh O for the four types of heuristic sets. We see that saturating the costs is beneﬁcial for all considered abstraction heuristics: the overall coverage increases by 9, 51, 176 and 171 tasks, respectively. A per-domain analysis reveals that h SPh O solves more tasks than h Ph O in 6, 17, 20 and 20 domains across the four settings, while the opposite is true in

HC SYS CART COMB

agricola (20) 0 0 0 0 airport (50) 23 28 25 +2 31 barman (34) 4 4 4 4 blocks (35) 28 26 +1 18 26 +1 childsnack (20) 0 0 0 0 data-network (20) 10 9 10 12 depot (22) 7 7 4 +1 7 driverlog (20) 12 12 7 13 elevators (50) 40 33 33 +4 42 ﬂoortile (40) 2 2 2 2 freecell (80) 17 +1 14 +1 14 +39 15 +38 ged (20) 19 15 15 15 grid (5) 3 2 2 2 +1 gripper (20) 7 7 7 7 hiking (20) 10 10 +1 10 +1 9 +2 logistics (63) 27 25 16 +8 28 miconic (150) 63 50 +2 52 +81 60 +82 movie (30) 30 30 30 30 mprime (35) 22 21 25 24 mystery (30) 15 15 17 17 nomystery (20) 19 16 10 +5 19 openstacks (100) 40 38 +2 37 +1 37 +2 organic (20) 7 7 7 7 organic-split (20) 9 7 8 7 parcprinter (50) 28 30 +2 24 28 +3 parking (40) 10 -1 3 +4 0 2 +4 pathways (30) 4 4 4 4 pegsol (50) 44 44 +4 44 +2 44 +4 petri-net (20) 0 2 +2 1 +1 0 pipes-nt (50) 15 +1 15 +1 15 +1 16 +1 pipes-t (50) 10 +2 8 +3 10 +1 9 +1 psr-small (50) 49 +1 49 +1 48 49 +1 rovers (40) 7 6 5 +1 7 satellite (36) 6 6 5 6 scanalyzer (50) 23 11 +16 9 +4 15 +12 snake (20) 8 +1 6 +1 7 6 +1 sokoban (50) 44 48 +1 35 +6 48 +1 spider (20) 12 12 +1 7 +4 12 +1 storage (30) 15 15 14 15 termes (20) 9 6 -1 5 8 tetris (17) 5 +4 3 5 3 tidybot (40) 21 18 7 +8 18 +3 tpp (30) 6 6 6 6 transport (70) 31 21 22 27 trucks (30) 7 7 6 +4 7 +3 visitall (40) 28 27 12 27 woodwork (50) 15 25 +9 9 +2 25 +9 zenotravel (20) 13 11 8 12 +1

Sum 824 +9 761 +51 661 +176 808 +171

Table 1: Absolute number of solved tasks by traditional posthoc optimization and the difference in coverage when using saturated post-hoc optimization instead for the four different types of abstraction heuristics.

100 102 104 106

saturated Ph O

Figure 3: Expansions excluding the last f layer for traditional and saturated post-hoc optimization when using the combination of abstraction heuristics (COMB).

only a single domain for HC and SYS and never for CART nor COMB. Figure 3 explains why h SPh O solves so many more tasks than h Ph O for the combination of abstraction heuristics (COMB) by comparing the number of expansions before the last f layer: saturating the costs often makes the resulting heuristic much more accurate. There are 327 commonly solved tasks for which cost saturation decreases the number of expansions. Furthermore, for 52 of these 327 tasks h Ph O expands states before the last f layer whereas h SPh O is perfect.

We showed that we can transport the idea of cost saturation to post-hoc optimization by considering for each heuristic only the fraction of costs that actually contributes to its estimates. The result is a cost partitioning algorithm that dominates the original both in theory and on the IPC benchmarks.

Acknowledgments

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), and this research was partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under grant agreement no. 952215.

References Edelkamp, S. 2001. Planning with Pattern Databases. In Cesta, A.; and Borrajo, D., eds., Proceedings of the Sixth European Conference on Planning (ECP 2001), 84 90. AAAI Press.

Edelkamp, S. 2006. Automated Creation of Pattern Database Search Heuristics. In Edelkamp, S.; and Lomuscio, A., eds.,

Proceedings of the 4th Workshop on Model Checking and Artiﬁcial Intelligence (Mo Ch Art 2006), 35 50.

Felner, A.; Korf, R.; and Hanan, S. 2004. Additive Pattern Database Heuristics. Journal of Artiﬁcial Intelligence Research 22: 279 318.

Haslum, P.; Bonet, B.; and Geffner, H. 2005. New Admissible Heuristics for Domain-Independent Planning. In Proceedings of the Twentieth National Conference on Artiﬁcial Intelligence (AAAI 2005), 1163 1168. AAAI Press.

Haslum, P.; Botea, A.; Helmert, M.; Bonet, B.; and Koenig, S. 2007. Domain-Independent Construction of Pattern Database Heuristics for Cost-Optimal Planning. In Proceedings of the Twenty-Second AAAI Conference on Artiﬁcial Intelligence (AAAI 2007), 1007 1012. AAAI Press.

Helmert, M. 2006. The Fast Downward Planning System. Journal of Artiﬁcial Intelligence Research 26: 191 246.

Helmert, M.; Haslum, P.; and Hoffmann, J. 2007. Flexible Abstraction Heuristics for Optimal Sequential Planning. In Boddy, M.; Fox, M.; and Thi ebaux, S., eds., Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007), 176 183. AAAI Press.

Helmert, M.; Haslum, P.; Hoffmann, J.; and Nissim, R. 2014. Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces. Journal of the ACM 61(3): 16:1 63.

Karpas, E.; and Domshlak, C. 2009. Cost-Optimal Planning with Landmarks. In Boutilier, C., ed., Proceedings of the 21st International Joint Conference on Artiﬁcial Intelligence (IJCAI 2009), 1728 1733. AAAI Press.

Katz, M.; and Domshlak, C. 2008. Optimal Additive Composition of Abstraction-based Admissible Heuristics. In Rintanen, J.; Nebel, B.; Beck, J. C.; and Hansen, E., eds., Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS 2008), 174 181. AAAI Press.

Katz, M.; and Domshlak, C. 2010. Optimal admissible composition of abstraction heuristics. Artiﬁcial Intelligence 174(12 13): 767 798.

Pearl, J. 1984. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.

Pommerening, F.; Helmert, M.; R oger, G.; and Seipp, J. 2015. From Non-Negative to General Operator Cost Partitioning. In Bonet, B.; and Koenig, S., eds., Proceedings of the Twenty-Ninth AAAI Conference on Artiﬁcial Intelligence (AAAI 2015), 3335 3341. AAAI Press.

Pommerening, F.; R oger, G.; and Helmert, M. 2013. Getting the Most Out of Pattern Databases for Classical Planning. In Rossi, F., ed., Proceedings of the 23rd International Joint Conference on Artiﬁcial Intelligence (IJCAI 2013), 2357 2364. AAAI Press.

Pommerening, F.; R oger, G.; Helmert, M.; and Bonet, B. 2014. LP-based Heuristics for Cost-optimal Planning. In

Chien, S.; Fern, A.; Ruml, W.; and Do, M., eds., Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014), 226 234. AAAI Press. Schrijver, A. 1998. Theory of linear and integer programming. John Wiley & Sons. Seipp, J.; and Helmert, M. 2013. Counterexample-guided Cartesian Abstraction Reﬁnement. In Borrajo, D.; Kambhampati, S.; Oddi, A.; and Fratini, S., eds., Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling (ICAPS 2013), 347 351. AAAI Press. Seipp, J.; and Helmert, M. 2014. Diverse and Additive Cartesian Abstraction Heuristics. In Chien, S.; Fern, A.; Ruml, W.; and Do, M., eds., Proceedings of the Twenty Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014), 289 297. AAAI Press. Seipp, J.; and Helmert, M. 2018. Counterexample-Guided Cartesian Abstraction Reﬁnement for Classical Planning. Journal of Artiﬁcial Intelligence Research 62: 535 577. Seipp, J.; Keller, T.; and Helmert, M. 2017a. A Comparison of Cost Partitioning Algorithms for Optimal Classical Planning. In Barbulescu, L.; Frank, J.; Mausam; and Smith, S. F., eds., Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling (ICAPS 2017), 259 268. AAAI Press. Seipp, J.; Keller, T.; and Helmert, M. 2017b. Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning. In Singh, S.; and Markovitch, S., eds., Proceedings of the Thirty-First AAAI Conference on Artiﬁcial Intelligence (AAAI 2017), 3651 3657. AAAI Press. Seipp, J.; Keller, T.; and Helmert, M. 2020. Saturated Cost Partitioning for Optimal Classical Planning. Journal of Artiﬁcial Intelligence Research 67: 129 167. Seipp, J.; Keller, T.; and Helmert, M. 2021. Code, benchmarks and experiment data for the AAAI 2021 paper Saturated Post-hoc Optimization for Classical Planning . https: //doi.org/10.5281/zenodo.4302051. Seipp, J.; Pommerening, F.; Sievers, S.; and Helmert, M. 2017. Downward Lab. https://doi.org/10.5281/zenodo. 790461.