Generalized Planning: Non-Deterministic Abstractions and Trajectory Constraints

1 Introduction

Generalized planning, where a single plan works for multiple domains, has been drawing sustained attention in the AI community [Levesque, 2005; Srivastava et al., 2008; Bonet et al., 2009; Srivastava et al., 2011a; Hu and Levesque, 2010; Hu and De Giacomo, 2011; Bonet and Geffner, 2015; Belle and Levesque, 2016]. This form of planning has the aim of finding generalized solutions that solve in one shot an entire class of problems. For example, the policy "if block x is not clear, pick up the clear block above x and put it on the table" is general in the sense that it achieves the goal clear(x) for many problems, indeed any block world instance.

In this work, we study the characterization and computation of such policies for families of problems that share a common structure. This structure has been characterized as made of two parts: a common pool of actions and observations [Hu and De Giacomo, 2011], and a common structural reduction into a single abstract problem P that is nondeterministic even if the concrete problems Pi are deterministic [Bonet and Geffner, 2015]. Policies µ that solve the ab-

Hector Geffner ICREA Univ. Pompeu Fabra Barcelona, Spain hector.geffner@upf.edu Sasha Rubin Univ. Federico II Naples, Italy rubin@unina.it

stract problem P have been shown to solve any such problem Pi provided that they terminate in Pi. In this work, we shed light on why this termination condition is needed and how it can be removed. The key observation is that the abstract problem P captures the common structure among the concrete problems Pi that is local (Markovian) but misses common structure that is global. We show nonetheless that such global structure can be accounted for by extending the abstract problems with trajectory constraints; i.e., constraints on the interleaved sequences of actions and observations or states that are possible. For example, a trajectory constraint may state that a non-negative numerical variable X will eventually have value zero in trajectories where it is decreased infinitely often and increased finitely often. Similarly, a trajectory constraint can be used to express fairness assumptions; namely, that infinite occurrences of an action, must result in infinite occurrences of each one of its possible (non-deterministic) outcomes. The language of the partially observable non-deterministic problems extended with trajectory constraints provides us with a powerful framework for analyzing and even computing general policies that solve infinite classes of concrete problems.

In the following, we first lay out the framework, discuss the limitations of earlier work, and introduce projections and trajectory constraints. We then show how to do generalized planning using LTL synthesis techniques, and for a specific class of problems, using efficient planners for fully observable non-deterministic problems.

2 Framework

The framework extends the one by Bonet and Geffner [2015].

2.1 Model

A partially observable non-deterministic problem (PONDP) is a tuple P = 〈S, I, Ω, Act, T, A, obs, F 〉 where

1. S is a set of states s,
2. I ⊆ S is the set of initial states,
3. Ω is the finite set of observations,
4. Act is the finite set of actions,
5. T ⊆ S is the set of goal states,
6. A : S → 2Act is the available-actions function,
7. obs : S →Ω is the observation function, and
8. F : Act ×S → 2S \ {∅} is the partial successor function with domain {(a, s) : a ∈ A(s)}.

In this work we assume observable goals and observable action-preconditions; these assumptions are made uniformly when we talk about a class of PONDPs P:

Definition 1. A class P of PONDPs consists of a set of PONDPs P with 1) the same set of actions Act, 2) the same set of observations Ω, 3) a common subset TΩ ⊆ Ω of goal observations such that for all P ∈ P, s ∈ T if and only if obs(s) ∈ TΩ, and 4) common subsets of actions Aω ⊆ Act, one for each observation ω ∈ Ω, such that for all P in P and s in P , A(s) = Aobs(s).

Example. Consider the class P of problems that involve a single non-negative integer variable X, initially positive, and an observation function obs that determines if X is 0 or not (written X = 0 and X ̸= 0). The actions Inc and Dec increment and decrement the value of X by 1 respectively, except when X = 0 where Dec has no effect. The goal is X = 0. The problems in P differ on the initial positive value for X that may be known, e.g., X = 5, or partially known, e.g., X ∈ [5, 10].

PONDPs are similar to Goal POMDPs [Bonet and Geffner, 2009] except that uncertainty is represented by sets of states rather than by probabilities. Deterministic sensing is not restrictive [Chatterjee and Chmel´ık, 2015]. For fully observable non-deterministic problems (FONDP) the observation function obs(s) = s is usually omitted. The results below apply to fully observable problems provided that Ω is regarded as a set of state features, and obs(·) as the function that maps states into features.

2.2 Solutions

Let P = 〈S, I, Ω, Act, T, A, obs, F〉 be a PONDP. A stateaction sequence over P is a finite or infinite sequence of the form 〈s0, a0, s1, a1, · · ·〉 where each si ∈ S and ai ∈ Act. Such a sequence reaches a state s if s = sn for some n ≥ 0, and is goal reaching in P if it reaches a state in T. An observation-action sequence over P is a finite or infinite sequence of the form 〈ω0, a0, ω1, a1, · · ·〉 where each ωi ∈ Ω and ai ∈ Act. Let us extend obs over state-action sequences: for τ = 〈s0, a0, s1, a1, . . .〉, define obs(τ) = 〈obs(s0), a0, obs(s1), a1, . . .〉. A trajectory of P is a stateaction sequence over P such that s0 ∈ I, and for i ≥ 0, ai ∈ A(si) and si+1 ∈ F(ai, si). An observation trajectory of P is an observation-action sequence of the form obs(τ) where τ is a trajectory of P.

A policy is a partial function µ : Ω+ → Act where Ω+ is the set of finite non-empty sequences over the set Ω. A policy µ is valid if it selects applicable actions, i.e., if 〈s0, a0, s1, a1, . . .〉 is a trajectory, then for the observation sequence xi = 〈obs(s0), . . . , obs(si)〉, µ(xi) is undefined, written µ(xi) = ⊥, or µ(xi) ∈ A(si). A policy that depends on the last observation only is called memoryless. We write memoryless policies as partial functions µ : Ω → Act.

A trajectory τ = 〈s0, a0, s1, a1, . . .〉 is generated by µ if µ(obs(s0) . . . obs(sn)) = an for all n ≥ 0 for which sn and an are in τ. A µ-trajectory of P is a maximal trajectory τ generated by µ, i.e., either a) τ is infinite, or b) τ is finite and cannot be extended with µ; namely, τ = 〈s0, a0, s1, a1, . . . , sn-1, an-1, sn〉 and

µ(obs(s0) . . . obs(sn)) = ⊥. If µ is a valid policy and every µ-trajectory is goal reaching then we say that µ solves (or is a solution of) P .

A transition in P is a triplet (s, a, s′ ) ∈ S × Act × S such that s′ ∈ F(a, s). A transition (s, a, s′ ) occurs in a trajectory 〈s0, a0, s1, a1, . . .〉 if for some i ≥ 0, s = si, a = ai, and s′ = si+1. A trajectory τ is fair if a) it is finite, or b) it is infinite and for all transitions (s, a, s′ ) and (s, a, s′′ ) in P for which s′ ̸= s′′ , if one transition occurs infinitely often in τ, the other occurs infinitely often in τ as well. If µ is a valid policy and every fair µ-trajectory is goal reaching then we say that µ is a fair solution to P [Cimatti et al., 2003].

2.3 The Observation Projection Abstraction

Bonet and Geffner [2015] introduce reductions as functions that can map a set of "concrete PONDPs problems" P into a single, often smaller, abstract PONDP P ′ that captures part of the common structure. A general way for reducing a class of problems into a smaller one is by projecting them onto their common observation space:

Definition 2. Let P be a class of PONDPs (over actions Act, observations Ω, and the set of goal observations TΩ). Define the FONDP P o = 〈So , I o , Acto , T o, Ao , F o 〉, called the observation projection of P, where

H1. So = Ω,

H2. ω ∈ I o iff there is P ∈ P and s ∈ I s.t. obs(s) = ω,

H3. Acto = Act,

H4. T o = TΩ,

H5. Ao (ω) = Aω for every ω ∈ Ω,

H6. for a ∈ Ao (ω), define ω′ ∈ F o (a, ω) iff there exists P ∈ P, (s, a, s′ ) in F s.t. obs(s) = ω and obs(s′ ) = ω′ .

This definition generalises the one by Bonet and Geffner [2015] which is for a single PONDP P , not a class P.

Example (continued). Recall the class P of problems with the non-negative integer variable X. Their observation projection P o is the FONDP with two states, that correspond to the two possible observations, and which we denote as X > 0 and X = 0. The transition function F o in P o for the action Inc maps the state X = 0 into X > 0, and the state X > 0 into itself; and for the action Dec it maps the state X = 0 into itself, and X > 0 into both X > 0 and X = 0. The initial state in P o is X > 0 and the goal state is X = 0.

The following is a direct consequence of the definitions:

Lemma 3. Let P be a class of PONDPs and let τ be a trajectory of some P ∈ P. Then (1) τ is goal reaching in P iff the observation-action sequence obs(τ) is goal reaching in P o . Furthermore, if µ is a valid policy for P o , then (2) µ is a valid policy for P and (3) if τ is a µ-trajectory then obs(τ) is a µ-trajectory of P o .

2.4 General Policies

A main result of Bonet and Geffner (2015, Theorem 5) is that:

Theorem 4. Let µ be a fair solution for the projection P o of the single problem P. If all the µ-trajectories in P that are fair are also finite, then µ is a fair solution for P .

One of the main goals of this work is to remove the termination (finiteness) condition so that a policy µ that solves the projection P o of a class of problems P will generalize automatically to all problems in the class. For this, however, we will need to extend the representation of abstract problems.

Example (continued). The policy µ that maps the observation X > 0 into the action Dec (namely, "decrease X if positive") is a fair solution to P o , and to each problem P in the class P above. The results of Bonet and Geffner [2015], however, are not strong enough for establishing this generalization. What they show instead is that the generalization holds provided that µ terminates at each problem P ∈ P.

3 Trajectory Constraints

In the example, the finiteness condition is required by Theorem 4 because there are other problems, not in the class P, that also reduce to P o but which are not solved by µ. Indeed, a problem P ′ like any of the problems in P but where the Dec action increases X rather than decreasing it when X = 5 is one such problem: one that cannot be solved by µ and one on which µ does not terminate (when, initially, X ≥ 5). These other problems exist because the abstraction represented by the non-deterministic problem P o is too weak: it captures some properties of the problems in P but misses properties that should not be abstracted away. One such property is that if a positive integer variable keeps being decreased, while being increased a finite number of times only, then the value of the variable will infinitely often reach the zero value. 1 This property is true for the class of problems P but is not true for the problem P ′ , and crucially, it is not true in the projection P o . Indeed, the projection P o captures the local (Markovian) properties of the problems in P but not the global properties. Global properties involve not just transitions but trajectories.

We will thus enrich the language of the abstract problems by considering trajectory constraints C, i.e., restrictions on the set of possible observation or state trajectories. The constraint CX that a non-negative variable X decreased infinitely often and increased finitely often, will infitenly often reach the value X = 0 is an example of a trajectory constraint. Another example is the fairness constraint CF ; namely, that infinite occurrences of a non-deterministic action in a state imply infinite occurrences of each one of its possible outcomes following the action in the same state.

3.1 Strong Generalization over Projections

Formally, a trajectory constraint C over a PONDP P is a set of infinite state-action sequences over P or a set of infinite observation-action sequences over P. A trajectory τ satisfies C if either a) τ is finite, or b) if C is a set of state-action sequences then τ ∈ C, and if C is a set of observation-action sequences then obs(τ) ∈ C. Thus trajectory constraints only constrain infinite sequences.

A PONDP P extended with a set of trajectory constraints C, written P/C, is called a PONDP with constraints. Solutions of P/C are defined as follows:

1 The stronger consequent of eventually reaching the zero value and staying at it also holds for the problems in P. However, we prefer to use this weaker condition as it is enough for our needs.

Definition 5 (Solution of PONDP with constraints). A policy µ solves P/C iff µ is valid for P and every µ-trajectory of P that satisfies C is goal reaching.

This notion of solution does not assume fairness as before (as in strong cyclic solutions); instead, it requires that the goal be reached along all the trajectories that satisfy the constraints. Still if C = CF is the fairness constraint above, a fair solution to P is nothing else than a policy µ that solves P extended with CF ; i.e. P/CF . When C contains all trajectories, the solutions to P and P/C coincide as expected.

We remark that a trajectory constraint C over the observation projection P o of P is a trajectory constraint over every P in P. The next theorem says that a policy that solves P o /C also solves every P/C.

Theorem 6 (Generalization with Constraints). If P o is the observation projection of a class of problems P and C is a trajectory constraint over P o , then a policy that solves P o /C also solves P/C for all P ∈ P.

Proof. Suppose that µ solves P o /C. Let P be a problem in P. By Lemma 3 (2), µ is a valid policy for P ∈ P. To see that µ solves P/C, take a trajectory τ of P that satisfies C, i.e., obs(τ) ∈ C. By Lemma 3 (3), obs(τ) is a µ-trajectory of P o . By assumption obs(τ) is goal reaching. By Lemma 3 (1), τ is goal reaching.

Say that P satisfies the constraint C if all infinite trajectories in P satisfy C. Then, an easy corollary is that:

Corollary 7. Let P o be the observation projection of a class P of PONDPs, let C be a trajectory constraint over P o , and let P be a problem in P. If P satisfies C, then a policy that solves P o /C also solves P .

More generally, if C and C ′ are constraints over P , say that C implies C ′ if every infinite trajectory over P that satisfies C also satisfies C ′ . We then obtain that:

Corollary 8. Let P o be the observation projection of a class P of PONDPs, and let C ′ be a trajectory constraint over P o . If P is a problem in P, C is a constraint over P, and C implies C ′ , then a policy that solves P o /C ′ also solves P/C.

Trajectory constraints in P o are indeed powerful and can be used to account for all the solutions of a class P.

Theorem 9 (Completeness). If P o is the observation projection of a class of problems P, and µ is a policy that solves all the problems in P, then there is a constraint C over P o such that µ solves P o /C.

Sketch. Define C to be the set of observation sequences of the form obs(τ) where τ varies over all the trajectories of all P ∈ P. Suppose µ solves every P in P. First, one can show that µ is valid in P o using the assumption that action preconditions are observable (i.e., Ao (ω) = Aω = A(s) for all s such that obs(s) = ω). Second, to see that µ solves P o /C take a µ-trajectory τ of P o that satisfies C. By definition of C, there is a trajectory τ ′ in some P ∈ P such that obs(τ ′ ) = τ. It is not hard to see that τ ′ is a µ-trajectory of P. Thus, since τ ′ is goal-reaching and goals are uniformly observable (Definition 1), then τ is goal reaching.

Example (continued). The problems P above with integer variable X and actions Inc and Dec and goal X = 0, are all solved by the policy µ "if X > 0, do Dec". However, the observation projection P o is not solved by µ as there are trajectories where the outcome of the action Dec in P o , with non-deterministic effects X > 0 |X = 0, is always X > 0. Bonet and Geffner [2015] deal with this by taking µ as a fair solution to P and then proving termination of µ in P (a similar approach is used by Srivastava et al. [2011b]). The theorem and corollary above provide an alternative. The policy µ does not solve P o but solves P o with constraint CX, where CX is the trajectory constraint that states that if the action Dec is done infinitely often and the action Inc is done finitely often then infinitely often X = 0. Theorem 6 implies that µ solves P/CX for every P in the class. Yet, since P satisfies CX, Corollary 7 implies that µ must solve P too. The generalization also applies to problems P where increases and decreases in the variable X are non-deterministic as long as no decrease can make X negative. In such a case, if CF is the trajectory constraint over P that says that non-deterministic actions are fair, from the fact that CF implies CX in any such problem P, Corollary 8 implies that a policy µ that solves P o /CX must also solve P/CF ; i.e., the strong solution to the abstraction P o over the constraint CX, represents a fair solution to such non-deterministic problems P .

4 Generalized Planning as LTL Synthesis

Suppose that we are in the condition of Theorem 6. That is we have a class of problems P whose observation projection is P o , and a constraint C over P o . Let's further assume that C is expressible in Linear-time Temporal Logic (LTL). Then we can provide an actual policy that solves P o /C, and hence solves P/C for all P ∈ P. We show how in this section.

For convenience, we define the syntax and semantics of LTL over a set Σ of alphabet symbols (rather than a set of atomic propositions). The syntax of LTL is defined by the following grammar: Ψ ::= true | l | Ψ ∧ Ψ | ¬Ψ | ◦Ψ | ΨUΨ, where l ∈ Σ. We denote infinite strings α ∈ Σω by α = α0α1 · · · , and write α≥j = αjαj+1 . . . . The semantics of LTL, α |= Ψ, is defined inductively as follows: α |= true; α |= l iff α0 = l; α |= Ψ1 ∧Ψ2 iff α |= Ψi, for i = 1, 2; α |= ¬Ψ iff α ̸|= Ψ; α |= ◦Ψ iff α≥1 |= Ψ; and α |= Ψ1 UΨ2 iff there exists j such that α≥j |= Ψ2 and for all i < j we have that α≥i |= Ψ1. We use the usual shorthands, e.g., ♦Φ for trueUΦ (read "eventually") and □Φ for ¬♦¬Φ (read "always"). Define mod(Ψ) = {α ∈ Σω : α |= Ψ}.

Assume that the trajectory constraint C is expressed as an LTL formula Ψ, i.e., Σ = Ω ∪ Act and mod(Ψ) = C. Let Φ .= Ψ ⊃ ♦T o where ♦T o is the reachability goal of P o expressed in LTL. To build a policy solving P o /C proceed as follows. The idea is to think of policies µ : Ω+ → Act as (Ωbranching Act-labeled) trees, and to build a tree-automaton accepting those policies such that every µ-trajectory satisfies the formula Φ. Here are the steps:

1. Build a nondeterministic B¨uchi automaton Ab for the formula Φ (exponential in Φ) [Vardi and Wolper, 1994].
2. Determinize Ab to obtain a deterministic parity word automaton (DPW) Ad that accepts the models of Φ

(exponential in Ab, and produces linearly many priorities) [Piterman, 2007]. An infinite word α is accepted by a DPW A iff the largest priority of the states visited infinitely often by α is even.

1. Build a deterministic parity tree automaton At that accepts a policy µ iff every µ-trajectory satisfies Φ (polynomial in Ad and P o , and no change in the number of priorities). This can be done by simulating P o and Ad as follows: from state (s, q) (of the product of P and Ad) and reading action a, launch for each s′ ∈ F(a, s) a copy of the automaton in state (s′ , q′ ) in direction s′ where q′ is the updated state of Ad.
2. Test At for non-emptiness (polynomial in At and exponential in the number of priorities of At) [Zielonka, 1998].

This yields the following complexity (the lower-bound is inherited from Pnueli and Rosner [1989]):

Theorem 10. Let P o /C be the observation projection with trajectory constraint C expressed as the LTL formula Ψ. Then solving P o /C (and hence all P/C with P ∈ P) is 2EXPTIME-complete. In particular, it is double-exponential in |Ψ| + |T o | and polynomial in |P o |.

This is a worst-case complexity. In practice, the automaton At may be small also in the formula Φ .= Ψ ⊃ ♦T o .

Example (continued). We express CX in LTL. The constraint LTL formula ΨX (over alphabet {X = 0,X ̸= 0}∪{Inc,Dec}) is ♦□¬Inc ∧ □♦Dec ⊃ □♦(X = 0) . Then, mod(ΨX) = CX. The resulting formula Φ .= ΨX ⊃ ♦(X = 0) generates a relatively small automaton: the DPW Ad has 5 states and 3 priorities, see Figure 1. As a further example, consider the case of N ∈ N variables. Each variable Xi has a formula Ψi analogous to ΨX. Consider the constraint Ψ = ∧iΨi. The above algorithm gives us, as worstcase, DPW for Φ .= Ψ ⊃ ♦(X = 0) of size 22O(N) with 2O(N) many priorities. However, analogously to Figure 1, there is a DPW of size 2O(N) with 3 priorities.

5 Qualitative Numerical Problems

To concretize, we consider a simple but broad class of problems where generalized planning can be reduced to FOND planning. These problems have a set of non-negative numeric variables, that do not have to be integer, and standard boolean propositions and actions that can increase or decrease the value of the numeric variables non-deterministically. The general problem of stacking a block x on a block y in any blocks-world problem, with any number of blocks in any configuration, can be cast as a problem of this type. An abstraction of some of these problems appears in [Srivastava et al., 2011b; 2015].

A qualitative numerical problem or QNP is a tuple RV = 〈F, Init, Act, G, V, InitV , INC, DEC〉 where the first four components define a STRIPS planning problem extended with atoms X = 0 and X > 0 for numerical variables X in a set V , that may appear as action preconditions and goals, sets InitV (X) of possible initial values for each variable X ∈ V , and effect descriptors Dec(X) and Inc(X), with a semantics given by the functions INC and DEC that take a variable X, an action a, and a state s, and yield a subset INC(X, a, s) and DEC(X, a, s) of possible values x′ of X in the successor states. If these ranges contain a single number, the problem is deterministic, else it is nondeterministic. If x is the value of X in s, the only requirement is that for all x′ ∈ DEC(x, a, s), 0 ≤ x′ ≤ x, and that for all x′ ∈ INC(X, a, s), x′ > x when x = 0 and x′ ≥ x when x > 0. 2 All the propositions in F are assumed to be observable, while for numerical variables X, only the booleans X = 0 and X > 0 are observable.

A QNP RV = 〈F, Init,Act,G, V, InitV , INC, DEC〉 represents a PONDP PV in syntactic form. If sV is a valuation over the variables in V , sV [X] is the value of X in sV , and b[sV ] its boolean projection; i.e. b[sV ][X] = 0 if sV [X] = 0 and b[sV ][X] = 1 otherwise. The PONDP PV corresponds to the tuple 〈S, I, Ω, Act, T, A, obs, F 〉 where

1. S is the set of valuations 〈sF , sV 〉 over the variables in F and V respectively,
2. I is the set of pairs 〈sF , sV 〉 where sF is uniquely determined by Init and sV [X] ∈ InitV (X) for each X ∈ V ,
3. Ω = {〈sF , b[sV ]〉 : 〈sF , sV 〉 ∈ S},
4. Act is the finite set of actions given,
5. T ⊆ S is the set of states that satisfy the atoms in G,

6. A(s) is the set of actions whose precondition are true in s,

1. obs(s) = 〈sF , b[sV ]〉 for s = 〈sF , sV 〉,
2. F(a, s) for s = 〈sF , sV 〉 is the set of states s′ = 〈s′F , s′V 〉 where s′F is the STRIPS successor of a in s, and s′V [X] is in INC(X, a, s), DEC(X, a, s), or {sV [X]} according to whether a features an Inc(X) effect, a Dec(X) effect, or none.

An example is RV = 〈F, Init,Act,G, V, InitV , INC, DEC〉 where F is empty, V = {X, Y }, InitV (X) = {20} and InitV (Y ) = {30}, the goal is {X = 0, Y = 0}, and Act contains two actions: an action a with effects Dec(X) and Inc(Y ), and an action b with effect Dec(Y ). The functions INC always increases the value by 1 and DEC decreases the value by 1 except when it is less than 1 when the value is decreased to 0. A policy µ that solves RV is "do a if X > 0 and Y = 0, and do b if Y > 0". Simple variations of RV can be obtained by changing the initial situation, e.g., setting it to InitV (X) = [10, 20] and InitV (Y ) = [15, 30], or the INC

2 Inc(X) effects always increase variable X when X = 0. Otherwise, trajectory constraints would be needed also for increments.

and DEC functions. For example, a variable X can be set to increase or decrease any number between 0 and 1 as long as values do not become negative. The policy µ solves all these variations except for those where infinite sequences of decrements fail to drive a variable to zero. We rule out such QNPs by means of the following trajectory constraint:

Definition 11 (QNP Constraint). The trajectory constraint CX for a numerical variable X in a QNP excludes the trajectories that after a given time point contain a) an infinite number of actions with Dec(X) effects, b) a finite number of actions with Inc(X) effects, c) no state where X = 0.

This is analogous to the LTL constraint in Section 4. The set of constraints CX for all variables X ∈ V is denoted as CV . We will be interested in solving QNPs RV given that the constraints CV hold. Moreover, as we have seen, there are policies that solve entire families of similar QNPs:

Definition 12 (Similar QNPs). Two QNPs are similar if they only differ in the INC, DEC or InitV functions, and for each variable X, X = 0 is initially possible in one if it is initially possible in the other, and the same for X > 0.

We want to obtain policies that solve whole classes of similar QNPs by solving a single abstract problem. For a QNP RV , we define its syntactic projection as RoV : 3

Definition 13 (Syntactic Projection of QNPs). If RV = 〈F, Init,Act,G, V, InitV , INC,DEC〉 is a QNP, its syntactic projection is the non-deterministic (boolean) problem RoV = 〈F ′ , Init′ ,Act′ ,G〉, where

1. F ′ is F with new atoms X = 0 andX > 0 added for each variable X; i.e. F ′ = F ∪ {X = 0, X > 0 : X ∈ V },
2. Init′ is Init and X = 0 (resp. X > 0) true iff X > 0 (resp. X = 0) is not initially possible in InitV .
3. Act′ is Act but where in each action and for each variable X, the effect Inc(X) is replaced by the atomX > 0, and the effect Dec(X) is replaced by the conditional effect "if X > 0 then X > 0 | X = 0".

Recalling that X > 0 is an abbreviation for X ̸= 0, the atoms X = 0 and X > 0 are mutually exclusive. We refer to the action with non-deterministic effects in RoV as the Dec(X) actions as such actions have Dec(X) effects in RV . This convention is assumed when applying CV constraints to RoV . The syntactic projection RoV denotes a FONDP that features multiple initial states when for some variable X, both X = 0 and X > 0 are possible in InitV :

Theorem14. The FONDP denoted by RoV is the observation projection of the class RV made of all the PONDPs R′V that are similar to RV .

The generalization captured by Theorem 6 implies that:

Theorem 15 (QNP Generalization). Let µ a policy that solves RoV /CV ; i.e. the FONDP denoted by RoV given CV . Then, µ solves R′V /CV for all QNPs R′V similar to RV .

In addition, the constraints CV are strong enough in QNPs for making the abstraction RoV complete for the class of problems RV similar to RV :

3 For simplicity we use the syntax of STRIPS with negation and conditional effects [Gazen and Knoblock, 1997].

Theorem 16 (QNP Completeness). Let µ be a policy that solves the class of problems RV made up of all the QNPs R′V that are similar to RV given CV . Then µ must solve the projection RoV given CV .

This is because the class RV contains a problem R∗V where each variable X has two possible values X = 0 and X = 1 such that the semantics of the Dec(X) and Inc(X) effects make R∗V equivalent to the projection RoV , with the valuations over the two-valued X variables in correspondence with the boolean values X = 0 and X > 0 in RoV .

5.1 QNP Solving as FOND Planning

The syntactic projection RoV of a QNP RV represents a FONDP with non-deterministic (boolean) effects X > 0 |X = 0 for the actions in RV with Dec(X) effects. It may appear from Theorem 15 that one could use off-theshelf FOND planners for solving RoV and hence for solving all QNPs similar to RV . There is, however, an obstacle: the effects X > 0 |X = 0 are not fair. Indeed, even executing forever only actions with Dec(X) effects does not guarantee that eventually X = 0 will be true. In order to use fair (strong cyclic) FOND planners off-the-shelf, we thus need to compile the FONDP RoV given the constraints CV into a fair FONDP with no constraints.

For this, it is convenient to make two assumptions and to extend the problem RV with extra booleans and actions that do not affect the problem but provide us with handles in the projection. The assumptions are that actions with Dec(X) effects have the (observable) precondition X > 0, and more critically, that actions feature decrement effects for at most one variable. The new atoms are qX, one for each variable X ∈ V , initially all false. The new actions for each variable X in V are set(X) and unset(X), the first with no precondition and effect qX, the second with precondition X = 0 and effect ¬qX. Finally, preconditions qX are added to actions with effect Dec(X) and precondition ¬qX to all actions with effect Inc(X). Basically, qX is set in order to decrease the variable X to zero. When qX is set, X cannot be increased and qX can be unset only when X = 0. We say that RV is closed when RV is extended in this way and complies with the assumptions above (and likewise for its projection RoV ).

Theorem 17 (Generalization with FOND Planner). µ is a fair solution to the FONDPRoV for a closed QNPRV iff µ solves all QNPs that are similar to RV given the constraints CV .

Sketch: We need to show that µ is a fair solution to RoV iff µ solves RoV /CV . The rest follows from Theorems 15 and 16. (⇒). If µ does not solve the FONDP RoV given CV , there must a µ-trajectory τ that is not goal reaching but that satisfies CV and is not fair in RoV . Thus, there must be a subtrajectory 〈si, ai, . . . , si+m〉 that forms a loop with si+m = si, where no sk is a goal state, and 1) some ak has a Dec(X) effect in RV , and 2) X > 0 is true in all sk, i ≤ k ≤ i+m. 1) must be true as τ is not fair in RoV and only actions with Dec(X) actions in RV are not deterministic in RoV , and 2) must be true as, from the assumptions in RV , X = 0 needs to be achieved by an action that decrements X, in contradiction with the assumption that τ is not fair in RoV . Finally, since τ satisfies CV , then it must contain infinite actions with Inc(X) effects, but then the loop must feature unset(X) actions with precondition X = 0 in contradiction with 2. (⇐) If µ solves RoV /CV but µ is not a fair solution to RoV , then there must be an infinite µ-trajectory τ that is not goal reaching and does not satisfy CV , but which is fair in RoV . This means that there is a loop in τ with some Dec(X) action, no Inc(X) action, and where X = 0 is false. But τ can't then be fair in RoV .

6 Discussion

We have studied ways in which a (possibly infinite) set of problems with partial observations (PONDPs) that satisfy a set of trajectory constraints can all be solved by solving a single fully observable problem (FONDP) given by the common observation projection, augmented with the trajectory constraints. The trajectory constraints play a crucial role in adding enough expressive power to the observation projection. The single abstract problem can be solved with automata theoretic techniques typical of LTL synthesis when the trajectory constraints can be expressed in LTL, and in some cases, by more efficient FOND planners.

The class of qualitative numerical problems are related to those considered by Srivastava et al. [2011b; 2015] although the theoretical foundations are different. We obtain the FONDPs RoV from an explicit observation projection, and rather than using FOND planners to provide fair solutions to RoV that are then checked for termination, we look for strong solutions to RoV given a set of explicit trajectory constraints CV , and show that under some conditions, they can be obtained from fair solutions to a suitable transformed problem. It is also interesting to compare our work to the approach adopted to deal with the onedimensional planning problems [Hu and Levesque, 2010; Hu and De Giacomo, 2011]. There we have infinitely many concrete problems that are all identical except for an unobservable parameter ranging over naturals that can only decrease. A technique for solving such generalized planning problems is based on defining one single abstract planning problem to solve that is "large enough" [Hu and De Giacomo, 2011]. Here, instead, we would address such problems by considering a much smaller abstraction, the observation projection, but with trajectory constraints that capture that the hidden parameter can only decrease.

Our work is also relevant for planning under incomplete information. The prototypical example is the treechopping problem of felling a tree that requires an unknown/unobservable number of chops. This was studied by Sardi˜na et al. [2006], where, in our terminology, the authors analyse exactly the issue of losing the "global property" when passing to the "observation projection". Finally, our approach can be seen as a concretization of insights by De Giacomo et al. [2016] where trace constraints are shown to be necessary for the belief-state construction to work on infinite domains.

Acknowledgments

H. Geffner was supported by grant TIN2015-67959-P, MINECO, Spain; S. Rubin by a Marie Curie fellowship of INdAM; and G. De Giacomo by the Sapienza project "Immersive Cognitive Environments".