Decoupled Search for the Masses: A Novel Task Transformation for Classical Planning

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-06 19:28:59

Abstract: Automated problem reformulation is a common technique in classical planning to identify and exploit problem structures. Decoupled search is an approach that automatically decomposes planning tasks based on their causal structure, often significantly reducing the search effort. However, its broad applicability is limited by the need for specialized algorithms. In this paper, we present an approach that embodies decoupled search for non-optimal planning through a novel task transformation. Specifically, given a task and a decomposition, we create a transformed task such that the state space of the transformed task is isomorphic to that of decoupled search on the original task. This eliminates the need for specialized algorithms and allows the use of various planning technology in the decoupled-search framework. Empirical evaluation shows that our method is empirically competitive with specialized decoupled algorithms and favorable to other related problem reformulation techniques.

Main paper: 
 t: 
 F contains a transition s D o G --→ t D ∈ T F whenever o G ∈ O G and s D , t D ∈ S F such that: (a) s D * |= pre(o G ), (b) center(t D ) = center(s D ) o G , and (c) leaves(t D ) = {s L o G | s L ∈ leaves * (s D ), pre(o G )[L] ⊆ s L }. 4. I F = ⟨I[C], {I[L] | L ∈ L}⟩ is the initial state. 5. S F G = {s D ∈ S F | s D * |= G}is the set of goal states. Example 3. Consider our running example with the factoring F = F t . Part of the decoupled state space is illustrated in Figure 2 . In the unsaturated initial state I F and its saturated counterpart I F * , the single center variable t has the value l 1 . In I F , each leaf has a single leaf state, (p 1 , l 1 ) and (p 2 , l 1 ), indicating the initial location l 1 of both packages. In the saturated initial state I F * ,I F : t = l 1 l 1 l 2 t p 1 1 0 0 p 2 1 0 0 I F * : t = l 1 l 1 l 2 t p 1 1 0 1 p 2 1 0 1 saturate s D : t = l 2 l 1 l 2 t p 1 1 0 1 p 2 1 0 1 s D * : t = l 2 l 1 l 2 t p 1 1 1 1 p 2 1 1 1 saturate drive(l 1 , l 2 )Figure 2 : Illustration of the decoupled state space needed to determine a decoupled plan for the running example.we have a total of four leaf states, namely leaves * (I F ) = {(p 1 , l 1 ), (p 1 , t), (p 2 , l 1 ), (p 2 , t)}. This is due to the applicability of leaf-only operators load(l 1 , p i ) for both packages. Since I F * ̸ ∈ S F G , we proceed by applying the only applicable global operator, drive(l 1 , l 2 ), resulting in the unsaturated decoupled state s D . Here, the center variable is updated, while the reached leaf states remain unchanged, since they satisfy the preconditions of the operator and are not affected by it. The saturated decoupled state s D * matches the goal condition due to the unload leaf-only operators, giving us a decoupled plan: ⟨drive(l 1 , l 2 )⟩.We remark that a decoupled plan -a sequence of labels representing a path from an initial state to a goal state in the decoupled state-space -is not a plan in the original task because it considers only global operators and ignores the leaf-only ones. However, it is efficiently possible to construct a plan for the original task from the decoupled plan by scheduling leaf-only operators along the global ones. In this work we focus on finding decoupled plans, and simply adopt the existing method of plan reconstruction as a postprocessing step. For details of this procedure, refer the interested reader to the literature (Gnad and Hoffmann 2018) .In this section, we first formalize and exemplify our novel task transformation that generates a FDR task by decoupling a SAS + planning task based on a given factoring. We prove the correctness of our transformation by showing that the search space of the resulting FDR task is isomorphic to that of decoupled search on the original task. We then derive optimizations to the vanilla encoding that utilize specific causal relationships between factors. Finally, within our new framework, we demonstrate that the approach by Miura and Fukunaga (2017) represents a special form of decoupled search by task transformation. We conclude by showing that our approach generalizes it in multiple dimensions.We define a task transformation called dec that transforms a given SAS + planning task into a decoupled FDR planning task given a factoring F. Definition 11 (Decoupled Transformation). Let Π = ⟨V, I, G, O⟩ be SAS + planning task and F = ⟨C, L⟩ be a factoring for Π. We define the decoupled transformation dec as a function that produces a new FDR planningtask dec(Π, F) = ⟨V dec , D dec , I dec , G dec , O dec , A dec ⟩.The components of this task are detailed below, and together they form the new planning task called Π dec F . The basic concept behind the task transformation is to em-340 bed the leaf state space into the background theory represented by the axioms of the FDR task. The key idea is that an unextended state in Π dec F corresponds to an unsaturated decoupled state for Π, while an extended state corresponds to a saturated decoupled state. Leaf-only operators, essential 345 for saturating decoupled states, are transformed into axioms.Primary variables. We define a set of primary variables V dec that consists of the center variables C with their original domain and a binary variable v s L for every leaf state s L ∈ S L . Intuitively, the primary variables describe an un-350 saturated decoupled state, where the center state is represented by the center variables as in decoupled search and the v s L variables represent the reached leaf states after the application of a global operator.V dec = C ∪ {v s L | s L ∈ S L } with D v s L = {0, 1}Secondary variables. The secondary variables D dec con-355 sist of three main components. First, we have a derived predicate d s L for each leaf state. These variables, along with the center primary variables, are used to represent a saturated decoupled state. Second, for each leaf, we have a derived variable to encode whether we have reached a leaf state that 360 satisfies G[L]. Third, similar to the goal condition, for each global operator o and leaf L, we have a derived variable used to encode whether we have reached a leaf state s L ∈ S L , satisfying the precondition pre(o)[L] ⊆ s L . D dec = {d s L | s L ∈ S L } ∪ {d G[L] | L ∈ L, G[L] ̸ = ∅} ∪ {d pre(o)[L] | L ∈ L, o ∈ O G , pre(o)[L] ̸ = ∅}I dec = I[C] ∪ {v I[L] | L ∈ L} G dec = G[C] ∪ {d G[L] | L ∈ L, d G[L] ̸ = ∅} Operators. Each operator o dec ∈ O dec in Π dec F corre- sponds to a global operator o ∈ O G in the original task Π. O dec = {o dec | o ∈ O G }For an operator o dec ∈ O dec , the preconditions and effects on the center variables remain the same as for o. Ad-375 ditionally, we replace the preconditions on the leaf variables in pre(o) with a derived variable d pre(o) [L] for each leaf L.pre(o dec ) = pre(o)[C] ∪ {d pre(o)[L] | L ∈ L, pre(o)[L] ̸ = ∅} eff (o dec ) = eff (o)[C]We use conditional effects to handle the variables that encode reached leaf states. The underlying concept is that these conditional effects copy the reached leaf states from the previous states to the new one, provided that they match the applied global operator. The first set of conditional effects denotes that a decoupled state t L is reached in the successor state if a state s L exists such that t L = s L o . These effect conditions are on the derived variables d s L , since they correspond to the saturated decoupled state, while the actual effect is on the primary variable v t L , which represents the unsaturated successor state. The second set of conditional effects encode that a leaf state t L becomes false if there is no leaf state s L reached such that t L = s L o . The latter is 390 necessary because of the closed-world assumption in classical planning, which ensures that primary variables retain their values if they are not affected by an operator.ceff (o dec ) = {(d s L ▷ v t L ) | L ∈ L, t L ∈ S L , d s L ∈ 1 o t L } ∪ {(0 o t L ▷ ¬v t L ) | L ∈ L, t L ∈ S L } with x o t L = {(d s L , x) | s L ∈ preimg(t L , o)}Axioms. The axioms form the final component of Π dec F , which consists of four subcomponents for each leaf L ∈ L.395 A dec = L∈L (A L frame ∪ A L pre ∪ A L G ∪ A O L ̸ C )After applying a global operator, all derived variable values are reset to false. Thus, the first set of axioms A L frame is concerned with restoring the previously reached leaf states, which are stored in the v s L variables and set accordingly by the conditional effects of the operators O dec . More precisely, 400 the value of d s L becomes true if v s L is true.A L frame = {d s L ← v s L | s L ∈ S L }The second and third sets of axioms are used to determine whether a leaf state s L satisfies the goal condition or the precondition of an operator. A L G = {d G[L] ← d s L | d G[L] ∈ D dec , s L ∈S L , G[L] ⊆ s L } A L pre = {d pre(o)[L] ← d s L | d pre(o)[L] ∈ D dec , s L ∈ S L , pre(o)[L] ⊆ s L } The fourthA O L ̸ C = {d t L ← d s L ∪ pre(o)[C] | t L ∈ S L , o ∈ O L ̸ C s L ∈ preimg(t L , o)}We next show that Π dec F is a well-formed FDR task (full proof is given in the Appendix). Lemma 1. Let Π be a SAS + planning task and F be a factoring for Π. Then Π dec F is a well-formed FDR planning task.A(I dec ):I dec : t = l 1 v { * } Val (p 1 , l 1 ) 1 (p 1 , l 2 ) 0 (p 1 , t) 0 (p 2 , l 1 ) 1 (p 2 , l 2 ) 0 (p 2 , t) 0 d { * } Val (p 1 , l 1 ) 1 (p 1 , l 2 ) 0 (p 1 , t) 1 (p 2 , l 1 ) 1 (p 2 , l 2 ) 0 (p 2 , t) 1 extend A(s): s: t = l 2 v { * } Val (p 1 , l 1 ) 1 (p 1 , l 2 ) 0 (p 1 , t) 1 (p 2 , l 1 ) 1 (p 2 , l 2 ) 0 (p 2 , t) 1 d { * } Val (p 1 , l 1 ) 1 (p 1 , l 2 ) 1 (p 1 , t) 1 (p 2 , l 1 ) 1 (p 2 , l 2 ) 1 (p 2 , t) 1 extend drive(l 1 , l 2 )Figure 3 : Illustration of the state space of the transformed task Π dec F needed to determine a decoupled plan for the running example.Proof sketch. Initial state, goal, preconditions, and unconditional effects are consistent by construction. Further, the conditional effects do not assign conflicting values to the same variable. Finally, a single axiom layer forms a valid stratification, since no secondary variable appears in any axiom body condition with the default value of 0.Example 4. Consider the running example with factoring F = F t . Figure 3 illustrates parts of the state space of Π dec F . The primary variables include the center variable t and a variable v s L for each leaf state s L . The secondary variables include a variable d s L for each leaf state, and variables indicating whether the global operator preconditions or the goal condition are satisfied. The two global operators drive, which also form the set O dec , lack preconditions on leaf variables. Thus, there are no secondary variables for the preconditions, there are no A L pre -axioms, and the conditional effects for both operators simply write the values from the secondary variables d s L to the primary variables v s L . The goal G dec = d {(p1,l2)} ∧d {(p2,l2)} refers to the leaf variables p 1 and p 2 . Since we have single variables in the leaves, it follows that d G[Li] = d {(li,l2)} . These variables already exist as they represent leaf states. As a result, the A L G -axioms are trivial: d {(li,l2)} ← d {(li,l2)} . Note that this is not always true, e.g., if both packages were in the same leaf. The transformed task concludes with the frame axioms, which copy values from v s L to d s L variables, and the leaf-only operator axioms, representing load (d (pi,t) ← (p i , l j ) ∧ (t, l j )) and unload operators (d (pi,lj ) ← (p i , t) ∧ (t, l j )).Figure 3 shows the initial state I dec and its extension, A(I dec ), where the truck and both packages are at l 1 . In A(I dec ), we can infer that the packages can be at l 1 or in the truck. After applying the only applicable operator, we find a goal state s that yields the plan ⟨drive(l 1 , l 2 )⟩.To establish the relationship between the decoupled search space Θ D (Π, F) and the state space of the transformed planning task Θ(Π dec F ), we construct a function that maps between these two transition systems.Definition 12 (Mapping Function). Let Π be a SAS + planning task, F be a factoring for Π, S F be the states of Θ D (Π, F), and S dec be the states of Θ(Π dec F ). We define the function φ : S F → S dec as φ(s D ) = s such that s[C] = center(s D ) and s(v s L ) = 1 if s L ∈ leaves(s D ) and s(v s L ) = 0 otherwise.Intuitively, function φ establishes a one-to-one correspondence between decoupled states s D in Θ D (Π, F) and states 460 s of Π dec F . Two states s D and s are mapped to each other iff they match in the center variables, and a leaf state s L is reached in s D iff v s L is true in s. For example, φ(I F ) = I dec and φ(s D ) = s in our running examples as can be seen in Figures 2 and 3 .It is also convenient to establish a relation between a saturated decoupled state and the corresponding extended state of Π dec F . Lemma 2 shows that the saturation of a decoupled state s D and the extension of the corresponding state φ(s D ) are equivalent. This equivalence is proved by infer-470 ring the reachability of the leaf states in s D * , symbolized by leaves * (s D ), and in A(φ(s D )), denoted by the variables d s L (proof is given in the Appendix). Illustrative examples of this equivalence can be observed in Figures 2 and 3 , exemplified by I F and I dec , as well as s D and s.Lemma 2. Let s D ∈ S F be a decoupled state ands L ∈ S L a leaf state. Then s L ∈ leaves * (s D ) iff A(φ(s D ))(d s L ) = 1.Finally, we show that the decoupled search space and the state space of the transformed planning task are isomorphic. This implies that search algorithms applied to the transformed planning task will behave identically to their specialized counterparts designed for decoupled search. For the detailed proof, we refer the reader to the Appendix. Theorem 1. Let Π = ⟨V, I, G, O⟩ be a SAS + planning task and F be a factoring for Π. Then the FDR state space of 485 Π dec F and the decoupled state space of Π are isomorphic, i.e., Θ(Π dec F ) ∼ Θ D (Π, F).Proof sketch. Let Θ D (Π, F) = ⟨S F , O G , T F , I F , S F G ⟩ and Θ(Π dec F ) = ⟨S dec , O dec , T dec , I dec , S dec G ⟩.Function φ is bijective since it establishes a one-to-one mapping between the different state sets. Furthermore, it holds that 1.φ(I F ) = I dec , 2. s D ∈ S F G iff φ(s D ) ∈ S dec G , and 3. s D o -→ t D ∈ T F iff φ(s D ) o dec --→ φ(t D ) ∈ T dec .In the introduced task transformation, every global operator and every leaf is treated in the same way, regardless of the underlying structure. This results in an encoding that can contain many conditional effects to represent the semantics of the reached leaf states. However, we can exploit the fact that certain global operators have varying and sometimes no 500 influence on the reachability of leaf states for a particular leaf. This insight will help to derive a more compact encoding of the effects of global operators on leaves. Definition 13 (Irrelevant Operator). For a SAS + task Π and a factoringF = ⟨C, L⟩, a global operator o G ∈ O G 505 is L-irrelevant for a leaf L ∈ L iff both of the following conditions hold: (1) V (o G ) ∩ L = ∅, and (2) V (o G ) ∩ V (pre(o L )) = ∅ for all leaf-only operators o L ∈ O L ̸ C .Intuitively, applying an L-irrelevant global operator o G does not affect the reachability within a leaf L in any way. Consequently, there's no need to transfer the inferred values from d s L to v s L for the successor state, since these values can be inferred again from the unchanged v s L variables. This shows that we can omit conditional effects on leaves L for which an operator is considered L-irrelevant.Next, we introduce the concept of conclusive operators and conclusive leaves. Definition 14 (Conclusive Operator). For a SAS + planning task Π and a factoringF = ⟨C, L⟩, a global operator o G ∈ O G is L-conclusive for a leaf L ∈ L iff V (o G ) ∩ L = L.Definition 15 (Conclusive Leaf). For a SAS + planning task Π and a factoringF = ⟨C, L⟩, a leaf L ∈ L is conclusive iff it holds that each global operator o G ∈ O G is either L- conclusive or L-irrelevant.The idea behind Definition 14 is that after applying an L-conclusive global operator, exactly one leaf state s L ∈ S L is reached, since all variables L are conclusively fixed by the operator effect or precondition. With that, for an Lconclusive leaf (Definition 15), the application of a global operator will either uniquely fix all variable values of L or not affect the reachability within L. As initially only a single leaf state is reached in each leaf, this eliminates the need for a separate variable v s L for each leaf state within a conclusive leaf L. A single leaf state is sufficient to infer the reachable leaf states of L at any point, hence we can represent this state in a factored way using the original primary variables of L and adapt A L frame to refer to these in the body. Finally, for global operators o G ∈ O G that have no preconditions and effects on a leaf L, along any transitions D o G --→ t D if s L ∈ leaves(s D ) then s L ∈ leaves(t D ). We can exploit this by dropping the conditional effects of o G that make any variable v s L false. Example 5. Consider our running example with F t . Here, the drive operators are neither conclusive nor irrelevant to the two leaves. The leaf variables are not mentioned in the operators, but the position of the truck t, which is affected by these operators, appears in the preconditions of the leafonly operators. However, both leaves {p 1 } and {p 2 } are fork leaves, so the global drive operators have no precondition or effect on the leaves. Thus, we can omit the conditional effects for those operators that make the v s L variables false. Now let us reconsider the example with an additional truck and a factoring similar to F p , where the two packages are the center, and the two trucks form individual leaves. When a global load operator is applied to load a package onto truck t 1 , its influence is only on the reachability of leaf {t 1 }, by requiring that the truck be positioned at the same location as the package. So this operator is {t 1 }-conclusive and {t 2 }-irrelevant. Thus, for this particular operator, there is no need to encode the conditional effect associated with the {t 2 } leaf. Finally, all leaves are actually conclusive, since all load and unload operators are either irrelevant or conclusive for each leaf. Miura and Fukunaga (2017) describe methods to transform a given planning task into a more concise representation by introducing derived predicates and axioms. They propose two methods, one based on mutexes, which we will not discuss further as it is orthogonal to our work, and a method called τ -axiom extraction that identifies operators with specific properties. This method turns these operators into axioms and casts their effect variables into derived variables. More precisely, their approach searches for a cardinality maximal set of variables L ⊆ V, where each operator o either affects only variables of L, i. e., V (eff (o)) ⊆ L, and is then transformed into axioms, or determines all values of L, i. e., L ⊆ V (pre(o)), and remains an operator. A closer look reveals that this is equivalent to searching for a set of global operators that are L-conclusive for a single leaf.Overall, this means that the approach introduced by Miura and Fukunaga ( 2017) is a special case of our decoupled task transformation. The approach presented in this paper extends their concept in several dimensions, embodying decoupled search in its full generality: allowing arbitrary and multiple leaves instead of a single conclusive one, and allowing arbitrary global operators instead of supporting exclusively conclusive ones.We implemented our decoupled task transformation in the Fast Downward 23.06 framework (FD) (Helmert 2006) . Our experiments were conducted on a cluster of Intel Xeon Gold 6130 CPUs using Downward Lab 8.0 (Seipp et al. 2017) , with runtime and memory limits of 30 min and 8 GiB, on all 2106 STRIPS instances from the satisficing sequential tracks of the International Planning Competitions 1998-2023. Our code and experimental data are available online. 3 We extended FD's task transformation interface for our own transformation, such that we can (1) run a search directly on the transformed task, or (2) write the transformed task to disk in (grounded) PDDL or FD's own * .sas format. To reconstruct full plans from the obtained globaloperator sequences, we integrated the solution reconstruction of the decoupled-search planner of Gnad and Hoffmann (2018) . In the following, we evaluate our approach by performing search directly on the transformed task with two different configurations: lazy greedy best-first search (GBFS) with the h FF heuristic (Hoffmann and Nebel 2001) and a dual-queue open list with preferred operators (PO) (Richter and Helmert 2009) , and the first iteration of LAMA (Richter and Westphal 2010) . We always use an operator cost of one and impose the 30-min runtime limit on the entire process, i. e., transformation and search.We compare our decoupled task representation with the outlined optimizations (dec) to the original SAS + encoding of FD (sas). To see the effect of the optimizations, we also show data for the non-optimized basic transformation (dec ̸ o ). Furthermore, we compare to the native decoupledsearch implementation of Gnad and Hoffmann (2018) (gh) , and the transformation by Miura and Fukunaga (2017) (mf ) . For the latter we reimplemented their variable-based axiom 3 Link removed to ensure anonymous submission. As factoring strategy for our transformation and native 625 decoupled search, we pick the best configuration reported by Gnad, Torralba, and Fišer (2022) for satisficing planning, called F20s, giving it a time limit of 30s. As a minor modification, we restrict the set of potential leaf factors to variable sets with domain-size product smaller than one million. The 630 original strategy uses 2 32 as limit, but we observed that too large leaf factors incur a significant overhead in our transformation. We say that the strategy is successful if it terminates in the limits and results in a factoring with at least two leaf factors. Otherwise, like prior work on decoupled search, we 635 abstain from solving the task, assuming that a linear searchspace reduction does not usually pay off. We use the IBM CPLEX solver in version 12.10 to compute the factorings. 4Transformation statistics. Table 1 shows runtime statistics of our transformation. When the factoring is success-640 ful, the transformation takes negligible time in most cases, finishing in less than 10 seconds for 97% of the instances. The maximum runtime is 600 seconds. There are only 4 instances in which the transformation runs out of time or memory. In Figure 4 we analyze the task sizes under the transfor-645 mation. The size of a task is measured as the encoding size in the same way as this is done by FD's translator component (Helmert 2009) . The left plot compares the original encoding to the optimized decoupled task. As expected, the transformation can lead to a significant increase in the encoding 650 size, up to more than four orders of magnitude. The majority of instances only sees a moderate increase of up to a factor of 10, though. The right plot shows that our optimizations are indeed effective in reducing the encoding size, yielding savings of almost four orders of magnitude. We highlight 655 the ratio of conclusive leaves over the total number of leaves in different colors/shapes. This nicely illustrates that if most leaves are conclusive then the transformed task is usually only larger by a constant factor than the original task. That is because our optimizations effectively reduce the encoding 660 size in that case, as seen in the right plot.Planning performance. Considering the factoring that embodies the mf approach, we can observe that it is not applicable in the vast majority of instances due to the restriction to a single conclusive leaf. On our benchmark set, the 665 mf approach is effective on 311 instances, of which 271 are solved with GBFS and h FF , respectively 307 with LAMA. The sas baseline solves 269, respectively 307 instances as well on that instance set, so performs very similarly in terms of coverage. Runtime-wise, we see a maximum speed-up factor of 337; in terms of arithmetic/geometric mean mf is faster than sas by a factor of 2.18/1.03. However, it turns out that some strategies reported in Gnad, Torralba, and Fišer (2022) result in factorings that outperform mf when a single leaf factor is considered, leading to a larger reduction.Turning to the full benchmark set, Table 2 shows coverage results (number of instances solved) for all instances where F20s is successful (omitting the already discussed results for mf ). For GBFS with h FF and PO we observe a huge impact of our encoding optimizations, with +75 solved instances 680 distributed over many domains. While our transformationbased approach is generally behind the native implementation (gh), it clearly outperforms the original encoding (sas), even if that uses LAMA. Notably, our approach beats gh in two domains. Compared to the Merge-And-Shrink reformulation (ts), either of the methods outperforms the other in some domains, in total dec is ahead by 29 instances. We remark that both gh and ts would require a specialized adaptation of the landmark heuristic in LAMA, whereas our approach works out of the box. When using LAMA, our approach shows particularly good results in childsnack, floortile, and nomystery, and beats the baseline with SAS + encoding by 22 instances overall.We introduced a novel task transformations for classical 695 planning that exactly mimics the behavior of decoupled state space search, emphasizing the power of task reformulations. Our transformation works for arbitrary tasks in SAS + format, encoding the leaf dynamics of decoupled search as axioms into a FDR task. We prove the correctness of our transformation by showing that the state space of the transformed task is isomorphic to the decoupled state space when employing the same problem decomposition. This allows any search technique to be applied to the decoupled task without specific adaptation, opening up numerous possibilities for the use of decoupled search. In our evaluation, we demonstrate this using the well-known LAMA planner.While the overall search performance on the transformed task may fall slightly behind a native decoupled search implementation, we observe that it is competitive on many do-710 mains. Depending on the properties of the factoring, it occasionally even outperforms the native approach. As a result, planners of different kinds can now be "automatically decoupled" while maintaining near-native performance.For future work, we plan to further investigate approaches 715 that reduce the size of the transformed task. This could be achieved by employing the irrelevance pruning of Torralba et al. (2016) , which admissibly prunes the leaf state spaces. Another interesting question is whether it is feasible to adapt our approach to be suitable for optimal planning. If leaf op-720 erators have no costs, our current transformation ensures optimality. However, in the general scenario, tracking leafoperator costs along with derived predicates remains an open question. Finally, we are curious to see if it is possible to encode other reduction techniques like symmetry breaking 725 (Domshlak, Katz, and Shleyfman 2012) or partial-order reduction (Wehrle and Helmert 2012) as a task transformation.ified semantics(Apt, Blair, and Walker 1988; Thiébaux, 1 We assume well-formed effects, meaning that multiple conditional effects assigning different values to the same variable cannot trigger in the same state, and unconditional effects do not assign different values to variables than the conditional ones.An operator can be both a global and a leaf operator.https://www.ibm.com/analytics/cplex-optimizer 
introduction: 
 Classical planning is concerned with finding a sequence of actions that transforms the initial state of a problem into a 20 desired one. To solve planning tasks, a representation is required that allows to search for a solution within the induced state space. Both theory and practice show that the way these problems are represented has a significant impact on the performance and success rate of planning approaches.In domain-specific settings, problem reformulations can be approached in a very targeted way. Common examples include solving puzzles such as the Rubik's Cube, where the search is not over atomic actions but over macro actions (Korf 1997) . Similarly, in the design of algorithms for matrix multiplication, the search is often not in the space of arithmetic instructions, but encapsulated as a tensor decomposition (Fawzi et al. 2022; Speck et al. 2023) .It is well-known that classical planning is PSPACEcomplete in general (Bylander 1994) . Nevertheless, the representation and modeling of a problem can significantly affect practical performance due to aspects like accidental complexity (Haslum 2007) . Thus, problem reformulation is very relevant also in domain-independent planning with the underlying idea of exploiting the inherent struc-40 ture of the planning problem. Reformulation can yield an alternative state space that may differ significantly in size and structure from the original one, while at the same time facilitating search. An example of this is the merge-andshrink task reformulation, which was designed to search in factored transition systems (Torralba and Sievers 2019) . In this work we show that decoupled state-space search, which is based on an alternative state representation, similar to binary decision diagrams (Bryant 1986; Torralba et al. 2017) , can also be interpreted as a task reformulation. Decoupled search automatically decomposes a planning problem into conditionally independent leaf components with a synchronizing center factor that interacts with the leaves, allowing the search to exploit this causal relationship (Gnad and Hoffmann 2018) . A major drawback of techniques like the merge-and-shrink reformulation and decoupled search is that they require specialized algorithms and implementations, because most methods are tailored to established planning formalisms. This often leads to challenges in transferring knowledge and novel techniques to these approaches.In this paper, we show that it is possible to simulate decoupled search for non-optimal planning via a task transformation within the widely supported finite-domain representation formalism (FDR) (Helmert 2009) . This alleviates the need for specialized algorithms and enables the full toolbox of planning technology in the decoupled-search framework. More precisely, we demonstrate that given a SAS + planning task (a subset of FDR) (Bäckström and Nebel 1995) , we can decompose the task as usual for decoupled search and create a FDR planning task for which the induced state space is isomorphic to that of decoupled search on the original task. Thus, a search algorithm on the transformed planning task will behave in the same way as its native decoupled search counterpart. We further show that a task reformulation by Miura and Fukunaga (2017) is closely related to our work and can be placed in the framework of decoupled search. We show that our approach generalizes it in several dimensions.Our experiments with different planning techniques demonstrate that, just as specialized decoupled-search algorithms, our task transformation performs favorably to search on the original SAS + representation and to other reformulations techniques in multiple domains. It is even competitive with a native implementation on a large number of domains. This highlights the versatility and usefulness of our approach, which embodies the idea and workings of decoupled search through a task transformation.A partial state is a consistent assignment to variables in V ∪ D. A state is a complete and consistent assignment to all variables in V, and an extended state is an assignment to all variables in V ∪ D. By S we refer to the set of all states.In the context of partial variable assignments, we sometimes denote the variable-value pair (v, x) by writing v = x, and for binary variables we also use v to denote the variablevalue pair (v, 1) and ¬v to denote (v, 0). For a partial state p we denote the subset of variables defined in p by V (p) ⊆ V ∪ D. Furthermore, we denote s[L] for a partial state s and a set of variables L ⊆ V ∪ D to represent the restriction/projection of s onto the variables L, i.e.,s[L] = {(v, x) ∈ s | v ∈ L} and s(v) = x for the assign- ment of v to x made in s.Planning operators encode the transitions between states.Definition 2 (Operators). O is a set of operators where eachoperator o ∈ O is a triplet ⟨pre(o), eff (o), ceff (o)⟩. The precondition pre(o) is a partial state over V ∪ D, the effect eff (o) is a partial state over V, and ceff (o) is a set of condi- tional effects (cond ▷ v = x), where cond is a partial state over V ∪ D, v ∈ V is a primary variable, and x ∈ D v . 1We say that an operator o ∈ O affects a variable v ∈ V if it has an effect on it, formally v ∈ V (eff (a)).Axioms serve as a means of defining a background theory that describes specific predicates based on other predicates. 120 Definition 3 (Axioms). A is a set of axioms a ∈ A of the form a = h ← b, where the head h is a value assignment of 1 to a derived variable d ∈ D, i.e, h = (d, 1) (or just h = d), and the body b is a partial state over primary and secondary variables V ∪ D.A is partitioned into layers A 1 ≺ • • • ≺ A k .The layer of an axiom is defined by the layer of its head which is determined by a partition of the set of derived variables into subsets D 1 ≺ • • • ≺ D k . We assume that this partition forms a stratification, i.e., that for all i ∈ [k], and 130 for each d i ∈ D i , it holds that (1) if d j ∈ D j appears in the body of an axiom with head d i , then j ≤ i, and (2) if d j ∈ D j appears with its default value d j = 0 (so its negation ¬d j ) in the body of an axiom with head d i , then j < i.The semantics of axioms are defined by the standard strat-Hoffmann, and Nebel 2005). Given a state s ∈ S, the values of the primary variables are preserved, while the values of the derived variables d ∈ D are set to their default value (false), i.e., ¬d. Then, a fixed-point computation is performed for each axiom layer in turn to determine the final values of the derived variables (Helmert 2009 ): For each axiom d ← b in layer A 1 , d is set to 1 if b evaluates to true. This process is repeated until no more variable changes occur. The values of the secondary variables defined in layer i are then fixed, and the computation proceeds to the next layer. Finally, the evaluated derived variables together with the state s form the unique extended state A(s).With this, we can define a planning task in finite-domain representation as follows (Helmert 2009) (v) = x for all (v, x) ∈ eff (o), t(v) = x for all (cond ▷ v = x) ∈ ceff (o)with cond ⊆ A(s), and t(v) = s(v) for all variables that do not have such effects. Similarly, we define the application of an operator to partial states p. An operator o is applicable in p if pre(o)[V (p)] ⊆ p, and the resulting state is defined asp ′ = s o [V (p)].Based on the semantics of axioms and operators, we can define the state space of a FDR task. In this paper, we focus on satisficing planning, aiming to compute any path in the state space of a given FDR planning task from the initial state I to some goal state s G ∈ S G .A SAS + planning task is a simplified version of a FDR planning task that does not include derived variables, axioms, or conditional effects (Bäckström and Nebel 1995) . Definition 6 (SAS + Planning Task). A SAS + planning task is a FDR planning task Π = ⟨V, D, I, G, O, A⟩ where D = A = ∅ and for each operatoro = ⟨pre(o), eff (o), ceff (o)⟩ ∈ O, it holds that ceff (o) = ∅.To simplify the notation, we sometimes denote a SAS + task as Π = ⟨V, I, G, O⟩, and exclude the empty components of a SAS + operator by representing it as o = ⟨pre(o), eff (o)⟩. Moreover, by V (o) = V (pre(o)) ∪ V (eff (o)), we refer to the variables in the precondition and effect of such operators. It will be convenient to use the concept of the preimage preimg(p ′ , o) of a partial state p ′ and an operator o. We define this concept as the set of predecessor partial states p such that they share the same variables (V (p) = V (p ′ )), o is applicable in p (pre(o)[V (p)] ⊆ p), and p ′ results from the application of o to p (p ′ = p o ).l 1 l 2 t p 1 p 2 p 1 p 2Figure 1 : Illustration of the initial state (solid packages) and goal (dashed packages) of the running example.In the remainder of this paper, we will use the following running example in the form of a SAS + planning task.Example 1 (Running Example). Let us consider a simple logistics scenario with two connected locations, l 1 and l 2 , along with two packages, p 1 and p 2 , and one truck t. These are represented by the variables V = {t, p 1 , p 2 }, with domains:D t = {l 1 , l 2 } and D p1 = D p2 = {l 1 , l 2 , t}.Initially, both the packages and the truck are at position l 1 , modeled as I(v) = l 1 for all v ∈ V. The goal is to transport both packages to l 2 , given as G = {(p 1 , l 2 ), (p 2 , l 2 )}. Both the initial and goal states are illustrated in Figure 1 .There are three types of operators in this example: drive operators that drive the truck between locations, load operators responsible for loading a package onto the truck, and unload operators for unloading a package from the truck. Formally, we have for any i, j ∈ {1, 2}:• drive(l i , l j ) = ⟨{(t, l i )}, {(t, l j )}⟩ with j ̸ = k 210 • load(p i , l j ) = ⟨{(t, l j ), (p i , l j )}, {(p i , t)}⟩ • unload(p i , l j ) = ⟨{(t, l j ), (p i , t)}, {(p i , l j )}⟩A possible plan is to first load the two packages into the truck, then drive the truck to l 2 , and unload both packages.In Example 1, the number of states grows exponentially as the number of packages grows. This can pose a significant challenge to modern search algorithms.Decoupled search (Gnad and Hoffmann 2018 ) is a paradigm for reformulating the state space of SAS + planning tasks. It can efficiently solve problems like Example 1 by identifying and exploiting causal structure via problem decomposition.Definition 7 (Factoring). Let Π be a SAS + planning task. A pair F = ⟨C, L⟩ with {C}, L ⊆ 2 V is termed a factoring for Π if either {C} ∪ L or L forms a partition of the set of variables V. C represents the (possibly empty) center of F, while L denotes its leaves. Let F = ⟨C, L⟩ be a factoring for Π. An operator o ∈ O is a global operator if there does not exist an L ∈ L such that V (pre(o)) ⊆ C ∪ L and V (eff (o)) ⊆ L. The set of allC := O L \O G . O L ̸ Cis the set of all leaf-only operators. A complete assignment to C or to an L ∈ L is called a center state or leaf state, respectively. S L is the set of all leaf states, and that of a particular leaf L is denoted by S L .Example 2. A natural factoring F t for the planning task outlined in Example 1 is F t = ⟨{t}, {{p 1 }, {p 2 }}⟩. Here, the truck forms the center C = {t}, while each package p i forms a leaf L i = {p i }. The operators load and unload are leaf-only operators, with preconditions concerning the truck (center) and the respective package (leaf), and effects concerning the package (leaf) only. Conversely, the truck drive operators represent global operators, with preconditions and effects that only affect the truck (center). An alternative factoring, F p = ⟨{p 1 , p 2 }, {{t}}⟩, puts the package variables into the center, while assigning the truck to a leaf. Thus, in F p , the roles of the operators are swapped, i.e., the drive operators become leaf-only operators, while the load and unload operators act as global operators. Definition 8 (Decoupled State). A decoupled state s D is a pair ⟨center(s D ), leaves(s D )⟩ where center(s D ) is a center state and leaves(s D ) ⊆ S L is a set of leaf states.In essence, a decoupled state s D represents a collection of explicit states from the original planning task Π, differing only in the variables of the leaves. A decoupled state s D satisfies a partial state p, denoted by With this, we define the decoupled state space as follows. Definition 10 (Decoupled State Space). Let Π be a SAS + planning task and F = ⟨C, L⟩ a factoring for Π. The decoupled state space is a labeled transition systems D |= p, iff (i) p[C] ⊆ center(s D ) and (ii) for every L ∈ L, there exists s L ∈ S L such that p[L] ⊆ s L and leaves(s D )(s L ) = 1. Definition 9 (Saturated Decoupled State). Let O L | s C := {o L | o L ∈ O L ̸ C ∧ pre(o L )[C] ⊆ s C }Θ D (Π, F) = ⟨S F , O G , T F , I F , S FG ⟩ where: 1. S F is the set of all decoupled states. 2. The transition labels are the global operators O G . 
 
 Appendix:  


Decision: Keeping this short: this is a clear accept. All reviewers liked the work, and we look forward to seeing it as ICAPS. Because everyone was in (positive) agreement, the paper did not attract further discussion, so I have nothing to add to the reviews. Congratulations on a very nice paper!

Reviews: review: strength_weakness: strength_weakness: These are minor remarks about the paper, please consider them for the eventual camera ready:

l.210  with j \neq i
Def. 7: Strictly speaking, a partition cannot be empty.
questions: questions: 1) Work has been done in the area of extracting macros from the inherent structure of the planning problem. Can the decoupled task reformulation be facilitated by an initial transformation of the problem, associating actions into macros? I have in mind in particular the aggregation, if necessary, of leaf-only operators and/or global operators.

2) Certain benchmarks "resist" to the approach, requiring a longer runtime. Have you analysed the reasons of that, and can you provide a way to classify planning instances in order to evaluate their degree of "decouplability"?
strength_weakness: strength_weakness: - Notations are plethoric and really hard to follow (for instance def. 9). In my opinion, many notations fall into over-formalization with indices, exponents, brackets, square brackets, parentheses, starts, \cal letters, arrows etc. Fortunately, the examples are very helpful.
questions: questions: I have no particular question for the authors. I think this is a particularly well-conducted piece of work, well positioned in relation to the bibliography, even if the results are mixed.

1 - Could you please make explicit the meaning of 1^{O}_{t^L} and 0^{O}_{t^L} (line 390)?
strength_weakness: strength_weakness: Evaluation (minor):
The optimizations were significantly important in some domains, such as transport and openstacks. Understanding why that's the case would help guide future work, such as if there's the possibility to guide the decoupled representation construction in a way that prefers conclusive leaves.

Errata:
L210: j \neq k => i \neq j
L261: There's a use of the leaves(...)(...) syntax that isn't explained or defined, but matches the prices syntax in recent decoupled search papers.
questions: questions: 1. The gain against LAMA and GBFS was highly concentrated in a few domains. Are there clear metrics from the translation which explain those results? That would be a benefit in portfolio approaches to planning.

Post-rebuttal:
Thank you for the discussion