Versatile Cost Partitioning with Exact Sensitivity Analysis

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 15:53:07

Abstract: Saturated post-hoc optimization is a powerful method for computing admissible heuristics for optimal classical planning. The approach solves a linear program (LP) for each state encountered during the search, which is computationally demanding. In this paper, we theoretically and empirically analyze to which extent we can reuse an LP solution of one state for another. We introduce a novel sensitivity analysis that can exactly characterize the set of states for which a unique LP solution is optimal. Furthermore, we identify two properties of the underlying LPs that affect reusability. Finally, we introduce an algorithm that optimizes LP solutions to generalize well to other states. Our new algorithms significantly reduce the number of necessary LP computations.

Main paper: 
 introduction: 
 The objective of optimal classical planning is to find a cheapest sequence of actions that achieves some goal. One of the main methods for optimal planning is A * search (Hart, Nilsson, and Raphael 1968 ) with an admissible heuristic (Pearl 1984) . Currently, the strongest admissible heuristics are based on cost partitioning (Katz and Domshlak 2010) .In practice, cost partitions are often optimized using linear programs (LPs).Saturated post-hoc optimization (Pommerening, Röger, and Helmert 2013; Seipp, Keller, and Helmert 2021) is a prominent example for this. It partitions costs according to a weighted sum of saturated cost functions. In each state encountered during the search these weights are optimized by an LP which incurs significant computational costs. Höft, Speck, and Seipp (2023) introduce methods to drastically reduce the number of solved LPs without compromising the quality of the heuristic. Their approach uses the concept of sensitivity analysis from Operations Research, which determines how changes to an LP affect its optimal solutions. In the context of (saturated) post-hoc optimization, the LPs computing cost partitions for two different states s and s ′ only differ in the bounds for some constraints. With sensitivity analysis one can often avoid computing a cost partition for s ′ by cheaply adapting the cost partition for s to s ′ .In the work by Höft, Speck, and Seipp (2023) , sensitivity analysis approximates the set of states where a cost partition can be adapted. Here, we go beyond that and develop a method that can characterize this set exactly.We show that two properties of the underlying LP influence the relationship between a LP solution and the desired planning heuristic: degeneracy, where multiple solutions describe the same heuristic and non-uniqueness, where multiple heuristics are optimal. In the first case, improving the constraint formulation of the LP can reduce degeneracy; in the second, improving the columns of the LP can reduce non-uniqueness.In the presence of multiple equally good solutions, we would like to break ties in favor of solutions that generalize to more states. Therefore, we introduce an algorithm which favors LP solutions that correspond to more versatile cost partitions, increasing reusability. Our empirical evaluation shows that our new methods help to drastically reduce the number of LP computations required for the saturated posthoc optimization heuristic.We consider SAS + planning tasks (Bäckström and Nebel 1995) with operator costs. The details of planning tasks are not important for this paper, the only relevant part is that a planning task induces a weighted transition system. A weighted transition system T = ⟨S, L, T, cost, s 0 , S * ⟩ consists of a finite set of states S, a finite set of labels L, a finite set of labeled transitions T : s ℓ -→ s ′ with s, s ′ ∈ S and ℓ ∈ L, a cost function cost : L → R ∪ {-∞, ∞} that assigns a cost to each label, an initial state s 0 ∈ S, and a set of goal states S * ⊆ S. We also write s ∈ T for s ∈ S. A sequence of transitions leading from a state s to a goal state is called an s-plan and an s 0 -plan is called a plan. A plan is optimal if it has minimal cumulative cost.Heuristic search (Bonet and Geffner 2001) is a common way of solving planning tasks optimally. A heuristic function h: S → R ∪ {-∞, ∞} estimates the cost of the cheapest s-plan for each state s. It is admissible if it never overestimates the true cost of a cheapest splan h * T (s). Strong representatives of admissible heuristics are abstraction heuristics (Edelkamp 2001; Helmert, Haslum, and Hoffmann 2007; Katz and Domshlak 2010; Seipp and Helmert 2018) which simplify the transition system of a planning task with a surjective abstraction function α : S → S α , yielding an abstract transition system T α : ⟨S α , L, T α , cost, α(s 0 ), S α * ⟩, whereT α = {α(s) ℓ - → α(s ′ ) | s ℓ - → s ′ ∈ T } and S α * = {α(s) | s ∈ S * }.The preferable way of combining several heuristics admissibly is cost partitioning (Katz and Domshlak 2010; Pommerening et al. 2015) . A cost partition C in a transition system T is a tuple of cost functions C = ⟨cost 1 , . . . , cost n ⟩, such that n i=1 cost i (ℓ) ≤ cost(ℓ) for all labels ℓ ∈ L. Evaluating a tuple of admissible heuristics H = ⟨h 1 , . . . , h n ⟩ for state s under C yields the admissible estimate h C (s) = n i=1 h i (cost i , s), where each heuristic h i is evaluated under cost function cost i .A strong heuristic based on cost partitioning is saturated post-hoc optimization (SPhO) (Pommerening, Röger, and Helmert 2013; Seipp, Keller, and Helmert 2021) , which is defined as follows. Given a transition system T and a tuple of abstraction heuristics H for T , the heuristic value h SPhO (s) for a state s is the objective value of the following linear program.SPhO-LP(s): Minimizeℓ∈L cost(ℓ) • Y ℓ subject to ℓ∈L mscf h (ℓ) • Y ℓ ≥ h(s) for all h ∈ H Y ℓ ≥ 0 for all ℓ ∈ LHere, mscf is the minimum saturated cost function defined as mscf(ℓ) = supa ℓ - →b∈T (h * T (a) ⊖ h * T (b)), where the ⊖ operator is defined as regular subtraction for finite values. For infinite values, we usex ⊖ y = -∞ iff x = -∞ or y = ∞, and x ⊖ y = ∞ iff x = ∞ ̸ = y or x ̸ = -∞ = y.Linear programs (Thie and Keough 2008) , such as SPhO-LP, can be written in the canonical form max x∈R n {c ⊤ x | Ax ≤ b, x ≥ 0} where x is the vector of decision variables, c ∈ R n is a vector of objective coefficients, A ∈ R m×n is the coefficient matrix, and b ∈ R m is a vector of bounds. To solve a linear program with the simplex algorithm (Bradley, Hax, and Magnanti 1977) , m slack variables are introduced to transform all constraints from inequalities to equalities. The simplex algorithm defines solutions by iterating over bases. A basis is a valid partitioning of variables and slack variables into m basic and n non-basic variables. We indicate the indices of the basic variables as B and the indices of the non-basic variables as N . A partitioning into basic and non-basic variables is valid if the matrix B formed by the m columns of A associated with the basic variables is invertible. Each basis defines a unique LP solution by setting the non-basic decision variables to zero:x N = 0, and the basic decision variables tox B = B -1 b. The objective value is then obtained as c ⊤ B x B .Höft, Speck, and Seipp (2023) establish that performing sensitivity analysis (Gal 1986 ) on the SPhO-LP can determine whether the computed cost partition for a state s can be cheaply adapted to another state s ′ without compromising the quality of the heuristic. They introduce four approaches, however, all of these approaches are approximations, so they may fail to recognize that a previously computed cost partition, can be reused for a newly encountered state. The uns.100% Rule (lower for 0 tasks) Exact (lower for 559 tasks) strongest among them is called "100% rule" and is guaranteed to require at most as many LP computations as any of 130 the other methods (Note that despite its name, the 100% rule also is an approximation.)A natural question is whether one can go beyond an approximate sensitivity analysis, and if so, to what extent it reduces the number of LP optimizations. To perform such an 135 exact sensitivity analysis, we build on the established result that a basis remains optimal under changes in its constraint bounds ∆b if and only if all components in the basis header x * B remain greater than or equal to zero i.e, x * B + ∆x * B ≥ 0 (Bazaraa, Jarvis, and Sherali 2009). The effects on the basis 140 header from changing the constraint bounds b by ∆b are captured by the columns of the solution tableau matrix B -1 , as ∆x B = B -1 ∆b (Vanderbei 2020) . Therefore, it holds that x B + ∆x B = x B + B -1 ∆b. And thus, changing the bounds b of an optimally solved LP by ∆b will preserve optimality 145 of the current solution as long as x B + B -1 ∆b ≥ 0.Based on this result, we define the following algorithm that maintains a set of basis headers and solution tableau matrices ⟨x, B -1 ⟩: When we encounter a state s during the search, we check whether one of the stored entries satis-150 fies x B + B -1 ∆b ≥ 0. If so, we can use it to efficiently compute the heuristic value h SPhO (s). Otherwise, we solve SPhO-LP(s) and add its basis header and solution tableau matrix to our collection. We refer to Höft, Speck, and Seipp (2023) for the algorithm details, as our sensitivity analysis 155 can be used in the same setting. We call this approach the exact sensitivity analysis for the h SPhO heuristic, since it allows us to compute h SPhO while reusing a previous basis, for exactly those states s where this is possible.Figure 1 compares the number of LP solver calls required 160 to compute the h SPhO heuristic by exact sensitivity analysis and the 100% rule. This comparison is based on systematic pattern databases up to size 2 (Pommerening, Röger, and Helmert 2013 ). 1 Overall, we observe a significant increase in the reusability of cost partitions when using exact sensitivity analysis. It increases the average percentage of evaluations that do not require re-optimizing the LP from 79% to 85%. However, this advantage comes at the cost of slower evaluation and higher memory consumption, which is why some tasks can only be solved using the 100% rule.All sensitivity analysis methods evaluate the reusability of a basis, not the reusability of the solution defined by the basis. There is a difference between these two cases, because multiple bases can define the same solution coefficients x B . This means that there can be multiple LP solutions that yield the same cost partition. A necessary condition for this case is degeneracy. An LP solution is degenerate if the basis defining it has basic variables of value zero (Bazaraa, Jarvis, and Sherali 2009).Proposition 1. If an LP solution is degenerate there can be alternative solutions with the same solution coefficients.There is also the opposite case of alternative solutions that describe a different cost partition, which is captured by the notion of LP solution uniqueness (Bazaraa, Jarvis, and Sherali 2009). Proposition 2. If an LP solution is non-unique there can be alternative solutions with different solution coefficients.So far, the topic of alternative optimal solutions for LPbased heuristics has not been discussed in the planning literature, because it is irrelevant when optimizing the LP for every state. However, when reusing LP solutions between different states, alternative solutions are of high interest, as their reusability can be very different. With the definitions of degeneracy and uniqueness, we can establish a precise relationship between sensitivity analysis and cost partitioning. Proposition 3. Given an LP solution sol for SPhO-LP(s) inducing cost partition C, sensitivity analysis can determine the exact set of states for which C is optimal iff sol is nondegenerate and unique.Proof. Since sol is non-degenerate and unique, there are no other solutions for SPhO-LP(s). Therefore, there are also no other cost partitions besides C for s that yield h SPhO (s). As a consequence, sol is reusable for exactly those states s ′ for which C is optimal.We analyze the extent of degeneracy and uniqueness on SPhO LP solutions in Figure 2 . It shows that the LPs computed for h SPhO over different sets of pattern database (PDB) heuristics (Edelkamp 2001 ) have many alternative solutions. The number of degenerate solutions is highest for systematic patterns of sizes 1 and 2 (Pommerening, Röger, and Helmert 2013) . Removing patterns of size 1 from the collection decreases the average number of degenerate solutions slightly. A possible explanation for this is that the size-1 patterns are subsets of the size-2 patterns, which can lead to redundant constraints. Considering only size-1 patterns has much fewer degenerate solutions than the other two variants and even gives rise to some non-degenerate unique solutions.While a non-degenerate and unique LP solution describes a 220 single optimal basis, degenerate or non-unique LP solutions imply that there are multiple optimal bases. The existence of multiple optimal bases can affect the reusability of a computed LP solution, since sensitivity analysis is defined for a specific optimal basis.Example 1. Consider three states: s 0 , s 1 , and s 2 . Further, assume that the SPhO LP for state s 0 yields two optimal bases, x 1 and x 2 , and performing a sensitivity analysis on x i allows us to efficiently compute the heuristic value for state s i . LP solvers can provide only one of these optimal bases at 230 a time. So regardless of which basis (x 1 or x 2 ) the solver returns, an additional LP computation becomes necessary to derive the heuristic values for both states s 2 and s 3 . However, if we can reformulate the LP in a way that does not affect the computed heuristic value and at the same time re-235 duces the space of optimal bases, ideally resulting in a single optimal basis (non-degeneracy and uniqueness), it becomes more likely that we can avoid the need for such additional LP computations.It is therefore interesting to study whether we can refor-240 mulate the SPhO-LP to reduce the number of optimal bases by reducing degeneracy or non-uniqueness. Although it is generally not easy to predict whether a given LP will encounter degenerate solutions, there are two known criteria. Duplicated columns can lead to degenerate solutions and 245 duplicated rows can lead to non-unique solutions (Bazaraa, Jarvis, and Sherali 2009) .For the SPhO heuristic, this means that abstractions with the same minimum saturated cost function can affect degeneracy, and labels that have the same minimum satu-250 rated cost under all abstractions can affect non-uniqueness. Both observations are not new. Pommerening, Röger, and Helmert (2013) proposed to group duplicate labels, while Höft, Speck, and Seipp (2023) introduced abstraction grouping. Our analysis of optimal bases gives a novel explanation 255 of why these techniques can reduce the number of required Algorithm 1 Greedily increase heuristic weights.1: procedure INCREASEWEIGHTS(H, rem, s)2:for h ∈ H with h(s) = 0, in random order do 3: 1 also shows empirical evidence that abstraction and label grouping is beneficial.∆w = min ℓ∈L rem(ℓ) mscf h (ℓ) mscf h (ℓ) > 0 4: w h += ∆w 5: for ℓ ∈ L do 6: rem(ℓ) -= mscf h (ℓ) • ∆w LP computations. TableAs we discussed above, there can be multiple cost partitionsC that yield the same heuristic value h C (s) = h SPhO (s) for a given state s. Therefore, instead of accepting the arbitrary cost partition C that the LP solver finds for state s, we hypothesize that it is beneficial to optimize C to obtain a more versatile cost partition C ′ . Such an optimized cost partition needs to preserve the estimate for s, i.e., h C ′ (s) = h C (s), but apart from this requirement we can change it to make it optimal for more other states s ′ than the unoptimized C.To obtain more versatile cost partitions, we turn to the dual of the SPhO-LP (Seipp, Keller, and Helmert 2021) :Dual SPhO-LP(s): Maximize h∈H h(s) • w h s.t. h∈H mscf h (ℓ) • w h ≤ cost(ℓ) for all ℓ ∈ L w h ≥ 0 for all h ∈ H.Intuitively, this LP maximizes a weight w h for each abstraction heuristic h ∈ H. In the resulting cost partition C, each heuristic h ∈ H is assigned the cost function cost h , where cost h (ℓ) = mscf h (ℓ) • w h . The value h SPhO (s) can then be computed as h SPhO (s) = h C (s) = h∈H w h • h(s).When inspecting the SPhO-LP in dual form, it becomes apparent that the LP solver only optimizes the weights w h for heuristics with a non-zero estimate h(s). All heuristics h with h(s) = 0 do not factor into the optimization and their weights can be set arbitrarily by the LP solver. Therefore, we can increase the versatility of a cost partition C by increas-280 ing the weights w h for heuristics h with h(s) = 0 to obtain cost partition C ′ . This will preserve the estimate for s, but possibly increase the estimates for other states s ′ , making it more likely that C ′ is optimal for s ′ than C. Additionally, increasing the weights can make the sensitivity analysis more versatile. This is the case, since the new basis can only require fewer changes to be adapted for a new state s ′ . We define a greedy procedure for increasing weights in Algorithm 1. It expects the remaining costs for all labels ℓ ∈ L, which we compute as rem(ℓ) = cost(ℓ) -h∈H mscf h (ℓ) • w h . Then the procedure iterates over the heuristics h with h(s) = 0 in a random order and increases the weight w h as long as the remaining label costs allow for an increase.If the INCREASEWEIGHTS procedure found a higher lution back into the LP solver, so that its sensitivity analysis can benefit from the change. We do so by solving the same SPhO-LP again, but warm-starting it with the optimized weights. Re-solving the LP is cheap as long as the LP solver detects that the provided solution is already optimal.If negative costs occur in the minimum saturated cost functions and the provided solution is degenerate or nonunique, the simplex algorithm may fail to detect its optimality, reject it and searches its own solution again (Bazaraa, Jarvis, and Sherali 2009) . In our experimental analysis of SPhO with INCREASEWEIGHTS, we therefore skip the procedure when we detect negative saturated costs. This happens for roughly 30% of our benchmark tasks.The number of times the INCREASEWEIGHTS procedure finds a weight to increase differs a lot between planning domains and even between tasks from the same domain. In the Petri-Net-Alignment domain, for example, weights are increased between 0% and 21% of the time after finding an LP solution. As Table 1 shows, using INCREASEWEIGHTS usually decreases the number of LP solver calls. It is also raises the number of solved tasks from 682 to 832 for plain exact sensitivity analysis and from 790 to 832 if we group heuristics and labels.This paper focuses on the reusability of LP solutions computed for determining heuristic values for saturated post-hoc optimization. We introduced an exact sensitivity analysis approach that improves over existing approximations and empirically showed that it drastically reduces the required LP solver calls compared to the previous state of the art. Furthermore, we showed the importance of considering multiple alternative LP solutions and their potential to generalize to other states. Based on this insight, we proposed a novel greedy approach to optimize cost partitions for increased versatility, resulting in an even greater reduction in the number of LP computations required.An interesting avenue for future work is to explore methods that not only aim to increase the versatility of a given LP solution, but also directly optimize for its reusability.Höft, Speck, and Seipp (2023) group abstractions with the same minimum saturated cost functions in a single constraint while 
 
 Appendix:  


Decision: The reviewers agree that this is a well and clearly structured paper that makes an interesting and valuable contribution to cost partition.

We ask the authors to follow the reviewers' recommendations and include additional clarifications in the final version of their paper, as well as make the code and experimental data available.

Reviews: review: strength_weakness: strength_weakness: The "exact" method could not solve many problems due to processing overheads. However, the nature of these overheads is unclear. I expect that the smaller number of LP calls would reduce the runtime. Also, the exact count/ percentage of the unsolved instances is not given.
questions: questions: What percentage of instances, depicted in Figure 1, remained unsolved with the "exact" method? Also, since we are potentially solving a small number of LPs, what is the reason for slower runs? Is it purely because of exact sensitivity analysis?

As per Table 1, Cell(x, y) holds the number of tasks for which Algorithm x needs fewer LP solver calls than Algorithm y. Also, Cell( Base, W+) = 81 and Cell(W+, Base) = 45. Does this mean Base is more effective in reducing LP solver calls than W+, or am I misreading this table?

I understand that degeneracy and non-uniqueness would affect the reusability of an LP solution. However, I am unclear whether uniqueness and non-degeneracy are more likely to have a positive effect. Is there a theoretical basis for this? Also, it is unclear why increasing weights using the IncreaseWeight method makes the resulting cost partition more likely to be optimal for another state.
strength_weakness: strength_weakness: I do not see any major issue. The proposed method is pretty straightforward and
heavily builds on previous research from OR which I very much appreciate.

There are only few minor easily fixable issues:

The notation B^{-1} is not introduced. I assume it is inverse of matrix B, but
it should be explicitly stated to avoid confusion. Similarly for transposition x^T.

There are also terms related to LP solutions that are not defined or explained,
for example, "basis header" or "solution tableau matrix". It should be if not
formally defined, then at least explained on an intuitive level. Moreover, when
citing a specific results from books, I think it should, in this case, include
also a specific theorem or chapter so that the reader can find it more easily.
After all, ICAPS audience might not be familiar with these results from OR and
it would improve the paper if it also provided a little bit more guidance to
interested readers.

Example 1: I do not see reason to number examples here since it contains exactly
one example. I suggest to include it as an ordinary paragraph starting with "For
example". In this case, I think it actually does not break the flow of the text.
questions: questions: Do you think a similar approach would somehow be useful also in different
LP-based heuristics such as state-equation or potential heuristics?
(This is just out of curiosity, so do not feel obligated to answer it if you
don't have enogh space or you fell you don't have anything to say on that.)\

==== POST-REBUTTAL ====
Thank you for your answers.
strength_weakness: strength_weakness: The paper is not not devoid of weaknesses. In the first place, the contribution w.r.t. Höft et al. (2023), although meaningful, feels quite incremental: both work focused on reusing LP solutions, with the main difference being the use of exact vs approximate methods.

Although never unequivocally stated, the text contains several comments that suggest that the exact approach is in fact performing worse than the approximate one in terms of run-time. This is hinted by a comment at page 3, by the lack of plots referring to run-times, and by the fact that a new symmetry-breaking technique is introduced (the weight-increase approach), despite apparently working less well than existing methods. These issues do not significantly impact the theoretical value of the investigation, but they reduce its practical significance.

I suspect that alternative approaches to amortize the computation overhead may have chance to work better in this setting. Rather than focusing on reusing optimal LP solutions, the authors may also consider:

- Incremental computation, where earlier LP solutions are repaired rather than reused as they are; this is especially appealing since cost-partitioning is meant to be used during tree search, on states that might change in minor ways from parent to child node. This approach is cornerstone of MILP branch & bound, where it is typically performed via the dual simplex algorithm.

- Reusing LP solutions, even if they are not optimal. Here the idea is that any feasible solution will yield an admissible heuristic. This assumes that LP solutions can stay feasible, or that they can be repaired even suboptimally at a very-low computational cost; in this context, the frequency of solution of LPs could become a configurable parameter that one could adjust to obtain the best run-time.

- Consider primal-dual solutions (e.g. Lagrangian relaxations with multipliers optimized via sub-gradient ascent) as a repair approach. This is somewhat complementary to the previous lines, since this kind of approaches provides optimality guarantees at convergence, but can be stopped before convergence and still yield a feasible solution.

For this specific paper, I suspect that making it clear that the emphasis is on a theoretical evaluation may lead to a more consistent message.

Finally, providing access to the code would improve reproducibility (though the technique is simple enough that could be implemented without too much difficulty)


Minor points:

* pg 2: clarify whether evaluating mscf requires double state enumeration, or whether more efficient procedures can be used
* pg 2: unless I am mistaken, the "basis header" mentioned here refers to the tableau header (a basis is just a set of columns and, rather than a table); a more proper term would be "reduced cost vector", "vector of reduced costs", or something along these lines
* pg 2: storing inverted matrices, i.e. B^{-1}, is typically avoided due to the high risk of numerical instability inherent in the inversion operation; if any technique to avoid inversion is employed in the paper, it would be worth mentioning; if no such technique is employed, then numerical instability is an issue to keep in mind
questions: questions: - Is it indeed the case that in most situation the exact approach has a higher run-time compared to the approximate one?
- Is my reading of table 1 correct? That would suggest that the W+ symmetry breaking approach is not working particularly well