Merging or Computing Saturated Cost Partitionings? A Merge Strategy for the Merge-and-Shrink Framework

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-08 11:01:17

Abstract: The merge-and-shrink framework is a powerful tool for computing
  abstraction heuristics for optimal classical planning. Merging is one
  of its name-giving transformations. It entails computing the product
  of two factors of a factored transition system. To decide which two
  factors to merge, the framework uses a merge strategy. While there
  exist many merge strategies, it is generally unclear what constitutes
  a strong merge strategy, and a previous analysis shows that there is
  still lots of room for improvement with existing merge strategies. In
  this paper, we devise a new scoring function for score-based merge
  strategies based on answering the question whether merging two
  factors has any benefits over computing saturated cost partitioning
  heuristics over the factors instead. Our experimental evaluation
  shows that our new merge strategy achieves state-of-the-art
  performance on IPC benchmarks.

Main paper: 
 introduction: 
 Classical planning is the problem of finding a sequence of deterministic actions that lead from a given initial state to a state satisfying a desired goal condition (e.g., Ghallab, Nau, and Traverso 2004) . The dominant approach of recent years 20 to optimally solving classical planning problems is heuristic search, in particular using the A * algorithm in conjunction with admissible heuristics (Pearl 1984) . The state-of-theart class of admissible heuristics is based on abstractions, such as pattern databases (e.g., Rovner, Sievers, and Helmert 2019) , domain abstractions (Kreft et al. 2023) , Cartesian abstractions (e.g., Seipp and Helmert 2018) , and merge-andshrink (M&S) abstractions (e.g., Sievers and Helmert 2021) , the latter being the focus of this work.The M&S framework first computes a factored representation of the given planning task, called factored transition system (FTS), which consists of transition systems (called factors) sharing the same set of labels. This FTS implicitly represents the state space of the task through its product system. The framework then repeatedly applies transformations to the current FTS. At any point, each factor of the FTS is an abstraction of the initial FTS (and with this, of the task).One of the name-giving transformations is merging, which means to replace two factors by their product in the FTS. To decide which pair of factors to merge, the framework uses a merge strategy. Starting with the original work adapting merge-and-shrink from model check-ing (Dräger, Finkbeiner, and Podelski 2009) to planning (Helmert, Haslum, and Hoffmann 2007; Helmert et al. 2014) , there has been considerable work exploring merge strategies (Sievers, Wehrle, and Helmert 2014; Fan, Müller, and Holte 2014; Sievers et al. 2015; Sievers, Wehrle, and Helmert 2016) . The current state of the art is constituted by the two score-based merge strategies DFP and sbMI-ASM, which choose the best pair of factors by computing scores for them, and by the SCC merge strategy, which first computes the strongly connected components (SCC) of the causal graph (Knoblock 1994) of the task to partition the state variables and then uses any score-based merge strategy for first computing a (product) transition system for each block before possibly further merging the resulting products.In general, merging cannot decrease the heuristic quality of the abstraction represented by the current FTS. However, we observe that it may also not improve it compared to the information available when not merging the factors. In particular, when computing saturated cost partitionings (SCPs) (Seipp, Keller, and Helmert 2020) over the two factors in question leads to an equally-informed heuristic compared to merging, we can decide to avoid increasing the size of the FTS by merging them and potentially even stop the M&S computation early in favor of computing SCPs over the remaining factors. We devise a new score-based merge strategy based on this observation and experimentally show that it establishes a new state of the art on IPC benchmarks.The M&S framework works on any transition system as long as it allows for a factored representation. Planning tasks in the SAS + formalism (Bäckström and Nebel 1995) , which are defined over finite-domain state variables V , induce such transition systems T = ⟨S, L, T, s 0 , S * ⟩, where S is the set of states (defined over V ), L is the set of labels ℓ with cost cost(ℓ) ∈ R + 0 , S × L × S ⊆ T is the transition relation, s 0 is the initial state, and S * ⊆ S is the set of goal states. An s-plan for T is a path π = ⟨ℓ 1 , . . . , ℓ n ⟩ from state s to some goal state from S * . Its cost is cost(π) = n i=1 cost(ℓ i ). It is optimal if there is no s-plan with lower cost. A plan for T is an s 0 -plan for T . Optimal planning is the problem of finding an optimal plan or showing that no plan exists.A heuristic h T : S → R + 0 for T maps a state s ∈ S to an estimate of the cost of an s-plan for T . By h * T we denote the Algorithm 1: M&S algorithm extended to compute SCP heuristics and to stop early according to the merge strategy.Input: FTS F Output: Heuristic for F 1: function M&SWITHSCP(F ) 2:F ′ ← F , H ← ∅ 3:while not TERMINATE(F ′ ) do4: i, j ← MERGESTRATEGY(F ′ ) 5:if not i, j then break 6:F ′ ← LABELREDUCTIONSTRATEGY(F ′ ) 7: H ← H ∪ h SCP ω 8: F ′ ← SHRINKSTRATEGY(F ′ , i, j) 9: F ′ ← (F ′ \ {T i , T j }) ∪ {T i ⊗ T j } 10: F ′ ← PRUNESTRATEGY(F ′ , i ⊗ j) 11:return COMPUTEHEURISTIC(F ′ , H) perfect heuristic for T which maps a state s to the cost of an optimal s-plan for T . h T is admissible iff h T (s) ≤ h * T (s) for all s ∈ S. We drop T if it is clear from context.An abstraction for T is a function α : S → S ′ . It induces the abstract transition system T α = ⟨S ′ , L, {⟨α(s), ℓ, α(t)⟩ | ⟨s, ℓ, t⟩ ∈ T }, α(s 0 ), {α(s) | s ∈ S * }⟩. The abstraction heuristic for T induced by α is defined as h α T = h * T α , i.e., as the perfect heuristic for the abstract transition system.Given multiple admissible heuristics (Katz and Domshlak 2010) . Saturated cost partitioning (SCP) computes cost functions 100 C as follows, assuming any fixed order ω for the heuristics from H. It maintains a remaining cost function rc which is initialized to rc 0 = cost. In each iteration i over the heuristics according to ω, it computes cost i as the minimal cost function satisfying h i (s, rc i-1 ) = h i (s, cost i ) 105 for all s ∈ S, called saturated cost function, which for abstraction heuristics is uniquely defined as cost i (ℓ) = max ⟨s,ℓ,t⟩∈T (h i (s, rc i-1 ) -h i (t, rc i-1 )) for all ℓ ∈ L, and sets the remaining costs for the next iteration to rc i = rc i-1 -cost i . We write h SCP ω for the resulting SCP heuristic.H = ⟨h 1 , . . . , h n ⟩ for T , the cost functions C = ⟨cost 1 , . . . , cost n ⟩ form a cost 95 partition if n i=1 cost i ≤ cost. We write h(s, cost ′ ) for the evaluation of h on s using an alternative cost function cost ′ instead of cost. The cost-partitioned heuristic h H,C (s) = n i=1 h i (s, cost i ) is admissibleA factored transition system (FTS) F = ⟨T1 , . . . , T n ⟩ consists of transition systems, called factors, sharing the same set of labels. LetT i = ⟨S i , L, T i , s i 0 , S i * ⟩ for 1 ≤ i ≤ n. F compactly represents the (synchronized) product de- fined as F = ⟨S ⊗ , L, T ⊗ , s ⊗ 0 , S ⊗ * ⟩, where S ⊗ , s ⊗ 0 , S ⊗ * is 115the Cartesian product over the components of all factors T i andT ⊗ = {⟨s 1 , . . . , s n ⟩, ℓ, ⟨t 1 , . . . , t n ⟩ | ⟨s i , ℓ, t i ⟩ ∈ T i }.Algorithm 1 shows the M&S framework as implemented in the Fast Downward planning system (Helmert 2006) , extended with the facility to optionally compute SCP heuris-120 tics (Sievers et al. 2020) . Ignore line 5 for the moment. For a given F , the algorithm runs its main loop until the maintained FTS F ′ only contains a single factor or function TER-MINATE stops the loop (line 3). In each iteration, it selects the pair of factors to merge next (line 4), possibly applies label reduction (line 6), which means abstracting the set return single element from M of labels, possibly shrinks the two factors (line 8), which means abstracting them, merges the two factors (line 9), which means replacing the factors by their product in F ′ , and prunes the product (line 10), which means removing dead states and their transitions. All of these transformations apply abstractions to F ′ , and at any point, each factor T of F ′ is an abstraction of the original FTS F and as such induces the factor heuristic for F , written h T F = h * T . 1 At the end (line 11), the algorithm either returns the standard M&S heuristic h M&S = max T ∈F ′ h T F , defined as the maximum heuristic over the factor heuristics induced by F ′ , or the M&S-SCP heuristic h M&S SCP = max h∈H h, defined as the maximum heuristic over all SCP heuristics h SCP ω ∈ H previously computed (line 7) using some order ω over the factor heuristics induced by intermediate FTS F ′ .A merge strategy needs to decide which pair of factors to merge given the FTS. We consider score-based merge strategies (Sievers, Wehrle, and Helmert 2016 ) that use scoring functions for evaluating merge candidates (i.e., pairs of factors) of an FTS. As shown in Algorithm 2, given an FTS F , a set of merge candidates M over F , and some scoring functions S, the strategy iteratively (line 2) computes scores for all merge candidates using a scoring function (line 3), removes all but the best candidates (line 4), and repeats until only a single candidate is left which it returns (line 6). To ensure that a single merge candidate remains, at least one scoring function must define unique scores for distinct merge candidates. We also use the SCC merge strategy which initially partitions the variables of the task and during execution of the M&S algorithm uses score-based merge strategies to decide which factors within each block to merge next, before possibly also merging the resulting products afterwards.Due to the large space of possible merge strategies, it is hard to find general criteria defining strong merge strategies, and the analysis by Sievers, Wehrle, and Helmert (2016) shows that state-of-the-art merge strategies still leave ample room for improvement. When using the M&S framework extended to compute the M&S-SCP heuristic, a natural question that arises is how merging two factors compares to leaving them for exploitation in the SCP(s) computed during M&S. To address this question, we devise the maximum for FILTERINGFUNCTION ∈ S do 3:M ← FILTERINGFUNCTION(F, M ) 4: if M = ∅ then 5:return none 6:return single element from M SCP scoring function (mSCP-sf) that prefers merge candidates whose product heuristic yields the largest improvement compared to the maximum over the two SCP heuristics over the two factors. Analogously, the maximum factor scoring function (mFactor-sf) prefers candidates whose product heuristic improves most compared to the maximum over the two factor heuristics, thus mimicking the computation of the standard M&S heuristic. To evaluate the improvement of heuristics, we compare the heuristic values of the initial state or the average values over the finite heuristic values, denoted by function AVG. Formally, let F = ⟨T 1 , . . . , T n ⟩ be an FTS with T i = ⟨S i , L, T i , s i 0 , S i * ⟩ for 1 ≤ i ≤ n. Let i, j ∈ {1, . . . , n} with i ̸ = j, let T ⊗ = T i ⊗ T j , and let s 0 = ⟨s 1 0 , . . . , s n 0 ⟩ be the initial state of F . Recall that h T i F , h T j F , and h T ⊗ F are the factor heuristics for F induced by T i , T j , and T ⊗ . We have the following variants for evaluating the merge candidate ⟨T i , T j ⟩ and the product T ⊗ :h init prod = h T ⊗ F (s 0 ) h init mFactor = max(h T i F (s 0 ), h T j F (s 0 )) h init mSCP = max(h SCP ⟨T i F ,T j F ⟩ (s 0 ), h SCP ⟨T j F ,T i F ⟩ (s 0 )) h avg prod = AVG(h T ⊗ F ) h avg mFactor = max(AVG(h T j F ), AVG(h T i F )) h avg mSCP = max(AVG(h SCP ⟨T i F ,T j F ⟩ ), AVG(h SCP ⟨T j F ,T i F ⟩)) Since we want to prefer candidates with the largest im-180 provement of initial or average heuristic values of the product compared to the factors and since we need to minimize scores, we define mFactor-sf to compute the score as h init mFactor -h init prod or h avg mFactor -h avg prod depending on using initial or average heuristic values. Analogously, mSCP-sf is defined as h init mSCP -h init prod or h avg mSCP -h avg prod . In general, the difference computed by both scoring functions cannot be positive because merging, being an information-preserving transformation, dominates any other combination of the factor heuristics. However, in our implementation, we compute the product of the two shrunk factors to mimic what the M&S algorithm would do (cf. lines 8 and 9). This means that the difference computed by mSCPsf can be positive, in which case merging is deemed worse than computing the SCP heuristics. Every score-based merge strategy can also be cast as a filter-based merge strategy by turning scoring functions into filtering functions that return the set of candidates with minimal score. Our maximum factor/SCP scoring functions, cast as filtering functions, additionally discard all merge candidates with a non-negative score. Furthermore, we extend the SCC merge strategy to allow using filter-based merge strategies instead of score-based ones and to return no merge candidate when the filtering functions discarded all candidates.Finally, we remark that when stopping the M&S computation early due to mSCP-sf having discarded all candidates, h M&S SCP is not guaranteed to be at least as good as the heuristic we would obtain after continuing merging more factors. The reason is that SCP greedily assigns costs to factors so that not all pairs of factors can have assigned full costs in the SCP computed over the final FTS. We therefore also consider adding the SCP heuristics computed over all pairs of remaining factors to the set H before computing h M&S SCP .We implemented all strategies in the existing M&S framework in Fast Downward 23.06 and evaluate them computing M&S and M&S-SCP heuristics for at most 900s, using bisimulation-based shrinking with a size limit of 50000 states, exact label reduction and full pruning of dead states. We evaluate the heuristics in an A * search, using Downward Lab (Seipp et al. 2017) to limit each planner run to 30 minutes and 3.5 GiB on IPC benchmarks from all sequential optimal tracks, a set consisting of 66 domains with 1847 tasks in total. Following Sievers et al. (2020) , we compute an SCP heuristic in each iteration of the M&S algorithm using a random order over the factor heuristics. We begin by evaluating mFactor and mSCP using initial (init) or average (avg) h-values, used as scoring (sf) or filtering (ff) functions in a score-based or filter-based merge strategy. of all combinations. We observe that stopping the M&S algorithm when there is no good merge candidate (ff) leads to worse coverage, presumably because continuing merging factors can potentially lead to better factor heuristics in later iterations. We further observe that mSCP mostly dominates mFactor, likely because the evaluation of improvement is more nuanced with mSCP, except when terminating early and using h M&S , which seems reasonable given that h M&S does not compute SCP heuristics. Finally, using the initial heuristic value to evaluate merge candidates is a better criterion than using the average heuristic value except for two cases of ff. In the remainder, we only consider the mSCP scoring and filtering functions using initial heuristic values.Next, we evaluate the addition of SCP heuristics computed for each pair of remaining factors (one for each order) to the set H before computing h M&S SCP . For the filter-based strategy, we consider the alternatives of always adding these heuristics (alw) or only if the M&S algorithm stopped due to the merge strategy having filtered all candidates (stop). Table 2 shows coverage for these variants in comparison to not including these additional SCP heuristics (none). Clearly, there is no positive effect due to including the additional SCP heuristics. The likely reason is that SCPs over pairs of factors generally do not yield strong heuristics compared to SCPs over full FTS, so that the overhead caused by their inclusion is not worth it.Finally, Table 3 shows coverage of the state-of-the art strategies DFP and sbMIASM (sbM), our best strategies with the maximum SCP scoring and filtering functions using initial heuristic values, and their integration with the SCC strategy. We observe again that the filter-based strategy cannot compete with the other strategies. While mSCPsf solves fewer tasks than the state-of-the-art strategies when computing h M&S (which seems reasonable given that h M&S does not compute SCP heuristics), integrated with the SCC strategy, it outperforms them. For h M&S SCP , both mSCP-sf and SCC-mSCP-sf significantly outperform the state of the art.To verify that the strong coverage results do not stem only from a few domains, mains in which each planner in a row solves more tasks than the planners in the columns. We observe that both mSCPsf and its integration with SCC strictly dominate all other strategies also under this measure. Finally, to assess where 285 the strength of the new strategies stem from, Figure 1 compares the number of expansions of the A * search (excluding the last f -layer) using the previous best M&S-SCP heuristic computed with the sbM strategy to using our new best strategy. We note that while the heuristics display orthogo-290 nal strengths, there is a larger number of cases where our strategy results in a stronger heuristic than vice versa.We presented a scoring function for the M&S framework that prefers merge candidates whose product results in the 295 largest heuristic improvement compared to using the factors in SCP heuristics instead. We also investigated filtering functions that stop the M&S algorithm if no merge candidate is deemed useful for merging. The new score-based merge strategy as well as its integration with the SCC merge strat-300 egy significantly outperform previous merge strategies. In future work, we want to investigate merge strategies which consider merging factors beyond a single iteration.Note that M&S uses special data structures to store the state mapping from the original FTS to individual factor heuristics(Helmert, Röger, and Sievers2015). As the details do not matter, we omit them in the presentation. 
 
 Appendix:  


Decision: The authors present a new merging strategy for the merge-and-shrink framework, which is based on saturated cost partitioning. The idea is novel and shows promising results. It is not the most surprising result and is generally incremental work based on the current state of the art and already known ideas.
We feel that the result and this particular combination of MS and SCP is nevertheless worth publishing.

One main point I want to stress to the authors (if the paper is ultimately accepted) is readability. Especially details in algorithm 1 and the exact handling of the scps (and factor orders omega) should be better explained in the paper. For example, the author's statement "we mitigate this by including all pairs after ending the main loop of M&S" in their rebuttal should be explained in the paper in more detail.

Reviews: review: strength_weakness: strength_weakness: The primary concern I have is that the paper does not justify the proposed scoring strategy well. The paper only provides empirical results to support its claim but does not explain the underlying logic or rationale behind the strategy. It is unclear why this strategy is superior to other alternatives. A more convincing justification would require a discussion of the implications and trade-offs of the strategy and theoretical considerations.

**POST-REBUTTAL
===============
Thank you for your responses.
questions: questions: I request you to respond to the concern raised in the weakness section.
strength_weakness: strength_weakness: The paper has some clarity issues.

Algorithm 1 has a couple of issues:
- If the merge strategy does not produce any i,j (first iteration, lines 4 and 5) H will be returned as the empty set (line 11). Shouldn't H be initialized as H=\{h^{SCP}_w\}?

- Line 7 uses a w order that's not specified in the algorithm. From what I understand you're always using random orders in your experiments,
but there's no reason why you couldn't use a different strategy. Shouldn't there be an order computation for the scp step?

- On line 10, you compute the synchronized product of two indices i,j instead of transition systems T_i, T_j. This is confusing.

Line 117 has confusing notation.

In Algorithm 2, the scoring functions seem to be represented as a set, but it should be made clear that there's an order to them. Different
orders can produce drastically different results.

Instead of using the argmin and making sure you have a scoring functions that defines unique scores, couldn't you use some kind of
tiebreaking considering all scoring functions? Or a voting system of some sort?

Merging or Computing Cost Partitions:
Lines 175-180: I assume you refer to the average values over all states, but maybe this could be explicitly written.

On Algorithm 3 the order of the filtering functions is relevant too, but they're being treated as a set.

When filtering, you discard all candidates that have a non-negative score. This seems to be quite aggressive, and maybe short-sighted:    maybe in this iteration merging two candidates is not beneficial, but subsequent iterations might greatly improve the end result. The motivation for this aggressive behavior might be lacking. For this filtering based merge strategy to be well justified for me, it should be less greedy, and devise ways of estimating if no further improvements can be made (farther than in the current iteration).

 What do you mean when you say "we extend the SCC merge strategy to allow using filter-based merge strategies instead of score-based ones and to return no merge candidate when the filtering functions discarded all candidates."? You compute the SCC and only consider candidates in the same component for the filtering functions? Isn't this again too aggressive?

Lines 217 through 225 are not clear to me. What do you mean when you say mSCP-sf discarded all candidates? Isn't sf refering to scoring    function? From what I understand the score-based merge strategy never discards all merge candidates. I guess this was suppossed to be    for mSCP-ff.  Assuming this refers to filtering-based merge strategies, I still do not understand what you mean by "We therefore also consider adding the SCP heuristics computed over all pairs of remaining factors to the set H before computing h^{M&D}_{SCP}".  If I'm missing something and this refers to score-based merge strategies, I think this should be explained clearer and in more detail, since  they produce the best results by a big margin.

Experiments:
The experiments show that the filtering approach yields worst results, and the explanation is "presumably because continuing merging     factors can potentially lead to better factors heuristics in later iterations". Why do you have to presume it? Can't you look at the same configurations for the score based filtering and verify this fact? The motivation and analysis of the results for the filtering based merge strategies are vague.

 What other scoring/filtering functions are you using? You only refer to one scoring function per configuration, but you need at least one of the scoring functions used in each configuration to produce unique scores, and none of the proposed scoring functions is  guaranteed to produce unique scores. I think more details about the configuration of each strategy would benefit the paper.

Intuitively, using the average h values should be better than using the initial heuristic value. Do you have an explanation of why using the initial h values is better?

The results are quite good. Can't you include a per domain results of the coverage? (Table 4 caption says per-domain coverage, but this    table is aggregating all domains).

Overall, the paper proposes an interesting new scoring functions for the M&S framework, but the motivation for filter-based merge strategy might be too vague. There are a few sections that could be explained in more detail. This might be because 2 out of 4 pages are for  introduction and background, leaving you with little space and having to be too brief in some sections.

-------------------
Post-rebuttal
-------------------
Thank you for your answers! 
If accepted I would recommend to: (1) revise Algorithm 1 carefully. What is explained is that for the SCP heuristic it generates the max of the SCP heuristics in H, but it also do other things that are only explained in the text and that it would be good to define in a more formal way (scp over the final factors, including all possible pairs after ending the main loop); (2) incorporate per domain results (supplementary material or extra page).
questions: questions: 1. Can you clarify the paragraph starting with "Finally, we remark that when stopping the M&S computation ... (lines 217-225)?
2. Can you solve the issues related to Alg.1 described in the "weakenesses of the paper"?
3. Can you clarify why if the order is relevant for scoring functions they are represented as a set in Alg. 2?
4. Can you clarify the details on the experiments: why do you have to presume the causes of the performance for the filtering-based approach? can you describe all the scoring functions used in the experiments (configuration)? Can you explain why using the average heuristic value is worse than the initial heuristic value? Can you include per domain results in coverage?
5. Do you plan to make the code publicly available?
5. Are you using the benchmarks from the last IPC or just those until IPC 2018?
strength_weakness: strength_weakness: My only concern with this paper is the 'size' of its contribution, as it looks very close to the infamous least publishable unit.


Minor comments:

Should one cite the original work on A*? I don’t know, but given that there is enough space on the citations page, why not?

The Background section is technically sound. The question however, is how much information it provides for an unfamiliar reader? It seems that some details are missing in the synchronized product. In the text you use it as an unary operator on a set of transition systems, but in Alg 1 it is a binary operator on transition systems. Moreover, in line 10 of the algorithm you multiply what seems to be the indices i,j of transition systems. If this is a shorthand notation, please specify what is what. 

You write “a set of merge candidates M over F”, does this means M is a subset of F, or does it mean that the elements in M were created using the factors of F, i.e., the elements of M can appear in F’ at some point?

Just to be sure, do you mean that h^{avg} := 1/|S| \sum_{s\in S} h(s), S are the states that can reach some goal state s_{\ast}? Can you make it clearer?

The results in table 4 are not easy to read. I understand that there are space limitations to present the large table, but domain-counting seems somewhat simplistic.


*POST-REBUTTAL*
===============
Thank you for your response.
I belive that the paper would benefit from a table of the per domain results. If purchasing an additional page is too expensive, consider publishing the results in supplementary materials and providing a citation to these materials in the original paper.
May the odds be ever in your favor.
questions: questions: 1. You write "using the initial heuristic value to evaluate merge candidates is a better criterion than using the average heuristic value except for two cases of ff."
Do you have an intuition about the reason for this?

2. I didn't see any mentioning about publishing the code upon the acceptance of the paper. I marked the option "Authors promise to release code and domains (whichever apply)."  Was I corrrect?