Merge-and-Shrink Task Reformulation for Classical Planning

1 Introduction

Classical planning deals with the problem of finding a sequence of actions that achieve a set of goals, given a model of the world that describes an initial state and a set of available actions. For representing the problem, different planning formalisms can be used, the most common being STRIPS or finite-domain representation (FDR). The choice of formalism does not change the complexity of the problem, which is PSPACE-complete [Bylander, 1994; B¨ackstr¨om and Nebel, 1995]. However, it may impact the so-called accidental complexity, when the structure of the task is disguised by how it is encoded [Haslum, 2007]. Accidental complexity can be dealt with by reformulating the planning task prior to solving it. There are several reformulation methods based on, e.g., downward-refinable abstractions [Haslum, 2007] or tunnel macros [Coles and Coles, 2010], which can be combined to reduce the size of FDR tasks [Tozicka et al., 2016].

Merge-and-Shrink (M&S) is a general framework to generate abstractions, originally defined in the model-checking area [Dr¨ager et al., 2006; Dr¨ager et al., 2009], that can be used to derive an admissible heuristic [Helmert et al., 2007; Helmert et al., 2014] and/or detect unsolvability [Hoffmann et al., 2014]. Further work on the topic noticed that this can be understood as applying transformations to a set of transition systems [Sievers et al., 2014] and hence as a method to transform planning tasks in the factored transition system (FTS) representation [Torralba and Kissmann, 2015]. However, these methods perform the search on an FDR task, only using M&S to derive heuristics or remove irrelevant actions.

In this paper, we use M&S as a task reformulation method on FTS tasks. We show that some of the M&S transformations originally devised for constructing abstraction heuristics can also be used for optimal and satisficing reformulation. To do so, we provide algorithms that transform solutions for the reformulated task into plans for the original task. We also show that our M&S reformulations dominate their counterparts based on FDR representations, i.e., a suitable combination of existing M&S transformations can always do the same (and sometimes more) simplifications to any task.

To search on the FTS representation, planning algorithms and heuristics originally devised for STRIPS or FDR tasks must be adapted. As the FTS formalism is slightly more expressive than FDR, this is similar to adapting algorithms to support (a limited form of) disjunctive preconditions and conditional effects. We adapt heuristic search methods with M&S and delete-relaxation heuristics for the FTS representation. Our experimental study shows the potential of these reformulations to reduce the state space and speed-up the search. Full proofs and additional experimental results are included in a technical report [Torralba and Sievers, 2019].

2 Representation of Planning Tasks

A planning task is a compact representation of a TS. A transition system (TS) is a tuple Θ = 〈S, L, T, sI , S ⋆ 〉 where S is a finite set of states, L is a finite set of labels each associated with a label cost c(ℓ) ∈ R+0 , T ⊆ S × L × S is a set of transitions, sI ∈ S is the initial state, and S ⋆ ⊆ S is the set of goal states. We use s ∈ Θ to refer to states in Θ and s ℓ-→ t ∈ Θ to refer to its transitions. An s-plan for a state s is a path from s to any s∗ ∈ S ⋆ . Its cost is the summed label costs of all labels of the path. The perfect heuristic, h∗ (s), is the cost of a cheapest s-plan. An s-plan is optimal iff its cost equals h∗ (s). A plan for Π is an sI -plan.

An abstraction is a function α mapping states in Θ to a set of abstract states Sα. The abstract state space Θα is 〈Sα,L, T α, sIα, S ⋆α〉, where α(s) ℓ-→ α(s′ ) ∈ T α iff s ℓ-→ s′ in Θ, sIα = α(sI ), and S ⋆α = {α(s) | s ∈ S ⋆ }.

An FDR task is a tuple ΠV = 〈V,A, sI , G〉. V is a finite set of variables v, each with a finite domain Dv. A partial state is a function s on a subset V(s) of V, so that s(v) ∈ Dv for all v ∈ V(s); s is a state if V(s) = V. sI is the initial state and the goal G is a partial state. A is a finite set of actions. Each a ∈ A is a tuple 〈prea, eff a, c(a)〉 where prea and eff a are partial states, called its precondition and effect, and c(a) ∈ R+0 is its cost. An action a is applicable in a state s if ∀v∈V(pre a )s(v) = prea(v). Applying it yields the successor state sJaK with sJaK(v) = eff a(v) if v ∈ V(eff a) and sJaK(v) = s(v) otherwise.

The state space of an FDR task ΠV is a TS Θ = 〈S,L, T, sI , S ⋆ 〉 where S is the set of all states, sI = sI , s ∈ S ⋆ iff ∀v∈V(G)G(v) = s(v), L = A, and s a-→ sJaK ∈ T if a is applicable in s.

An FTS task is a set of TSs {Θ1, . . . , Θn} with a common set L of labels. The synchronized product Θ1⊗Θ2 of two TSs is another TS with states S = {(s1, s2) | s1 ∈ Θ1∧s2 ∈ Θ2}, labels L = L1 = L2, transitions T = {(s1, s2) ℓ-→ (s′1 s′2 ) | s1 ℓ-→ s′1 ∈ Θ1 ∧ s2 ℓ-→ s′2 ∈ Θ2}, initial state sI = (sI1 , sI2 ), and goal states S ⋆ = {(s1, s2) | s1 ∈ S ⋆ 1 ∧ s2 ∈ S ⋆ 2 }.

The state space of an FTS task ΠT = {Θ1, . . . ,Θn} is defined as Θ = Θ1 ⊗ · · · ⊗ Θk. Whenever it is not clear from context, we will use subscripts to differentiate states in the state space (s, s′ , t ∈ Θ) and in the individual components (si, s′i , ti ∈ Θi). Given s ∈ Θ, we write s[Θi] to refer to the projection of s onto Θi. A solution π for an FTS task is a sequence s0 ℓ1 -→ s1 ℓ2 -→ . . . ℓk -→ sk such that sk ∈ S ⋆ .

There is a close connection between FTS and FDR tasks, since TSs in an FTS task correspond to FDR variables with domain equal to the set of states of the TS. Then, states in FDR (which are assignments of values to variables) correspond to states in the FTS representation, which are an assignment of states si to each Θi. Given an FDR task ΠV it is simple to construct the corresponding FTS task, which we call the atomic representation of ΠV . There is a TS Θv for every variable v, with one state sv ∈ Θv per value in Dv. For every action a ∈ A, there is an outgoing transition from sv if v ̸∈ V(prea) or prea(v) = sv which leads to sv if v ̸∈ V(eff a) or tv if eff a(v) = tv.

As running example, consider a task where a truck can drive between four locations with a limited amount of fuel and with the restriction that the engine can only be turned on with a full tank. This can be encoded as an FDR task with three variables V = {vt, vf , vs} with domains Dt = {A, B, C, D}, Df = {2, 1, 0}, and Ds = {off, rd, on} that represent the position of the truck, the amount of fuel available, and the status of the engine (off, ready, on), respectively. In the atomic FTS task, shown in Fig. 1a, there are hence three TSs Θvt ,Θvf ,Θvs , one for each variable. The task has an action DRx-y,f1-f2 with precondition {vt = x, vf = f1, vs = on} and effect {vt = y, vf = f2} for every pair of connected locations (x, y), and every f1, f2 ∈ Df s.t. f2 = f1 - 1. These actions induce transitions from x to y in Θvt , from f1 to f2 in Θvf , and a self-looping transition at state on in Θvs . Furthermore, there exist actions checkfuel, CF, with precondition {vf = 2, vs = off} and effect {vs = rd} and ON with precondition {vs = rd} and effect {vs = on}. All actions have unit cost. The initial state of the FDR task is sI = {vt = A, vf = 2, vs = off} and its goal is G = {vt = D}, which translates to (A, 2, off) being the initial state (marked with incoming arrows) and all (D, ∗, ∗) being goal states (marked with double circles) of the FTS task.

Figure 1: Example FTS task where a truck must drive from A to D with a fuel capacity of 2 and the restriction to first check the fuel capacity and turn on the engine. Transitions with wildcards (*) have multiple labels, e.g., DRA-B,* stands for DRA-B,2-1 and DRA-B,1-0. Each subfigure corresponds to a reformulation (see Section 3).

The reverse transformation from an FTS to an FDR task is not as straightforward and it may require to introduce more FDR actions than there are labels in the FTS task. The reason is that transitions in the individual TSs are more expressive than the precondition-effect tuple of FDR actions because they can encode a limited form of angelic non-determinism, disjunctive preconditions, and conditional effects. Consider the task shown in Fig. 1b, an FTS task of the same planning task that uses label DR for all drive actions. Translating this task to FDR requires re-introducing multiple actions to represent DR for different pairs of locations and amounts of fuel. One reason is the non-determinism where there are multiple transitions with the same label and source state, but different targets. For example, in the state (A, 2, on), we can apply two transitions with label DR to reach either (C, 1, on) or (B, 1, on). The non-determinism is angelic because the result is chosen by the planner at will. Also, the transitions in Θvf encode a disjunctive precondition (DR is applicable for vf = 2 or vf = 1) and conditional effects (the result of DR is vf = 1 iff vf = 2 holds in the source state).

3 M&S Task Reformulation Framework

A task reformulation is a transformation of a task such that any solution for the new task can be transformed into a solution for the original task. We follow the definition of task reduction introduced by Tozicka et al. [2016] but without requiring the reformulated task to be smaller than the input task. Most of the reformulations we consider aim to reduce the size of the task, but reformulations that make the task bigger may be useful as well, e.g., if it makes the search space smaller.

Definition 1 (Task reformulation). A task reformulation ρ is a partial function from tasks to tasks s.t.:

1. ρ(Π) is solvable if and only if Π is solvable, and
2. there exists a plan reconstruction function ←-ρ that maps each solution π of ρ(Π) to a solution ←-ρ (π) of Π.

A task reformulation is polynomial if both ρ and ←-ρ can be computed in polynomial time in the size of the input task and the reconstructed plan. It is optimal if, given an optimal plan π of ρ(Π), ←-ρ (π) is an optimal plan of Π. We are interested in polynomial reformulations for optimal and satisficing planning. Note that we explicitly allow the reformulated plan to be exponentially larger than the input task. This is necessary for domains (e.g. Towers of Hanoi) where the original plan is exponentially long, but a reformulation with a solution that implicitly encodes the plan can be found in polynomial time.

3.1 Merge-and-Shrink Transformations

There are multiple M&S transformations that can be used to reformulate an FTS task ΠT = {Θ1, . . . , Θn} with labels L. A transformation is exact if it preserves the set of solutions and hence is an optimal reformulation.

Label reduction reduces the set of labels by mapping some of them to a common new one [Sievers et al., 2014]. It is exact if for any pair of labels ℓ, ℓ′ ∈ L reduced to the same label, c(ℓ) = c(ℓ′ ) and ℓ and ℓ′ induce the same transitions in all but (at most) one Θi, 1 ≤ i ≤ n. The task of Fig. 1b is the result of repeatedly applying exact label reduction on the atomic task of Fig. 1a. By itself, it does not affect the search space, but it reduces the amount of labels increasing the efficiency and effectiveness of other transformations.

Shrinking consists of replacing one TS Θi ∈ ΠT by an abstraction thereof. This results in an abstraction of the original task, possibly introducing spurious plans that do not have any counterpart in the original task. Therefore, not all shrink transformations are suitable for task reformulation. However, using refinable abstraction hierarchies is a long standing idea in planning [Sacerdoti, 1974; Bacchus and Yang, 1994; Knoblock, 1994]. We compute refinable abstractions via shrinking strategies based on bisimulation [Milner, 1971].

Definition 2 (Bisimulation). Let Θ = 〈S,L, T, sI , S ⋆ 〉 be a TS. An equivalence relation ∼ on S is a goal-respecting bisimulation iff s ∼ t implies that (a) s ∈ S ⋆ ↔ t ∈ S ⋆ , and (b) {[s′ ] | s ℓ-→ s′ ∈ T} = {[t′ ] | t ℓ-→ t′ ∈ T} for all ℓ ∈ L where [s] denotes the equivalence class of s.

Bisimulation shrinking aggregates all states in the same equivalence class of the coarsest bisimulation of some Θi ∈ ΠT . This is a symmetry-reduction technique that preserves all plans and as such is an exact transformation [Helmert et al., 2014; Sievers et al., 2015]. In our example (cf. Fig. 1b), states B and C of Θvt are bisimilar in Θvt and are hence combined into a new state BC by bisimulation shrinking (cf.

Fig. 1c). Note that shrinking B and C is only possible after label reduction, since otherwise their outgoing labels differ.

When preserving optimality is not necessary, it suffices to guarantee that any abstract plan can be refined into a real plan. Hoffmann et al. [2014] used shrinking strategies with this property for proving unsolvability with M&S. We re-define these strategies using a different nomenclature based on the notion of weak bisimulation [Milner, 1971; Milner, 1990]. The key idea is to consider τ-labels which are "internal" to a TS in the sense that they can always be taken in Θi without changing other TSs. The set of τlabels for Θi consists of those labels ℓ having a transition sj ℓ-→ sj ∀sj ∈ Θj ∀Θj, j ̸= i. Other definitions are possible; ours is more general than that of own-labels used by Hoffmann et al. [2014], whereas there are stronger notions based on dominance [Torralba, 2017; Torralba, 2018]. We use τ =⇒ to denote a (possibly empty) path using only τ -labels, and s ℓ =⇒ s′ as a shorthand for s τ =⇒ ℓ-→ τ =⇒ s′ .

Following the observation by Haslum [2007] that it suffices to focus on paths with labels that either are outside relevant (i.e., have some effect on other variables) or reach the goal, we devise a variant of weak bisimulation that ignores some irrelevant paths. We say that a label ℓ is outside relevant for a transition systemΘi if there exists some Θj with i ̸= j such that sj ℓ-→ tj for some sj ̸= tj. A path si ℓ =⇒ s′i is relevant for Θi if ℓ is outside relevant for Θi, or there does not exist si τ =⇒ s′′ i such that s′i ∼ s′′ i . Otherwise, it is safe to ignore such path in weak bisimulation because the alternative τ -path can always be used to reach s′′ instead.

Definition 3 (Weak Bisimulation). Let Θ be a TS with a set τ of τ-labels, and a set Trel of relevant paths. An equivalence relation ∼ on S is a goal-respecting weak bisimulation iff s ∼ t implies (∃s′∈S ⋆s τ =⇒ s′ ) ↔ (∃t′∈S ⋆t τ =⇒ t′ ), and ∀ℓ∈L{[s′ ] | s ℓ =⇒ s′ ∈ Trel} = {[t′ ] | t ℓ =⇒ t′ ∈ Trel }.

Weak bisimulation shrinking maps all weakly bisimilar states into the same abstract state. In our example (cf. Fig. 1b), ON is a τ-label in Θvs , therefore states rd and on of Θvs are weakly bisimilar (both have a single relevant path DR ==⇒ [on]) resulting in Θvs as shown in Fig. 1c.

Another useful abstraction transformation consists of removing TSs with a core state. We say that a state sC is a core for Θi if (1) for every outside relevant label ℓ there exists sC ℓ =⇒ sC , (2) there is a τ-path from the initial state to sC , and (3) there is a τ-path from sC to a goal state. Such a TS can be abstracted away because all outside relevant labels can always be reached via a τ -path through sC .

Merging replaces two TSs by their synchronized product. Fig. 1d shows the FTS task that results from merging Θvf and Θvs of the FTS task shown in Fig. 1c. Merging is an exact transformation [Helmert et al., 2014], which comes at the price that the size of the task grows quadratically with every merge, so it increases exponentially with the number of merges. In practice, we limit the maximum size of any TS in the reformulated task, forbidding any merge that goes beyond this limit. As label reduction, by itself merging does not change the reachable search space. However, it often enables additional label reduction, shrinking, and/or pruning. In our example of Fig. 1d, CF has become a τ -label, so 2off and 2ro could be reduced by weak bisimulation.

Finally, there are multiple pruning techniques defined in the M&S framework. If a state si is unreachable (from the initial state) or irrelevant (cannot reach a goal) in any Θi, it can be pruned [Helmert et al., 2014]. If a label ℓ is dead (i.e., there is no transition labeled with ℓ in any Θi ∈ ΠT ) or irrelevant (i.e., all transitions labeled with ℓ are self-loop transitions), then it can be pruned [Sievers et al., 2014]. If a TS Θi ∈ ΠT is the only one with a goal defined, i.e., there are no non-goal states in Θj ∈ ΠT with j ̸= i, all outgoing transitions from goal states in Θi can be removed [Hoffmann et al., 2014]. If a TS has only one state and no dead labels, it can be pruned. All these pruning techniques preserve at least one optimal plan and are therefore exact transformations.

3.2 Plan Reconstruction

M&S iteratively applies the transformations described above on a task ΠT = {Θ1, . . . ,Θk}, resulting in a sequence of reformulation steps ρ1, . . . , ρn producing a sequence of planning tasks ΠT0 , . . . ,ΠTn where ΠT0 = ΠT , and ΠTi = ρi(ΠTi-1 ) for i ∈ [1, n]. We can run any planning algorithm to find a plan πρn = sρn 1 ℓρn 1 --→ sρn 2 ℓρn 2 --→ s3, . . . of the final task ΠTn . The plan reconstruction procedure is then tasked to compute a plan π = s1 ℓ1 -→ s2 ℓ2 -→ . . . for the original task ΠT from πρn and the sequence of reformulations.

Performing a reconstruction ←- ρi for each step ρi has some overhead because it requires to store each intermediate task. We avoid this by combining sequences of reformulations that correspond to merge, label reduction, and bisimulation transformations. Pruning-based transformations can be ignored by the plan reconstruction procedure because the plan found is still valid for the original task without any modifications. Plan reconstruction can be done for the entire transformation at once without storing information about the intermediate planning tasks. Therefore, we have a sequence of transformations ΠT ρ1 -→ ΠT1 ρ2 -→ ΠT2 . . . with only two types of reformulations to consider: merging + label reduction + bisimulation shrinking (ρMLB ), and weak bisimulation shrinking (ρτB ).

We first consider the reconstruction of a reformulation ρMLB on a task ΠTi , resulting in a task ΠTi+1 . The state space of ΠTi+1 is a bisimulation of the state space of ΠTi , so any sequence s1 ℓ1 -→ s2 ℓ2 -→ . . . in ΠTi has its counterpart α(s) ℓ′1 -→ α(s2) ℓ′2 -→ . . . in ΠTi+1 and vice versa. To reconstruct the plan, we need two functions α and λ, mapping states and labels in ΠTi to states and labels in ΠTi+1 . The α function is computed by M&S heuristics and compactly represented with the so-called cascading tables or merge-and-shrink representation [Helmert et al., 2014; Helmert et al., 2015]. The label mapping is simply the composition of all label reduction transformations used by ρMLB .

The plan can be reconstructed step by step, starting from sI . Given the current factored state s and a step in the abstract plan α(s) ℓ′ -→ t′ , find a transition s ℓ-→ t such that α(t) = t′ and λ(ℓ) = ℓ′ . Note that the straightforward approach of enumerating all transitions applicable from s is not guaranteed to terminate in polynomial time because, unlike in FDR tasks where the number of successors is bounded by the number of actions, in FTS there may be exponentially many successors in the size of the task. However, one can use the cascading tables representation to retrieve a factored state t = (t1, . . . , tn) such that s ℓ-→ t, ℓ′ = λ(ℓ) and α(t) = t′ . This works as follows: First, for each transition system Θi, obtain the set S′ i of target states ti such that si ℓ-→ ti for any label ℓ such that ℓ′ = λ(ℓ). Then, traverse the cascading tables and, for each intermediate table that maps states of two transition systems Θi,Θj to an abstract TS Θγ = γ(Θi ⊗Θj), compute the set of abstract states Sγ = {sγ | ∃si∈S′i ,sj∈S′j sγ = γ((si, sj))}, mapping each sγ ∈ Sγ to one such (si, sj) pair. This allows us to keep track of one factored state for each abstract state. After all cascading tables have been traversed, it suffices to return the factored state t associated with the abstract state t′ .

Proposition 1. Label reduction, merging (up to a size limit), pruning and bisimulation shrinking are optimal and polynomial reformulations.

Proof. It is well-known that all these techniques can be computed in polynomial time [Helmert et al., 2014; Sievers et al., 2014]. Each step of the plan can be reconstructed by traversing the cascading-tables representation, which is polynomial in the size of the input task.

We now consider the reconstruction of a reformulation ρτB on a task ΠTi = {Θ1, . . . ,Θk} where ρτB applies weak bisimulation shrinking to some TS in ΠTi . We assume WLOG that Θ1 is the shrunk TS, so ΠTi+1 = {ατB (Θ1),Θ2, . . . ,Θk}. As ατB is induced by a weak bisimulation on the states of Θ1, then for any state s in ΠTi and any transition ρτB (s) ℓ-→ tρ in the reformulated task, there exists a path s ℓ =⇒ t in the original task such that ρτB (t) = tρ . Therefore, to reconstruct the plan for ΠTi from a plan for ΠTi+1 one must re-introduce the τ-label transitions until reaching a state where ℓ is applicable and this results in some t such that ρτB (t) τ =⇒ tρ . The search can be done locally in Θ1 because τ-labels have self-loop transitions in other TSs. To do so, we first look for all states u1 such that u1 ℓ-→ ( τ-→)∗ t1 in Θ1 and (ατB (t1), s[Θ2], . . . , s[Θn]) = tρ . Then, we run uniform-cost search from s[Θ1] using only transitions with τ -labels until we reach such an u1. Note that this runs in polynomial time in the size of the input task.

This procedure has similarities with red-black plan repair [Domshlak et al., 2015], the plan reconstruction of the merge values reformulation [Tozicka et al., 2016], or decoupled search [Gnad and Hoffmann, 2018]. These algorithms repair an abstract/relaxed plan by introducing additional actions to enable the preconditions ignored by the relaxed plan. Our case is slightly more complex because the same label may have multiple targets so one must ensure the remaining abstract plan is applicable in the resulting state.

If a TS Θi with a core state sC was abstracted away, its corresponding path must be reconstructed as well. For each transition in the abstract plan with label ℓ, we find the shortest si ℓ =⇒ s′i from the current state si (initialized to the initial state of Θi in the first iteration, and to the final state in the path of the previous iterations afterwards), and s′i τ =⇒ sC . Note that to keep the plan shorter, we do not enforce the τ-path to go via the core state, but rather the condition above suffices to ensure that the rest of the plan can be reconstructed.

Proposition 2. Weak bisimulation shrinking is a polynomial reformulation.

Proof. The coarsest weak bisimulation of a TS can be computed by computing the bisimulation of the transitive closure of the TS over τ. Each step of the plan reconstruction corresponds to an uniform-cost search on each TS. Both operations take polynomial time in the size of the TS.

Consider the following plan of the task shown in Fig. 1c: (A, 2, off) CF --→ (A, 2, ro) DR --→ (BC, 1, ro) DR --→ (D, 0, ro). To reconstruct the plan for the task prior to weak bisimulation shrinking (cf. Fig. 1b), we execute it and, when DR cannot be applied in rd, we insert a τ-transition with ON resulting in the plan: (A, 2, off) CF --→ (A, 2, rd) ON --→ (A, 2, on) DR --→ (BC, 1, on) DR --→ (D, 0, on). Then, we reconstruct the plan for the atomic task of Fig. 1a step by step, resulting in a plan: (A, 2, off) CF --→ (A, 2, rd) ON --→ (A, 2, on) DRA-B,2-1 -----→ (B, 1, on) DRB-D,1-0 -----→ (D, 0, on).

4 Relation to FDRReformulationMethods

The M&S reformulations are closely related to previous FDR reformulation methods like the generalize actions [Tozicka et al., 2016], fluent merging [Seipp and Helmert, 2011], and abstraction-based reformulations [Helmert, 2006b; Haslum, 2007; Tozicka et al., 2016]. To compare reformulation methods over different formalisms, we consider that a method dominates another if it can perform the same reformulations.

Definition 4 (Dominance of Reformulation Methods). An FTS task reformulation method X dominates an FDR reformulation method Y if, given an FDR task ΠV and a reformulation ρY ∈ Y applicable over ΠV , there exists a reformulation ρX ∈ X such that it is applicable in atomic(ΠV ) and ρX (atomic(ΠV )) = atomic(ρY (ΠV )). We say that the domination is strict if there exists ρX ∈ X such that it is applicable in atomic(ΠV ) but there does not exist any ρY ∈ Y applicable in ΠV and ρX (atomic(ΠV )) = atomic(ρY (ΠV )).

The generalize actions reformulation reduces the number of FDR actions by substituting two actions by a single one if they are equal except for a precondition on a binary variable. Formally, whenever there is a variable w with domain Dw = {x, y}, and two actions a1, a2 s.t. V(prea1) = V(prea2), ∀v ∈ (V(prea1) \ {w}) prea1(v) = prea2(v), prea1(w) = x, prea2(w) = y, and eff a1 = eff a2. Then, a1 and a2 can be replaced by a′ where eff a′ = eff a1 and prea′ (v) = prea1(v) ∀v ∈ (V(prea1) \ {w}).

Theorem1. Exact label reduction strictly dominates the generalize actions reformulation.

Proof Sketch. If generalize actions replaces a1 and a2 in ΠV by a′ , then there are labels ℓ1 and ℓ2 in atomic(ΠV ) that correspond to a1 and a2 and a TS Θw that corresponds to w in ΠV . As a1 and a2 have the same effects and preconditions on all variables except v, then ℓ1 and ℓ2 are equal except for

Θw so they can be reduced. Label reduction is more general because it may result in transitions with different targets from the same state and label, which is not possible in FDR.

Fluent merging is an FDR reformulation inspired by the merge transformation in M&S [Seipp and Helmert, 2011]. It replaces two variables v1, v2 ∈ V by their product, resulting in a variable v1,2 with domain Dv1,v2 = Dv1 × Dv2 . However, adapting the FDR actions is not straightforward since they would require disjunctive preconditions. For example, if action a1 has a precondition on v1 but not on v2, then the action is applicable for several values of Dv1,v2 but not for all of them. Since FDR does not allow for disjunctive preconditions, multiple copies of the actions are needed to encode the preconditions and effects on the new variable. Similarly, auxiliary actions must be added to encode a disjunctive goal whenever a goal and a non-goal variable are merged. In this case, the merge transformation does not dominate fluent merging because it does not add such auxiliary labels and transitions. This is arguably an advantage since adding them is not expected to be beneficial or, otherwise, an equivalent reformulation could be defined in M&S.

The use of abstraction for task reformulation in planning has a long history [Knoblock, 1994]. The key idea is to solve an abstraction of the problem and then refine the abstract solution by filling the gaps. Not all abstractions are suitable for this, since they need to ensure that any solution for the abstract task can be refined into a plan for the original task. Abstractions with this property are said to be refinable. Abstraction reformulations were first applied in FDR by the Fast Downward planner [Helmert, 2006a]. Their reformulation abstracts away any root variable in the causal graph (i.e., does not have dependencies on other variables) whose free domain transition graph is strongly connected (i.e., one can always set the variable to any desired value by applying a sequence of actions). This was generalized by Haslum [2007] into the safe variable abstraction reformulation under the observation that (1) it suffices to consider values that are relevant for other variables (because they are precondition or effect of an action that has another variable in its effect); and (2) the goal only needs to be achieved at the end of the plan so the goal value must be free reachable from other relevant values, but it is not necessary that other values are reachable from the goal value.

Finally, one can also ignore the difference among some values of a variable without ignoring it completely: the merge values reformulation reduces the domain of an FDR variable by merging several values whenever they can be switched via actions without any side effects [Tozicka et al., 2016]. Formally, let v be a variable with x, y ∈ Dv, and a1 and a2 be actions s.t. V(prea1) = V(eff a1) = V(prea2) = V(eff a2) = {v}, and prea1(v) = eff a2(v) = x, and prea2(v) = eff a1(v) = y. Then, x may be removed from Dv, replacing every occurrence of x in A, I, and G by y.

As all these methods, weak bisimulation shrinking obtains a refinable abstraction, but on the FTS representation, taking advantage of the flexibility of M&S to compute abstractions.

Theorem 2. Removing transition systems with core states after applying weak bismulation shrinking strictly dominates the safe variable abstraction reformulation.

Proof Sketch. If a variable is abstracted away, abstract states corresponding to the values that appear in the preconditions of outside relevant actions are all weakly bisimilar. After shrinking, the resulting abstract state is a core state.

Theorem 3. Weak bisimulation shrinking strictly dominates the merge values reformulation.

Proof Sketch. If values x, y of variable v are merged, there exist ℓ1, ℓ2 in atomic(ΠV ) corresponding to a1, a2, and a TS Θv representing v. As v is the only variable in the preconditions and effects of a1 and a2, ℓ1 and ℓ2 are τ-labels in Θv. Since x τ =⇒ y and y τ =⇒ x, x and y are weakly bisimilar.

5 Search on the FTS Representation

To use our reformulation framework, planning algorithms must be used to find a solution to the reformulated FTS task. Heuristic search is a leading approach for solving classical planning problems [Bonet and Geffner, 2001]. A compilation into an FDR task having an action for each combination of transitions with the same label in different TSs is possible, but may incur a big overhead, potentially losing any gains obtained by the reformulation methods. Here, we consider how to apply heuristic search algorithms to FTS tasks by defining the successor generation and heuristic evaluation.

Successor generation is the operation that, given a state s, generates all transitions s l-→ t in the state space of the task. This typically is done in two steps: (1) generate the set of actions that are applicable in s and (2) for each such action obtain the corresponding successor state.

Since the number of actions in FDR tasks may be very large, iterating over all of them to check whether they are applicable in s is inefficient. The Fast Downward Planning System uses a tree data-structure to efficiently retrieve the applicable actions in a given state [Helmert, 2006b]. However, this data-structure relies on actions being applicable either only for one value of each variable if v ∈ V(prea) or in all values of such variable otherwise. This is no longer true for labels in the FTS representation. A label is applicable in a factored state s if there exists an outgoing transition s[Θi] l-→ ti for each Θi ∈ ΠT . Since there may be any number of transitions in each Θi from any number of source states, labels may be applicable for arbitrary sets of states. We pre-compute for every abstract state si ∈ Θi the set of labels with an outgoing transition from si, denoted Lsi . Then, given a state s, the set of applicable labels can be computed as ⋂Θi Ls[Θi].

Step (2) is simple in FDR since the new state is a copy of s, overriding the value of variables in the effect. In the FTS representation, however, there may be multiple successors from s with label ℓ. We enumerate all possible successors by considering all outgoing transitions from s[Θi] in every Θi. To do this efficiently, for each label ℓ we divide the set of TSs in ΠT in three sets: the irrelevant TSs where ℓ only induces self-loop transitions, deterministic TSs where for every si ∈ Θi there is a single outgoing transition with ℓ, and non-deterministic TSs where there may be multiple transitions from the same source state. Only the latter require to enumerate all possible transitions, whereas irrelevant TSs are ignored and the effect on deterministic TSs can be set as in FDR tasks.

We now discuss how to derive heuristic functions for the FTS representation, which are essential to guide the search and find solutions to large tasks. As most heuristic functions have originally been defined for STRIPS or FDR, they need to be adapted to use them in FTS tasks. This is similar to adding support for a limited form of disjunctive preconditions and conditional effects. In optimal planning, we use merge-andshrink heuristics since they are already based on FTS.

To apply our reformulation framework on satisficing planning, we adapt the FF heuristic [Hoffmann and Nebel, 2001]. FF is based on the delete-relaxation, ignoring the delete effects of STRIPS actions. In FDR, "ignoring deletes" is interpreted as ignoring the negative effect of the actions, so that variables accumulate values instead of replacing them. This is easily extrapolated to the FTS representation by considering that each TS may simultaneously be in multiple states.

To compute the heuristic, we compile our task into an FDR task with one unary action asi,ℓ,ti for each transition si ℓ-→ ti in some Θi. This action has ti as effect, and si as precondition plus additional preconditions for each other Θj where l is not applicable in all states. If there is a single state sj ∈ Θj where ℓ is applicable, we add sj to the precondition of asi,ℓ,ti . If there are more than one, we add an auxiliary fact to our task fℓ,j that represents the disjunction of those states, as well as auxiliary unary actions from each of those states to fℓ,j .

Afterwards, we retrieve the relaxed plan as a set of transitions si ℓ-→ ti, and add the cost of all their labels to obtain the heuristic value. One difference to FF for FDR is that there, FF counts each action only once because no action needs to be applied more than once in delete-free tasks. We do not do this to avoid underestimating the goal distance when the same label may have different effects (e.g. label DR in Fig.1b).

The delete-relaxation is also useful to select preferred actions. In FDR, an action is preferred in state s if it belongs to the relaxed plan of FF for s. In FTS, we consider s ℓ-→ t to be preferred if the relaxed plan from s contains a transition labeled with ℓ and with target ti s.t. ∃Θit[Θi] = ti.

6 Experiments

We implemented the M&S reformulation framework in Fast Downward (FD) [Helmert, 2006b], using its existing M&S framework [Sievers, 2018] and extending it with weak bisimulation as well as pruning transformations that remove dead labels and irrelevant TSs and labels. We also modified the layout of the algorithm: firstly, since our pruning transformations might trigger further pruning opportunities, we always repeatedly apply them until a fixpoint is reached. Secondly, we run label reduction and shrinking on the atomic FTS task until no more simplifications are possible. Finally, we cannot exactly control the amount of shrinking done because this would result in non-refinable abstractions that do not admit plan reconstruction. Instead, we restrict merging to satisfy the size limit and only shrink after merging and pruning.

To consider the effects of some of the M&S transformations on the task reformulation individually, we consider the following configurations. As the simplest baseline, we only transform the FDR task (FDR) into the atomic FTS task (a), without any further transformations. This does not affect the state space at all, but serves for quantifying the overhead of our implementation over FD, mainly due to using different data structures to represent the task and perform successor generation. Another variant of atomic adds exact label reduction and shrinking (a-ls), either based on bisimulation for optimal planning or weak bisimulation for satisficing planning. Other configurations combine label reduction and shrinking with a merge strategy. For the latter, we consider DFP (d-ls) and sbMIASM (m-ls, called dyn-MIASM originally) [Sievers et al., 2014], with a size limit of 1000 on the resulting product. We did not find qualitative differences with size limits of 100 and 10000. We impose a time limit of 900s on the reformulation process. For the overall planning, we use a limit of 3.5 GiB and 1800s. We use all STRIPS benchmarks from the optimal/satisficing tracks of all IPCs, two sets consisting of 1827/1816 tasks across 48 unique domains. 1

6.1 Search Space Reduction

To assess the impact of our task reformulations on the reachable state space, we run uniform-cost search and evaluate the number of expansions until the last f-layer. Fig. 2 compares the FDR representation against a-ls and d-ls with bisimulation (top) and weak bisimulation (bottom) shrinking. We observe that even with only label reduction and bisimulation shrinking (a-ls) there are state space reductions of up to one order of magnitude in some cases. Most of these gains are due to shrinking, given that label reduction does not change the state space and pruning cannot be performed often in the atomic representation due to the preprocessing of FD. When using merge transformations (d-ls), state space reductions can often be of up to several orders of magnitude. It is worth noting that merging does not affect the state space, so this reduction is due to the synergy with pruning and shrinking.

1 Implementation: https://doi.org/10.5281/zenodo.3232878, dataset with benchmarks: https://doi.org/10.5281/zenodo.3232844.

If optimality does not need to be preserved, larger reductions can be achieved with weak bisimulation shrinking. In this case, 305 tasks (including entire domains like logistics, miconic, movie, rovers, and zenotravel) can be solved during the reformulation resulting in 0 expansions (points on the xaxis). The reason is that weak bisimulation shrinks away entire TSs (e.g., if they form a single connected component with actions without side preconditions or effects, which translate to τ-labels). An example is logistics: as trucks/airplanes can always freely change their location with the drive/fly action, weak bisimulation simplifies the TSs describing their position, after which the TSs for packages can also be simplified. Previous abstraction reformulation approaches solved many of these domains too, with the exception of Rovers, where they obtained reductions but without completely simplifying the domain. With merge reformulations, 460 tasks are solved with DFP (completely solving transport-opt), and 514 with MIASM (solving all but two instances in parcprinter-opt). This is remarkable given the low limit of 1000 abstract states.

6.2 Results with Informed Search

We evaluate the impact of our reformulations in terms of coverage (see Table 1), expansions, and total time (see Fig. 3). On the optimal benchmarks, we run A∗ with hmax and M&S with DFP using a 50000 size limit and (approximate) bisimulation shrinking. On the satisficing benchmarks, we run lazy greedy search with hFF , with and without preferred operators. The comparison of FDR and atomic (a) shows that our implementation has some overhead. Both configurations explore the same state space with very similar heuristics. hmax and hFF are computed in the same way with no big overhead and the runtime of plan reconstruction is usually negligible. In terms of heuristic value, hmax is identical and hFF only differs due to tie-breaking and because some actions may be counted twice. One of the main sources of overhead is the memory used to represent FTS tasks. Our data structures use O(|L|) memory on each TS, whereas in FDR no memory is wasted for variables not mentioned in the preconditions or effects.

Label reduction and shrinking on the atomic FTS task (a-ls) is useful in most cases, increasing total coverage in all configurations. This reformulation reduces the state space as well as the task description size (i.e. reducing the TSs in the FTS representation). Therefore, gains in expanded nodes usually translate into lower search times, and it can pay off despite the overhead of the precomputation phase on total time.

Merge reductions (d-ls), however, are oftentimes harmful in combination with delete-relaxation heuristics (hmax and hFF ), due to the overhead caused by increasing the task size. Nevertheless, they can be very useful in some domains, whenever there is enough synergy with pruning (e.g. woodworking, tpp) or shrinking (e.g. childsnack). Indeed, for all heuristics we tried, merge reformulations are useful in at least a few domains. This is also reflected in the orcl column that shows how many instances are solved by any of our configurations. This is often much larger than our atomic configuration, but also than the FDR baseline, showing that if the right reformulations are chosen for each domain, they can compensate for the overhead of using an FTS representation.

The results of d-ls with M&S heuristics are different because there are more cases where the heuristic is less informed after the d-ls reformulation, increasing the number of expansions. There is also a large number of instances where the heuristic value for the initial state is perfect for a-ls whereas a large amount of search is needed with d-ls. The reason is that the options available for the merge strategy during the reformulation are reduced by the limit on abstract states, leading to different merge decisions, and possibly degrading the quality of the heuristic. However, with M&S heuristics there is no overhead in runtime so d-ls pays off more often.

The rightmost two columns of Fig. 3 show results with hFF and preferred operators for satisficing planning. The reductions obtained by weak bisimulation shrinking are much stronger than by optimality preserving strategies, improving the performance of a-ls and d-ls in terms of expanded nodes. In terms of runtime, a-ls is useful in many cases despite the overhead caused by spending up to 900s in preprocessing. Merge reformulations, however, increase the computational cost of the heuristic, so they do not pay off over a-ls except in a few cases where the reduction is huge.

7 Conclusion

In this work, we use the M&S framework for task reformulation and analyze its advantages over reformulations in FDR. Our results show a large potential of state space reductions, that sometimes can solve entire domains without any search.

The framework has even more potential by integrating new reformulation methods like subsumed transition pruning [Torralba and Kissmann, 2015], or graph factorization [Wehrle et al., 2016]. Our results also show that not all reformulations are always helpful. Thus, to materialize all this potential, methods to automatically select the best reformulation method for each domain are also of great interest [Gerevini et al., 2009; Fuentetaja et al., 2018].

Acknowledgments

Silvan Sievers has received funding for this work from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 817639). ´Alvaro Torralba has received support by the German Research Foundation (DFG), under grant HO 2169/5-1 and DFG grant 389792660 as part of TRR 248 (see https://perspicuous-computing.science).