Features, Projections, and Representation Change for Generalized Planning

1 Introduction

Generalized planning is concerned with the characterization and computation of plans that solve many instances at once [Srivastava et al., 2008; Bonet et al., 2009; Srivastava et al., 2011a; Hu and De Giacomo, 2011; Belle and Levesque, 2016; Segovia et al., 2016]. For example, the policy "if left of the target, move right" and "if right of the target, move left", solves the problem of getting to the target in a 1 × n environment, regardless of the agent and target positions or the value of n.

The standard, semantic, formulation of generalized planning due to Hu and De Giacomo [2011] assumes that all the problems in the class share a common set of features and actions. Often, however, this assumption is false. For example, in the Blocksworld, the policy "if the gripper is empty, pick the clear block above x and place it on the table" eventually achieves the goal clear(x) in any instance, yet the set of such instances do not have (ground) actions in common. Indeed, the expression "pick up the clear block above x" may mean "pick block a from b" in one case, and "pick block c from d" in another. A similar situation arises in most of the standard relational planning domains. Instances share the same action schemas but policies cannot map features into action schemas; they must select concrete, ground, actions.

In this work, we show how to extend the formulation of generalized planning to relational domains where the set of actions and objects depend on the instance. This is done by projecting the actions over a common set of features, resulting in a common set of general actions that can be used in generalized plans. We also address the computation of the resulting general policies by means of transformations and fully observable non-deterministic (FOND) planners, and discuss the relevance to work on learning general policies.

Generalized planning has also been formulated as a problem in first-order logic with solutions associated with programs with loops, where actions schemas do not need to be instantiated [Srivastava et al., 2011a]. The resulting formulation, however, is complex and cannot benefit from existing propositional planners. First-order decision theoretic planning can also be used to generate general plans but these are only effective over finite horizons [Boutilier et al., 2001; Wang et al., 2008; van Otterlo, 2012].

The paper is organized as follows. We review the definition of generalized planning and introduce abstract actions and projections. We then consider the computation of generalized policies, look at examples, and discuss related work and challenges.

2 Generalized Planning

The planning instances P that we consider are classical planning problems expressed in some compact language as a tuple P = 〈V, I,A,G〉 where V is a set of state variables that can take a finite set of values (boolean or not), I is a set of atoms over V defining an initial state s0, G is a set of atoms or literals over V describing the goal states, and A is a set of actions a with their preconditions and effects that define the set A(s) of actions applicable in any state s, and the successor state function f(a, s), a ∈ A(s). A state is a valuation over V and a solution to P is an applicable action sequence

π = a0, . . . , an that generates a state sequence s0, s1, . . . , sn where sn is a goal state (makes G true). In this sequence, ai ∈ A(si) and si+1 = f(ai, si) for i = 0, . . . , n-1. A state s is reachable in P if s = sn for one such sequence.

A general planning problem Q is a collection of instances P assumed to share a common set of actions and a common set of features or observations [Hu and De Giacomo, 2011]. A boolean feature p for a class Q of problems represents a function φp that takes an instance P fromQ and a reachable state s in P , 1 and results in a boolean value denoted as φp(s), with the reference to the problem P omitted. Features are sometimes associated with observations, and in such cases φp is a sensing function. For example, if Q is the class of all block instances with goal on(a, b) for two blocks a and b, above(a, b) would be a feature that is true when a is above b. If F denotes the set of all boolean features, φF (s) denotes the values of all features in the state s.

A general policy or plan for a class of problems Q sharing a common set of boolean features and actions is a partial function π that maps feature histories into actions. A policy π solves the generalized problem Q if it solves each instance P in Q. A policy π solves P if the state trajectory s0, . . . , sn induced by π on P is goal reaching. In such trajectory, ai = π(φF (s0), . . . , φF (si)), si+1 = f(ai, si) for i < n, and sn is the first state in the sequence where the goal of P is true, the policy π is not defined, or π returns an action an that is not applicable at sn. In the following, for simplicity, we only consider memoryless policies that map single feature valuations into actions and thus ai = π(φF (si)).

2.1 Numerical Features

For extending the formulation to domains where actions take arguments that vary from instance to instance, we need numerical features. A numerical feature n for a generalized problem Q represents a function φn that takes an instance P and a state s, and results in a non-negative integer value denoted as φn(s). For the problem Q representing the Blocksworld instances with goal on(a, b), a numerical feature n(a) can represent the number of blocks above a. The set of features F becomes thus a pair F = 〈B, N〉 of boolean and numerical features B and N. A valuation over F is an assignment of truth values to the boolean features p ∈ B and non-negative integer values to the numerical features n ∈ N. A boolean valuation over F, on the other hand, is an assignment of truth values to the boolean features p ∈ B and to the atoms n = 0 for n ∈ N. The feature valuation for a state s is denoted as φF (s), while the boolean valuation as φB(s). The number of feature valuations is infinite but the number of boolean valuations is 2|F | . Policies for a generalized problem Q over a set of features F = 〈B, N〉 are defined as:

Definition 1 (Generalized Planning). A policy for a generalized problem Q over the features F = 〈B,N〉 is a partial mapping π from boolean valuations over F into the common actions in Q. The policy π solves Q if π solves each instance P in Q; i.e., if the trajectory s0, . . . , sn induced by the policy π in P is goal reaching.

1 Non-reachable states are often not meaningful, like a state when one block is on top of itself.

As before, the trajectory s0, . . . , sn induced by π is such that ai = π(φB(si)), si+1 = f(ai, si) for i < n, and sn is the first state in the sequence where π(φB(sn)) = ⊥, an ̸∈ A(sn), or the goal of P is true.

2.2 Parametric Goals and Features

We are often interested in finding a policy for all instances of a domain whose goal has a special form. For example, we may be interested in a policy for the class Q of all Blocksworld instances with goal of the form on(x, y) where x and y are any blocks. Two instances P and P ′ with goals on(a, b) and on(c, d) respectively, are part of Q with values for x and y being a and b in P , and c and d in P ′ . General features using such parameters can be used, with the value of the parameters in an instance P being determined by matching the goal of P with the generic goal. A parametric feature like n(x) that tracks the number of blocks above x thus represents the feature n(a) in P and the feature n(c) in P ′ .

3 Abstract Actions

A generalized planning problem like "all Blocksworld instances with goal of the form on(x, y)" admits simple and general plans yet such plans cannot be accounted for in the current framework. The reason is that such instances share no common pool of actions. This is indeed the situation in relational domains where objects and actions change across instances. For dealing with such domains, we define the notion of abstract actions that capture the effect of actions on the common set of features.

The abstract actions for a generalized problem Q are defined as pairs ¯a = 〈Pre; Eff 〉 where Pre and Eff are the action precondition and effects expressed in terms of the set of features F = 〈B,N〉. The syntax is simple: preconditions may include atoms p and n = 0 or their negations, for p ∈ B and n ∈ N, and effects may be boolean, p or ¬p for p ∈ B, or numerical increments and decrements expressed as n↑ and n↓ respectively for n ∈ N. In the language of abstract actions, features represent state variables (fluents), not functions, with n representing a non-negative integer, and n↑ and n↓ representing updates n := n+∆ and n := n-∆′ for random positive integers ∆ and ∆′ that are not allowed to make n negative. The numerical updates are thus non-deterministic. The negation of atom n = 0 is expressed as n > 0 and it must be a precondition of any abstract action that decrease n for ensuring that n remains non-negative.

Definition 2. An abstract action ¯a over the features F = 〈B,N〉 is a pair 〈Pre; Eff 〉 such that 1) each precondition in Pre is a literal p or ¬p for p ∈ B, or a literal n = 0 or n > 0 for n ∈ N, 2) each effect in Eff is a boolean literal over B, or a numerical update n↑ or n↓ for n ∈ N, and 3) n > 0 is in Pre if n↓ is in Eff .

We want abstract actions that represent the diverse set of concrete actions in the different instances P of the generalized problem Q. The number of concrete actions across all instances in Q is often infinite but the number of abstract actions is bounded by 32|F| .

Abstract actions operate over abstract states ¯ s that are valuations over the feature variables. An abstract action ¯a =

〈Pre; Eff 〉 represents a concrete action a over a state s in instance P if the two actions are applicable in s, and they affect the values of the features in a similar way. Let us say that Pre is true in s if Pre is true in the valuation φB(s). Then:

Definition 3. The abstract action ¯a = 〈Pre; Eff 〉 over a set of features F represents the action a on the state s of instance P in Q iff 1) the preconditions of a and ¯a both hold in s, and 2) the effects of a and ¯a over F are similar:

1. for each boolean feature p in B, if p changes from true to false (resp. from false to true) in transition s ⇝ f(a, s) then ¬p ∈ Eff (resp. p ∈ Eff ),
2. for each boolean feature p in B, if p (resp. ¬p) is in Eff , then p is true (resp. false) in f(a, s), and
3. for each numerical feature n in N, n↓ (resp. n↑) in Eff iff φn(f(a, s)) < φn(s) (resp. φn(f(a, s)) > φn(s)).

Example. Let Qclear be the set of Blocksworld instances P with goal of the form clear(x) and initial situation where the arm is empty, 2 and let F = {H, n(x)} be the set of features where H holds iff the arm is holding some block, and n(x) counts the number of blocks above x. The abstract action

represents any action that picks up a block from above x, as it makes H true and decreases the number of blocks above x. If P is an instance with goal clear(a) and s is a state where on(b, a), on(c, b), and clear(c) are all true, ¯a represents the action Unstack(c, b) as both actions, the abstract and the concrete, are applicable in s, make H true, and decrease n(x). Likewise,

represents any action that places the block being held anywhere but above x (as it does not affect n(x)). In the state s′ that results from the state s and the action Unstack(c, b), ¯a′ represents the action Putdown(c), and also Stack(c, d) if d is a block in P that is clear in both s and s′ .

We say that an abstract action ¯a is sound when it represents some concrete action in each (reachable) state s of each instance P of Q where ¯a is applicable:

Definition 4. An abstract action ¯a = 〈Pre; Eff 〉 is sound in the problem Q over the features F iff for each instance P in Q and each reachable state s in P where Pre holds, ¯a represents one or more actions a from P on the state s.

The abstract action (1) is sound in Qclear as in any reachable state of any instance where the arm is empty and there are blocks above x, there is an unstack action that makes the feature H true and decreases the number of blocks above x. The abstract action (2) is sound too. The two actions, however, do not provide a complete representation:

Definition 5. A set A of abstract actions over the set of features F is complete for Q if for any instance P in Q, any reachable state s of P, and any action a that is applicable at s, there is an abstract action ¯a in A that represents a on s.

2 Throughout, Blocksworld refers to the encoding with action schemas Stack(x, y), Unstack(x, y), Pickup(x), and Putdown(x).

The set made of the two actions above is not complete as they cannot represent concrete actions that, for example, pick up the target block x or a block that is not above x.

Example. A sound and complete set of abstract actions AF ′ for Qclear can be obtained with the features F ′ = {X,H,Z, n(x),m(x)} where H, X, and Z represent that block x is being held, that some other block is being held, and that there is a block below x respectively. The new counter m(x) tracks the number of blocks that are not in the same tower as x or being held. The abstract actions in AF ′ , with names for making their meaning explicit, are:

• Pick-x-some-below=〈¬H,¬X,n(x)=0,Z;X,¬Z,m(x)↑〉,
• Pick-x-none-below = 〈¬H, ¬X, n(x) = 0, ¬Z; X〉,
• Pick-above-x = 〈¬H, ¬X, n(x) > 0; H, n(x)↓〉,
• Pick-other = 〈¬H, ¬X, m(x) > 0; H, m(x)↓〉,
• Put-x-on-table = 〈X; ¬X〉,
• Put-x-above-some = 〈X; ¬X, Z, m(x)↓〉,
• Put-aside = 〈H; ¬H,m(x)↑〉,
• Put-above-x = 〈H; ¬H, n(x)↑〉.

4 Generalized Planning Revisited

The notion of generalized planning can be extended to relational domains, where instances share no common pool of actions, by moving to the abstract representation provided by abstract actions:

Definition 6. Let Q be a generalized planning problem, F be a set of features, and AF be a set of sound abstract actions. A policy for Q over F is a partial mapping π from the boolean valuations over F into AF . The (abstract) policy π solves Q if π solves each instance P in Q; i.e., if all the trajectories s0, . . . , sn induced by π in P are goal reaching.

Abstract policies π map boolean valuations over F into sound abstract actions. We write ai ∈ π(φB(si)) to express that ai is one of the concrete actions represented by the abstract action ¯ai = π(φB(si)) in the state si of instance P. Since the abstract actions in AF are assumed to be sound, there must be one such concrete action ai over any reachable state si of any problem P where ¯ai is applicable. Such concrete action, however, is not necessarily unique. The trajectories s0, . . . , sn induced by the policy π in P are such that ai ∈ π(φB(si)), si+1 = f(ai, si) for i < n, and sn is the first state in the sequence where the goal of P is true, π(φB(sn)) = ⊥, or an ̸∈ A(sn).

Example. For the generalized problem Qclear with features F = {H, n(x)}, and actions (1) and (2), the following policy, expressed in compact form in terms of two rules, is a solution:

The policy picks blocks above x and puts them aside (not above x) until n(x) becomes zero.

5 Computation

We focus next on the computation of general policies. We proceed in two steps. First, we map the generalized problem Q given features F = 〈B,N〉 and a set AF of sound actions into a numerical non-deterministic problem QF . While numerical planning problems can be undecidable [Helmert, 2002], these numerical problems are simpler and correspond to the so-called qualitative numerical problems (QNPs) whose solutions can be obtained using standard, boolean FOND planners [Srivastava et al., 2011b; Bonet et al., 2017].

5.1 Feature Projection QF

For defining the first reduction, we assume a set AF of sound abstract actions and formulas IF and GF , defined over the atoms p for p ∈ B and n = 0 for n ∈ N, that provide a sound approximation of the initial and goal states of the instances in Q. For this, it must be the case that for any instance P in Q: a) the truth valuation φB(s) for the initial state s of P satisfies IF , and b) the reachable states s in P with a truth valuation φB(s) that satisfies GF are goal states of P.

Definition 7. For a given set of sound abstract actions AF , and sound initial and goal formulas IF and GF for Q, the projection QF = 〈VF , IF , GF , AF 〉 of Q is a numerical, nondeterministic planning problem with actions AF , initial and goal situations IF and GF , and state variables VF = F .

The states in a projection QF are valuations ¯ s over the features F that in QF , like in abstract actions, represent state variables and not functions. The possible initial states are the valuations that satisfy IF , the goal states are the ones that satisfy GF , and the actions are the abstract actions in AF .

Solutions to a projection QF are partial policies π that map boolean valuations over F into actions in AF such that all the state trajectories induced by π in QF are goal reaching. A state trajectory ¯ s0, . . . , ¯ sn is induced by π in QF if ¯ s0 is a state that satisfies IF , ¯ai = π(¯ si), ¯ si+1 ∈ ¯ F (¯ai, ¯ si) for i < n, and ¯ sn is the first state in the sequence where GF is true, π(¯ sn) is not defined, or ¯an is not applicable in ¯ sn. ¯ F(·, ·) is a non-deterministic transition function defined by the actions in AF in the usual way. The soundness of IF , GF , and AF imply the soundness of the projection QF :

Theorem 8. If AF is a set of sound abstract actions for the features F, and the formulas IF and GF are sound for Q, then a solution π for QF is also a solution for Q.

To see why this results holds, notice that if ¯ai is an abstract action applicable in ¯ si and s, where s is a state for some instance P in Q, then there is at least one concrete action ai in P that is represented by ¯ai in s. Also, for every state trajectory s0, . . . , sn induced by the policy π on P , there is one abstract state trajectory ¯ s0, . . . , ¯ sn induced by π in QF that tracks the values of the features, i.e. where ¯ si = φF (si) for i = 0, . . . , n, as a result of the soundness of AF and the definition of IF . Since the latter trajectories are goal reaching, the former must be too since GF is sound.

The projections QF are sound but not complete. The incompleteness is the result of the abstraction (nondeterministic feature increments and decrements), and the choice of AF , IF , and GF that are only assumed to be sound.

Example. Let us consider the features F = {H, n(x)}, the set of abstract actions AF = {¯a, ¯a′ } given by (1) and (2), IF = {¬H, n(x) > 0}, and GF = {n(x) = 0}. The policy given by (3) solves the projection QF = 〈VF , IF , GF , AF 〉 of Qclear, and hence, by Theorem 8, also Qclear.

5.2 Boolean Projection and FOND ProblemQ+F

The second piece of the computational model is the reduction of the projection QF into a standard (boolean) fully observable non-deterministic (FOND) problem. For this we exploit a reduction from qualitative numerical planning problems (QNPs) into FOND [Srivastava et al., 2011b; Bonet et al., 2017]. This reduction replaces the numerical variables n by propositional symbols named "n = 0" that are meant to be true when the numerical variable n has value zero. The negation of the symbol "n = 0" is denoted as "n > 0".

Definition 9. Let Q be a generalized problem and QF be a projection of Q for F = 〈B,N〉. The boolean projection Q′F associated with QF is the FOND problem obtained from QF by replacing 1) the numerical variables n ∈ N by the symbols n = 0, 2) first-order literals n = 0 by propositional literals n = 0, 3) effects n↑ by deterministic effects n > 0, and 4) effects n↓ by non-deterministic effects n > 0 | n = 0.

The boolean projection Q′F is a FOND problem but neither the strong or strong cyclic solutions of Q′F [Cimatti et al., 2003] capture the solutions of the numerical problemQF . The reason is that the non-deterministic effects n > 0 | n = 0 in Q′F are neither fair, as assumed in strong cyclic solutions, nor adversarial, as assumed in strong solutions. They are conditionally fair, meaning that from any time point on, infinite occurrences of effects n > 0 | n = 0 (decrements) imply the eventual outcome n = 0, on the condition that from that point on, no action with effect n > 0 (increment) occurs.

The policies of the boolean FOND problem Q′F that capture the policies of the numerical problemQF are the strong cyclic solutions that terminate [Srivastava et al., 2011b]. We call them the qualitative solutions of Q′F and define them equivalently as:

Definition 10. A qualitative solution of the FOND Q′F = 〈V ′F , I ′F , G′F , A′F 〉 is a partial mapping π from boolean feature valuations into actions in A′F such that the state-action trajectories induced by π over Q′F that are conditionally fair are all goal reaching.

A state-action trajectory s′0 , a′0 , s′1 , . . . over Q′F is not conditionally fair iff a) it is infinite, b) after a certain time step i, it contains infinite actions with effects n > 0 | n = 0 and no action with effect n > 0, and c) there is no time step after i where n = 0. The qualitative solutions of Q′F capture the solutions of the numerical projection QF exactly:

Theorem 11. π is a qualitative solution of the boolean FOND Q′F iff π is a solution of the numerical projection QF .

This is because for every trajectory s0, s1, . . . induced by policy π over the numerical problemQF , there is a trajectory s′0 , s′1 , . . . induced by π over the boolean problem Q′F , and vice versa, where s′i is the boolean projection of the state si; namely, p is true in s′i iff p is true in si, and n = 0 is true (resp. false) in s′i iff n has value (resp. greater than) 0 in si.

We say that Q+F is a qualitative FOND associated with the boolean projection Q′F if the strong cyclic solutions π of Q+F represent qualitative solutions of Q′F ; i.e., strong cyclic solutions of Q′F that terminate [Srivastava et al., 2011b]. Under some conditions, roughly, that variables that are decreased by some action are not increased by other actions, Q+F can be set to Q′F itself. In other cases, a suitable translation is needed [Bonet et al., 2017]. Provided a sound translation, 3 solutions to a generalized problem Q can be computed from Q+F using off-the-shelf FOND planners: 4

Theorem 12. Let QF be a feature projection of a generalized problem Q, and let Q+F be a qualitative FOND problem associated with the boolean projection Q′F . The strong cyclic solutions of Q+F are solutions of the generalized problem Q.

This is a soundness result. Completeness is lost already in the reduction from Q to QF as discussed above.

Example. For Qclear and the projection QF above with F = {H, n(x)}, the boolean projection Q′F = 〈V ′F , I ′F , G′F , A′F 〉 has boolean variables V ′F = {H, n(x) = 0}, initial and goal formulas I ′F = {¬H, n(x) > 0} and G′F = {n(x) = 0}, and actions A′F = {¯a′1 , ¯a′2 } where ¯a′1 = 〈¬H, n(x) > 0; H, n(x) > 0 | n(x) = 0〉 and ¯a′2 = 〈H; ¬H〉. Since there are no actions in QF that increment the numerical variable n(x), Q+F is Q′F and hence, by Theorem 12, the strong cyclic solutions to Q′F are solutions to Qclear. The policy shown in (3) was computed from Q′F by the FOND planner MyND [Mattm¨uller et al., 2010] in 58 milliseconds.

6 Examples and Experiments

We illustrate the representation changes and the resulting methods for computing policies in four problems. Experiments were done on an Intel i5-4670 CPU with 8Gb of RAM.

6.1 Moving in Rectangular Grids

The generalized problemQmove involves an agent that moves in an arbitrary n ×m grid. The instances P are represented with atoms at(x, y) and actions Move(x, y, x′ , y′ ), and have goals of the form at(x∗ , y∗ ). A general policy for Qmove can be obtained by introducing the features ∆X = |x∗ - xs| and ∆Y = |y∗ - ys| where at(xs, ys) is true in the state s. A projection QF of Qmove is obtained from this set of features F, the goal formula GF = {∆X = 0,∆Y = 0}, and the initial DNF formula IF with four terms corresponding to the four truth valuations of the atoms ∆X = 0 and ∆Y = 0. The set AF of abstract actions

• Move-in-row = 〈∆X > 0; ∆X↓〉,
• Move-in-column = 〈∆Y > 0; ∆Y ↓〉

is sound and captures the actions that move the agent toward the target horizontally and vertically. AF is not complete as it is missing the two abstract actions for moving away from the target. The boolean projection Q′F is QF with the atoms ∆X = 0 and ∆Y = 0, and their negations, interpreted as propositional literals, and the two actions transformed as:

3 The translation by Bonet et al. [2017] is actually not sound in general as claimed. We'll report the fix elsewhere.

4 For this, the formulas IF and GF must be expressed in DNF. Compiling them into conjunctions of literals, as expected by FOND planners, is direct using extra atoms.

• Move-in-row′ = 〈∆X > 0; ∆X = 0 | ∆X > 0〉,
• Move-in-column′ = 〈∆Y > 0;∆Y = 0 |∆Y > 0〉.

The resulting FOND problemQ+F is equal to Q′F . The MyND planner yields the policy below in 54 milliseconds, which from Theorem 12, is a solution of Qmove:

• ∆X > 0, ∆Y > 0 ⇒ Move-in-row′ ,
• ∆X = 0, ∆Y > 0 ⇒ Move-in-column′ .

6.2 Sliding Puzzles

We consider next the generalized problem Qslide where a designated tile t∗ must be moved to a target location (x∗t , y∗ t ) in a sliding puzzle. The STRIPS encoding of an instance P contains atoms at(t, x, y) and atB(x, y) for the location of tiles and the "blank", and actions Move(t, x, y, x′ , y′ ) for exchanging the location of tile t and the blank if in adjacent cells. For solving Qslide, we consider two numerical features: the Manhattan distance ∆t from the current location of the target tile to its target location, and the minimal total distance ∆b that the blank must traverse without going through the current target location so that that target tile can be moved and decrement the value of ∆t.

The feature projection QF has goal formula GF = {∆t = 0}, initial formula IF given by the DNF with four terms corresponding to the four truth valuations of the atoms ∆t = 0 and ∆b = 0, and the two abstract actions

• Move-blank = 〈∆b > 0; ∆b↓〉,
• Move-tile = 〈∆b = 0, ∆t > 0; ∆t↓, ∆b↑〉.

The boolean projection Q′F is QF with the atoms ∆t = 0 and ∆b = 0, and their negations, interpreted as propositional literals, and the two actions transformed as:

• Move-blank′ : 〈∆b > 0;∆b > 0 |∆b = 0〉,
• Move-tile′ : 〈∆b = 0,∆t > 0;∆b > 0,∆t > 0 |∆t = 0〉.

As before, Q+F is equal to Q′F because the only action that increments a variable, ∆b, cannot be used until ∆b = 0. MyND solves Q+F in 65 milliseconds, producing the policy below which by Theorem 12 solves the generalized problem Qmove:

• ∆b > 0, ∆t > 0 ⇒ Move-blank′ ,
• ∆b = 0, ∆t > 0 ⇒ Move-tile′ .

6.3 Blocksworld: Achieving on(x, y)

The problem Qon is about achieving goals of the form on(x, y) in Blocksworld instances where for simplicity, the gripper is initially empty, and the blocks x and y are in different towers with blocks above them. We use a set of features F given by n(x) and n(y) for the number of blocks above x and y, booleans X and H that are true when the gripper is holding x or another block, and on(x, y) that is true when x is on y. As before, we include a sound but incomplete set of actions AF needed to solve Qon where E abbreviates the conjunction ¬X and ¬H:

• Pick-x = 〈E, n(x) = 0; X〉,
• Pick-above-x = 〈E, n(x) > 0; H, n(x)↓〉,
• Pick-above-y = 〈E, n(y) > 0; H, n(y)↓〉,
• Put-x-on-y = 〈X, n(y) = 0; ¬X, on(x, y), n(y)↑〉,
• Put-other-aside = 〈H; ¬H〉.

The projected problem QF has this set of actions AF , IF = {n(x) > 0, n(y) > 0, E, ¬on(x, y)}, and GF = {on(x, y)}. The projection Q′F is QF but with the propositional reading of the atoms n(·) = 0 and their negations, and actions A′F :

• Pick-x′ = 〈E, n(x) = 0; X〉,
• Pick-above-x′ = 〈E, n(x) = 0; H, n(x) > 0 | n(x) = 0〉,
• Pick-above-y′ = 〈E, n(y) = 0; H, n(y) > 0 | n(y) = 0〉,
• Put-x-on-y′ = 〈X, n(y) > 0; ¬X, on(x, y), n(y) > 0〉
• Put-other-aside′ = 〈H; ¬H〉.

Since the effects that increment a variable also achieve the goal, the qualitative problemQ+F is equal to Q′F . The planner MyND over Q+F yields the policy π below in 70 milliseconds, that solves Q+F and hence Qon. The negated goal condition ¬on(x, y) is part of the following rules but it is for reasons of clarity:

• E, n(x) > 0, n(y) > 0 ⇒ Pick-above-x′ ,
• H, ¬X, n(x) > 0, n(y) > 0 ⇒ Put-other-aside′ ,
• H, ¬X, n(x) = 0, n(y) > 0 ⇒ Put-other-aside′ ,
• E, n(x) = 0, n(y) > 0 ⇒ Pick-above-y′ ,
• H, ¬X, n(x) = 0, n(y) = 0 ⇒ Put-other-aside′ ,
• E, n(x) = 0, n(y) = 0 ⇒ Pick-above-x′ ,
• X, ¬H, n(x) = 0, n(y) = 0 ⇒ Put-x-on-y′ .

6.4 Blocksworld: Building a Tower

We consider a final generalized blocks problem, Qtower, where the task is building a tower with all the blocks. For this, we consider the feature set F ′ and the set of abstract actions AF ′ above (end of Sect. 3), with IF ′ = {¬X, ¬H, Z, n(x) > 0,m(x) > 0} and GF ′ = {¬X, ¬H,m(x) = 0}. For space reasons we do not show the projections QF ′ and Q′F ′ , or the problemQ+F ′ fed to the planner. The resulting policy

• ¬X, ¬H, m(x) > 0 ⇒ Pick-other,
• ¬X, H, m(x) > 0 ⇒ Put-above-x,
• ¬X, H, m(x) = 0 ⇒ Put-above-x.

is obtained with the FOND-SAT-based planner [Geffner and Geffner, 2018] in 284 milliseconds (the FOND planner MyND produces a buggy plan in this case). Interestingly, the addition of the atom ¬Z to GF yields a very different policy that builds a single tower but with x at the bottom.

7 Discussion

Arbitrary Goals, Concepts, Indexicals, and Memory

Most of the examples above deal with instances involving atomic goals (except Qtower). The definition of a generalized problem that would yield a policy for solving any Blocksworld instance is more challenging. Inductive, as opposed to model-based approaches, for obtaining such policies have been reported [Mart´ın and Geffner, 2004; Fern et al., 2006]. These approaches learn generalized policies from sampled instances and their plans. They do not learn boolean and numerical features but unary predicates or concepts like "the clear block that is above x", yet features, concepts, and indexical or deictic representations [Chapman, 1989; Ballard et al., 1997] are closely related to each other. The execution of general policies requires tracking a fixed number of features, and hence constant memory, independent of the instance size, that is given by the number of features. This is relevant from a cognitive point view where short term memory is bounded and small [Ballard et al., 1995].

General Policy Size, Polynomial Features, and Width

The numerical feature h∗ that measures the optimal distance to the goal can be used in the policy πGen given by the rule h∗ > 0 ⇒ MoveToGoal for solving any problem. Here MoveToGoal is the abstract action ¯a = 〈h∗ > 0; h∗↓〉 that is sound and represents any concrete optimal action. The problem with the feature h∗ is that its computation is intractable in general, thus it is reasonable to impose the requirement that features should be computable in (low) polynomial time. Interestingly, however, instances over many of the standard classical domains featuring atomic goals have a bounded and small width, which implies that they can be solved optimally in low polynomial time [Lipovetzky and Geffner, 2012]. This means that the general policy πGen is not useless after all, as it solves all such instances in polynomial time. The general policy π computed by FOND planners above, however, involves a fixed set of boolean variables that can be tracked in time that is constant and does not depend on the instance size.

Deep Learning of Generalized Policies, and Challenge

Deep learning methods have been recently used for learning generalized policies in domains like Sokoban [Groshev et al., 2017] and 3D navigation [Mirowski et al., 2016]. Deep learning methods however learn functions from inputs of a fixed size. Extensions for dealing with images or strings of arbitrary size have been developed but images and strings have a simple 2D or linear structure. The structure of relational representations is not so uniform and this is probably one of the main reasons that we have not yet seen deep (reinforcement) learning methods being used to solve arbitrary instances of the blocks world. Deep learning methods are good for learning features but in order to be applicable in such domains, they need the inputs expressed in terms of a fixed number of features as well, such as those considered in this work. The open challenge is to learn such features from data. The relevance of this work to learning is that it makes precise what needs to be learned. A crisp requirement is that the set of features F to be learned for a generalized problem Q should support a sound set of actions AF sufficient for solving the problem.

8 Summary

We have extended the standard semantic formulation of generalized planning to domains with instances that do not have actions in common by introducing abstract actions: actions that operate on the common pool of features, and whose soundness and completeness can be determined. General plans map features into abstract actions, which if sound, can always be instantiated with a concrete action. By a series of reductions, we have also shown how to obtain such policies using off-the-shelf FOND planners. The work relates to a number of concepts and threads in AI, and raises a number of crisp challenges, including the automatic discovery of the boolean and integer features that support general plans in relational domains.

Acknowledgements

We thank the anonymous reviewers for useful comments. H. Geffner is partially funded by grant TIN-2015-67959-P, MINECO, Spain.