Policies that Generalize: Solving Many Planning Problems with the Same Policy

1 Introduction

Consider a vacuum cleaning robot in a linear 1 × 5 grid, with the robot initially in the leftmost cell, and each of the n cells being either clean or dirty [Russell and Norvig, 2002]. If the robot can sense whether the current cell is clean or not, and whether it is in the last (rightmost) cell, the goal of having all cells clean can be achieved with the policy "if dirt, suck it; if clean and not in the last cell, move right". This is an example of a memoryless policy that maps observations into actions. Compact memoryless policies and finite-state machines are heavily used in robotics and video games as they provide a simple language for writing controllers that are robust and general [Murphy, 2000; Buckland, 2004]. For example, the vacuum cleaning policy for the 1 × 5 grid will also work in a 1 × 10 grid, and actually in any 1 × n grid. Moreover, it will work no matter how dirt is distributed, and even when the actions of moving right and sucking dirt may fail to achieve their effects sometimes. All these problem variations indeed appear to share a common structure, aside from the same set of actions and observations, and once the policy is derived from one problem it applies to all the variations. It is however not straightforward to pinpoint what is the common structure that supports such generalization. Indeed, what does the 1×5 instance with dirt all over has in common with the 1×10 instance where dirt is

Hector Geffner

ICREA & Universitat Pompeu Fabra Barcelona, SPAIN hector.geffner@upf.edu

in the second cell only? What do these instances have in common with non-deterministic variants where actions may fail? And, what part of the structure is missing when the policy does not work?

Our aim in this paper is to provide a characterization of the common structure that allows for policy generalization. We use a logical setting where uncertainty is represented by sets of states and the goal is to be achieved with certainty. In this setting, the notions of solution policy and generalization become very crisp: a policy solves a problem or not, and it generalizes to another problem or not. We thus ignore considerations of costs, quality or rewards, and do not consider probabilities explicitly. Our results, however, do apply to the probabilistic setting where goals are to be achieved with probability 1. This is a result of the correspondence between proper policies in stochastic systems and strong cyclic policies in purely non-deterministic ones [Bertsekas, 1995; Cimatti et al., 1998; Geffner and Bonet, 2013]. The theme of policies that are general has surfaced in generalized planning [Hu and De Giacomo, 2011; Srivastava et al., 2011a] and reinforcement learning [Taylor and Stone, 2009], and the relation to these research threads will be discussed.

The paper is organized as follows. We introduce the model and memoryless policies, define reductions, consider refinements, and extend the results to finite-state controllers. We also illustrate the ideas on examples and discuss related work.

2 Model, Policies, Solutions

A partially observable non-deterministic problem (PONDP) is a tuple P = 〈S, S0, T, A, F, o〉 where

1. S is a finite set of states s,
2. S0 is the set of possible initial states S0 ⊆ S,
3. T is the set of goal states T ⊆ S,
4. A(s) ⊆ A is set of actions applicable in s ∈ S,
5. F(a, s) ⊆ S denotes the successor states, s ∈ S, a ∈ A(s)
6. o is the observation function o(s) ∈ Ωo where Ωo is the set of possible observations.

PONDPs are similar to POMDPs with deterministic sensing (Partially Observable Markov Decision Processes; [Kaelbling et al., 1998]) and in particular to Goal POMDPs where goals have to be achieved with certainty [Bonet and Geffner, 2009]. A key difference is that uncertainty is represented by sets of states rather than probability distributions. For policies that must achieve the goal with certainty, however, the distinction is irrelevant; all that matters is which observations and state transition are possible, not their exact numerical probabilities [Bertsekas, 1995]. Similarly, noisy sensing can be compiled into deterministic sensing by extending the states with the observations [Chatterjee and Chmel´ık, 2015].

The basic notions are reviewed next. A sequence τ = 〈s0, s1, . . .〉 of states is a state trajectory in P iff s0 ∈ S0 and for every state si+1 in τ there is an action ai in A(si) such that si+1 ∈ F(ai, si). A trajectory τ reaches a state s if τ contains s, and τ is goal reaching if it reaches a goal state. A state s is reachable if there is a trajectory that reaches s.

A memoryless policy is a partial function µ : Ωo → A where µ(ω) is the action prescribed in all the states s with o(s) = ω, with the only restriction that the action µ(ω) must be applicable at s; µ(o(s)) ∈ A(s). The trajectories generated by µ, called the µ-trajectories, are the finite or infinite sequences 〈s0, s1, . . .〉 where s0 ∈ S0, and si+1 ∈ F(µ(o(si)), si) for all the states si+1 in the sequence. A µ-trajectory is maximal if it is infinite or it if it ends in a state s for which µ(o(s)) is undefined. Sometimes actions are included in µ-trajectories which are then denoted as 〈s0, a0, s1, a1, s2, . . .〉 where ai = µ(o(si)). A state is reachable by µ if there is a µ-trajectory that reaches the state.

A transition in P is a triplet (s, a, s′ ) such that s′ ∈ F (a, s) and a ∈ A(s). A transition (s, a, s′ ) occurs in a trajectory 〈s0, a0, s1, a1, . . .〉 if for some i, s = si, a = ai, and s′ = si+1. A trajectory τ is fair if it is finite and maximal, or if for any two 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.

A policy µ solves P iff every fair µ-trajectory is goal reaching. If µ solves P, µ is said to be a solution to P, and a valid policy for P. Solutions are thus strong cyclic policies [Cimatti et al., 1998]. A solution µ is strong when the fair µ-trajectories are all finite and end in a goal state.

3 Characterizing the Common Structure

We define a structural relation among PONDPs and establish properties that follow from it. The reduction of a problem P into a "smaller" problem P ′ allows us to establish sufficient conditions under which a policy that solves P ′ also solves the "larger" problem P .

Definition 1 (Reduction). Let P = 〈S, S0, T,A, F, o〉 and P ′ = 〈S′ , S′0 , T ′ ,A′ , F ′ , o′ 〉 be two problems with the same sets of observations; i.e., Ωo = Ωo′ . A function h : S → S′ reduces P to P ′ iff

• R1. A′ (h(s)) ⊆ A(s) for all s ∈ S,
• R2. o(s) = o′ (h(s)) for all s ∈ S,
• R3. if s′ ∈ F(a, s) then h(s′ ) ∈ F ′ (a, h(s)) for all s, s′ ∈ S and a ∈ A′ (h(s)),
• R4. if s0 ∈ S0 then h(s0) ∈ S′0 for all s0 ∈ S0,
• R5. if s ̸∈ T then h(s) ̸∈ T ′ for all s ∈ S.

The intuition for R1-R5 is that a reduction 1) doesn't introduce non-applicable actions, 2) preserves observations, and

3) maps transitions into transitions, initial states into initial states, and non-goal states into non-goal states.

Reductions are not symmetric in general, and thus, they are different than other types of relations among structurally similar problems like bisimulations [Milner, 1989]. In particular, deterministic systems can be reduced into non-deterministic systems but the opposite reduction may not be feasible.

Example: Countdown. Let us first consider the problem of driving a state counter from some value to zero using the actions Inc and Dec, and a sensor that tells if the goal has been achieved. The problem is the tuple Pn = 〈S, S0, T, A, F, o〉 where S = {0, 1, . . . , n}, S0 = S, T = {0}, A contains the actions Inc and Dec, o(s) is 0 or "+" respectively iff s is 0 or positive, and s′ ∈ F(a, s) iff s′ = s + 1 when a = Inc and s < n, s′ = s - 1 when a = Dec and s > 0, and else, s = s′ . The simple policy µ where µ(ω) = Dec if ω = + solves the problem. The function h(s) = 0 if s = 0 and h(s) = 1 if s > 0 maps the problem Pn into the abstract and smaller problem P ′ = 〈S′ , S′0 , T ′ ,A′ , F ′ , o′ 〉 where all positive states in Pn are represented by a single state. More precisely, S′ contains just the two states 0 and 1, S′0 = S′ , T ′ = T, A′ = A, o(s′ ) is 0 or + according to whether s′ is 0 or 1, F ′ (a, 0) = F(a, 0) for a ∈ {Inc, Dec}, F ′ (Dec, 1) = {1, 0}, and F ′ (Inc, 0) = F ′ (Inc, 1) = {1}. The function h reduces the deterministic problem Pn, for any n, into a single non-deterministic problem P ′ where nondeterminism is used in the transition F ′ (Dec, 1) = {1, 0} to capture the possible transitions from different states s in Pn that are reduced to the same state h(s) = 1 in P ′ .

Clearly, the h-mapping satisfies R1, R2, R4, and R5 as it doesn't introduce non-applicable actions (P and P ′ have the same actions and they are always applicable), s and h(s) give rise to the same observations, initial states of Pn map into initial states of P ′ , and non-goal states are preserved (i.e. s ̸= 0 implies h(s) ̸= 0). It is also simple to check that h satisfies condition R3. Thus, h reduces Pn to P ′ . Since this reduction works for any n > 1, this means that all problems Pn can be reduced to the problem P ′ where a single state is being used to represent n states in Pn. The memoryless policy µ(ω) = Dec if ω = + solves P ′ and each problem Pn. ■

We turn now to the conditions under which a policy that solves a problem P ′ will also solve problems that can be reduced to P ′ . First of all, from the definition above, it follows that when h reduces P into P ′ , any memoryless policy µ for P ′ is a memoryless policy for P; i.e., µ is executable in P: 1

Theorem 2 (Executability). If µ is a policy for P ′ and h reduces P into P ′ , then µ is a policy for P .

We consider next the trajectories τ generated by the policy µ in P, and the sequences h(τ) that such trajectories induce over P ′ , where h(τ) is the trajectory τ = 〈s0, a0, s1, a1, . . .〉 with the states si replaced by h(si); i.e., h(τ) = 〈h(s0), a0, h(s1), a1, . . .〉. The first result is that when h is a reduction of P into P ′ , h maps trajectories τ generated by a policy µ in P into sequences h(τ) that are µ-trajectories in P ′ :

1 Formal proofs omitted for lack of space.

Theorem 3. For a reduction h of P into P ′ , if µ is a policy for P ′ and τ = 〈s0, a0, s1, a1, . . .〉 is a µ-trajectory in P, then h(τ) is µ-trajectory in P ′ .

From R5, it follows that if the µ-trajectory τ doesn't reach a goal in P, the µ-trajectory h(τ) doesn't reach a goal in P ′ either. If µ is a solution of P ′ , however, and the µ-trajectory h(τ) is fair, then h(τ) must reach the goal in P ′ . Hence,

Theorem 4 (Structural Generalization). Let µ be a policy that solves P ′ and let h be a reduction from P into P ′ . Then µ solves P if h maps the fair µ-trajectories τ in P into trajectories h(τ) that are fair in P ′ .

We'll illustrate the use of this theorem and some of its corollaries below. A first corollary is that a sufficient condition for a policy µ to generalize from P ′ to a problem P that can be reduced to P ′ arises when µ is terminating in P :

Theorem 5. Let µ be a policy that solves P ′ . The policy µ solves a problem P that can be reduced to P ′ if all the fair µ-trajectories in P are finite.

One way in which we'll be able to show the termination of a policy µ on problems P is by showing that the policy µ is monotonic, meaning that when action µ(o(s)) is applied to any (non-goal) state s, then s will not be reachable from the resulting states s′ while following the policy. Often this can be shown with structural arguments in a simple manner. For example, in the Countdown problem, if s > 0 and µ(o(s)) = Dec, then s won't be reachable from the resulting state if the policy µ doesn't include the action Inc in some (reachable) state. Clearly if a policy µ is monotonic in P, then µ must terminate in P. In other cases, however, showing termination may be as hard as showing that µ solves the problem itself.

Example: Countdown (continued). The problem Pn with n + 1 states i = 0, . . . , n reduces to the non-deterministic problem P ′ with 2 states through the function h(0) = 0 and h(i) = 1 for i > 0. The policy µ(ω) = Dec for ω = + solves P ′ because (1, Dec, 0) ∈ F ′ and hence fair µ-trajectories that start in the state 1 in P ′ reach goal 0. Theorem 5 says that µ solves Pn for any n > 1 if µ-trajectories in Pn terminate, which holds since µ is monotonic (see above).

It's also important to see variations on which the generalization does not work. For this, let P ′n be a problem like Pn but with a "buggy" Dec action that sets the counter back to n from 1; i.e., with F(Dec, 1) = {n}. The function h still reduces P ′n into P ′ because the new transition n ∈ F(Dec, 1) requires the transition h(n) ∈ F ′ (Dec, h(1)) which is true in F ′ as h(n) = h(1) = 1 and 1 ∈ F ′ (Dec, 1). Yet, the µtrajectories τ that start in any state i > 0 in P ′n , consist of the sequence i, i - 1, . . . , 1 followed by the loop n, n - 1, . . . , 1. Such trajectories τ are fair in P ′n , that is deterministic, but result in trajectories h(τ) = 〈1,Dec, 1,Dec, . . .〉 that are not fair in P ′ , as the transition (1,Dec, 0) in P ′ never occurs. Thus, h reduces P ′n into P ′ but does not reduce fair trajectories in P ′n into fair trajectories in P ′ , and Theorem 4 can't be used to generalize µ from P ′ into P ′n . ■

4 The Structure of Abstract Problems

In the Countdown example, the non-deterministic problem P ′ is used to show that the policy that solves the instance P1 generalizes to any instance Pn, n > 1. The problem P ′ , however, is very similar to P1; indeed, it is the problem P1 with an additional state transition (s, a, s′ ) for a = Dec and s = s′ = 1. As we will see, this pattern is common, and we will often show that a solution to P generalizes to another problem Q in the same class by considering a problem P ′ that is like P but augmented with an extra set of possible transitions E. We make explicit the structure of such problems P ′ by writing them as P +E. Recall that a transition (s, a, s′ ) is in P when a is applicable in s and s′ is a possible successor, i.e., a ∈ A(s) and s′ ∈ F(a, s).

Definition 6 (Admissible Extensions). Let µ be a policy for problem P. An extension E to P given µ is a set of triplets (s, a, s′ ) for states s and s′ in P and a = µ(s) such that (s, a, s′ ) is not a transition in P. The extension is admissible if each state s′ in such triplets is reachable by µ in P.

Definition 7 (Structured Abstractions). Let µ be a policy for P and let E be an admissible extension to P given µ. P +E denotes the problem P augmented with the transitions in E.

In Countdown, P ′ is P1 + E where E = {(s,Dec, s)} for s = 1 is an admissible extension. Clearly,

Theorem 8. If µ is a policy that solves P, and E is an admissible extension of P given µ, µ solves P + E.

For using the structure of problems P +E for generalization, however, a corresponding notion of fairness is required:

Definition 9 (P-fairness). Let µ be a policy for P and let E be an admissible extension of P given µ. A µ-trajectory τ in P +E is P-fair if for any transition (s, a, s′ ) in P that occurs infinitely often in τ, other transitions (s, a, s′′ ) in P occur infinitely often in τ too.

In other words, a trajectory τ generated by µ in P + E is P-fair if it doesn't skip P-transitions forever although it may well skip E transitions. Our main result follows:

Theorem 10 (Main). Let µ be a policy that solves P and let h be a reduction from a problem Q into P + E where E is an admissible extension of P given µ. Then µ solves Q if h maps the fair µ-trajectories τ in Q into trajectories h(τ) that are P-fair in P +E.

Thus a policy µ for P generalizes to Q if 1) Q is structurally similar to P in the sense that Q can be reduced to P +E, and 2) the reduction h maps µ-trajectories τ in Q into h(τ) trajectories in P + E that eventually evolve according to P, not P + E. Theorem 4 is a special case of this result when E is empty. When P is deterministic, P-fairness can be shown by bounding the number of E-transitions in the executions:

Theorem 11. Let τ be a µ-trajectory for the problem P +E. If P is deterministic and transitions (s, a, s′ ) from E occur a finite number of times in τ, then τ is P-fair.

5 Projections and Restrictions

We consider next two ways of replacing the problems P and Q mentioned in the theorems by suitable simplifications.

5.1 Projections over the Observations

A standard way by which a problem P can be reduced into a smaller problem P ′ is by projecting P onto the space of observations. We formalize this in terms of a function hobs and a projected problem P o :

Definition 12. For P = 〈S, S0, T, A, F, o〉, the function hobs is defined as hobs(s) = o(s), and the problem P o as the tuple P o = 〈S′ , S′0 , T ′ , A′ , F ′ , o′ 〉 with

1. S′ = {ω | ω ∈ Ωo},
2. A′ (ω) = ∩sA(s) for all s in S such that o(s) = ω,
3. o′ (ω) = ω,
4. ω′ ∈ F ′ (a, ω) iff there is s′ ∈ F(a, s) such that ω = o(s), ω′ = o(s′ ), and a ∈ A′ (ω),
5. S′0 = {o(s) | s ∈ S0},
6. T ′ = {o(s) | s ∈ T}.

By construction, the function hobs complies with conditions R1-R4 for being a reduction of problem P into P o but it does not necessarily comply with R5. For this, an extra condition is needed on P; namely, that goals states s are observable; i.e., o(s) ̸= o(s′ ) when s ∈ T and s′ /∈ T :

Theorem 13. If P = 〈S, S0, T,A, F, o〉 is a problem with observable goals, hobs(s) reduces P into P o .

It follows that if a policy µ solves P o , µ solves P too if the goals are observable and µ terminates in P .

5.2 Restricted Problems

For showing that a policy µ generalizes from a problem P to a family of problems Q, it is not necessary to use reductions that consider all actions and states. Suitable restrictions can be used instead:

Definition 14. A restriction PR of P = 〈S, S0, T,A, F, o〉 is a problem PR = 〈SR, S0, TR,AR, FR, oR〉 that is like P except for 1) the sets AR(s) of actions applicable at state s may exclude some actions from A(s), and 2) the set SR of states excludes from S those that become unreachable. TR is T ∩ SR, while FR and oR are the functions F and o in P restricted to the states in SR.

A particular type of restriction PR arises when the sets of applicable actions is restricted to contain a single action, and in particular, the action determined by µ. We denote with Pµ the restriction PR of P where AR(s) = {µ(o(s))} for each state s. For a policy µ to generalize from P to Q, it suffices to consider functions h that reduce Qµ into Pµ +E:

Theorem 15. Let µ be a policy that solves P and let h be a reduction from Qµ into Pµ + E where E is an admissible extension of P given µ. Then µ solves Q if h maps the fair µ-trajectories τ in Qµ into trajectories h(τ) that are P-fair in Pµ + E.

Restrictions also enable the use of the reduction hobs in problems where the goals are not observable. Indeed, Pµ reduces to P o µ if the states s that may be confused with goal states s′ in P are not reachable by µ in P.

6 Examples

Dust-Cleaning Robot. There is a 1 × n grid whose cells may be dirty or not, and a cleaning robot that is positioned on the leftmost cell. The task for the robot is to clean all the cells. The actions allow the robot to move right and to suck dirt. Formally, P = Pn is the problem 〈S, S0, T,A, F, o〉 whose states are of the form 〈i, d1, . . . , dn〉, where i ∈ [1, n] denotes the robot location and dk ∈ {0, 1} denotes whether cell k is clean or dirty. The set S0 contains the 2n states 〈1, d1, . . . , dn〉 where the robot is at the leftmost cell. The set T of goals contains all states 〈i, d1, . . . , dn〉 where each dk = 0. The actions in A are Suck and Right, both applicable in all the states, with F(Suck, 〈i, d1, . . . , di, . . . , dn〉) = {〈i, d1, . . . , 0, . . . , dn〉}, F(Right, 〈i, d1, . . . , dn〉) = {〈i + 1, d1, . . . , dn〉} for i < n, and F(Right, 〈i, d1, . . . , dn〉) = {〈i, d1, . . . , dn〉} for i = n. The observation function o is such that o(〈i, d1, . . . , dn〉) is the pair 〈o1, o2〉 where o1 ∈ {e,m} reveals the end of the corridor (e), and o2 ∈ {d, c} whether the current cell is dirty or clean.

We consider a reduction of the deterministic problem Pn with n×2n states into the problem P +E with 8 states where P is P2, and E comprises two transitions (s, a, s′ ) where s = 〈1, d′1 , d′2 〉, a = Right, and s′ is either 〈1, 0, d′2 〉 or 〈1, 1, d′2 〉. That is, P + E is like P2 but when the robot is not in the rightmost cell, the action Right can "fail" leaving the robot in the same cell, making the cell either clean or dirty.

The policy µ, µ(〈o1, o2〉) = Suck if o2 = d, and µ(〈o1, o2〉) = Right if o1 = m and o2 = c, solves the problem P2 and can be shown to solve any problem Pn. For this, the restriction Qµ of Q = Pn can be reduced into the restriction Pµ + E for P = P2 with the function h(〈i, d1, . . . , dn〉) = 〈i′ , d′1 , d′2 〉 such that i′ = 1 and d′1 = di for i < n, and else i′ = 2 and d′1 = 0, with d′2 = dn in both cases. In addition, since the policy µ terminates in any problem Pn as it's monotonic (actions Suck and Right in µ have effects that are not undone by µ), the trajectories h(τ) in Theorem 15 must be finite and fair, from which it follows that µ solves Pn for any n and any initial configuration of dirt. ■

Wall Following. We consider next the problem of finding an observable goal in a room with some columns. The agent can sense the goal and the presence of a wall on its right side and in front. The actions are move forward (F), rotate left (L) and right (R), and rotate left/right followed by a forward movement (LF/RF). An n ×m instance is a tuple Pn,m = 〈S, S0, T, A, F, o〉 whose states s are of the form (c, d) where c ∈ [1, n] × [1, m] is a cell in the grid and d ∈ {n, s, e, w} is the heading of the agent. The initial state is (1, 1, e) and the observable goal state is associated with a goal cell. The state transitions are the expected ones, except that actions that try to leave the grid and actions that are applied at states (c, d) where c is in a column have no effect. For simplicity, the columns are modeled as observable cells to be avoided. The observation function o maps each state s into an observation in Ωo = { , ▷ , ▷ , ▷ } where o(s) = if s ∈ T, and o(s) is ▷ , ▷ , or ▷ according to whether the agent senses wall on its right side and front.

The wall-following policy µ that we consider executes F when observing ▷ , Lwhen observing ▷ , and RF when observing ▷ . We want to illustrate how this policy generalizes to the class of Pn,m problems consisting of any number of columns separated by two or more spaces, where the columns have any height shorter than m- 1 and any (positive) width, and the goal is in first row to the right of an empty cell. The policy generalizes to a larger class of problems but these restrictions are sufficiently general and make the analysis simpler.

Figure 1 shows the problem P in this class that we use to show that µ solves the other problems such as the one shown on the right. The set of transitions E needed to reduce any Qµ to Pµ + E includes the triplets (s, a, s′ ) where a = F and 〈s, s′ 〉 is either 〈(ℓ8, e), (ℓ2, e)〉, or 〈(ℓi, d), (ℓi, d)〉, for i = 3, 5, 7, 8, any heading d, and the cells ℓi shown on the left of Figure 1.

The function h that reduces Qµ into Pµ + E maps states (c, d) in Qµ into states (g(c), d) in Pµ +E, while preserving the heading d. The function g is obtained from the cell labeling shown in Fig. 1; namely, g(c) = c′ if cell c in Qµ has the label c′ which corresponds to a particular cell in Pµ on the left. While we are showing the function g for the particular problem Q shown, g can be defined to apply to any problem in the class.

In order to apply Theorem 15, we need to prove that h is a reduction, that E is an admissible extension of P given µ, and that the single trajectory τ generated by µ in Q maps into a trajectory h(τ) where E-transitions occur a finite number of times. The first two parts are left to the reader. The right part of Fig. 1 shows the trajectory τ that is finite so that the last condition is true as well. One could prove such termination by monotonicity arguments but more insight can be gained by looking at the trajectory h(τ) where states s in τ are replaced by h(s). The sequence of cells in the states appearing in h(τ) corresponds to the sequence of labels ℓi shown in the figure on the right. Interestingly, it's possible to show that the set of label sequences that result for the different problems Q for which Theorem 15 applies given P, E, and h as above, corresponds to a regular language; namely, the language that is captured by the regular expression ℓ+1 (ℓ22 ℓ+3 ℓ4ℓ+5 ℓ6ℓ+7 ℓ8ℓ+8 )∗ ℓ9. ■

7 Finite-State Controllers

A finite-state controller (FSC) is a tuple C = 〈Q, A, Ω, δ, q0〉 where Q is the set of controller states, A and Ω are sets of actions and observations, q0 ∈ Q is the initial controller state, and δ is (partial) transition function that maps controller state and observation pairs 〈q, o〉 ∈ Q × Ω into action and controller state pairs 〈a, q′ 〉 ∈ A×Q. A controller C can also be represented by tuples 〈q, o, a, q′ 〉 that express that the transition function δ maps the pair 〈q, o〉 into the pair 〈a, q′ 〉.

A controller C generates a C-trajectory made of interleaved sequences of pairs and actions where the pairs bundle a problem state s with a controller state q. That is, a C-trajectory is a sequence 〈(s0, q0), a0, (s1, q1), a1, . . .〉 where s0 ∈ S0 and q0 is the initial controller state, si+1 ∈ F(ai, si) for i ≥ 0, and C contains the tuples 〈qi, oi, ai, qi+1〉 where oi = o(si) for i ≥ 0. A controller C for a problem P must be executable and hence we assume that a tuple 〈q, o, a, q′ 〉 in C implies that a ∈ A(s) for every state s with o(s) = o. A controller C solves P if all the fair C-trajectories τ that it generates reach a goal state, where a trajectory is fair if it is finite and maximal, or transitions 〈(s, q), a, (s′ , q′ )〉 appear infinitely often in τ when transitions 〈(s, q), a, (s′′ , q′′ )〉 appear infinitely often for s′′ ̸= s′ and s′ ∈ F(a, s). The key difference with memoryless policies is that the action ai selected at step i does not depend only on the observation oi but also in the controller state qi. The notions and results for memoryless controllers extend in a natural way to FSCs:

Theorem 16. If C is a controller that solves P ′ and h reduces P into P ′ , then C is controller for P, and for every C-trajectory τ generated by C in P, there is a C-trajectory h(τ) generated by C in P where h(τ) is τ with the (problem) states s replaced by h(s).

Theorem 17. Let C be a finite-state controller that solves P and let h reduce Q into P + E where E is admissible extension of P given C. Then C solves Q if the fair C-trajectories τ in Q map into trajectories h(τ) that are P-fair in P +E.

A C-trajectory τ is P-fair in P +E when the sequence of states and actions in τ is P-fair in the sense defined above (no P-transitions skipped for ever). As before, the function h does not need to reduce Q into P + E when the controller C is given, it suffices to reduce QC into PC + E where PC is the restriction of P under C. That is, if PT is defined as the problem P with the transitions (s, a, s′ ) that are not in T excluded, PC is PT where T is the set of transitions (s, a, s′ ) in P that appear in some C-trajectory. With this notion,

Theorem 18. Let C be a finite-state controller that solves P and let h reduce QC into PC +E where E is admissible extension of P given C. Then C solves Q if the fair C-trajectories τ in QC map into trajectories h(τ) that are P-fair in PC +E.

Example: Visual Marker. This problem is from Bonet et al. [2009], inspired by the use of deictic representations [Chapman, 1989; Ballard et al., 1997], and where a visual marker needs to be placed over a hidden green block in a scene that contains a number of block towers. The marker can be moved one cell at a time in each of the four directions. Observations are 'G' for the green block, and pairs where the first component tells whether the marker is next to the table ('T') or not ('-'), and the second whether the cell beneath the marker is empty ('C') or a non-green block ('B'). An (n,m) instance represents a scene in a n ×m grid where the towers do not reach the 'roof', the marker is initially located at the empty cell (1, 1), and exactly one block is green. A simple instance P is shown in Fig. 2 along with the controller C derived by Bonet et al., while a larger instance Q is shown in Fig. 3(b).

The states in P are the pairs (c, g) where c, g ∈ [1, 5] × [1, 4] are the cells for the marker and the hidden green block respectively. The actions affect the cell for the marker leaving the other cell intact. The initial states are the pairs (c, g) where c = (1, 1) and g is one of the 3 cells in the second tower which we denote as gi for i = 1, 2, 3 from the bottom up. The goal states are the pairs (gi, gi) for i = 1, 2, 3. The observation function in P encodes the map as in Wall Following, so that the observation for the state (c, d) for c = (2, 2) and d = (4, 3) is -B, and for c = d = (4, 3) is G.

For proving that the controller C for P generalizes to any problem Q, we consider a general reduction function h and extension E. The states s = (c, g) in QC are mapped into states h(s) = (f1(c, g), f2(g)) in PC that decompose h into two functions: one f2, mapping goal cells into goal cells, the other f1, mapping marker cells into marker cells with a dependence on the goal cell. The function f2(g) is (4, 1) if g = (x, 1), (4, 2) if g = (x, 2), and (4, 3) if g = (x, y) for y > 2. For describing the function f1(c, g) from states s = (c, g) in QC into marker cells in PC, we label the latter as ℓ1 to ℓ8 as shown in Fig. 3 and consider two cases. If c = (x, y), g = (x′ , y′ ) and y = y′ , then the marker is in the goal tower in Q. Such states s = (c, d) are mapped into cells in the goal tower in P; i.e. f1(c, d) = (4, y′′ ) where y′′ = y if y < 3 and y′′ = 3 otherwise. On the other hand, if y ̸= y′ , f1(c, d) is mapped into the unique cell in {ℓ1, . . . , ℓ4} in PC that give rise to the same observation as (c, g) in QC. Fig. 3(b) shows the values of the function f1(c, g) for g = (5, 2) and the various cells c in QC for the particular problem Q shown.

The set of transitions E required for h to reduce QC into PC +E expresses the idea in which the C-trajectories τ in QC get mapped into trajectories h(τ) in PC +E that go back and forth between the non-goal towers and empty cells in P until a goal tower is reached in Q. For this, 27 transitions (s, a, s′ ) need to be added to P in E. If s = (c, g) and s′ = (c′ , g′ ), g and g′ must be equal, and the 9 transitions for each of the three g = gi goal cells in P are as follows. For a = Right, if c = (1, 1), c′ is (1, 1) and (4, 1), and if c = (2, 1), c′ is (1, 1), (2, 1), and (4, 1). For Up and Down, if c = (2, 2), c′ = c, and for Up only and c = (4, 2), c′ = c. Finally, for a = Up and c = (2, 1), c′ = (2, 3). We lack the space for explaining why all these transitions are needed or to prove formally that E is an admissible extension of PC given C and that h does indeed reduce QC into PC + E. Theorem 18 implies that C solves Q if C-trajectories τ in Q map into trajectories h(τ) that contain a finite number of E-transitions. One such trajectory τ is displayed in Fig. 3 for the problemQ shown that follows from the initial state where the hidden green block is at (5, 2). The labels show the PC-cells visited by the trajectory h(τ ) induced over P . ■

8 RelatedWork

Bonet et al. [2009] and Hu and De Giacomo [2013] show how to derive certain types of controllers automatically. The generality of these controllers has been addressed formally in [Hu and De Giacomo, 2011], and in a different form in [Srivastava et al., 2011a] and [Hu and Levesque, 2011]. A related generalized planning framework appears in [Srivastava et al., 2011b] that captures nested loops involving a set of non-negative variables that may be increased or decreased non-deterministically, and where the notion of terminating strong cyclic policies plays a central role. A key difference to these works is that our approach is not "top down" but "bottom up"; namely, rather than solving a (harder) generalized problem to obtain a general solution, we look at solutions to easy problems and analyze how they generalize to larger problems. Our reductions are also related to abstraction and transfer methods in MDP planning and reinforcement learning [Li et al., 2006; Konidaris and Barto, 2007; Taylor and Stone, 2009]. One difference is that these formulations use rewards rather than goals, and hence the abstractions are bound to either preserve optimality (which is too restrictive) or to approximate reward. Our focus on goal achievement makes things simpler and crisper, yet the results do apply to the computation of proper controllers for Goal MDPs and POMDPs.

9 Discussion

We have studied the conditions under which a controller that solves a POND problem P will solve a different problem Q sharing the same actions and observations. A practical consequence of this is that there may be no need for complex models and scalable algorithms for deriving controllers for large problems, as often, controllers derived for much smaller problems sharing the same structure will work equally well. The shared structure involves a common set of actions and observations, which in itself, is a crisp requirement on problem representation. For example, policies for a blocksworld instance won't generalize to another instance when the actions involve the names of the blocks. The same holds for MDP policies expressed as mappings between states and actions. The appeal of so-called deictic or agent-centered representations [Chapman, 1989; Ballard et al., 1997; Konidaris and Barto, 2007] is that they yield sets of actions and observations that are not tied to specific instances and spaces, and hence are general and can be used for representing general policies.