Transition Landmarks from Abstraction Cuts

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 18:01:01

Abstract: We introduce *transition-counting constraints* as a principled tool to formalize constraints that must hold in every solution of a transition system. We show how to obtain *transition landmark* constraints from *abstraction cuts*. Transition landmarks dominate operator landmarks in theory but require solving a linear program that is prohibitively large in practice. We compare different approximations that replace transition-counting variables with more compact operator-counting variables. These are based on projections to operator landmarks and further relaxations. For one important special case, we show that the projection is lossless even for integer-valued variables. We finally discuss efficient data structures to derive cuts from abstractions and store them in a way that avoids repeated computation in every state. We compare the resulting heuristics and other heuristics both theoretically and on the IPC benchmarks.

Main paper: 
 compute the cut: 
 C = {s o -→ s ′ ∈ T | s / ∈ Z, s ′ ∈ Z}. 3. Terminate if C = ∅. 4.Reduce the remaining costs of each transition t ∈ C. We consider two variants here:• disjoint variant: Set rem(t) = 0.• overlapping variant: Decrease rem(t) by the cost of the cheapest transition in C, i.e., by min t ′ ∈C rem(t ′ ).The top of Figure 3 shows an example of the generated goal zones and cuts. In every iteration, the remaining cost of at least one transition is updated from a positive value to 0 and the source of that transition will be added to Z in the next iteration. This can only happen at most |S| times, so the loop is guaranteed to terminate.The disjoint variant adds all source states of the transitions in the cut to the goal zone in the next iteration. Consequently, a transition can occur in at most one cut and the resulting cuts are pairwise disjoint. In the overlapping variant, expensive transitions can occur in multiple cuts.Let Z i be the goal zone in iteration i, C i be the generated cut, andS i = {s | s o -→ s ′ ∈ C i }.It is easy to see that C i is an s-cut for all states s ∈ S \ Z i . This includes the set S i but interestingly it also includes S j for all j > i. We can uses 0 s 1 s 2 s 3 s 4 t 1 : a t 2 : b t 3 : b t 4 : c t 5 : c t 6 : d C = {{t 4 , t 5 }, {t 1 , t 3 }, {t 1 , t 2 }} S = { s 4 , s 3 , s 2 , s 1 , s 0 } Figure 3: Transition system with cost(t 1 ) = 2 and cost(t i ) = 1 for i > 1.Boxes around states show the goal zone after each iteration. Transitions entering a goal zone are part of the cut. In the disjoint variant, the dashed cut is not found. Below is the set C of discovered cuts and our data structure mapping states s ∈ S to sets of s-cuts.this connection to efficiently store the cuts: We store all cuts in a list [C 1 , . . . , C n ] in the order they were created. We then store an index i s into this list for every state s, where i s is the last iteration in which s ∈ S i . The bottom of Figure 3 has 460 an example of this data structure. If we want to retrieve the set of s-cuts for some state s, this is just the first i s entries of the list. The index is zero for all states s g that are in the goal zone initially: none of the computed cuts are s g -cuts for such state. Dead-end states s de that have no path to the goal 465 use index n. Technically, all cuts are s de -cuts for such states because the fact that every s de -plan passes through a cut is vacuously true for all cuts if there are no s de -plans.When considering disjoint cuts constraints, we are also interested in subsets of cuts S ⊆ C where C is a set of s-cuts. 470 Different states s use different sets C and thus have different choices for S. However, as before, we can create a list of all possible choices of S ordered in a way that all subsets involving only C 1 , . . . C i come before the first subset involving C i+1 . We can then quickly identify the relevant subsets 475 S for each state s. This is useful as we can set up a single linear program in which we only have to enable/disable constraints when switching from one state to another.Even if not all subsets should be considered, this approach can be helpful. For example, consider the case, where we 480 want to consider only maximally connected subsets S ⊂ C. We can order the maximally connected subsets involving only cuts C 1 , . . . C i before any set involving C i+1 again. States in S i have a maximally connected component X i that includes C i . If C i+1 shares an operator with C i , then 485 states in S i+1 will contain a maximally connected component {C i+1 } ∪ X i . This is a superset of X i , so X i is not maximally connected for states in S i+1 . Collecting the prefix of the list up to the entry for S i+1 will thus collect more sets than just the maximally connected ones. However, this 490 collection is still limited and supports efficient incremental computation, so we also use it in our experiments. We call it c dcset(C) max and analogously define c dcset(C) atomic,max Our algorithm not only generates cuts but also partitions transition costs between them. Let α C = min t∈C rem(t) be the minimal cost of a transition in the cut at the time it is discovered. For these values of α the functions cost C as defined in the previous section form a cost partitioning of the original cost function. This is particularly interesting in the overlapping variant of the algorithm, where cuts are created according to h *layers in the transition system: The first cut is induced by a goal zone Z 1 consisting of all states s with h * (s) = 0. Then in each step the cut C i separates states s ∈ Z i with h * (s) < j≤i α Cj from states with a higher heuristic value. States s in S i have exactly the goal distance h * (s) = j≤i α Cj . Consider c cutcost (C,α) for these values of α in a state s ∈ S i . The right-hand side simplifies to j≤i α Cj = h * (s).For each transition t = s o -→ s ′ on the left-hand side,C∈C t∈C α C = h * (s) -h * (s ′ ).The cost function expressed in the coefficients on the left-hand side of c cutcost(C,α) can then be interpreted as cost sat (o) = max s o -→s ′ ∈T (h * (s) -h * (s ′ )), the saturated cost function in the transition system. Constraint c cutcost (C,α) for this choice of α thus is the saturated post-hoc optimization constraint (Pommerening, Röger, and Helmert 2013) : o∈O cost sat (o)Y o ≥ h * (s).The above result implies that for the right set of cuts, c tlm-set(C) dominates saturated post-hoc optimization. We can show with an example that this dominance can be strict: In Figure 3 , the saturated post-hoc optimization constraint is2Y a + Y b + Y c ≥ 3. It has a solution at Y c = 3, Y a = Y b = 0 which does not satisfy the transition landmark Y c ≥ 1.Many other ways of discovering cuts are possible. For example, one could also start from the initial state and generate landmarks in a forward direction. Another possible improvement would be to consider a beyond-goal zone as in LM-cut, of states that can only be reached after reaching a goal state. The graph could also be limited to states reachable from s when computing landmarks for s. This can be useful for example in state s 1 in Figure 3 where {t 3 } is an s 1 -cut but both variants of our method only find {t 1 , t 3 }. Using this cut would make efficient storage and re-use of the linear program during search more difficult though. We leave the exploration of other cut generation methods for future work and focus on the two variants described above. So far these arguments can all be made with a single abstraction. As our overall aim is to extract constraints from many small abstractions and combine them in operatorcounting LP/IPs, we also compare this to other heuris-550 tics that do so. In the previous section, we have seen that c tlm-set(C) implies the saturated post-hoc optimization constraint if C contains sufficiently many cuts.Finally, we try to find an upper bound on the heuristic quality and show that it can be tight. Combining constraints 555 from different cuts in an operator-counting LP corresponds to optimal general cost partitioning. We have already seen that negative costs cannot contribute to our cut-based constraints. Since our constraints are operator-counting constraints, using all constraints from a single abstraction in a 560 single operator-counting LP gives an admissible estimate for that abstraction. This value cannot exceed the cost of a shortest path in the abstraction. Non-negative cost partitioning of abstraction heuristics (called nnOCP in Figure 4 ) combines the cost of shortest paths in each abstraction, so our heuris-565 tics are limited by it.For sufficiently many cuts, we can show that the operatorcounting LP for c tlm-set(C) is optimal for its transition system under all non-negative cost functions: Consider a nonnegative cost function cost and the set C of all s-cuts. Then 570 there is one set S ⊆ C that separates heuristic layers according to cost. Any solution to the transition landmark constraints must pass through all those cuts and thus cause at least cost h * , i.e., min{ o∈O cost(o)Y o | c tlm-set(C) } ≥ h * (s, cost). This means that if we combine constraints 575 c tlm-set(C) for several abstractions in one operator-counting LP and include sufficiently many cuts in all cases, the resulting heuristic matches nnOCP over those abstractions.We implemented transition counting and our cut genera-580 tion method for en Fast Downward version 22.06 (Helmert 2006) . We use its operator-counting heuristic with CPLEX 22.1.1 as the LP solver to evaluate operator-counting LPs for our various constraints on the 1827 problems from the optimal tracks of the international planning competitions 1998-5852018. Experiments are conducted on Intel Xeon Silver 4114 processors running on 2.2 GHz with a time limit of 30 minutes and a memory limit of 3.5 GiB. We will publish our code, data and benchmarks upon acceptance.In this section, we write disj and ovlp for cuts discovered c tlm-set(ovlp) we have the same number of variables and a comparable number of constraints but the heuristic quality is improved, leading to fewer state expansions. The cuts discovered with the overlapping variant are not guaranteed to be stronger than the ones by the disjoint variant. Theoretically the heuristic for c tlm-set(ovlp) does not dominate the one for c tlm-set(disj) but in practice, it always led to fewer expansions. For disjoint cut sets, we have shown that c dc-set(disj) all and c dc-set(disj) connected are equivalent to c tlm-set (disj) . Our experiments confirm this by yielding the same number of expanded states.Moreover, we find that projecting away auxiliary variables is beneficial, as c dc-set(disj) all usually solves the problems significantly faster than c tlm-set (disj) . The speed improvement is even more pronounced when considering c dc-set(disj) connected which only includes the constraints for connected subsets of disj. atomic,max yield weaker heuristics, they still solve more problems than the other approaches. This is no surprise, as the number of connected subsets of disj can still be exponential in |disj|, while the number of inequalities for the weaker constraints is linear in |disj|. This speeds up the solver times for evaluating the heuristic in each state at the expense of heuristic quality. The difference in terms of coverage and planning time is marginal between these methods, with c dcset(disj) max coming out on top followed by c dc-set(disj) atomic . Even though these two are incomparable in theory, in practice c We also observe that c dcset(disj) max expands more states than c dc-set(disj) connected in only 3 out of the 47 domains. It is hence a much cheaper relaxation that does not lose much information in practice. However, given that c dc-set(disj) atomic results in comparable performance as c dcset(disj) max , the benefit of transition counting over operator counting is limited for this particular set of cuts. We still believe the approach is worth pursuing further, as we have seen cases in our examples throughout the paper where transition counting adds information. Examples like the one in Figure 2 seem natural to us and not like rare exceptions. A direction worth exploring would be alternative cut generation methods to create more informed cuts.We introduced transition counting, an extension to the operator-counting framework. Transition-counting constraints can be formulated in any transition system but interesting planning tasks induce transition systems with a prohibitive amount of transitions. Our linking and translation constraints offer effective ways to formulate transitioncounting constraints based on smaller abstractions with fewer transitions. They can then be used together with other operator-counting constraints for the full planning task.Transition-counting constraints based on cuts can differentiate multiple uses of the same operator in different contexts. They dominate the landmark constraints derived from the same cuts, even if transition-counting variables are projected out. Projections to operator-counting variables such as c dc-set(C) connected for pairwise disjoint cuts contain the same information as c tlm-set(C) but at a different size trade-off. Their relaxations give up some accuracy for a smaller size.Experimentally, we have seen that just considering maximally connected subsets of C (c dc-set(C) max) had the best tradeoff despite being an aggressive relaxation of c dc-set(C) connected . While we saw that distinguishing transitions in cuts can improve the heuristic value, this happened only rarely in practice and operator landmarks based on the same cuts perform almost as good. This might be an effect of our cut generation method. New ways of extracting cuts from abstractions, particularly ones that generate an interesting set of overlapping cuts, could lead to improved performance.Another interesting line of future work is to add additional transition-counting constraints, such as for example (some relaxation of) state-equation constraints (van den Briel et al. 2007; Bonet 2013) , or to consider larger abstractions. 
introduction: 
 Operator counting (Pommerening et al. 2014 ) is a framework in classical planning to combine information from different sources. It uses constraints on the number of times each operator of the task is used. One source of inaccuracy in this framework is that one planning operator usually induces many transitions. Information on how often an operator is used aggregates over these transitions an thus cannot distinguish different uses of the same operator.We introduce transition counting as an extension of operator counting to a more fine grained level. Since the number of transitions in a planning task is prohibitively large, we show how to derive transition-counting constraints from abstractions. Such constraints are more compact and can be linked to the operator-counting framework as well.In particular, we investigate transition landmarks based on cuts in a transition system. These can have an advantage over operator landmarks derived from the same information as they distinguish different uses of the same operator. We then explore what effect these constraints have on the operatorcounting variables as this is the only way they can interact with other constraints. Projections of cut-based constraints to operator-counting variables can still be large but can be relaxed further, trading off accuracy for a smaller size.We also introduce a way of finding cuts in transition systems based on LM-cut (Helmert and Domshlak 2009) and an efficient data structure to access them during a search.Finally, we empirically evaluate the constraints and their relaxations on IPC benchmarks.Classical planning We consider planning task with operators O and a cost function cost : O → R 0 (e.g., Bäckström and Nebel 1995; Haslum et al. 2019) . Further details of the planning framework are not important as we work on the induced transition systems.A planning task Π induces a transition system T (Π) = ⟨S, O, T, I, G, cost⟩ with a finite set of states S; the operators O of Π; a finite set of transitions T ⊆ S × O × S where an individual transition is written as s o -→ s ′ and label(s o -→ s ′ ) = o is used to denote its label; an initial state I ∈ S; a set of goal states G ⊆ S; and the transition cost function cost : T → R 0 is defined based on the cost function of Π as cost(t) = cost(label(t)).A sequence of transitions π = ⟨t 1 , . . . , t n ⟩ is an s-plan for T (Π) iff t i ∈ T with t i = s i-1 oi -→ s i for 1 ≤ i ≤ n, s 0 = s and s n ∈ G. If s = I, π is a plan for Π. The cost of an s-plan π = ⟨t 1 , . . . , t n ⟩ is the sum over the transition costs of the sequence, i.e., cost(π) = n i=1 cost(t i ). An s-plan is optimal if it has minimal cost among all s-plans. The perfect heuristic h ⋆ maps each state s to the cost of an optimal splan and to ∞ if no such plan exists. A function h : S → R + 0 ∪ {∞} is called an admissible heuristic if h ≤ h ⋆ .Landmarks In this work we consider disjunctive action landmarks (Zhu and Givan 2003; Helmert and Domshlak 2009; Büchner, Keller, and Helmert 2021) and call them landmarks for brevity.Let T be a transition system with operators O and let s be one of its states. We call a set of operators L ⊆ O a landmark for s if for all s-plans π = ⟨t 1 , . . . , t n ⟩ there is an 1 ≤ i ≤ n such that label(t i ) ∈ L.Abstractions An abstraction function α maps all states of a transition system T to a set of states S α , and a label reduction λ maps its operators to a set of labels O λ . Such abstraction functions induce an abstract transition system (or abstraction) T αλ = ⟨S α , O λ , T αλ , I α , G α , cost λ ⟩ whereT αλ = {α(s) λ(o) ---→ α(s ′ ) | s o -→ s ′ ∈ T }, I α = α(I), G α = {α(s) | s ∈ G}, and cost λ (s ℓ - → s ′ ) ≤ min o∈λ -1 (ℓ) cost(o), where T are the transitions and G the goal states of T (Π). Usually, α is chosen such that T α is much smaller than T (Π), e.g., as projecting s to a small subset P of variables. In that case the abstraction is called a projection (or atomic projection if |P | = 1). A common choice for λ is exact label reduction that maps operators to the same label iff they have the same cost and induce transitions between the same pairs of abstract states.An important property of abstractions is that all paths in T are also feasible in T αλ . Given a sequence of transitions ⟨s 0o1 -→ s 1 , . . . , s n-1 on -→ s n ⟩ such that s i-1 oi -→ s i ∈ T for all 1 ≤ i ≤ n, it holds that α(s i-1 ) λ(oi)---→ α(s i ) ∈ T α . Put differently, the cost of an optimal plan in the abstract transition system is a lower bound on the cost of an optimal plan in the original transition system. The perfect heuristic for the abstract transition system (h αλ ) is therefore admissible for the original transition system.Operator Counting Consider a set of abstractions A = {T α1λ1 , . . . , T αnλn }. Each heuristic h αiλi provides an admissible estimate, but to use them in an optimal search algorithm like A ⋆ we have to combine them in a way that maintains admissibility. Operator counting (Pommerening et al. 2014 ) is a framework to admissibly combine admissible heuristics that can be expressed in terms of necessary plan properties called operator-counting constraints.We denote with occur(o, π) the number of occurrences Operator-counting constraints have been derived from a variety of planning heuristics, including landmarks and orderings between landmarks (e.g., Büchner, Keller, and Helmert 2021) , the delete relaxation (e.g., Helmert and Domshlak 2009; Imai and Fukunaga 2014) and net change constraints (Bonet 2013). Abstraction heuristics have also been used before to derive operator-counting constraints. Pommerening, Röger, and Helmert (2013) introduce posthoc optimization constraints which describe the relationship between operators that are relevant for the abstraction, their cost and the heuristic value of the abstraction, and Seipp, Keller, and Helmert (2021) strengthen post-hoc optimization constraints by taking saturated costs into account.Transition Counting Pommerening et al. (2014) show that cost partitioning (Katz and Domshlak 2010) of abstraction heuristics can be encoded in the operator-counting framework. They use auxiliary variables for the number of times each abstract transition is used. This turns out to be unnecessary as the same heuristic can be encoded more compactly without these variables but it suggests an extension of the operator-counting framework to the level of transitions.Definition 1. Let ⟨S, O, T, I, G, cost⟩ be a transition system and let s ∈ S. Let Y be a set of non-negative real-valued and integer variables, including non-negative (integer-valued) operator-and transition-counting variables Y o for each o ∈ O and Y t for each t ∈ T along with any number of additional variables. We denote the number of occurrences of operators o ∈ O and transitions t ∈ T in π with occur(o, π) and occur(t, π). A set of linear inequalities over Y is called 145 a transition-counting constraint for s if for all s-plans π there exists a feasible solution with Y o = occur(o, π) for all o ∈ O and Y t = occur(t, π) for all t ∈ T .A transition constraint set for s is a set of transitioncounting constraints for s where the only common variables 150 between constraints are the counting variables.By definition, every transition-counting constraint and every transition constraint set is an operator-counting constraint. (Note that we have to consider a set of transitioncounting constraints as a single operator-counting constraint 155 because they share variables other than Y o .)If we want transition-counting constraints to be useful in the operator-counting framework, we have to link the transition counts to the operator counts. Definition 2. Consider a transition system T with operators O and transitions T . The linking constraint is the set of linear inequalities c link(T ) :t∈T label(t)=o Y t = Y o for all o ∈ O.Please observe that the linking constraint is a transition-160 counting (and thus also an operator-counting) constraint as the equations obviously holds for any plan.Using variables for every transition in a planning task Π is typically intractable but we can do so for small abstractions of Π. Unless the label reduction is the identity, though, 165 abstractions use labels different from O. The following constraint translates between O and O λ . Definition 3. Let λ be a label reduction. The translation constraint for λ is the set of linear inequalities c translate(λ) :o∈λ -1 (ℓ) Y o = Y ℓ for all ℓ ∈ O λ .With this constraint, we can use operator-counting constraints from abstractions. Proposition 1. Let T αλ be an abstraction of planning task 170 Π and let c be an operator-counting constraint for a state α(s) of T αλ . Then {c, c translate(λ) } is an operator-counting constraint for s in Π.Proof. Let π be an s-plan and let λ(π) be the sequence that uses label λ(o) where π uses o. Since T αλ is an abstraction 175 of T (Π), λ(π) is an α(s)-plan. As c is an operator-counting constraint for α(s) in T αλ , there is a solution of c with Y ℓ = occur(ℓ, λ(π)) = o∈λ -1 (ℓ) occur(o, π). Extending it with Y o = occur(o, π) also satisfies c translate (λ) .Note that c translate(λ) can be used to eliminate variables Y ℓ 180 from c (replacing Y ℓ with o∈λ -1 (ℓ) Y o ) so the resulting constraint is in terms of the original operators.We can thus derive transition-counting constraints for an abstraction, link them together with a linking constraint, and then use Proposition 1 to get an operator-counting constraint for the original task. In the remainder of this paper, we thus usually ignore the fact that a transition system is an abstraction and just treat it as the only transition system.Since auxiliary variables like transition-counting variables are not shared between different operator-counting constraints, we compare their relative strength solely based on their solutions for operator-counting variables. We say an operator-counting constraint c 1 is implied by a constraint c 2 for real-valued variables if Sol LP (c 2 ) ⊆ Sol LP (c 1 ). If there are solutions in Sol LP (c 1 ) that are not in Sol LP (c 2 ), we say that c 1 is weaker than c 2 (or that c 2 is stronger) wrt. real-valued variables. If Sol LP (c 2 ) = Sol LP (c 1 ), both constraints imply each other, and we say they are equivalent wrt. real-valued variables. Using a stronger operator-counting constraint in an operatorcounting LP can only increase the objective value, while replacing a constraint with an equivalent one will not change the objective value, even in the presence of other constraints. A way to show that c 1 is implied by c 2 for real-valued variables is to show that the inequalities in c 1 are conic combinations of the inequalities in c 2 . For example,c 2 := {2Y t -Y a ≥ 0, Y b -2Y t ≥ 0} implies c 1 := {Y b ≥ Y a } because the inequality is the sum of the inequalities in c 2 .Analogously to the definitions above we define the set of integer-valued solutions Sol IP (c) and the terms implied, weaker, stronger, and equivalent wrt. integer-valued variables. We know that Sol IP (c) ⊆ Sol LP (c) ∩ N n but not all integer-valued solutions in Sol LP (c) are necessarily in Sol IP (c). Consider for example a constraint c := {Y a ≤ 2Y t , 2Y t ≤ Y b }. We have Sol LP (c) = {Y | Y a ≤ Y b }, and Y a = Y b = 1 is a solution in Sol LP (c) ∩ N n . However, this solution is not in Sol IP (c), as there is no integer Y t ∈ N with Y a = 1 ≤ 2Y t ≤ 1 = Y b .An important result from Operations Research (e.g., Conforti, Cornuéjols, and Zambelli 2014) shows that if the coefficient matrix of the auxiliary variables is totally unimodular, then integer-valued solutions in Sol LP (c) ∩ N n can always be extended to an integer-valued solution of c, so Sol LP (c) ∩ N n = Sol IP (c). In that case, if a constraint c 1 is implied by c 2 wrt. real-valued variables, it is also implied wrt. integer variables, and if it is weaker wrt. integer variables, it is also weaker wrt. real-valued variables. In such cases we just use the terms implied and weaker without reference to integer or real-valued variables.We now focus on specific transition-counting constraints related to landmarks. So far, landmarks are derived with label propagation in the relaxed task graph (Zhu and Givan 2003; Keyder, Richter, and Helmert 2010) , backwardchaining in the delete relaxation (Hoffmann, Porteous, and Sebastia 2004; Richter, Helmert, and Westphal 2008) , or as cuts in a graph justifying cost of a relaxed task (Helmert and Domshlak 2009) . We propose a new method of deriving landmarks from cuts in (abstract) transition systems. Definition 5. Let T = ⟨S, O, T, I, G, cost⟩ be a transition 245 system and s a state in S.t∈C Y t ≥ 1 for all C ∈ C t∈T label(t)=o Y t = Y o for all o ∈ O o∈O C Y o ≥ 1 for all C ∈ C o∈O S Y o ≥ |S| for all(*) S ⊆ C (*) depending on X o∈O ( max t∈T label(t)=o C∈C t∈C α C )Y o ≥ C∈C α C c tl m -s et ( C ) c tl m ( C ) c li nk ( T ) c ol m -s et ( C ) c ol m ( C ) c dc -s et X ( C ) c dc ( S ) c cu tc os t( C ,α )A set of transitions C ⊆ T is an s- cut iff there is a subset of states Z ⊂ S with s / ∈ Z, G ⊆ Z, and C = {s 1 o -→ s 2 ∈ T | s 1 / ∈ Z, s 2 ∈ Z}.Such cuts induce disjunctive action landmarks that must hold in every plan for the transition system. In this and the following sections we introduce several constraints based on cuts. Figure 1 collects the most important ones in a single place and is meant for quick reference. 255 The first such constraint uses transition-counting constraints to be more fine-grained than just talking aboutO C . Proposition 3. If C is an s-cut then the transition landmark constraint c tlm(C) : t∈C Y t ≥ 1 is a transition-counting constraint.If the transition landmark constraint for a single cut C is linked to operator counts, it contributes the same in-260 formation to the operator-counting framework as the landmark O C . (We defer proving this statement to Proposition 7, where we prove it in a more general form.) Proposition 4. Let C be an s-cut derived from a transition system T . Then the operator landmark constraint c olm(C) : The advantage of transition landmarks over operator landmarks becomes clear if we use more than one cut. Consider the transition system and the two s I -cuts C 1 and C 2 depicted in Figure 2 . Operator landmark constraints just use the disjunctive action landmarks derived from these cuts:o∈O C Y o ≥ 1 is equivalent to {c tlm(C) , c link(T ) }. s I s 1 s 2 s 3 t1 : a t 2 : b t 3 : c t4 : a C1 C2Y a + Y b ≥ 1 c olm(C1) Y a + Y c ≥ 1 c olm(C2)These constraints have a solution Y a = 1 and Y b = Y c = 0. However, we can see in the transition system that using operator a once will not suffice to solve the task. If we distinguish transitions in the constraints, two cuts with different transitions that are labeled with the same operator can no longer be resolved with just a single use of the operator. The transition landmark constraints for the cuts areY t1 + Y t3 ≥ 1 c tlm(C1) Y t2 + Y t4 ≥ 1 c tlm(C2)Together with the linking constraint c link(T ) , in particular the 265 equation Y t1 + Y t2 = Y a , the assignment from above is no longer a solution. In fact, every solution requires a total operator count of at least 2. Definition 6. Let T be a transition system, s one of its states, and C a set of s-cuts in T . The transition landmark setconstraint for C is the transition constraint set c tlm-set(C) := {c tlm(C) | C ∈ C} ∪ {c link(T ) }.We get the following connection to operator landmarks as a corollary of Proposition 4 and the example above. Proposition 5. Let C be a set of s-cuts derived from a transition system T . Then c tlm-set(C) implies c olm-set(C) := {c olm(O C ) | C ∈ C} and can be stronger.Even though the transition landmark set constraint dominates the operator landmark set constraint in terms of heuristic guidance, it comes with a significant drawback: it requires many auxiliary variables and linking constraints which, as we will see in our experimental evaluation, impair planner performance in practice. We are therefore interested in projecting out transition-counting variables or approximating the projection.If cuts are disjoint, this means every transition occurs in at most one cut. It is important to note that this only refers to the transitions. An operator can still be used to label different transitions occurring in multiple cuts. In our running example, cuts C 1 and C 2 are disjoint because they do not share a transition, even though both cuts mention operator a. In fact, if the induced landmarks of the cut are disjoint as well, transition landmark set constraints have no advantage over operator landmark set constraints.If we consider a set of cuts S (say S = {C 1 , C 2 } in our running example), every plan has to pass through all of the cuts in S. If cuts in S are pairwise disjoint, this takes |S| separate transitions. These transitions can only be labeled with operators in O S := {label(t) | t ∈ C, C ∈ S} = C∈S O C , i.e., the operators mentioned anywhere in S. (In our example, O S = {a, b, c}.) We can conclude that the sum of operator-counts for operators in O S must be at least |S|.In the example, this corresponds to the constraint Y a + Y b + Y c ≥ 2. This argument holds in general, so the following constraints are operator-counting constraints: Definition 7. Let S be a set of pairwise disjoint s-cuts. The disjoint cuts constraint for S is c dc(S) :o∈O S Y o ≥ |S|.To see the importance of cuts being pairwise disjoint, consider that we add the cut C 3 = {t 2 , t 3 } to the example. The disjoint cut constraint for S = {C 1 , C 2 , C 3 } would exclude plans of length 2, which clearly exist.When comparing disjoint cuts constraints to operator landmark constraints, we first observe that c olm(C) for a cut C is the same as the c dc(S) for a set of cuts S = {C}. For larger sets S, the constraint becomes incomparable to operator landmark constraints. We can see this in our running example, where {c olm(C1) , c olm(C2) } = {Y a + Y b ≥ 1, Y a + Y c ≥ 1} and {c dc({C1,C2}) } = {Y a + Y b + Y c ≥ 2}. The as- signment Y a = Y c = 0 and Y b = 2 satisfies Y a +Y b +Y c ≥ 2 but not Y a + Y c ≥ 1, while the assignment Y a = 1 and Y b = Y c = 0 satisfies Y a + Y b ≥ 1 and Y a + Y c ≥ 1 but not Y a + Y b + Y c ≥ 2.We now show that multiple disjoint cuts constraints can be used to express a constraint equivalent to c tlm-set(C) if cuts in C are pairwise disjoint. We start by showing that c dc(S) is implied by c tlm-set(C) for every subset of cuts S ⊆ C. Proposition 6. Let C be a set of pairwise disjoint s-cuts and S ⊆ C one of its subsets. Then c dc(S) is implied by c tlm-set(C) but can be weaker, even for S = C.Proof. To show that c dc(S) is implied, we can sum up constraints c tlm(C) for C ∈ S. On the right-hand side, this adds 1 for each C ∈ S, resulting in |S|. Sums for different cuts do not overlap, so each transition-counting variable occurs at most once on the left-hand side. We can then add constraint Y t ≥ 0 to include transition-counting variables on the lefthand side that belong to operators in O S but do not occur in the sum yet. Afterwards, we can use equations from c link(T ) for all o ∈ O S to replace sums of transition-counting variables with the corresponding operator-counting variables.To see that c dc(S) for S = C can be weaker than c tlm-set(C) consider our running example: Y a = Y c = 0 and Y b = 2 is a solution for c dc(C) but not for c tlm-set (C) .While a single disjunctive cuts constraint can be weaker than the transition landmark set constraint, including such constraints for all subsets S ⊆ C makes the resulting constraint equivalent: Proposition 7. Let C be a set of pairwise disjoint s-cuts in a transition system T . Then c tlm-set(C) and c dc-set(C) all := {c dc(S) | S ⊆ C} are equivalent.We refer to the technical report (Anonymized 2023) for the full derivation and only present a rough sketch here.Proof sketch. The coefficient matrix of c tlm-set(C) is totally unimodular if cuts are pairwise disjoint, so showing equivalence wrt. real-valued variables is sufficient. For this case, we consider combinations of constraints c tlm(C) , c link(T ) , and Y t ≥ 0, similar to the approach in the proof of Proposition 6. However, instead of considering one specific combination, we consider all conic combinations by multiplying the coefficient matrix with the extreme rays of a cone D that describes conditions for all Y t reaching a coefficient of 0. For a set of multipliers α, the resulting combination of inequalities is the constraint c cutcost(C,α) :o∈O ( max t∈T label(t)=o C∈C t∈C α C )Y o ≥ C∈C α C and c tlm-set(C) is equivalent to {c cutcost(C,α) | α ≥ 0}.We show that for disjoint cuts, a vector α can only be an extreme ray of the cone This shows that c cutcost(C,α) exactly matches c dc (Sα) . ThusD if it is binary, so c tlm-set(C) is equivalent to {c cutcost(C,α) | α ∈ {0, 1} |C| }.{c cutcost(C,α) | α ∈ {0, 1} |C| } is equivalent to c dc-set(C) .Say two cuts C 1 , C 2 are share an operator if O C1 ∩ O C2 ̸ = ∅, i.e, some operator is used as a label in both of 355 the cuts. For a set of cuts S, consider the graph G S where each C ∈ S is a node and there is an edge between two cuts iff they share an operator. We say S is connected if G S has a single connected component. We now show that we only have to consider connected subsets S ⊆ C. If S is not connected, consider a connected component S 1 of G S and S 2 = S \ S 1 . In that case, O S1 and O S2 are disjoint, so c dc(S1) + c dc(S2) = c dc(S) , i.e., c dc(S) is implied by the other two constraints. Together with Proposition 7 we get the following result: In the other extreme all connected subsets are considered and the constraint is equivalent to c tlm (C) . But there are options in between, for example c dc-set(C) atomic,max := {c dc(S) | S ⊆ C, |S| = 1 or S is a maximally connected subset of C}. This constraint has at most 2|C| constraints and dominates the operator landmark set constraint.To get a better understanding of c tlm-set(C) , let us first consider how a transition-counting LP combines the constraints c tlm(C) for C ∈ C. A known result for operator counting states that combining operator-counting constraints in an operator-counting LP is equivalent to optimal operator cost partitioning over heuristics that each consider one constraint individually (Pommerening et al. 2015) . This result generalizes to transition cost partitioning (Keller et al. 2016 ) in a straightforward way.Let C∈C cost C ≤ cost be the transition cost partition computed by this combination. Assigning different costs to two transitions t 1 , t 2 ∈ C can never be useful, as the cheapest way of satisfying a single cut is to use its cheapest transition. Assigning negative costs to a transition also cannot be useful as there is no upper limit how often a transition within a cut can be used. Assigning negative costs would make the heuristic value for this cut arbitrarily low, so it cannot be part of an optimal cost partition. Finally, assigning non-zero costs cost C (t) > 0 for some transition t / ∈ C can never be beneficial. We can thus limit attention to cost functions cost C defined ascost C (t) = α C if t ∈ C 0 otherwise for some α C ≥ 0.The operator-counting constraint c tlm-set(C) also contains the linking constraint in addition to the constraints discussed above. In the context of cost partitioning, it has the effect of restricting the transition cost functions to the operator cost function of the planning task. In our case, this requires thatcost(o) ≥ max t∈T label(t)=o cost(t) ≥ max t∈T label(t)=o C∈C cost C (t) = max t∈T label(t)=o C∈C t∈C α cIn the proof of Proposition 7 we saw that c tlm-set(C) is equivalent to {c cutcost(C,α) | α ≥ 0}. This is true even for overlapping cuts and the argument above gives an intuition on why this is the case: vectors α correspond to non-negative transition cost partitions over the cuts, and the coefficients of variables Y o correspond to cost functions that are just high enough to guarantee admissibility.So far, we assumed a set of cuts C was given. We now show one method to extract C from a transition system. The intention is to use sufficiently small abstractions but the method works on any transition system.The number of all possible cuts grows exponentially in the number of states, which quickly becomes prohibitive even in small transition systems, so we focus on generating informative cuts that cover different parts of the transition system. Cuts having large overlaps are more likely to be satisfied with a small set of transitions. Likewise, cuts that contain both cheap and expensive transitions are more likely to be satisfied by a cheap transition, wasting the cost of the more expensive ones. We thus prefer cuts that only overlap in expensive transitions.Our method is an adaption of LM-Cut (Helmert and Domshlak 2009) , where cuts in a justification graph are found as the boundary to an incrementally increasing goal zone. One difference is that in LM-Cut the justification graph can change from one iteration to the next, whereas in our case the transition system remains stable. Also, our algorithm tracks costs of individual transitions where LM-cut uses operator cost functions. Given a transition system T = ⟨S, O, T, I, G, cost⟩, we maintain a goal zone Z ⊆ S and a cost function rem that tracks the remaining costs of all transitions. These are initialized to Z = G and rem = cost. We then generate cuts by iterating the following loop until termination: 1. Add states to Z from which any state in Z can be reached on a 0-cost path under cost function rem. 
 
 Appendix:  


Decision: The authors introduce the notion of transition-counting constraints for the operator counting framework. Computing them exactly can be prohibitively expensive, thus the authors devise approximation methods and compare them.

This is a strong paper that is well suited for ICAPS.

Reviews: review: strength_weakness: strength_weakness: The paper is well written and explained. However, there are a couple of things that I found confusing:

* The explanation of exact label reduction in the background without providing any reference, as this differs from the usual definition in the context of M&S abstractions. As far as I know, exact label reduction was introduced by Sievers et al. in "Generalized Label Reduction for Merge-and-Shrink Heuristics", AAAI'14. A thorough description is provided in the journal article "Merge-and-Shrink: A Compositional Theory of Transformations of Factored Transition Systems", JAIR 2021. As far as I know the term "exact label reduction" has not been used in other abstractions.
The key difference is that label reduction in the context of M&S may map operators to the same label if this does not add any additional transition, when considering the product with other transition systems. In the context of a single abstract transition system, all operators with the same cost could be reduced to the same label.

The definition in this paper is clear. But I'd use a different name or at least clarify that this differs from the definition used in M&S abstractions.

* In the experiments, I found it hard to understand what configurations correspond to previous work and which ones are new. If I understood correctly, the atomic variant is just the standard operator counting constraints, used in previous work.

* I am also missing some additional configurations from the related work, such as (saturated) post-hoc optimization and/or other work from the operator-counting framework (e.g. how far are the resulting heuristics from the nnOCP configuration in terms of expansions?)


Minor comments:
- Line 44: ‘planning task’ -> ‘planning tasks’.
- Line 69: ‘.Let’ -> ‘. Let’.
- Line 80: $\lambda^{-1}$ not defined.
- Line 265: $c^{tlm}$ constraints: $Y{t_1} + Y{t_2} \ge 1$ (2 instead of 3), $Y{t_3} + Y{t_4} \ge 1$ (3 instead of 2).
- Figure 3: why the disjoint variant does not find the dashed cut should be better explained.
- Line 354: two cuts C1, C2 are share -> remove are
- Line 493: missing final dot.
- Line 595: yields -> yield
questions: questions: 1) Is any of the configurations used equivalent to the operator-counting constraints without considering transition cuts?
2) Is any of the configurations used equivalent to the post-hoc optimization constraints without considering transition cuts?
strength_weakness: strength_weakness: - The experimental comparison appears to be 'internal' only, as it compares the variants discussed in the paper.  Having an 'external' validation w.r.t. state of the art would be useful to provide evidence for the potential computational benefits.
questions: questions: - "To avoid the prohibitive number of auxiliary variables,
we consider projections to operator-counting variables" -> Can you clarify that these approaches are still based on the new transition cuts, i.e., the projection to operator counting variables can still be stronger than the traditional operator-only based cuts?

- A related question: Can you clarify that as a result the experimental evaluation does not contain a baseline comparison with operator-only based cuts?

- Can you give a bit more insight on the computational bottlenecks, in particular, as it relates to the LP/IP solving times?
strength_weakness: strength_weakness: I did not find any error in the reasoning, but there are some technical flaws
that need to be addressed for CR:

Inverse of label reduction \lambda (\lambda^{-1}) is not introduced (it is,
strictly speaking, not an inverse function, but rather mapping from labels to
sets of labels s.t. \lambda^{-1}(l) = {l' \mid \lambda(l') = l}).

First, it is stated that details of planning task encoding is not important
(first paragraph of Background), but later projections are discussed. The result
is that the definition of projections refers to variables that are not defined
at all. So, at least encoding of states should be introduced in the background.

The text should explicitly distinguish between a solution of the LP (i.e.,
constraints + the optimization criteria) and what is called "feasible solution"
throughout the text. At first I was confused and it was hard to follow the text
before I realized that what is meant by "feasible solution" is simply a variable
assignment satisfying all constraints. This really should be made prominent in
the text because the whole explanation is based on distinguishing the two -- in
the end, we minimize some criteria of the LP to get admissible estimates, but we
construct constraints so that it is satisfied by every plan.

The text does not distinguish between a constraint, set of constraints or set of
sets of constraints. The definition (Def. 1) says that a constraint is a set of
linear inequalities, but almost all propositions mix together constraints and
sets of constraints (and maybe even sets of sets -- I lost track). Please, fix the
notation in this regard, it is just a matter of choosing the correct notation.
For example, Prop. says {c,c'} is a constraint where c and c' are also
constraints -- just replace {c,c'} with c \cup c'. Or in other places there is
{c | ... } which can simply be replaced with \bigcup_{...}c and so on.

First sentence below Proposition 1:
What does it mean that a constraint "is in terms of the original operators"?

Sol_{IP} is never introduced, only Sol_{LP} is defined. Moreover, Sol_{LP} is
not a good definition, because it says Y and Z are variables, and then there is
Sol_{LP} = {Y \in R^n \mid \exists Z \in R^m ...} -- so, strictly speaking, Y
and Z suddenly become tuples of reals. Moreover, as per definition, Y and Z
become completely disconnected from the Y and Z from the assumption (the
definition says "Let .. Y ... Z" so Y and Z are fixed for Sol_LP(c), but
suddenly we use them to iterate over tuples of numbers). Please, fix this.
I wouldn't mind if you were less formal and simply state that Sol_{LP} is a set
of all variable assignments to operator-counting variables such that there
exists a variable assignment to auxiliary variables that together satisfy c (or
something along those lines). I would, however, object to using formalism that
simply is not correct.

Last paragraph of "Comparing Operator-Counting Constraints": It is not clear
what is meant by "can be extended to integer-valued solution". Extended how?
Isn't it simply that every integer-valued solution to LP is also a solution to IP?

Caption of Fig. 2 says that it shows TS with two cuts: TS has four cuts, but the
figure is explicitly marking just two -- please, just make the text more
accurate.

In several places, propositions say "X can be stronger/weaker". This is not very
accurate formal statement -- what is meant by it is that there exist a task with
X and Y in it such that X is stronger/weaker than Y. Either move these claims
out of propositions into text or make them more accurate mathematical statements. In
either case, please, explain better what exactly is meant by it because it is
not entirely clear (this is not just nit-picking, the propositions assume a
fixed task, so it might be confusing what these parts of the claims actually
mean).



Typos:
Background, Landmarks paragraph: "brevity.Let" --> missing space between "." and "Let"

page 5, left column in the middle: "two counts C_1,C_2 *are share* an operator"  --> remove "are"
questions: questions: Feel free to address anything in my review. In particular, indicate whether
you're willing to fix the technical flaws I pointed out (or refute them if you
think I'm reading it wrong).

=== POST-REBUTTAL ===
Thank you for answers and clarifications.
Please update the paper for CR (assuming the paper is accepted) as you describe. In particular, regarding Def. 4 and the issue raised by the reviewer w1i6 regarding label reduction.