Learning Generalized Policies for Fully Observable Non-Deterministic Planning Domains

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.

1. For every goal state s: V (s, 0)
2. For every alive state s: Exactly-1d∈N : {V (s, d)}
3. For every transition (s, s′ ):

1. For every alive state s and dead state s′ : ¬Good(s, s′ )
2. For every goal state s and non-goal state s′ :

1. For every alive state s and dead state s′ :

1. 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

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].

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.

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.