Efficiently Computing Transitions in Cartesian Abstractions

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-06 22:38:33

Abstract: Counterexample-guided Cartesian abstraction refinement yields strong heuristics for optimal classical planning. The approach iteratively finds a new abstract solution, checks where it fails for the original task and refines the abstraction to avoid the same failure in subsequent iterations. The main bottleneck of this refinement loop is the memory needed for storing all abstract transitions. To address this issue, we introduce an algorithm that efficiently computes abstract transitions on demand. This drastically reduces the memory consumption and allows us to solve tasks during the refinement loop and during the search that were previously out of reach.

Main paper: 
 introduction: 
 The most common approach to solving classical planning tasks optimally is A * search (Hart, Nilsson, and Raphael 1968 ) with an admissible heuristic (e.g., Helmert and Domshlak 2009; Karpas and Domshlak 2009; Katz and Domshlak 2010; Pommerening et al. 2015; Sievers and Helmert 2021) . Heuristics based on abstractions of the planning task have been particularly successful. Examples for abstraction-based heuristics are, in order of increasing gen-20 erality: pattern databases (PDBs; Edelkamp 2001; Sievers, Ortlieb, and Helmert 2012) , domain abstractions (Kreft et al. 2023) , and Cartesian abstractions (Seipp and Helmert 2018) .A prominent way of generating such abstractions is counterexample-guided abstraction refinement (CEGAR) (Clarke et al. 2003) . Since the introduction of CEGAR for classical planning in the context of Cartesian abstractions (Seipp and Helmert 2013) , the method has also been adapted to PDBs (Rovner, Sievers, and Helmert 2019 ) and domain abstractions (Kreft et al. 2023 ). Furthermore, CEGAR has been used to create PDBs and Cartesian abstractions for probabilistic planning tasks (Klößner et al. 2022; Klößner, Seipp, and Steinmetz 2023) .CEGAR starts with a very coarse abstraction and then iteratively finds a cheapest abstract solution, checks where it fails for the original task and refines the abstraction to avoid the same flaw in subsequent iterations by splitting the state that caused the flaw into two new states. If CEGAR finds a solution for the original task during the refinement process, it is guaranteed to be optimal. Otherwise, the resulting abstraction can be used as a heuristic for an A * search.Since domain abstractions and especially PDBs do not allow for fine-grained refinement, it is infeasible to solve nontrivial tasks while refining these types of abstractions. Therefore, existing approaches for these abstraction types mainly create collections of abstractions focusing on different aspects of the task (e.g., Haslum et al. 2007; Pommerening, Röger, and Helmert 2013; Franco et al. 2017; Seipp 2019) .Cartesian abstractions, however, allow for fine-grained refinements since each iteration only adds one additional state. Consequently, Cartesian CEGAR is able to solve large tasks during the refinement loop. Previously, the main bottlenecks of the refinement loop in the classical planning setting were the times for finding the next cheapest solution and the next flaw in it, but these two bottlenecks have been addressed recently by incrementally revising all cheapest paths (Seipp, von Allmen, and Helmert 2020) and by finding and addressing batches of flaws (Speck and Seipp 2022) . Now, the main bottleneck of the refinement loop is the memory needed for storing the abstract transitions. It is well known that storing abstract transitions, not abstract states, is the limiting factor for abstractions. In Cartesian abstractions, the problem is especially severe since we need access to both the incoming and outgoing transitions of a state in order to efficiently rewire the transition system after a refinement step. Merge-and-shrink abstractions address the problem by using label reduction (Sievers and Helmert 2021) . PDBs and domain abstractions circumvent the issue by computing abstract transitions on demand (Rovner, Sievers, and Helmert 2019; Kreft et al. 2023 ). To do this efficiently, they use perfect hashing (Sievers, Ortlieb, and Helmert 2012 ) and the successor generator data structure (Helmert 2006) .Cartesian abstractions are too general to allow for perfect hashing. However, they are specific enough that a successor generator can efficiently compute the operators o applicable in abstract state a. To efficiently compute which abstract states b can be reached from a by applying o, we turn to the abstraction's refinement hierarchy, which records all splits during the refinement loop in a tree data structure.In our experiments, we show that computing transitions on demand drastically reduces the memory footprint and thus increases the number of tasks solved during the refinement loop. For the remaining tasks, we obtain much better heuristic estimates than before and consequently solve many additional tasks in the ensuing A * search.A SAS + planning task (Bäckström and Nebel 1995) is a tuple Π = ⟨V, O, s 0 , s ⋆ ⟩, where V = ⟨v 1 , . . . , v n ⟩ is a finite sequence of state variables, each with an associated finite domain dom(v i ). An atom is a pair ⟨v, d⟩ with v ∈ V andd ∈ dom(v). A partial state s maps a subset V(s) of V to values s[v] ∈ dom(v) for v ∈ V(s). If V(s) = V, we call s a state.The set of all states in Π is S(Π). We often treat partial states as sets of atoms. Updating partial state p with partial state q results in partial state r = p ⊕ q, with r[v] = q[v] for all v ∈ V(q), and r [v] = p[v] for all v ∈ V(p) \ V(q).(o) = pre(o)⊕eff(o). Operator o is applicable in state s if pre(o) ⊆ s and applying o in s results in state s o = s ⊕ eff(o). The cost of o is cost(o) ∈ R + 0 .The initial state s 0 is a state and the goal s ⋆ is a partial state. Solving Π optimally implies finding a cheapest iteratively-applicable sequence of operators that transforms s 0 into a state s with s ⋆ ⊆ s.A task Π induces a transition system T which is a directed, labeled graph with states S(T ) = S(Π), labelsL(T ) = O, transitions T (T ) = {s o -→ s o | o ∈ O, s ∈ S(T ), pre(o) ⊆ s}, initial state s 0 (T ) = s 0 and goal states S ⋆ (T ) = {s | s ∈ S(T ), s ⋆ ⊆ s}.An abstraction ∼ of T is an equivalence relation over S(T ) (Seipp and Helmert 2018) . It induces an abstract transition system T ′ with states S(T′ ) = {[s] ∼ | s ∈ S(T )}, labels L(T ′ ) = L(T ), transitions T (T ) = {[s] ∼ o -→ [s ′ ] ∼ | s o -→ s ′ ∈ T (T )}, initial state [s 0 ] ∼ and goal states {[s] ∼ | s ∈ S ⋆ (T )}. An abstract state is Cartesian if it has the form A 1 × . . . × A n , where A i = dom(v i , a) ⊆ dom(v i ) for all 1 ≤ i ≤ |V|. An abstraction is Cartesian if all its states are Cartesian. A partial state p induces the Cartesian set C(p) = A 1 × . . . × A n , with A i = {p[v i ]} if v i ∈ V(p) and A i = dom(v i ) otherwise.The intersection of two Cartesian sets a= A 1 × . . . × A n and b = B 1 ×. . .×B n is a∩b = (A 1 ∩B 1 )×. . .×(A n ∩B n ). The regression of Cartesian set b = B 1 × . . . × B n over operator o ∈ O is regr(b, o) = A 1 × . . . × A n with A i =        B i if v i / ∈ V(post(o)) ∅ if v i ∈ V(post(o)) and post(o)[v i ] / ∈ B i pre(o)[v i ] if v i ∈ V(pre(o)) and post(o)[v i ] ∈ B i dom(v i ) otherwise.Similarly, the progression of Cartesian seta = A 1 × . . . × A n over operator o ∈ O is progr(a, o) = B 1 ×. . .×B n with B i =    A i if v i / ∈ V(post(o)) ∅ if v i ∈ V(pre(o)) and pre(o)[v i ] / ∈ A i post(o)[v i ] otherwise.For Cartesian CEGAR, we need to efficiently obtain both the incoming and outgoing transitions of a given abstract state. 1 Traditionally, this has been done by storing all transitions explicitly and rewiring them after each refinement step. Since this approach often quickly consumes huge amounts of memory, we now present an approach that computes the transitions on demand.We begin by defining under which conditions a Cartesian abstraction contains a given transition. Proposition 1. Cartesian abstraction T ′ contains a transition from state a ∈ S(T′ ) to state b ∈ S(T ′ ) via operator o ∈ O iff a ∩ C(pre(o)) ̸ = ∅ and b ∩ progr(a, o) ̸ = ∅.Proof sketch. Seipp and Helmert (2018) define the function CHECKTRANSITION(a, o, b) for this computation (see their Algorithm 5). It returns true iff three conditions are met: 1) all precondition atoms ⟨v, d⟩ are part of dom(a, v), 2) all postcondition atoms ⟨v, d⟩ are part of dom(b, v) and 3) for all variables v not mentioned by the operator the two abstract domains dom(a, v) and dom(b, v) intersect. We can distill the three conditions into two tests that check whether two Cartesian sets intersect. From condition 1) we get a ∩ C(pre(o)) ̸ = ∅, and from conditions 2) and 3) we get b ∩ progr(a, o) ̸ = ∅.The formulation of the transition check from Proposition 1 reveals that we can divide the task of computing the outgoing transitions of an abstract state a into two steps: first we compute the set of operators o that are applicable in a, then we compute the set of abstract states b reachable from a via transitions labeled with o. We use the same two-step approach for computing incoming transitions.The set O out (a) of operators applicable in abstract state a is {o ∈ O | C(pre(o)) ∩ a ̸ = ∅}. The naive way of computing O out (a) is to iterate over O and checking each operator for applicability. We can improve over this computation by exploiting the fact that a is a Cartesian set, which allows us to feed it into the successor generator data structure, developed for efficiently enumerating all operators applicable in a given concrete state (Helmert 2006) .In its original form, the successor generator is a tree data structure, where each internal node n branches over a subset of the values d ∈ dom(n.var) of a variable n.var. Additionally, internal nodes have a child node for the "don't care" value ⊤. When querying a successor generator for a given concrete state s, at each node n we follow the "don't care" child and the child for s[n.var] if it is defined. The traversal stops at the leaf nodes, which store the sets of applicable operators. A successor generator only needs space O( o∈O |pre(o)| + eff(o)|) and querying it is usually sublinear in the number of operators, and in the best case only linear in the number of applicable operators (Sievers, Ortlieb, and Helmert 2012) .Since our abstract states are Cartesian, we can reuse the successor generator data structure with minimal adaptation.Algorithm 1 Compute all applicable operators for a given abstract state a. The recursive algorithm is called with n set to the root node of the successor generator. If we remove all mentions of outgoing state a from Proposition 1, we see that the set of operators that can reach anabstract state b is O in (b) = {o ∈ O | C(post(o)) ∩ b ̸ = ∅}.Again, the naive way of computing this set by looping over all operators can be improved upon by using the successor generator data structure. We do so by constructing a successor generator for the set of inverted operatorsO ′ = {⟨post(o), pre(o)⟩ | o ∈ O}, i.e., instead of branching over preconditions, we branch over postconditions.Now that we have a method for efficiently computing the set of outgoing operators O out (a) in a given abstract state a, we need to efficiently find the set of abstract states b that can be reached from a via an operator o ∈ O out (a). We can formalize this set byT out (a, o) = {a o -→ b | b ∈ S(T ′ ), b ∩ progr(a, o) ̸ = ∅}.The naive computation of this set loops over all states b ∈ S(T ′ ) and checks whether b overlaps with progr(a, o). Since each iteration of the refinement loop adds another abstract state, this computation will run slower and slower over time.To compute T out (a, o) efficiently, we turn to another tree data structure, the refinement hierarchy, which holds a record of all refinements (Seipp and Helmert 2018 ).2 Each Algorithm 2 Compute the set of abstract states that share at least one concrete state with Cartesian set c, starting from refinement hierarchy root node n.1: function INTERSECT(c, n) 2:if n is leaf then Proof sketch. When intersecting two Cartesian sets, we can consider each variable independently of the others. INTER-230 SECT uses this to compute the overlapping states recursively, at each node n checking for which of the children the intersection for the split variable n.var is non-empty.Even though we need to follow at least one child node at each internal node, the fact that the depth of the refine-235 ment hierarchy is bounded by the number N of atoms in Π makes INTERSECT an appealing alternative to looping over all O(2 N ) states in the abstraction.Similarly to the outgoing transitions, the transitions induced 240 by operator o that lead into state b areT in (b, o) = {a o -→ b | a ∈ S(T ′ ), a ∩ regr(b, o) ̸ = ∅}. To compute this set efficiently, we call INTERSECT(regr(b, o), n).There is a middle ground between storing all transitions and 245 storing no transitions: we can store only optimal transitions. A transitiona o -→ b is optimal iff h * T ′ (a) = cost(o)+h * T ′ (b), where h * T ′ (x)is the cost of a cheapest path from x to a goal state in S ⋆ (T ′ ). The CEGAR algorithm uses incremental search (Seipp, von Allmen, and Helmert 2020) to maintain 250 for each state a a transition a o -→ b that starts a cheapest path from a. In several places of the algorithm the incremental search only needs access to the optimal transitions, so by caching them, we can often avoid computing all transitions. Figure 1 : Time and peak memory usage for refinement loop executions that find a concrete solution. Runs that exhaust the time or memory limit appear on "fail" axes. Experiments mal sequential tracks of the International Planning Competitions 1998-2018. We limit runtime to 30 minutes and memory to 4 GiB. When the refinement loop exhausts the internal time limit of 20 minutes or tries to use more than 3.5 GiB of memory, we stop refining and use the resulting heuristic in an A * search. All benchmarks, code and experiment data are available online (Reference removed for review). We compare the previous state of the art (STORE) to five variants of our algorithms in an ablation study. Before inspecting heuristic quality, we evaluate the effects on the refinement loop, which is our main focus. Table 1 shows that if we store all transitions in memory (STORE), we solve 580 tasks during refinement, but run out of memory for the vast majority of the remaining tasks. By computing all operators and transitions naively on demand (NAIVE) we never run out of memory, but the refinement loop slows down drastically, leading to solving only 352 tasks during refinement. Using successor generators for computing operators (SG) incurs up to a ten-fold speedup for some commonly solved tasks, but this only translates to solving one extra task during refinement (353 tasks in total). In contrast, computing transitions using the refinement hierarchy (RH), while computing operators naively, leads to solving 582 tasks during refinement, a 65% increase over SG. Using the tree data structures for both computations (SGRH) leads to solving 600 tasks during refinement, while still almost never running out of memory. Finally, caching all optimal transitions (SGRHC) hits the sweet spot between memory usage and runtime and solves 637 tasks during refinement, 57 tasks more than STORE.Figure 1 compares our strongest variants, SGRH and SGRHC, to STORE in terms of runtime and memory consumption during the refinement loop. The plots visualize the time vs. memory trade-off: while SGRH is slightly slower than STORE, it uses much less memory. SGRHC uses more memory than SGRH but still less memory than STORE for most tasks. As a result, SGRH is roughly as fast as STORE.Regarding heuristic accuracy, Table 1 shows that all algorithm variants suffer from diminishing returns: solving additional tasks during the refinement becomes harder and harder and all variants benefit from switching from the refinement loop to an A * search eventually. We also see that all resulting heuristics are so fast to evaluate that runtime almost never becomes a bottleneck. Our strongest algorithm variants solve more tasks overall (up to 848 tasks) than the previous state of the art (STORE: 835 tasks). This is the case not only since more tasks are solved during refinement, but also since the resulting heuristics are more accurate. SGRHC computes a higher lower bound than STORE for 633 tasks, while the opposite is only true for 152 tasks. Also, SGRHC needs fewer expansions than STORE until the last f layer for 217 tasks, while the opposite only holds for 15 tasks.Our algorithms for efficiently computing transitions in Cartesian abstractions drastically reduce the memory usage during the refinement loop, while only slowing it down slightly. If we store all optimal transitions, we can trade a bit of memory for faster runtime and solve even more tasks.In future work, we want to evaluate whether the benefits of our algorithms for single abstractions carry over to the setting where we compute multiple Cartesian abstractions.While a plain forward search would only need outgoing transitions, it is much faster to find cheapest paths with incremental search, which requires access to both incoming and outgoing transitions(Seipp, von Allmen, andHelmert 2020).To simplify the presentation, we assume that each refinement splits off a single atom. To account for splitting off multiple atoms, our implementation uses a directed acyclic graph instead of a tree. 
 
 Appendix:  


Decision: Clear case, congratulations.

I recommend poster acceptance here as the topic seems rather specialized and of interest to a small subset of the community.

Reviews: review: strength_weakness: strength_weakness: - Although memory efficient, the proposed solution trades a bit on computation overhead. It would be interesting to have some discussion on the complexity of the solution.
questions: questions: - The paper is very well written and with detailed explanations. I do not have major questions or issues with the paper. My familiarity with abstractions for computing heuristics is low.

- Is there any scenario (say worst case in complexity) that the proposed solution might perform worse?
strength_weakness: strength_weakness: The paper presents only an incremental advance.
The number of instances solved during refinement increases significantly,
However, the overall number of solved tasks increases only slightly.

Small notes:

How dom(v_i, a) is introduced in line 117 is a little bit confusing
because "a" is only later specified as a = A_1 \times...

The use of yield in the pseudo-code was first confusing and made it harder 
to understand.
questions: questions: I have no further questions for the authors.
strength_weakness: strength_weakness: The performance gain seems to be mostly in terms of memory "only". The increase in coverage is modest. Overall the contribution is somewhat incremental.
questions: questions: (1) Can you provide some intuition why the heuristics resulting from your method are more accurate (cf., line 307)?

Typos:
296: "SGRH is roughly as fast as STORE" I believe, it should be "SGRHC"?.