--- title: "Learning Generalized Policies for Fully Observable Non-Deterministic Planning Domains" authors: - "Till Hofmann" - "Hector Geffner" doi: "10.24963/ijcai.2024/744" url: "https://ijcai.org/proceedings/2024/744" pdf: "https://ijcai.org/proceedings/2024/0744.pdf" venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence" year: 2024 pages: "6733-6742" track: "Main Track" keywords: - "Planning and Scheduling: PS: Learning in planning and scheduling" - "Planning and Scheduling: PS: Planning under uncertainty" --- # Learning Generalized Policies for Fully Observable Non-Deterministic Planning Domains Till Hofmann, Hector Geffner *Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 6733-6742. DOI: [10.24963/ijcai.2024/744](https://doi.org/10.24963/ijcai.2024/744) ## Abstract General policies represent reactive strategies for solving large families of planning problems like the infinite collection of solvable instances from a given domain. Methods for learning such policies from a collection of small training instances have been developed successfully for classical domains. In this work, we extend the formulations and the resulting combinatorial methods for learning general policies over fully observable, non-deterministic (FOND) domains. We also evaluate the resulting approach experimentally over a number of benchmark domains in FOND planning, present the general policies that result in some of these domains, and prove their correctness. The method for learning general policies for FOND planning can actually be seen as an alternative planning FOND planning method that searches for solutions not in the given state space but in an abstract state space defined by features that must be learned as well. ## Full text ## 1 Introduction General policies express reactive strategies for solving large families of planning problems such as all Blocks world problems [Srivastava et al., 2008; Hu and De Giacomo, 2011; Belle and Levesque, 2016; Bonet and Geffner, 2018; Illanes and McIlraith, 2019; Celorrio et al., 2019]. Methods for learning such policies have been developed successfully for classical domains appealing to either combinatorial or deep learning approaches [Rivlin et al., 2020; Bonet et al., 2019; St˚ahlberg et al., 2022a]. While the learning methods do not guarantee that the resulting general policies are correct and will solve all the problems in the target class, the policies obtained from combinatorial methods are more transparent and can be analyzed and shown to be correct on an individual basis [Franc`es et al., 2021; Drexler et al., 2022b]. Methods for learning general policies for Markov Decision Problems (MDPs) have also been developed [Toyer et al., 2020; Bajpai et al., 2018; Groshev et al., 2018; Chevalier-Boisvert et al., 2019], in most cases relying on deep learning and deep reinforcement learning (DRL) techniques [Goodfellow et al., 2016; Sutton and Barto, 1998; Franc¸ois-Lavet et al., 2018], but the performance of the learned policies is evaluated experimentally as their correctness cannot be assessed. The goal of this work is to extend the combinatorial approaches developed for learning general policies for classical domains to non-deterministic, fully observable (FOND) domains [Cimatti et al., 2003]. The motivations are twofold. On the one hand, FOND planning is closely related to both classical andMDP planning. Indeed, the FOND planners that scale up best are those relying on classical planners [Muise et al., 2012; Yoon et al., 2007; Muise et al., 2024], and the policies that reach the goal states of an MDP with probability 1 are precisely the policies that solve the FOND problem underlying the MDP; i.e., where the possible transitions are the ones that have positive probabilities [Geffner and Bonet, 2013; Ghallab et al., 2016]. This means that FOND models capture the qualitative structure of Goal MDPs, and that general policies that solve classes of FOND problems will also solve correctly a larger class of Goal MDPs. On the other hand, while the best FOND planners rely on classical planners, FOND planning is harder, requiring not just exponential time but exponential space. 1 So the formal relation between the two planning tasks is not so clear. Interestingly, this relation becomes clearer in the generalized setting, where, as we will see, generalized FOND planning reduces to generalized classical planning plus FOND dead-end detection. In other words, a general policy for a class Q of FOND problems can be obtained from a general policy for a class QD of classical problems obtained by the outcome relaxation from those in Q [Yoon et al., 2007; Muise et al., 2012], along with a description of the dead-end states to be avoided. The resulting method for learning general policies for FOND planning can also be seen as an alternative FOND planning method that solves a FOND problem by solving a number of classical problems, not in the given state space but in an abstract space defined by features that must be learned as well. The rest of the paper is organized as follows. We review related work and background first, and then introduce general FOND policies and a method for learning them, followed by an evaluation and analysis of the results. 1 Classical planning is PSPACE-hard [Bylander, 1994], while FOND planning is EXP-hard [Littman et al., 1998; Rintanen, 2004]. ## 2 RelatedWork General Policies for Classical Domains. The problem of learning general policies for classical domains has a long history [Khardon, 1999; Mart´ın and Geffner, 2004; Fern et al., 2006], and general policies have been formulated in terms of logic [Srivastava et al., 2011a; Illanes and McIlraith, 2019], and more recently in terms of features and rules [Bonet and Geffner, 2018; Bonet et al., 2019] that can be learned using combinatorial methods [Franc`es et al., 2021]. The rule language has also been used to express problem decompositions or sketches [Drexler et al., 2021; Drexler et al., 2022b], and in this work it will be used to express general policies for FOND problems. General Policies for MDPs. Deep learning (DL) and deep reinforcement learning (DRL) methods have also been used to learn general policies for classical domains [Groshev et al., 2018; Chevalier-Boisvert et al., 2019; Rivlin et al., 2020; St˚ahlberg et al., 2022b; St˚ahlberg et al., 2023] and MDPs [Boutilier et al., 2001; Wang et al., 2008; van Otterlo, 2012; Toyer et al., 2020; Bajpai et al., 2018; Rivlin et al., 2020; Sanner and Boutilier, 2009]. DL and DRL methods scale up better than combinatorial methods and do not need to assume an existing pool of features, but the resulting policies are not transparent and cannot be understood or shown to be correct. FOND Planning. FOND planning has become increasingly important as a way of solving other types of problems, including MDPs [Teichteil-K¨onigsbuch et al., 2010; Camacho et al., 2016], problems with extended temporal goals [Patrizi et al., 2013; Camacho et al., 2019; Bonassi et al., 2023] and generalized planning problems [Srivastava et al., 2011b; Bonet et al., 2017]. FOND planners rely on different techniques like OBDDs [Cimatti et al., 2003; Kissmann and Edelkamp, 2009], SAT [Geffner and Geffner, 2018], graph search [Mattm¨uller et al., 2010; Ram´ırez and Sardina, 2014; Pereira et al., 2022], and classical planning algorithms [Kuter et al., 2008; Fu et al., 2011; Muise et al., 2012; Muise et al., 2024], but problems are solved individually from scratch. Dead-Ends. Dead-ends in planning refer to states from which there is no solution. There has been work in learning to identify dead-ends in classical planning [Lipovetzky et al., 2016; Steinmetz and Hoffmann, 2017], and in FOND and MDP planning [Kolobov et al., 2010; Camacho et al., 2016]. Closer to this work is the learning of general dead-end representations [St˚ahlberg et al., 2021]. While dead-ends in the all-outcome relaxation of FOND problems [Yoon et al., 2007] are dead-ends of the FOND problem, the reverse is not true. ## 3 Background We review classical, generalized, and FOND planning. ## 3.1 Classical Planning A classical planning problem is a pair P = ⟨D, I⟩, where D is a first-order domain and I contains information about a domain instance [Geffner and Bonet, 2013; Ghallab et al., 2016; Haslum et al., 2019]. The domain D is a set of action schemas involving a number of domain predicates. The action schemas have preconditions and positive effects expressed by atoms p(x1, . . . , xk) and the negative (delete) effects are negations of such atoms, where p is a predicate symbol of arity k, and each term xi is a schema argument. The instance information is a tuple I = ⟨O, s0,G⟩ where O is a set of objects (constants); s0 is the initial state, and G is the goal. The ground atoms p(o1, . . . , ok) in the problem instance P = ⟨D, I⟩ are the atoms p(x1, . . . , xk) that result from replacing the terms xi by objects oi ∈ O, and the ground actions result from grounding the action schemas in a similar way. The states s are sets of ground atoms; those which are true in the state. The initial state s0 is a set of ground atoms, while G is a set of ground goal atoms. A classical planning problem P = ⟨D, I⟩ defines a state model M = ⟨S, s0, SG,Act,A, f⟩ where S is the set of states, s0 ∈ S is the initial state, SG ⊆ S is the set of goal states, Act is a set of (ground) actions, A(s) ⊆ Act is the set of actions applicable in the state s, and f(a, s) for a ∈ A(s) is a deterministic state transition function. In the model M(P) determined by P, the states s ∈ S are collection of ground atoms fromP, s0 is given, SG contains the states that include G, Act is the set of ground actions, a ∈ A(s) if the preconditions of a are true in s, and s′ = f(a, s) if a ∈ A(s) and s′ contains the positive effects of a and the atoms in s except those deleted by a. It is convenient to consider non-deterministic policies for classical planning problems instead of (open loop) plans. A policy π for a problem P is a partial function mapping states s of P into sets π(s) of actions from P , possibly empty. A πtrajectory in P is a sequence of states s0, . . . , sn that starts in the initial state of P such that si+1 = f(ai, si) if ai ∈ A(si) and ai ∈ π(si). The trajectory is cyclic if it contains the same state infinitely often and maximal if (1) sn is the first goal state of the sequence, (2) it is cyclic and does not contain goal states, (3) there is no action an in both π(sn) and A(sn), or (4) π(sn) is undefined. The policy π solves P if the maximal π-trajectories all reach a goal state of P. ## 3.2 Generalized Classical Planning Departing slightly from previous work, a general policy π for a class Q of classical instances over the same domain is taken to be a mapping that assigns a (concrete) policy πP to each problem P in Q. The general policy π solves Q if πP solves P for each P in Q. A general policy π can be represented in many forms from formulas or rules to value functions. Following [Bonet and Geffner, 2018; Bonet et al., 2019], we consider general policies π for classes of problems Q expressed by sets of rules C ↦→ E in terms of a collection Φ of Boolean features p and numerical features n that take value in the non-negative integers. The condition C is a set (conjunction) of Boolean feature conditions and the effect description E is a set (conjunction) of feature value changes. A Boolean feature condition is of the form p, ¬p, n = 0, and n > 0 for Boolean and numerical features p and n in Φ, and feature value changes are of the form p, ¬p, p? for Boolean p, and n↓, n↑, and n? for numerical n. The general policy π for a class of problems Q defined by a set R of rules C ↦→ E determines for each problem P in Q the policy πP that maps a reachable state s in P into the set of actions πP (s), where a ∈ πP (s) iff a is applicable in s, a ∈ A(s), and the successor state s′ = f(a, s) is such that the transition (s, s′ ) satisfies a rule in R. The transition (s, s′ ) satisfies a rule C ↦→ E if all feature conditions in C are true in s, and the values of the features change from s to s′ according to E; i.e., if p (resp. ¬p) is in E, then p(s′ ) = 1 (resp. p(s′ ) = 0), if n↓ (resp. n↑) is in E, n(s) > n(s′ ) (resp. n(s) < n(s′ )), if p (resp. n) is not mentioned at all in E, p(s) = p(s′ ) (resp. n(s) = n(s′ )), and if n=0 (resp. n>0) is in E, n(s′ ) = 0 (resp. n(s′ ) > 0). The transition (s, s′ ) satisfying rule R is also said to be compatible with rule R and if (s, s′ ) is compatible with some rule R of policy π, it is called compatible with the policy π. Methods for learning rule-based general policies for classical planning from small training instances have been developed [Bonet et al., 2019; Franc`es et al., 2021]. For this, a set of rules involving a set of features of minimum complexity is obtained by finding a satisfying assignment to a propositional theory T(S,F) of minimum cost, where S is the collection of state transitions appearing in the training instances, and F is a large pool of features obtained from the domain predicates in a domain-independent manner using a description logic grammar [Baader et al., 2008]. The complexity of feature f in F is given by the number of grammar rules needed to generate the unary predicate p(x) associated with f. Such unary predicate gives rise to the numerical feature np whose value in a state s is given by the number of objects o for which p(o) is true in s, and the Boolean feature bp that is true in s if np is positive in s. Since problems P in the target class Q often have different goals, it is assumed that the states s in P are extended with a suitable "copy" of the goal atoms; for each goal atom p(o1, . . . , ok), the states s in P are extended with the atom pG(o1, . . . , ok) where pG is a new predicate [Mart´ın and Geffner, 2004]. ## 3.3 FOND Planning A FOND model is a tuple M = ⟨S, s0, SG, Act, A, F⟩ similar to the one underlying classical planning except that the state transition function F is non-deterministic and maps an action a applicable in a state s into a non-empty set of successor states s′ ∈ F(a, s). The syntax for FOND problems is an extension of the syntax for classical planning where the actions a ∈ A are sets a = {b1, . . . , bk} of classical, deterministic actions bi, all sharing the same preconditions. The application of a results in the random application of one of the actions bi so that if a ∈ A(s), F(a, s) = {f(b1, s), . . . , f(bk, s)}. A (non-deterministic) policy π for a FOND problem P is a partial function that maps states into sets of actions of P. The π-trajectories s0, . . . , sn for FOND problems P are defined in the same way as for classical problems except that for each ai ∈ π(si), the condition si+1 = f(ai, si) is replaced by si+1 ∈ F(ai, si). In addition, a notion of fairness is needed in FOND planning that can be specified by considering π-trajectories that include the actions as s0, a0, s1, a1, . . . , sn where ai ∈ π(si). One such trajectory is deemed fair if it is finite, or if it is infinite, and infinite occurrences of states si followed by the same action ai are in turn followed by each of the possible successor states si+1 ∈ F(ai, si) an infinite number of times. A policy π is a strong cyclic solution or simply a solution of P if the maximal π-trajectories that are fair all reach the goal. ## 3.4 Dead-Ends and Deterministic Relaxations A state s is reachable in a classical or FOND problem P if there is a trajectory s0, . . . , sn that reaches s, where s = sn and si+1 = f(ai, si) or si+1 ∈ F(ai, si) for i = 0, . . . , n-1 and suitable actions ai in P. For a reachable state s in P, P[s] defines the problem that is like P but with initial state s. A reachable state s in P is alive if P[s] has a solution and a dead-end otherwise. Since a general policy π is often aimed at solving all solvable instances Q in a given domain, it is natural to ask for the class Q to be closed, in the sense that if P is in Q, then P [s] is in Q if s is not a dead-end. The set of deadends in a FOND problem P is related to the set of dead-end states in the classical problem PD that results from P when each non-deterministic action a = {b1, . . . , bm} is replaced by the set of deterministic actions b1, . . . , bm. The classical problem PD is the so-called deterministic relaxation or all-outcome relaxation [Yoon et al., 2007] and it plays an important role in FOND planners that rely on classical planning algorithms [Muise et al., 2012]. Clearly, if s is a dead-end state in PD, s will be a dead-end state in the FOND problem P, but the inverse implication is not true. ## 4 General Policies for FOND Planning We consider the semantics of general FOND policies and the language to describe them. ## 4.1 Semantical Considerations The semantics of general policies for classes Q of FOND problems is clear and direct: a general policy π for Qmust determine a policy πP for each problem P in Q, and π solves Q if each problem P in Q is solved by πP ; i.e., if πP is a strong cyclic policy for P. The language for representing general policies for classes of FOND problems, however, is a bit more subtle than in the case of classical planning. Nonetheless, a tight relation between general policies for FOND problems and general policies for classical problems can be established that will serve to motivate the language for expressing and then learning general FOND policies. Let Q be a collection of solvable FOND problems P that is closed in the following sense: if P is in Q and s is an alive state reachable in P , then P [s] is also in Q. Let QD stand for the determinization of Q; namely, the collection of classical problems PD obtained from the deterministic (all-outcome) relaxation of the FOND problems P in Q. Let us also say that a general policy πD for the determinization QD of Q is safe in PD if for every reachable state s of PD and every (deterministic) action bi ∈ πD(s), there is a (non-deterministic) action a such that bi ∈ a and no s′ ∈ F(a, s) is a dead-end. Finally, πD is safe in QD if it is safe in every PD ∈ QD. We can show the following relation between the general policies that solve the class of FOND problems Q and the general policies that solve the class of classical problems QD: 2 2 Proofs can be found in [Hofmann and Geffner, 2024b]. Theorem 1. Let Q be a collection of solvable FOND problems P that is closed, and let QD be determinization of Q. - (1) If π is a general policy that solves the FOND problems Q, a general safe policy πD can be constructed from π that solves the class of classical problems QD. - (2) If πD is a general safe policy that solves the classical problems QD, a general policy π that solves the FOND problems Q can be constructed from πD . This result expresses a basic intuition and the conditions that make the intuition valid; namely, that the uncertainty in the action effects of FOND problems can be "pushed" as uncertainty in the set of possible initial states, resulting in a collection of classical problems, and hence, a generalized classical planning problem. This suggests that one way to get a general policy for a class Q of FOND problems is by finding a general policy for the classical problems in the determinization QD. The theorem qualifies this intuition by requiring that the policy that solves QD must be safe and not visit a deadend state of P, because a state may be a dead-end in P but not in its determinization PD. The intuition that FOND planning can leverage classical planning in this way is present in a slightly different form in one of the most powerful FOND planners [Muise et al., 2012]. The correspondence between FOND and classical planning can be captured more explicitly in the generalized planning setting as a FOND problem does not map into a single classical planning problem but into a collection of them. ## 4.2 Expressing General FOND Policies The correspondence captured by Theorem 1 implies that general policies π for a class of FOND problems Q can be obtained from the general policies π′ for QD that are safe, i.e., those policies that avoid dead-ends in the "original" FOND problem P . This observation suggests that a suitable language for defining general FOND policies can be obtained by combining the rule language for describing general policies for classical domains with constraints that ensure that the general policies that solve the classical problems QD are safe and do not visit dead-end states of the FOND problem: Definition 1. The language for representing a general policy over a class Q of FOND problems is made up of a set R of rules C ↦→ E like for general classical policies, and a set of constraints B, each one being an (implicit) conjunction of Boolean feature conditions like C. Both the rules R and the constraints B are defined over a set Φ of Boolean and numerical features that are well defined over the reachable states of the problems P ∈ Q. The general FOND policy defined by a pair of rules R and constraints B is as follows: Definition 2. A set of rules R and constraints B define a general FOND policy π = πR,B over Q such that in a problem P ∈ Q, the concrete policy πP is such that a ∈ πP (s) iff - there is a state s′ ∈ F(a, s) such that the transition (s, s′ ) satisfies a rule C ↦→ E in R, and - there is no state s′ ∈ F(a, s) such that s′ satisfies a constraint in B. Let us say that a set of constraints B is sound relative to a class of FOND problems Q if every reachable dead-end state s in a problem P in Q satisfies a constraint in B. Furthermore, a general classical policy π is B-safe if for every reachable state s and every (deterministic) action bi ∈ π(s), there is a (non-deterministic) action a such that bi ∈ a and no s′ ∈ F(a, s) satisfies a constraint in B. The basic idea of the method for learning general FOND policies that we will pursue can then be expressed as follows: Theorem 2. Let Q be a class of FOND problems, QD its determinization, and B a sound set of constraints relative to Q. If the rules R encode a general classical policy that solves QD which is B-safe, then the general FOND policy πR,B that follows from Definition 2 solves Q. ## 5 Learning General FOND Policies Following Theorem 2, we will learn general policies πR,B that solve classes of FOND problems Q as follows: we sample a subclass of small FOND problems Q′ from Q and learn rules R and constraints B such that the general policy πR solves the classical problems in Q′D and is B-safe for a sound set of constraints B. With Definition 2, we then obtain a general FOND policy πR,B that solves the FOND problems in Q′ (but not necessarily all FOND problems in the target class Q). By looking for the simplest such policies in terms of the cost of the features involved, we will see that general policies that solve Q can be obtained. ## 5.1 Min-Cost SAT Formulation Following [Franc`es et al., 2021; Bonet et al., 2019], the problem of learning a general policy for a class of classical problems Q′D is cast as a combinatorial optimization problem, and more specifically as min-cost SAT problem over a propositional theory T = T(S,F) where S is the set of (possible) state transitions (s, s′ ) over the instances Pi in Q with states Si, and F is the pool of features constructed from predicates in the common domain of these instances. The policy rules R are then extracted from the transitions (s, s′ ) that are labeled as "good" in the min-cost satisfying assignment of T by looking at how the selected features change across the transitions. The constraints B will be extracted from T by enforcing a separation between the states that are dead-ends in Q′ from those that are not. The states appearing in S are prepartitioned into alive, dead-end, and goal states, as explained below in Section 5.2. The cost of an assignment is given by adding the costs of the features selected from the pool F. Every feature f ∈ F has a weight w(f) defined by the number of grammar rules needed to derive the unary predicate p(x) that defines f. The numerical feature np expresses the number of grounded p(o) atoms in a state s (i.e., the number of objects that satisfy p in s), while the Boolean feature bp is true if np is positive. The propositional variables in T(S, F) are the following: - Good(s, s′ ) is true if the transition (s, s′ ) is good, - Select(f) is true if the feature f is selected, - V (s, d) is true if the distance of s to a goal is at most d, where 0 ≤ d ≤ |Si| for s ∈ Si. The formulas in T(S,F) are in turn: - (1) For every alive state s: where a ∈ Safe(s) if no s′ ∈ F(a, s) is a dead-end. - (2) For every goal state s: V (s, 0) - (3) For every alive state s: Exactly-1d∈N : {V (s, d)} - (4) For every transition (s, s′ ): - (5) For every alive state s and dead state s′ : ¬Good(s, s′ ) - (6) For every goal state s and non-goal state s′ : - (7) For every alive state s and dead state s′ : - (8) For all transitions (s1, s′1 ) and (s2, s′2 ): where The expressions �f(s)� and ∆f(s, s′ ) stand for the value of feature f in s, and the way in which the value of f changes in the transition from s to s′ (up, down, and same value, for both Boolean and numerical features). The formulas express the following. For every alive state, there must be a good transition such that the corresponding FOND action is safe, i.e., none of the outcomes lead to a dead-end (1) and such that one good transition leads towards a goal (2, 3, 4). A transition leading to a dead-end may never be good (5). Furthermore, the selected features must be able to distinguish goal from non-goal states (6), alive states from dead-ends (7) and good from non-good transitions (8). The satisfying assignments of T(S,F) yield the rules R and the constraints B such that B is sound relative to the sampled class Q′ of FOND problems, and the classical policy πR given by the rules R constitute a general policy for the classical problems Q′D that is B-safe. From Theorem 2, the resulting πR,B FOND policy that follows from Definition 2 solves the collection of FOND problems Q′ . ## Algorithm 1 Dead-End Detection ``` Input: FOND model M(P ) = ⟨S, s0, SG, Act , A, F ⟩ Output: FOND dead-end set D ⊆ S 1: D← ∅; 2: repeat 3: for all s ∈ S \ D do 4: for all a ∈ A(s) do 5: if F (a, s) ∩ D ̸= ∅ then 6: Remove a from A(s) 7: for all s ∈ S \ D do 8: if ¬∃path s a1 -→ . . . ak -→ sg. ai ∈ A(si), sg ∈ SG then 9: Add s to D 10: until D does not change 11: return D ``` Theorem 3. The theory T(S,F) is satisfiable iff there is a general FOND policy πR,B over the features in the pool F that solves the set of sampled FOND problems Q′ , such that the selected features distinguish dead, alive, and goal states. Since we aim to learn a policy that generalizes beyond the sample instances, the sum of the weights w(f) of selected features f is minimized to penalize overfitting. Given a satisfying assignment T(S,F), the rules R and the constraints B that define the general FOND policy πR,B are extracted as follows. First, the features Φ are obtained from the true Select(f) atoms. Then, for each true atom Good(s, s′ ), a rule C ↦→ E is obtained where C is the Boolean feature valuation true in s (literals p, ¬p, n = 0, or n > 0), and n↑ ∈ E if ∆n(s, s′ ) = ↑, n↓ ∈ E if ∆n(s, s′ ) = ↓, p ∈ E if ∆p(s, s′ ) = ↑, and ¬p ∈ E if ∆p(s, s′ ) = ↓. Duplicate rules are pruned. Finally, the state constraints B are extracted from the Boolean feature evaluations of the dead-end states. ## 5.2 Dead-End Detection To identify the sets D of dead-end states in the sampled FOND problems Pi, similar to [Daniele et al., 2000], we iteratively exclude every action a from the set of applicable actions A(s) when a state s′ ∈ F(a, s) is in D, and place s in D when there is no path from s to the goal using the applicable sets A(s) that result. The resulting algorithm, shown in Algorithm 1, is sound and complete: Theorem 4. Algorithm 1 is sound and complete, i.e., state s ∈ D iff there is no solution of the FOND problem P [s]. ## 6 Evaluation We evaluate the approach on a number of FOND benchmarks, and analyze some of the learned general policies. 3 ## 6.1 Experimental Results We modeled and solved the min-cost SAT problem represented by the theory T(S,F) as an Answer Set Program (ASP) [Lifschitz, 2016] in clingo [Gebser et al., 2011]. We use the library pddl [Favorito et al., 2023] for PDDL parsing and DLPlan [Drexler et al., 2022a] for feature generation in the same way as [Drexler et al., 2022b; Franc`es et al., 2021]. As optimizations, instead of using the ranking V (s, d), we incrementally label all states where all selected transitions lead to the goal as safe and require that all alive states are also safe. Additionally, we do not try to distinguish all dead states from alive states and instead only compare alive states to critical states, which are those states that are dead-ends but have an incoming transition from an alive state. Finally, we preprocess the state space S by pruning all dead states that are not critical. 3 The source code, benchmark domains, and results are available at [Hofmann and Geffner, 2024a]. Table 1: Evaluation results, where |P| is the total number of problems, |T| is the number of problems used in training, and |S| is the number of solved problems, that includes training and testing. |O|T is the maximum number of objects in all training instances, |O|P is the maximum number of objects in all instances, tsolve is the solver's CPU time needed for finding the best policy, twall is the total wall time, mem is the maximum memory consumption, |F| is the size of the feature pool, |Φ| is the number of selected features, |C| is the number of constraints, k∗ is the maximum cost of the selected features, and cΦ is the total cost of all selected features. When the incremental learning approach does not deliver FOND policies that generalize to all problems in the distribution, the reason for the failure is indicated: I indicates that the number of facts exceeded the clingo limits, C indicates that no solution was found with max complexity 15, and M indicates that the solver ran out of memory. | Q | |P | | |S| | |T | | |O|T | |O|P | tsolve/s | twall/s | mem/MB | |F| | |Φ| | |C| | k∗ | cΦ | |--------------------|------------------|-----------------|------------------|------------------|------------------|------------|-----------|----------|-----------------|-----------------|-----------------|------|------| | acrobatics | 18 | 18 | 3 | 3 | 9 | <0.1 | 139 | 49 | 23 | 3 | 1 | 4 | 6 | | beam-walk | 9 | 9 | 2 | 3 | 9 | <0.1 | 13 | 41 | 22 | 2 | 0 | 4 | 5 | | blocks3ops | 95 | 95 | 4 | 4 | 20 | 224 | 1968 | 22237 | 194 | 3 | 0 | 5 | 11 | | blocks-clear | 95 | 95 | 2 | 3 | 20 | 1 | 37 | 185 | 34 | 2 | 0 | 4 | 6 | | blocks-on | 190 | 190 | 2 | 3 | 20 | 116 | 158 | 1966 | 704 | 3 | 0 | 6 | 11 | | doors | 19 | 19 | 5 | 7 | 33 | 78 | 1476 | 2805 | 625 | 4 | 1 | 10 | 19 | | first-responders | 99 | 15M | 2 | 5 | 36 | 2020 | 13929 | 212496 | 332 | 5 | 2 | 7 | 20 | | islands | 300 | 300 | 4 | 32 | 83 | 3903 | 13871 | 72895 | 1182 | 4 | 1 | 7 | 13 | | miner | 69 | 13I | 2 | 9 | 184 | 1071294 | 48964 | 199942 | 1073 | 8 | 4 | 6 | 28 | | spiky-tireworld | 170 | 36I | 3 | 6 | 23 | 5162 | 9114 | 73985 | 479 | 8 | 5 | 8 | 36 | | tireworld | 980 | 7C | 1 | 3 | 100 | <0.1 | 382 | 370 | 27 | 5 | 4 | 4 | 12 | | triangle-tireworld | 10 | 1I | 1 | 6 | 231 | <0.1 | 1868 | 70 973 | 27 | 3 | 1 | 4 | 9 | The FOND domains considered were taken from the FOND-SAT distribution [Geffner and Geffner, 2018], leaving out domains with unsupported features. All instances are either randomly generated or taken from the original benchmarks. In acrobatics, beam-walk, and doors, we augmented the existing problem set with smaller instances. The problems in the blocks variants are generated by scaling from small problems with only three blocks up to 20 blocks. In blocks3ops, the goal is to build a tower of blocks using a three-operator encoding (without a gripper). The domains blocks-clear and blocks-on use a four-operator encoding (including the gripper) and the goal is to clear a single block and stack a single pair of blocks. In islands, we created five variations of each problem from the original problem set. Miner and triangle-tireworld use the original problem set, while the instances for spiky-tireworld and tireworld are randomly generated. For all domains, the largest generated instances are of similar size or larger than the largest instances in the original benchmarks. All experiments were run on Intel Xeon Platinum 8352M CPUs with 32 threads, a memory limit of 220 GB, and a maximal feature complexity cmax = 15. The results are shown in Table 1. The suite of problems P in each domain is ordered by size, with the smallest problems used for training and the largest problems for testing. More precisely, starting with a singleton training set consisting of the smallest instance of P , the solver learns a new policy and iteratively tests whether the policy solves the next problem. If this validation fails, the failed instance is added to the training set and the process repeats. Since the instances in these domains become quite large and the min-cost SAT solver does not scale up to large instances, if the policies learned from the smallest instances do not generalize, the approach fails, as shown by the rows in the table with coverage numbers |S| in bold; namely, 5 of the 12 domains. In 7 of the 12 domains, on the other hand, the learning method delivers general FOND policies, some of which will be shown to be correct in the next section. ## 6.2 Correctness For proving the correctness of learned general FOND policies, we adapt a method from [Franc`es et al., 2021; Seipp et al., 2016] based on complete and descendent policies: Definition 3. A FOND policy π is - (1) dead-end-free if no π-trajectory visits a dead-end state, - (2) complete for an instance P if for every alive state s, we have π(s) ∩ A(s) ̸= ∅, - (3) descending over P if there is some function γ that maps states of P to a totally ordered set U such that for every alive state s and action a ∈ π(s) ∩ A(s), we have γ(s′ ) < γ(s) for some s′ ∈ F(a, s). Typically, one can show that a FOND policy π is descending by providing a fixed tuple ⟨f1, . . . , fn⟩ of state features. If for every π-compatible transition (s, s′ ), we have ⟨f1(s′ ), . . . , fn(s′ )⟩ < ⟨f1(s), . . . , fn(s)⟩ with lexicographic order <, then π is descending. It can be shown that such a policy indeed solves P : Theorem 5. If π is a policy that is dead-end-free, complete and descending for an instance P , then π solves P . ## Acrobatics An acrobat needs to reach the end of a beam consisting of n segments. The only ladder to climb up the beam is at its beginning. The acrobat may walk left or right on the beam and on the ground, climb up or down if there is a ladder, and jump on the beam. When walking on the beam, the acrobat may fall down. The acrobat may skip a segment by jumping over it, but she may fall down and break her leg while doing so. Once the leg is broken, she may no longer move. The learned policy πacro uses three features: (1) the distance d ≡ dist(position, next-fwd, positionG) between the current position and the goal position, (2) a Boolean feature U ≡ |up| which is true if the agent is currently on the beam, (3) a Boolean feature B ≡ |broken-leg| which is true if the agent's leg is broken. The learned policy πacro = πR,B consists of the following rules R: 4 It has a single constraint B = {b1}: If the acrobat is currently on the beam (U), she is not at the goal (d > 0), and the leg is not broken (¬B), then she should decrease the distance to the goal. Otherwise, if she is not on the beam (¬U) and the leg is not broken (¬B), then she should either climb up the ladder or move away from the goal (and therefore closer to the ladder). For the first rule, she may decide to jump to decrease the distance and thereby break her leg. The state constraint forbids this by requiring that she may not end up in a state where she has a broken leg and is not on the beam. Proposition 1. The general policy πacro = πR,B solves the class Qacro of solvable FOND acrobatics problems. ## Doors The player needs to move through a sequence of n rooms, which are connected by doors. Whenever the player goes to the next room, the incoming and outgoing doors of the room may open or close non-deterministically. There are separate actions for moving to the next room depending on whether the door is open or closed. For the last door, if the door is closed, the player needs to use a key, which is located in the first room. The player may not move back. The learned policy πdoors uses four features: (1) a Boolean feature G ≡ |player-at ⊓ final -loc|, which is true if the player is at the final location, (2) a Boolean feature S ≡ |¬∃door-in.player-at|, which is true if the player is at the start location (which does not have any incoming door), (3) a Boolean feature K ≡ |hold-key| which is true if the player is holding the key, (4) a Boolean feature F ≡ |open ⊓ (∃door -out .player -at ) ⊓ ∃door -in.final -loc|, which is true if the player is in the second-last room and the door to the final room is open. 4 The notation C ↦→ E1 | E2 abbreviates the two rules C ↦→ E1 and C ↦→ E2 with the same condition C. The policy πdoors = πR,B uses the following rules R: It uses one constraint B = {b1}: The need for feature F may not be immediately obvious, as it is not necessary for a strong-cyclic policy starting in the initial state. However, it is needed to distinguish dead from alive states, as the state where the player is in the second-last roomwithout a key and the last door is open is also alive: the player may just move through the open door without a key. Similarly, if F is false and the player is not holding the key, then the state is dead if the player is not at the start location. We can show that this policy is a solution for Qdoors: Proposition 2. The general policy πdoors = πR,B solves the class Qdoors of solvable FOND doors problems. ## Islands In Islands, there are two islands connected by a bridge. The person starts on one island while the goal is on the other island. They may swim across but with the risk to drown, from which they cannot recover. Alternatively, they may cross a bridge, but only if there are no monkeys on the bridge. A monkey can be moved to a drop location. The learned policy πislands uses three features: (1) a Boolean feature A ≡ |person-alive|; (2) a numerical feature ddrop ≡ dist(bridge-drop-location ⊓ bridge-road [0], road, person-at), which is the distance to a location that is both drop location and starting point of the bridge; (3) a numerical feature dg, which is the distance to the goal: dg ≡ dist(person-atG, road , person-at ). The policy πislands = πR,B consists of two rules R = {r1, r2}: It uses a single constraint B = {b1}: The agent first moves to the bridge (r2). After it has reached the bridge, it directly crosses it if possible ({dg↓, ddrop↑}). Otherwise, it selects an action that does not have any effect on the features ({}). The only action that is compatible with {} is moving a monkey. As this demonstrates, it is not necessary to encode the monkeys in the policy explicitly. Finally, the only constraint b1 requires that the person never dies. Proposition 3. The general policy πislands = πR,B solves the class Qislands of solvable FOND islands problems. Table 2: Evaluation results for policy learning with transition constraints, using the same notation as in Table 1. | Q | |P | | |S| | |T | | |O|T | |O|P | tsolve/s | twall/s | mem/MB | |F| | |Φ| | |C| | k∗ | cΦ | |--------------------|------------------|-----------------|------------------|------------------|------------------|------------|-----------|----------|-----------------|-----------------|-----------------|------|------| | acrobatics | 18 | 18 | 3 | 3 | 9 | <0.1 | 206 | 49 | 23 | 3 | 1 | 4 | 6 | | beam-walk | 9 | 9 | 2 | 3 | 9 | <0.1 | 16 | 40 | 22 | 2 | 0 | 4 | 5 | | blocks3ops | 95 | 95 | 5 | 4 | 20 | 664 | 4475 | 77722 | 235 | 3 | 0 | 5 | 11 | | blocks-clear | 95 | 95 | 2 | 3 | 20 | 1 | 37 | 185 | 34 | 2 | 0 | 4 | 6 | | blocks-on | 190 | 190 | 2 | 3 | 20 | 87 | 161 | 2021 | 704 | 3 | 0 | 6 | 11 | | doors | 19 | 19 | 3 | 5 | 33 | 1 | 1230 | 1003 | 68 | 3 | 2 | 6 | 11 | | first-responders | 99 | 15I | 2 | 5 | 36 | 1354 | 7577 | 105752 | 332 | 5 | 6 | 7 | 20 | | islands | 300 | 300 | 4 | 32 | 83 | 1889 | 14165 | 73173 | 1182 | 4 | 4 | 7 | 13 | | miner | 69 | 13I | 2 | 9 | 184 | 2468172 | 130980 | 131741 | 1073 | 8 | 61 | 6 | 28 | | spiky-tireworld | 170 | 17I | 3 | 6 | 23 | 115973 | 25454 | 81211 | 1284 | 7 | 36 | 7 | 29 | | tireworld | 980 | 980 | 4 | 5 | 100 | 8112 | 21571 | 72160 | 1804 | 5 | 20 | 8 | 20 | | triangle-tireworld | 10 | 10 | 2 | 15 | 231 | 3905 | 1489 | 107053 | 264 | 4 | 5 | 7 | 1 | ## 7 Variation: Transition Constraints The general FOND policies and learning schema presented above is based on state constraints, which describe states that must be avoided. Alternatively, we can also formulate general policies based on transition constraints. Syntactically, transition constraints are like policy rules and have the form C ↦→ E. However, they describe bad transitions and hence the policy π defined by a set of rules and transition constraints is such that for any P ∈ Q, a ∈ πP (s) if the transition (s′ , s) for some s′ ∈ F(a, s) satisfies a rule, and no state s′′ ∈ F(a, s) satisfies a transition constraint. Formally: Definition 4. The language for representing a general policy with transition constraints over a class Q of FOND problems is made up of a set R of rules C ↦→ E like for general classical policies, and a set of transition constraints T of the same form as rules. Definition 5. A set of rules R and transition constraints T define a transition-constrained general FOND policy π over Q such that a ∈ πP (s), where πP is the concrete policy determined by the general policy π in problem P in Q if - there is a state s′ ∈ F(a, s) such that the transition (s, s′ ) satisfies a rule C ↦→ E in R, and - there is no state s′ ∈ F(a, s) such that the transition (s, s′ ) satisfies a transition constraint C ↦→ E in T . We call a transition (s, s′ ) in a problem P critical if s is alive and s′ is a dead-end. Analogously to state constraints, we say that a set of transition constraints T is sound relative to a class of FOND problems Q, if every critical transition (s, s′ ) in a problem P in Q satisfies a constraint in T , and that a general policy π for a class of classical or FOND problems Q is T-safe if for no instance P in Q, there is a π-trajectory containing a critical transition. Theorem 6. Let Q is a class of FOND problems, let QD be its determinization, and let T be a sound set of transition constraints relative to Q. Then if the rules R encode a general classical policy that solves QD which is T-safe, the rules R and constraints T define a general FOND policy πR,T that solves Q. The experimental results that follow from the use of transition constraints instead of state constraints for defining and learning general FOND policies are shown in Table 2. We can see that in contrast to the state-based variant, the transitionbased variant solves all instances of tireworld and triangletireworld. ## 8 Conclusion We have extended the formulation for learning general policies for classical planning domains to fully-observable nondeterministic domains. The new formulation for expressing and learning FOND policies exploits a correspondence between the general policies that solve a family Q of FOND problems and the general safe policies that solve a family QD of classical problems PD obtained from the all-outcome relaxation (determinization) of the instances P in Q, where the safe policies are those that avoid the dead-end states of P. A representation of the collection of dead-end states is learned along with the features and rules. The resulting safe policies for the family of classical problems PD do not just solve the FOND problems in Q but potentially many other FOND problems as well, like those that result from random perturbations which do not create new dead states. This is because the formulation pushes the uncertainty in the action outcomes into uncertainty in the initial states that are all covered by the general policy that solves QD. The experiments over existing FOND benchmarks show that the approach is sufficiently practical, resulting in general FOND policies that can be understood and shown to be correct. ## Acknowledgements This work has been supported by the Alexander von Humboldt Foundation with funds from the Federal Ministry for Education and Research. It has also received funding from the European Research Council (ERC), Grant agreement No 885107, the Excellence Strategy of the Federal Government and the NRW L¨ander, Germany, and the Knut and Alice Wallenberg (KAW) Foundation under the WASP program. ## References 1. [Baader et al., 2008] Frank Baader, Ian Horrocks, and Ulrike Sat- tler. Handbook of Knowledge Representation, chapter Descrip- tion Logics, pages 135-180. Elsevier, 2008. 2. [Bajpai et al., 2018] Aniket Nick Bajpai, Sankalp Garg, and Mausam. Transfer of deep reactive policies for MDP planning. In NeurIPS, pages 10965-10975, 2018. 3. [Belle and Levesque, 2016] Vaishak Belle and Hector J. Levesque. Foundations for generalized planning in unbounded stochastic domains. In KR, pages 380-389, 2016. 4. [Bonassi et al., 2023] Luigi Bonassi, Giuseppe De Giacomo, Marco Favorito, Francesco Fuggitti, Alfonso Emilio Gerevini, and Enrico Scala. FOND planning for pure-past linear tempo- ral logic goals. In ECAI, pages 279-286. 2023. 5. [Bonet and Geffner, 2018] Blai Bonet and Hector Geffner. Fea- tures, projections, and representation change for generalized planning. In IJCAI, pages 4667-4673, 2018. 6. [Bonet et al., 2017] Blai Bonet, Giuseppe De Giacomo, Hector Geffner, and Sasha Rubin. Generalized planning: Non- deterministic abstractions and trajectory constraints. In IJCAI, pages 873-879, 2017. 7. [Bonet et al., 2019] Blai Bonet, Guillem Francès, and Hector Geffner. Learning features and abstract actions for computing generalized plans. In AAAI, pages 2703-2710, 2019. 8. [Boutilier et al., 2001] Craig Boutilier, Ray Reiter, and Bob Price. Symbolic dynamic programming for first-order MDPs. In IJCAI, pages 690-700, 2001. 9. [Bylander, 1994] Tom Bylander. The computational complexity of STRIPS planning. Artificial Intelligence, 69:165-204, 1994. 10. [Camacho et al., 2016] Alberto Camacho, Christian Muise, and Sheila McIlraith. From FOND to robust probabilistic planning: Computing compact policies that bypass avoidable deadends. In ICAPS, pages 65-69, 2016. 11. [Camacho et al., 2019] Alberto Camacho, Meghyn Bienvenu, and Sheila A. McIlraith. Towards a unified view of AI planning and reactive synthesis. In ICAPS, pages 58-67, 2019. 12. [Celorrio et al., 2019] Sergio Jiménez Celorrio, Javier Segovia- Aguas, and Anders Jonsson. A review of generalized planning. Knowl. Eng. Rev., 34, 2019. 13. [Chevalier-Boisvert et al., 2019] Maxime Chevalier-Boisvert, Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, and Yoshua Bengio. BabyAI: A platform to study the sample efficiency of grounded language learning. In ICLR, 2019. 14. [Cimatti et al., 2003] Alessandro Cimatti, Marco Pistore, Marco Roveri, and Paolo Traverso. Weak, strong, and strong cyclic planning via symbolic model checking. Artificial Intelligence, 147(1):35-84, 2003. 15. [Daniele et al., 2000] Marco Daniele, Paolo Traverso, and Moshe Y. Vardi. Strong cyclic planning revisited. In Recent Advances in AI Planning, pages 35-48, 2000. 16. [Drexler et al., 2021] Dominik Drexler, Jendrik Seipp, and Hector Geffner. Expressing and exploiting the common subgoal struc- ture of classical planning domains using sketches. In ICAPS, pages 258-268, 2021. 17. [Drexler et al., 2022a] Dominik Drexler, Guillem Francès, and Jen- drik Seipp. DLPlan. https://doi.org/10.5281/zenodo.5826139, 2022. https://doi.org/10.5281/zenodo.5826139 18. [Drexler et al., 2022b] Dominik Drexler, Jendrik Seipp, and Hector Geffner. Learning sketches for decomposing planning problems into subproblems of bounded width. In ICAPS, pages 62-70, 2022. 19. [Favorito et al., 2023] Marco Favorito, Francesco Fuggitti, and Christian Muise. pddl. https://ai-planning.github.io/pddl/, 2023. 20. [Fern et al., 2006] Alan Fern, Sungwook Yoon, and Robert Givan. Approximate policy iteration with a policy language bias: Solv- ing relational markov decision processes. JAIR, 25:75-118, 2006. 21. [Francès et al., 2021] Guillem Francès, Blai Bonet, and Hector Geffner. Learning general planning policies from small exam- ples without supervision. In AAAI, pages 11801-11808, 2021. 22. [Franc ¸ois-Lavet et al., 2018] Vincent Franc ¸ois-Lavet, Peter Hen- derson, Riashat Islam, Marc G Bellemare, and Joelle Pineau. An introduction to deep reinforcement learning. Found. Trends. Mach. Learn., 2018. 23. [Fu et al., 2011] Jicheng Fu, Vincent Ng, Farokh B. Bastani, and I-Ling Yen. Simple and fast strong cyclic planning for fully- observable nondeterministic planning problems. In IJCAI, pages 1949-1954, 2011. 24. [Gebser et al., 2011] Martin Gebser, Benjamin Kaufmann, Roland Kaminski, Max Ostrowski, Torsten Schaub, and Marius Schnei- der. Potassco: The potsdam answer set solving collection. AI Communications, 24(2):107-124, June 2011. 25. [Geffner and Bonet, 2013] Hector Geffner and Blai Bonet. A Con- cise Introduction to Models and Methods for Automated Plan- ning. Morgan & Claypool Publishers, 2013. 26. [Geffner and Geffner, 2018] Tomas Geffner and Hector Geffner. Compact policies for fully observable non-deterministic planning as SAT. In ICAPS, pages 88-96, 2018. 27. [Ghallab et al., 2016] Malik Ghallab, Dana Nau, and Paolo Traverso. Automated planning and acting. Cambridge Univer- sity Press, 2016. 28. [Goodfellow et al., 2016] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT Press, 2016. 29. [Groshev et al., 2018] Edward Groshev, Maxwell Goldstein, Aviv Tamar, Siddharth Srivastava, and Pieter Abbeel. Learning gen- eralized reactive policies using deep neural networks. In ICAPS, 2018. 30. [Haslum et al., 2019] Patrik Haslum, Nir Lipovetzky, Daniele Mag- azzeni, and Christian Muise. An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers, 2019. 31. [Hofmann and Geffner, 2024a] Till Hofmann and Hector Geffner. Generalized FOND planning. Zenodo, May 2024. https://doi. org/10.5281/zenodo.11171181. https://doi.org/10.5281/zenodo.11171181 32. [Hofmann and Geffner, 2024b] Till Hofmann and Hector Geffner. Learning generalized policies for fully observable non- deterministic planning domains. http://arxiv.org/abs/2404.02499, 2024. 33. [Hu and De Giacomo, 2011] Yuxiao Hu and Giuseppe De Gia- como. Generalized planning: Synthesizing plans that work for multiple environments. In IJCAI, pages 918-923, 2011. 34. [Illanes and McIlraith, 2019] León Illanes and Sheila A. McIlraith. Generalized planning via abstraction: arbitrary numbers of ob- jects. In AAAI, 2019. 35. [Khardon, 1999] Roni Khardon. Learning action strategies for planning domains. Artificial Intelligence, 113:125-148, 1999. 36. [Kissmann and Edelkamp, 2009] Peter Kissmann and Stefan Edelkamp. Solving fully-observable non-deterministic planning problems via translation into a general game. KI 2009: Advances in AI, pages 1-8, 2009. 37. [Kolobov et al., 2010] Andrey Kolobov, Mausam, and Daniel S. Weld. Sixthsense: Fast and reliable recognition of dead ends in MDPs. In AAAI, pages 1108-1114, 2010. 38. [Kuter et al., 2008] Ugur Kuter, Dana Nau, Elnatan Reisner, and Robert P. Goldman. Using classical planners to solve nondeter- ministic planning problems. In ICAPS, pages 190-197, 2008. 39. [Lifschitz, 2016] Vladimir Lifschitz. Answer sets and the language of answer set programming. AI Magazine, 37(3):7-12, October 2016. 40. [Lipovetzky et al., 2016] Nir Lipovetzky, Christian Muise, and Hector Geffner. Traps, invariants, and dead-ends. In ICAPS, pages 211-215, 2016. 41. [Littman et al., 1998] Michael L. Littman, Judy Goldsmith, and Martin Mundhenk. The computational complexity of probabilis- tic planning. Journal of Artificial Intelligence Research, 9:1-36, 1998. 42. [Martín and Geffner, 2004] Mario Martín and Hector Geffner. Learning generalized policies from planning examples using con- cept languages. Applied Intelligence, 20(1):9-19, 2004. 43. [Mattmüller et al., 2010] Robert Mattmüller, Manuela Ortlieb, Malte Helmert, and Pascal Bercher. Pattern database heuristics for fully observable nondeterministic planning. In ICAPS, 2010. 44. [Muise et al., 2012] Christian Muise, Sheila A. McIlraith, and Christopher Beck. Improved non-deterministic planning by ex- ploiting state relevance. In ICAPS, 2012. 45. [Muise et al., 2024] Christian Muise, Sheila A. McIlraith, and J. Christopher Beck. PRP rebooted: Advancing the state of the art in FOND planning. In AAAI, pages 20212-20221, 2024. 46. [Patrizi et al., 2013] Fabio Patrizi, Nir Lipovetzky, and Hector Geffner. Fair LTL synthesis for non-deterministic systems using strong cyclic planners. In IJCAI, 2013. 47. [Pereira et al., 2022] Ramon Fraga Pereira, André Grahl Pereira, Frederico Messa, and Giuseppe De Giacomo. Iterative depth-first search for FOND planning. In ICAPS, pages 90-99, 2022. 48. [Ramírez and Sardina, 2014] Miquel Ramírez and Sebastian Sar- dina. Directed fixed-point regression-based planning for non- deterministic domains. In ICAPS, 2014. 49. [Rintanen, 2004] Jussi Rintanen. Complexity of planning with par- tial observability. In ICAPS, pages 345-354, 2004. 50. [Rivlin et al., 2020] Or Rivlin, Tamir Hazan, and Erez Karpas. Generalized planning with deep reinforcement learning. arXiv preprint arXiv:2005.02305, 2020. 51. [Sanner and Boutilier, 2009] Scott Sanner and Craig Boutilier. Practical solution techniques for first-order MDPs. Artificial In- telligence, 173(5-6):748-788, 2009. 52. [Seipp et al., 2016] Jendrik Seipp, Florian Pommerening, Gabriele Röger, and Malte Helmert. Correlation complexity of classical planning domains. In IJCAI, pages 3242-3250, 2016. 53. [Srivastava et al., 2008] Siddharth Srivastava, Neil Immerman, and Shlomo Zilberstein. Learning generalized plans using abstract counting. In Proc. AAAI, pages 991-997, 2008. 54. [Srivastava et al., 2011a] Siddharth Srivastava, Neil Immerman, and Shlomo Zilberstein. A new representation and associ- ated algorithms for generalized planning. Artificial Intelligence, 175(2):615-647, 2011. 55. [Srivastava et al., 2011b] Siddharth Srivastava, Shlomo Zilberstein, Neil Immerman, and Hector Geffner. Qualitative numeric plan- ning. In AAAI, 2011. 56. [Ståhlberg et al., 2021] Simon Ståhlberg, Guillem Francès, and Jendrik Seipp. Learning generalized unsolvability heuristics for classical planning. In IJCAI, pages 4175-4181, 2021. 57. [Ståhlberg et al., 2022a] Simon Ståhlberg, Blai Bonet, and Hector Geffner. Learning general optimal policies with graph neural net- works: Expressive power, transparency, and limits. In ICAPS, pages 629-637, 2022. 58. [Ståhlberg et al., 2022b] Simon Ståhlberg, Blai Bonet, and Hector Geffner. Learning generalized policies without supervision using GNNs. In Proc. KR, pages 474-483, 2022. 59. [Ståhlberg et al., 2023] Simon Ståhlberg, Blai Bonet, and Hector Geffner. Learning general policies with policy gradient methods. In KR, pages 647-657, 2023. 60. [Steinmetz and Hoffmann, 2017] Marcel Steinmetz and Jörg Hoff- mann. State space search nogood learning: Online refinement of critical-path dead-end detectors in planning. Artificial Intelli- gence, 245:1-37, 2017. 61. [Sutton and Barto, 1998] Richard Sutton and Andrew Barto. Intro- duction to Reinforcement Learning. MIT Press, 1998. 62. [Teichteil-Königsbuch et al., 2010] Florent Teichteil-Königsbuch, Ugur Kuter, and Guillaume Infantes. Incremental plan aggre- gation for generating policies in mdps. In AAMAS, pages 1231- 1238, 2010. 63. [Toyer et al., 2020] Sam Toyer, Sylvie Thiébaux, Felipe Trevizan, and Lexing Xie. Asnets: Deep learning for generalised planning. Journal of Artificial Intelligence Research, 68:1-68, 2020. 64. [van Otterlo, 2012] Martijn van Otterlo. Solving relational and first-order logical markov decision processes: A survey. In Rein- forcement Learning, pages 253-292. Springer, 2012. 65. [Wang et al., 2008] Chenggang Wang, Saket Joshi, and Roni Khardon. First order decision diagrams for relational MDPs. Journal of Artificial Intelligence Research, 31:431-472, 2008. 66. [Yoon et al., 2007] Sungwook Yoon, Alan Fern, and Robert Givan. FF-replan: A baseline for probabilistic planning. In ICAPS, pages 352-359, 2007.