Structural Symmetries for Fully Observable Nondeterministic Planning

1 Introduction

Fully observable nondeterministic (FOND) planning is a challenging task because the application of actions can have several possible outcomes, and planning algorithms must consider all these possibilities. Solutions to FOND planning tasks are represented as policies, which map states to actions, and thus determine the next action in the final plan depending on the actual outcome of the previously applied action. The current state of the art in FOND planning includes the Planner for Relevant Policies [Muise et al., 2012; 2014], which performs multiple runs of an underlying classical planner, and specifically focuses on relevant state parts. An alternative approach to solve FOND planning tasks is based on heuristic search with the LAO⇤ algorithm [Hansen and Zilberstein, 2001; Mattm¨uller et al., 2010]. Similar to solving classical planning tasks with A⇤ , an efficient FOND planning algorithm based on LAO⇤ features accurate distance heuristics to guide the search towards goal states, as well as (completeness-preserving) pruning methods to reduce the branching factor of the search space.

Pruning methods have shown their potential for classical planning and state-space search in recent years, and several methods have been proposed [Fox and Long, 1999; 2002; Coles and Coles, 2010; Pochter et al., 2011; Wehrle and Helmert, 2012; Domshlak et al., 2012; Nissim et al., 2012; Wehrle et al., 2013; Domshlak et al., 2013; Wehrle and Helmert, 2014; Holte and Burch, 2014; Holte et al., 2015]. In particular, symmetry reduction in the form of orbit space Michael Katz IBM Watson Health Israel katzm@il.ibm.com search has demonstrated to be effectively applicable in a wide range of classical planning domains, often reducing the state space size and increasing planning performance significantly [Domshlak et al., 2012; 2015]. In a nutshell, for classical planning, symmetry reduction computes equivalence classes of "symmetrical" states, with the property that states in equivalence classes need not be distinguished during the search because they in turn yield equivalent "symmetrical" paths in the state space. For example, assume that two objects O1 and O2 have to be carried with a vehicle V , where V has a right and a left place to load these objects. Then the state where O1 is loaded on the left and O2 on the right, and the state where O1 and O2 are loaded on the opposite positions, are symmetrical. Informally, the actual object position of O1 and O2 on the vehicle does not matter to carry them to the goal position, and hence, only one of these states needs to be considered.

While symmetry reduction has shown to be beneficial for A⇤ in "classical" state spaces, it is an open question whether it can be effectively generalized to FOND planning with LAO⇤ . We provide the framework for such a generalization, in particular addressing the questions how the concept of symmetries can be generalized to operators with nondeterministic effects, how the well-established orbit space search algorithm from classical planning can be generalized to AND/OR graphs, and how concrete policies can be reconstructed from "symmetrical" policies. We have implemented our framework within the Fast Downward planning system [Helmert, 2006], and evaluated our approach on a variety of FOND planning benchmarks. Our experiments show the potential of symmetries for LAO⇤ , both compared to the myND planner [Mattm¨uller et al., 2010] and compared to vanilla LAO⇤ . As a side result, our implementation offers a competitive LAO⇤ - based FOND planner to the community, making Fast Downward's features applicable to FOND planning as well.

2 Preliminaries

We use an SAS+ based notation [B¨ackstr¨om and Nebel, 1995] to model fully observable nondeterministic planning tasks with a finite set of finite-domain state variables V. Every variable v in V has a finite domain dom(v). A variable/value pair hv↪di for v 2 V and d 2 dom(v) is called a fact. A partial state s is a function from variables Vs ✓ V to values in the domains of Vs, whereas all variables in V ∩ Vs have an undefined value ?. We denote the value of v in s with s[v]

(including s[v] = ? if v 2 V ∩Vs). By vars(s) we denote the subset of variables for which a value is defined by the partial state s. A state is a partial state where all values are defined, i.e., with vars(s) = V. A state s complies with a partial state t, denoted by s ◆ t, if s[v] = t[v] for all v 2 vars(t).

We consider fully observable nondeterministic (FOND) planning tasks. In contrast to classical planning, operators in FOND planning can have several possible effects, where only one of these effects is applied when the operator is executed. Formally, FOND planning tasks are defined as follows.

Definition 1 (fully observable nondeterministic planning task). A fully observable nondeterministic (FOND) planning task is a tuple ⇧ = hV↪ O↪ s0↪ s?i, where

• ÷ O is a finite set of nondeterministic operators,
• ÷ V is a finite set of finite-domain state variables,
• ÷ s0 is the initial state, and

A nondeterministic operator o 2 O has the form hpre(o)↪ e↵s(o)i, where pre(o) is a partial state that denotes the precondition and e↵s(o) is the set of effects of o, where each effect in e↵s(o) is a partial state.

• ÷ s? is a partial state called goal.

In the following, we will denote a nondeterministic operator as an operator unless stated otherwise. An operator o is applicable in a state s iff s[v] = pre(o)[v] for all v 2 vars(pre(o)). If operator o is applicable in s, the set of successor states o(s) := ¶oe↵ (s) ♣ e↵ 2 e↵s(o)♦ of s is obtained from s based on the successor states oe↵ (s) for each e↵ 2 e↵s(o), where oe↵ (s) is obtained from s by setting the values of variables in vars(e↵ ) to their values in e↵ , and leaving the remaining variable values unchanged. We denote the set of applicable operators in s by app(s).

For a FOND planning task ⇧ = hV↪ O↪ s0↪ s?i, we define the transition system of ⇧ as T ⇧ = hS↪ T↪ s0↪ S?i, where S is the set of ⇧'s states, and T ✓ S ⇥ O ⇥ S is the set of transitions, with hs↪ o↪ s0 i 2 T iff o is applicable in s, and s0 is a possible outcome of applying o in s, i.e., s0 2 o(s). Furthermore, s0 is the initial state, and S? is the set of goal states, i.e., the set of states that comply with s?.

As mentioned, operators generally can have several effects, and applying an operator in a state yields a successor state where (nondeterministically) one of these effects has been applied. Hence, solutions to FOND planning tasks are not linear operator sequences as in classical planning, but rather policies which determine the next plan operator depending on the outcome of the previously applied plan operator.

Definition 2 (policy). Let ⇧ be a FOND planning task with set of states S. A policy is a mapping ⇡ : S ! O[¶?♦, which maps states to operators, or ⇡ is undefined (i.e., ⇡(s) =?).

We shortly denote the sequential application of the operators determined by ⇡ as following ⇡. A policy ⇡ is called weak if ⇡ defines at least one path from the initial state to a goal state when following ⇡. In this case, ⇡ is called a weak plan for ⇧. A policy ⇡ is closed if following ⇡ either leads to a goal state, or to a state where the policy is defined. It is proper if from every state visited following ⇡ there exits a path to a goal state following ⇡. A policy that is closed and proper is called a strong cyclic plan for ⇧. Furthermore, ⇡ is acyclic if it does not revisit already visited states. A closed and proper acyclic policy is called a strong plan for ⇧.

Informally, a weak plan is a sequence of operators which leads to a goal state if all nondeterministic operator outcomes were deterministic, which corresponds to a plan in classical planning. A strong plan guarantees that a goal state is reached, where an upper bound on the number of plan steps exists. In contrast, strong cyclic plans require a finite number of steps to reach a goal state, but no such upper bound on the plan steps can be provided a priori. However, strong cyclic planning is based on the fairness assumption, i.e. there is a nonzero probabilty that a goal state can be reached when following a strong cylic plan. We focus on the problem of finding strong cyclic plans with the LAO⇤ algorithm.

2.1 Symmetry Elimination in Classical Planning

Symmetry elimination has shown its potential for planning in several contexts [Fox and Long, 1999; 2002; Rintanen, 2003; Coles and Coles, 2010; Pochter et al., 2011; Domshlak et al., 2012; 2013; Shleyfman et al., 2015]. Symmetry elimination considers equivalence classes of symmetrical states, and allows for using representative states of each equivalence class. Recently, Shleyfman et al. [2015] introduced the notion of structural symmetries, which captures previously proposed concepts of symmetries for classical planning. In a nutshell, structural symmetries directly work on the factored representation of a classical planning task ⇧. They map operators to operators, and facts to facts in a way that the induced mapping on the state space graph T⇧ is an automorphism of T⇧.

Symmetry elimination has been considered in particular for planning as heuristic search. For a classical planning task ⇧ with state set S, a set of structural symmetries ⌃ induces a group Γ and an equivalence relation ⇠Γ on S, where s ⇠Γ s0 iff there is σ 2 Γ such that σ(s) = s0 . For a state s, pruning algorithms based on symmetry elimination only consider the equivalence classes of the successor states of s instead of all successor states, and only keep one representative element of these classes. In this sense, A⇤ with symmetry elimination applies all operators in s, but prunes some of the resulting successor states. The resulting reduced state transition graph is guaranteed to still contain an optimal plan in s. To achieve this, an algorithm called orbit space search has been introduced [Domshlak et al., 2015]. Orbit space search works directly in the orbit space induced by canonical representatives: Orbit space search searches the state space graph induced by canonical representatives for each encountered state, where states are mapped to corresponding representatives. As computing single canonical states for all symmetrical states is not tractable, a greedy approach is employed to compute symmetrical states in a safe way.

3 Structural Symmetries for FOND Planning

Structural symmetries [Shleyfman et al., 2015] are naturally extended to FOND planning tasks.

Definition 3 (structural symmetry). For a FOND planning task ⇧ = hV↪O↪ s0↪ s?i, let F be the set of ⇧'s facts, i.e., pairs hv↪ di with v 2 V, d 2 dom(v). A structural symmetry for ⇧ is a permutation σ : V [ F [ O ! V [ F [ O, where

1. σ(V) = V and σ(F) = F such that σ(hv↪ di) = hv0 ↪ d0 i iff v0 = σ(v), d 2 dom(v), and d0 2 dom(v0 )
2. σ(O) = O such that for o 2 O, σ(pre(o)) = pre(σ(o)), σ(e↵s(o)) = e↵s(σ(o))
3. σ(s?) = s?,

where σ(¶x1↪ ▷ ▷ ▷ ↪ xn♦) := ¶σ(x1)↪ ▷ ▷ ▷ ↪ σ(xn)♦, and for a partial state s, s0 := σ(s) is the partial state obtained from s such that for all hv↪ di with v 2 vars(s) and d 2 dom(v), σ(hv↪ di) = hv0 ↪ d0 i and s0 [v0 ] = d0 .

The only difference to structural symmetries for classical planning tasks is bullet point 2., second part, where we require σ(e↵s(o)) = e↵s(σ(o)), i.e., several effects of o are taken into account by σ, and the set of o's effects is mapped to the corresponding effect set of o's symmetrical counterpart.

To describe how to handle symmetries, we need the notion of Canonical mappings.

Definition 4 (canonical mapping). A mapping C : S 7! S is called a canonical mapping if for each state s 2 S there exists a structural symmetry σs such that C(s) = σs(s). The state C(s) is called the canonical state of s. A canonical mapping C is perfect if for each pair of symmetrical states s and t, we have C(s) = C(t).

As computing perfect canonical mappings is intractable, in practice, a greedy approach to compute canonical mappings is usually employed. Such a greedy approach is safe in the sense that states might not be recognized as symmetrical although they are. From now on, we assume a greedy algorithm for computing canonical mappings C. For a canonical mapping C, let SC = ¶C(s) ♣ s 2 S♦ be the set of canonical states of ⇧. We can now define induced canonical transition systems.

Definition 5 (canonical transition system). Given a transition system T ⇧ = hS↪ T↪ s0↪ S?i of the planning task ⇧, a canonical mapping C induces the canonical transition system T ⇧↪C = hSC ↪ T C ↪ sC0 ↪ SC ? i, where SC is the set of canonical states of ⇧, and T C = ¶hC(s)↪ o0 ↪ C(t)i ♣ hs↪ o↪ ·i 2 T↪ o0 = σs(o)↪ t 2 o0 (C(s))♦ be the set of canonical transitions. Furthermore, sC0 = C(s0), and SC ? = ¶C(s) ♣ s 2 S?♦.

For brevity, we will often write T C instead of T ⇧↪C if the context is clear. In T C , each transition hC(s)↪ o0 ↪ C(t)i in T C is a triplet consisting of a canonical state C(s), an operator o0 applicable in C(s), and a canonical state C(t), which is the canonical state of a state resulting from applying o0 in C(s). A mapping ⇡c : SC 7! O [ ¶?♦ is a canonical policy for ⇧. A canonical policy is a weak canonical plan if it is a weak plan for the canonical transition system, it is a strong cyclic canonical plan if it is a strong cyclic plan for the canonical transition system, and it is a strong canonical plan if it is a strong plan for the canonical transition system.

In the following, we provide an extension of the LAO⇤ algorithm with symmetry reduction, which results in an LAO⇤ search in a canonical transition system.

4 LAO⇤ in Canonical Transition Systems

We propose a FOND planning algorithm with symmetry reduction, consisting of three steps: Firstly, given the FOND planning task, compute a set of structural symmetries, which in turn determines the canonical transition system. Secondly, we propose a (straight-forward) extension of the LAO⇤ algorithm as previously used for FOND planning by Mattm¨uller et al. [2010]. The outcome is a strong cyclic canonical plan. Thirdly, in a post-processing phase and based on the strong cyclic canonical plan, a strong cyclic plan can be extracted.

The computation of structural symmetries is performed analogously as in classical planning. We refer the reader to the literature for details [Pochter et al., 2011; Domshlak et al., 2012; Shleyfman et al., 2015]. For the search part, we propose a variant of LAO⇤ [Mattm¨uller et al., 2010], which is extended to perform its search in a canonical transition system instead of the original. This is achieved by replacing encountered states with canonical representatives. We call the resulting algorithm canonical LAO⇤ (CLAO⇤ for short). It is shown in Algorithm 1.

Algorithm 1 The CLAO⇤ algorithm

1: Implicit graph G 0 consists of canonical initial state C(s0) 2: while C(s0) unsolved do 3: E UNEXPANDEDNONGOAL(TRACE(G 0 )) 4: if E = ; then E UNEXPANDEDNONGOAL(G 0 ) 5: N EXPANDALL(E) 6: for each new state s 2 N do 7: add canonical state C(s) to implicit graph G 0 8: connect C(s) to its ancestor 9: f(C(s)) ⇢0 if C(s) ◆ s? h(C(s)) otherwise 10: Z BACKWARDREACH(E) 11: VALUEITERATION(Z) 12: SOLVELABELLING(G 0 ) 13: return POLICYEXTRACTION(TRACE(G 0 ))

CLAO⇤ starts off with the canonical representative C(s0) of the initial state s0 (line 1). As long as the algorithm does not find a solution for the canonical initial state C(s0), it performs regular LAO⇤ for FOND planning (using a given heuristic h), with the exception that the successors resulting from operator applications are replaced by their respective canonical representatives.

As a final step, if a solution has been found by CLAO⇤ , a concrete policy is extracted. For this step, we refer back to the definition of canonical mappings (Def. 4): For a perfect canonical mapping, it suffices to define the concrete policy as

for all states s and corresponding canonical states C(s). As mentioned earlier, computing perfect canonical mappings is not tractable, and hence canonical mappings will rarely be perfect in a practical setting. Consequently, if the canonical mapping is not perfect, there can be two symmetrical states, such that the canonical policy is defined for only one of them, hence the policy extraction algorithm becomes slightly

Algorithm 2 Solution reconstruction algorithm

1: function POLICYEXTRACTION(⇡c) 2: Input: A canonical policy ⇡c 3: OPEN is a queue initialized with s0 4: CLOSED is a closed list, intially empty 5: ⇢s0 σs0 6: ⇡(s0) ⇢-1 s0 (⇡c(C(s0))) 7: while OPEN is not empty do 8: s pop(OPEN) 9: Add s to CLOSED 10: sc ⇢s(s) 11: if ⇡c(sc ) =? then continue 12: o ⇡(s) 13: for each successor state t in o(s) do 14: if t 2 CLOSED then continue 15: t ⇢s(t), tc C(t) 16: ⇢t σt ◦ ⇢s 17: ⇡(t) ⇢-1 t (⇡c(tc )) 18: Add t to OPEN 19: return policy ⇡

more technical. For clarity of presentation, assuming nonperfect canonical mapping, through the section we will use the following notation. For a state s, with the canonical state C(s), by sc we denote the representative of s in the canonical policy. As mentioned above, although s, C(s), and sc are all symmetrical, sc can be different from the canonical state C(s) of s. The mapping ⇢s then denotes the structural symmetry mapping from the state s to the representative state sc , i.e., ⇢s(s) = sc .

The procedure POLICYEXTRACTION - to extract concrete policies from canonical mappings that are not perfect - is shown in Algorithm 2. It follows all possible outcomes from applying the policy, mapping the current state to a representative in the canonical policy, not necessarily its canonical state. The overall algorithm is complete.

Theorem 1. The CLAO⇤ algorithm followed by POLICYEXTRACTION preserves the completeness of LAO⇤ .

Proof. The algorithm described in Algorithm 1 is an LAO⇤ search in the canonical transition system and thus returns a strong cyclic canonical plan, if the task is solvable. Otherwise, it returns a policy ⇡c such that ⇡c(C(s0)) =? and thus Algorithm 2 will return a policy ⇡ with ⇡(s0) =?.

Assuming that the task is solvable, we need to show that given the strong cyclic canonical plan ⇡c, the reconstruction step depicted in Algorithm 2 then returns a strong cyclic plan ⇡. We show that by induction on the distance of a state from the initial state s0, showing that for each state t with a parent s and an achieving operator o = ⇡(s), a corresponding state in the strong cyclic canonical plan with a policy operator defined can be found via the mapping ⇢. First, for the initial state itself, its corresponding state is C(s0), mapped from s0 via the structural symmetry ⇢s0 := σs0 , with ⇡c(C(s0)) being defined, and the policy ⇡(s0) is then obtained from ⇡c(C(s0)), as in lines 5-6 of Algorithm 2.

For the induction step, assume that (i) the corresponding state sc = ⇢s(s) in ⇡c is defined for the parent s via ⇢s, and (ii) the policy ⇡ is defined for s, with o = ⇡(s) being the symmetrical operator to the operator ⇡c(sc ) via ⇢s, that is ⇢s(o) = ⇡c(sc ). The step is visualized in Figure 1. Let t be a state resulting from an application of o in s, and let t = ⇢s(t) be the state resulting from mapping t with its parent symmetry ⇢s (line 15). Then, t is a state resulting from an application of ⇡c(sc ) in sc . Let C(t) be the canonical state of t. Then, (sc ↪ ⇡c(sc )↪C(t)) is a transition in the canonical transition system that corresponds to an outcome of applying ⇡c(sc ) in sc . Thus, ⇡c is defined on tc := C(t). The symmetry ⇢s maps from t to t and σt maps from t to tc . Thus, ⇢t := σt ◦ ⇢s (line 16) maps from t to tc , a state in the strong cyclic canonical plan with a policy operator defined. We can now define ⇡(t) by a mapping of the operator ⇡c(tc ) with the inverse symmetry ⇢-1 t (line 17), finishing the induction step.

We remark that in practice, there is no need for reconstructing the policy: Executing a policy can be done with the help of the canonical policy found by the CLAO⇤ algorithm, by restricting the line 13 in Algorithm 2 to the successor t that is the actual outcome of applying the operator o in the state s.

5 Experimental Evaluation

We have implemented the variant of LAO⇤ which has been previously used for FOND planning [Mattm¨uller et al., 2010] as well as CLAO⇤ within the Fast Downward planning system [Helmert, 2006]. In this section, we empirically investigate the usefulness of structural symmetries and symmetry reduction for FOND planning. In particular, we investigate the following research questions: In how many of the commonly available FOND planning domains do symmetries exist? What is the computational overhead to compute these symmetries? How much can the state space size be reduced with CLAO⇤ compared to LAO⇤ ? And finally, does the reduction pay off in overall runtime and in the number of tasks that can be solved? As a basis for these investigations, we compare the performance of our LAO⇤ implementation to the LAO⇤ -based FOND planner myND.

Our experiments have been conducted on a server equipped with 2.3 GHz Quad-Core AMD Opteron 2356 CPUs. The time and memory bounds per run are 30 minutes and 2GB, respectively. For the evaluation, we use the FF heuristic [Hoffmann and Nebel, 2001], a state-of-the-art heuristic for classical planning already available in Fast Downward (for FOND planning tasks, the FF heuristic is computed based of alloutcomes determinizations). The experiments focus on the computationally challenging parts, i.e., computing the structural symmetries, and searching with LAO⇤ and CLAO⇤ , excluding the policy extraction step (the latter could be done in linear time in the policy size). Our benchmark set consists of all IPC-08 FOND planning domains, including the larger tasks generated by Muise et al. [2012].

Fast Downward LAO⇤ compared to myND

We first investigated the performance of our LAO⇤ implementation in Fast Downward (shortly called FD-LAO⇤ in the following) compared to the FOND planner myND. For both FDLAO⇤ and myND, we used the FF heuristic, which is available in both solvers. In Figure 2, we report the coverage, i.e., the number of planning tasks for which a solution has been found within our resource bounds. The total number of planning tasks per domain in reported in parenthesis.

We observe that FD-LAO⇤ is competitive with myND, and additionally, FD-LAO⇤ has distinct advantages in the domains FAULTS-NEW and FIRST-RESPONDERS. Overall, FDLAO⇤ solves 57 more planning tasks, which is remarkable due to the usual exponential complexity increase in the task size. As a main conclusion, we observe that FD-LAO⇤ provides a competitive basis for the following experiments.

CLAO⇤ compared to FD-LAO⇤

In the following, we evaluate the potential of symmetry reduction for LAO⇤ -based FOND planning. Firstly, we observed that symmetries often occur in the common FOND planning benchmarks: out of 660 planning tasks that we have considered in total, symmetries have been found in 535 of these. The preprocessing time to compute the symmetries is depicted in Figure 3. The plot shows the number of tasks for which the symmetry precomputation has finished as a function over time (i.e., the point (x↪ y) on the plot means that for y tasks, the symmetry precomputation time is  x seconds).

We observe that the computation of symmetries can mostly be done rather efficiently: For most tasks, the computation finished within a couple of seconds (e.g., for ≥ 78% of the considered tasks, the symmetry computation finished within one second, for ≥ 90% of the tasks within ten seconds).

As a natural follow-up question, given that symmetries exist in many FOND planning domains, we investigate to which extent the size of the search spaces can be reduced when applying CLAO⇤ , and whether the reduction pays off in lower runtime. To address these questions, we provide scatterplots for the number of generated nodes and the runtime (including the time for the symmetry precomputation) in Figure 4 and 5.

A dot below the diagonal means that FD-LAO⇤ generates more nodes (or needs more time, respectively) than CLAO⇤ , and a dot above the diagonal means the opposite.

Figure 4 shows that the number of generated nodes with CLAO⇤ is mostly as high as for FD-LAO⇤ for most tasks. In addition, in several tasks CLAO⇤ generates significantly fewer nodes, sometimes by several orders of magnitude. The "straight line" in the plot corresponds to tasks of the FORESTNEW domain, where symmetry reduction particularly applies and reduces the state space.

Figure 5 shows that the reduced state space size in turn pays off in significantly reduced runtimes, again by orders of magnitude in several tasks. The runtimes include a slight overhead per node in order to compute symmetrical representative states. The plot shows in particular that this overhead is negligible compared to the smaller number of generated nodes. Finally, we compare the coverage of FD-LAO⇤ and CLAO⇤ in Figure 6. The table particularly shows the total number of tasks per domain (#T) as well as the number of tasks where symmetries have been found (#S) in parenthesis (#S◁#T).

The fewer number of generated nodes of CLAO⇤ also pays off in a significant coverage increase of 24 additionally solved tasks. Again, we remark that such a coverage increase is remarkable because the task's complexity usually increases exponentially in its size. In particular, CLAO⇤ achieves a significant coverage increase in the FAULTS-NEW domain (21 additionally solved tasks). The domains FOREST-NEW and BLOCKSWORLD show that the per-node overhead of symmetry reduction can also lead to a slight coverage decrease.

Finally, we also compared the sizes of the policies i.e., the number of state-action pairs needed to store the strong cyclic plan found by FD-LAO⇤ and CLAO⇤ . The plot is depicted in Figure 7. We observe that the sizes are often similar, although canonical policies are sometimes significantly more compact.

Overall, our experiments show that symmetry reduction can be very beneficial for FOND planning: Symmetries do occur in various domains, they can mostly be computed efficiently, and the resulting smaller state spaces often allow CLAO⇤ to solve more tasks than FD-LAO⇤ .

As a side effect of our experiments, we have also observed that the base implementation FD-LAO⇤ of LAO⇤ in the Fast Downward planning system has already shown promising performance compared to myND. We have thus also presented a new and competitive LAO⇤ -based FOND planner, making multiple Fast Downwards features available to the FOND planning community.

6 Conclusion

We have lifted symmetry reduction from classical planning with A⇤ to FOND planning with LAO⇤ . Our experimental evaluation has shown that the resulting algorithm CLAO⇤ is beneficial compared to pure LAO⇤ on a variety of common FOND planning domains. In the future, motivated by the encouraging results, it will be interesting to investigate the further potential of pruning methods for FOND planning with LAO⇤ , with a particular focus on the question whether synergy effects of different pruning methods can be achieved.

Acknowledgments

This work was partially supported by the Swiss National Science Foundation (SNSF) as part of the project "Automated Reformulation and Pruning in Factored State Spaces (ARAP)".