Automatic Generation of High-Level State Features for Generalized Planning

1 Introduction

A generalized plan is a single solution valid for a set of planning problems. Generalized plans are usually built with branching and repetition constructs which allow them to solve arbitrarily large problems, and problems with partial observability and non-deterministic actions [Bonet et al., 2010; Hu and Levesque, 2011; Srivastava et al., 2011; Hu and De Giacomo, 2013]. For many problems, generalized plans can only be efficiently computed if branching (and/or repetition) is done according to key features that allow high-level reasoning and help to accurately distinguish between states.

To illustrate this, consider the problem of finding the minimum element in the following list of five integers: (2↪ 5↪ 3↪ 1↪ 4). A classical plan for this problem is the 4-action sequence hinc(i)↪ inc(i)↪ inc(i)↪ j = ii where i and j are list iterators that initially point to the first position in the list, inc(i) increments iterator i, and j = i assigns iterator i to j. The goal is for iterator j to point to the minimum element in the list. The plan fails to generalize since it is no longer valid if the order of the integers in the list is changed or if integers are added to (or deleted from) the list.

A generalized plan can solve this problem for different list orders and sizes. In this work we focus on generalized plans in the form of planning programs [Jim´enez and Jonsson, 2015; Segovia-Aguas et al., 2016]. Figure 1 shows the planning program for finding the minimum element in a list of integers of any size. Instructions on lines 0 and 3, represented with diamonds, are conditional goto instructions that, respectively, jump to line 2 when ⇤i ⌅ ⇤j and to line 0 when i 6= n. The outgoing left branch of a diamond indicates that the condition holds and the right branch that it does not. Instructions on lines 1 and 2 are sequential instructions and are represented with boxes. Finally, end marks the program termination.

In this program, conditions ⇤i < ⇤j and i == n are highlevel state features necessary to compactly represent a solution that generalizes. These features abstract different list contents and sizes as well as different values for iterators i and j. Specifically, condition ⇤i < ⇤j abstracts the set of states where the element pointed to by i is smaller than that pointed to by j. Likewise, i == n abstracts the set of states where iterator i reaches the end of the list, no matter the list size.

In generalized planning problems, high-level state features are traditionally hand-coded which requires significant human expertise. The contribution of this work is to automatically generate the high-level features required to solve a given generalized planning problem. We do so updating the notion of planning programs and extending a previous compilation of generalized planning into classical planning [Jim´enez and Jonsson, 2015; Segovia-Aguas et al., 2016] to tightly integrate the computation of generalized plans with the computation of features in the form of conjunctive queries. The second contribution of this work is bringing a new landscape of challenging benchmarks to classical planning given that our extended compilation naturally models classification tasks as classical planning problems. This allows us to solve problems that integrate planning and classification using an offthe-shelf classical planner.

2 Background

The planning model we consider is classical planning with conditional effects. This formalism allows a generalized plan to repeatedly refer to the same action, while the actual action effects depend on the state in which the action is applied. In this section we also define planning programs, the formalism we use to represent and compute generalized plans.

2.1 Classical PlanningWith Conditional Effects

We represent states in terms of propositional variables or fluents and assume that fluents are instantiated from predicates. Specifically, there exists a set of predicates , and each predicate p 2 has an argument list of arity ar(p). Given a set of objects ⌦, the set of fluents F is induced by assigning objects in ⌦ to the arguments of predicates in , i.e. F = ¶p(!) : p 2 ↪ ! 2 ⌦ar(p) ♦ where, given a set X, Xn is the n-th Cartesian power of X.

A literal l is a valuation of a fluent f 2 F, i.e. l = f or l = ≻f. A set of literals L represents a partial assignment of values to fluents (WLOG we assume that L does not assign conflicting values to any fluent). Given L, let ≻L = ¶≻l : l 2 L♦ be the complement of L. A state s is a set of literals such that ♣s♣ = ♣F♣, i.e. a total assignment of values to fluents.

A classical planning problem with conditional effects is a tuple P = h ↪⌦↪A↪ I↪Gi, where is a set of predicates and ⌦ is a set of objects (inducing a set of fluents F), A is a set of actions, I is an initial state and G is a goal condition, i.e. a set of literals. Each action a 2 A has a set of literals pre(a) called the precondition and a set of conditional effects cond(a). Each conditional effect C BE 2 cond(a) is composed of sets of literals C (the condition) and E (the effect).

Action a is applicable in state s if and only if pre(a) ✓ s, and the resulting set of triggered effects is

i.e. effects whose conditions hold in s. The result of applying a in s is a new state ✓(s↪ a) = (s ∩ ≻e↵(s↪ a)) [ e↵(s↪ a).

A plan for P is an action sequence ⇡ = ha1↪ ▷ ▷ ▷ ↪ ani that induces a state sequence hs0↪ s1↪ ▷ ▷ ▷ ↪ sni such that s0 = I and, for each i such that 1  i  n, ai is applicable in si-1 and generates the successor state si = ✓(si-1↪ ai). The plan ⇡ solves P if and only if G ✓ sn, i.e. if the goal condition is satisfied following the application of ⇡ in I.

2.2 Planning Programs

Our aim is to generate high-level state features to compute generalized plans. Our definition of generalized planning is loosely based on that of Hu and De Giacomo (2011). We define a generalized planning problem P = ¶P1↪ ▷ ▷ ▷ ↪ PT♦ as a set of multiple individual planning problems that share fluents and actions. Consequently, each individual planning problem Pt 2 P is defined as Pt = h ↪⌦↪A↪ It↪Gti, where , ⌦ and A are shared and only the initial state It and goal condition Gt differ from other planning problems in P.

To represent and compute generalized plans we exploit a recent formalism called planning programs [Jim´enez and Jonsson, 2015; Segovia-Aguas et al., 2016]. Given a planning problem P = h ↪⌦↪A↪ I↪Gi, a planning program ⇧ is a numbered list of instructions with each instruction belonging to one of the following three types:

1. Sequential instruction, i.e. an action in A.
2. Conditional goto instruction, goto(i0 ↪ !f) where, i0 is the target program line and f 2 F is the jump condition.
3. Termination instruction marking the program end.

To execute a planning program ⇧ on P , we maintain a current state s, initialized to I, and a program counter pc, initialized to 0. Let w be the instruction on the line indicated by pc. If w 2 A, we update s as s = ✓(s↪w) and increment pc. If w = goto(i0 ↪ !f), we set pc to i0 if f does not hold in s, and increment pc otherwise (as in the original work, we jump whenever the condition f is false). Finally, if w is a termination instruction, execution ends successfully.

Since conditional goto instructions may cause infinite loops, execution fails whenever it reaches a pair of state and program counter (s↪ pc) already visited. A planning program ⇧ solves P if the execution ends successfully and the goal condition holds in the resulting state, i.e. G ✓ s. A planning program ⇧ solves a generalized planning problem P = ¶P1↪ ▷ ▷ ▷ ↪ PT ♦ if it solves every problem Pt 2 P.

Jim´enez and Jonsson (2015) described a compilation that takes a generalized planning problem P = ¶P1↪ ▷ ▷ ▷ ↪ PT♦ as input and produces a single classical planning problem Pn, where n bounds the maximum number of program lines. Briefly, Pn extends the set of fluents of instances in P with new fluents for encoding the content of the n program lines and the current value of the program counter. In addition, Pn replaces the actions of instances in P with new actions for programming and executing the program instructions on the different program lines. A solution plan to Pn corresponds to a planning program ⇧ that solves every problem in P.

3 Generating High-Level State Features

This section defines high-level state features as conjunctive queries and extends planning programs [Jim´enez and Jonsson, 2015; Segovia-Aguas et al., 2016] such that conditional

Figure 2: Derived predicates in the form of conjunctive queries for finding the minimum number in a list.

goto instructions jump according to the value of a conjunctive query. The section also extends the compilation from generalized planning into classical planning to generate planning programs with conjunctive queries using a classical planner.

3.1 High-Level State Features

The notion of a high-level state feature is very general and has been used in different areas of AI and for different purposes. If we restrict ourselves to planning, a high-level state feature can broadly be viewed as a state abstraction to compactly represent planning problems and/or solutions to planning problems. Diverse formalisms have been used to represent high-level state features in planning ranging from first order clauses [Veloso et al., 1995] to description logic formulae [Mart´ın and Geffner, 2004], LTL formulae [Cresswell and Coddington, 2004], PDDL derived predicates [Hoffmann and Edelkamp, 2005] and, more recently, observation formulae [Bonet et al., 2010].

In our formalism, states are represented in terms of fluents that are instantiated from the set of predicates . We consider high-level state features that are arbitrary formulae over the predicates in . A high-level state feature is also known as a derived predicate if it produces a new predicate whose truth value is determined by the corresponding formula. Derived predicates have proven useful for concisely representing planning problems with complex conditions and effects [Thi´ebaux et al., 2005] and for more efficiently solving optimal planning problems [Ivankovic and Haslum, 2015].

In this paper we restrict ourselves to formulae in the form of conjunctive queries from database theory [Chandra and Merlin, 1977]. Conjunctive queries are a fragment of firstorder logic in which formulae are constructed from atoms using conjunction and existential quantification (disallowing all other logical symbols). A conjunctive query can be written as

where x1↪ ▷ ▷ ▷ ↪ xk are free variables, xk+1↪ ▷ ▷ ▷ ↪ xm are bound variables, and φ1↪ ▷ ▷ ▷ ↪ φq are atoms.

Figure 2 shows two derived predicates, in the form of conjunctive queries, that correspond to features a == b and ⇤a < ⇤b. In both predicates, a and b act as free variables while x1 and x2 are bound variables. The first derived predicate models whether two given iterators point to the same memory address, while the second models whether the value pointed to by an iterator is less than the value pointed to by another iterator. The example assumes that predicate assign models the assignment of a memory address to a pointer variable, points-to models the content of the associated memory location, and lessthan models that a value is less than another.

Given a planning problem P = h ↪⌦↪A↪ I↪Gi, we define a derived predicate on a set of variables X = ¶x1↪ ▷ ▷ ▷ ↪ xm♦, each with domain ⌦. Each atom p(v) in the derived predicate consists of a predicate p 2 and a tuple v 2 Xar(p) that assigns variables in X to arguments of p. In addition, we make the following assumptions regarding predicates and objects:

1. We partition ⌦ into a set of variable objects ⌦v (not to be confused with the variables of a conjunctive query) and a set of remaining objects ⌦o.
2. For each predicate p 2 we designate at most one argument as a variable argument to be filled by a variable object (WLOG the variable argument always goes first). In the example, the first argument of predicates assign and points-to is a variable argument. For predicates without variable arguments, such as lessthan, we simply remove the variable argument and associated variable object.
3. In a conjunctive query, free variables can only be assigned to variable arguments of predicates and have domain ⌦v, while bound variables can only be assigned to non-variable arguments and have domain ⌦o.

Note that we could get rid of variable objects and variable arguments by redefining predicates (e.g. assign could become assign-i, assign-j and assign-n). As a consequence, all variables of a conjunctive query would be bound. However, variable objects offer flexibility, by allowing the variable objects to vary, and by generating derived predicates that are valid for a range of variable objects. For instance, the conditions i == n and ⇤i < ⇤j in the program of Figure 1 are generated by assigning objects to a and b accordingly (this requires i, j and n to be variable objects of the planning problem).

3.2 Planning Programs with Conjunctive Queries

To incorporate conjunctive queries into planning programs we simply replace the fluent f of conditional goto instructions goto(i0 ↪ !f) with a conjunctive query '. The execution of a planning program with conjunctive queries proceeds as explained in Section 2, except when the instruction associated with the current program counter is a conditional goto instruction goto(i0 ↪ !'). In that case, pc is set to i0 if ' does not unify with the current state s, else pc is incremented.

Let ' = (x1↪ ▷ ▷ ▷ ↪ xk)▷9xk+1↪ ▷ ▷ ▷ ↪ xm▷φ1 ^ · · · ^ φq be a conjunctive query, and let u 2 ⌦kv be an assignment of variable objects to the free variables x1↪ ▷ ▷ ▷ ↪ xk. We describe a strategy for unifying ' with the current state s. The idea is to maintain a subset Φ ✓ ⌦m-k o of possible joint assignments of objects to the bound variables xk+1↪ ▷ ▷ ▷ ↪ xm. We then unify the atoms of ' with s one at a time, starting with φ1, and update the set Φ as we go along. After processing all atoms, ' unifies with s if and only if Φ is non-empty, i.e. if there remains at least one possible joint assignment to the bound variables.

To illustrate this idea, consider again the example problem introduced in Section 1 for finding the minimum element in the integer list (2↪ 5↪ 3↪ 1↪ 4). Consider the derived predicate lessthan-pointers(a↪ b) from Figure 2, and let (i↪ j) be the assignment of variable objects to the free variables a↪ b. Assume that in the current state s, iterator i points to the third position of the list while iterator j points to the first position. Unification proceeds one atom at a time, and initially Φ = ⌦2o , i.e. all joint assignments to the bound variables x1↪ x2 are possible.

The first atom points-to(i↪ x1) unifies with x1 = 3, the element in the third position of the list. Consequently, joint assignments in Φ that do not assign the value 3 to x1 are no longer possible and thus removed. Likewise, the second atom points-to(j↪ x2) unifies with x2 = 2, and joint assignments that do not assign the value 2 to x2 are removed from Φ. As a result, Φ contains a single possible joint assignment (3↪ 2) to x1↪ x2. Since 3 is not less than 2, no joint assignment in Φ unifies with the third atom lessthan(x1↪ x2). As a result, Φ becomes empty, and ' is considered non-unifiable with s.

3.3 Computing Planning Programs with Conjunctive Queries

In this section we extend the compilation of Jim´enez and Jonsson (2015) to compute planning programs with conjunctive queries. The extended compilation takes as input a generalized planning problem P = ¶P1↪ ▷ ▷ ▷ ↪ PT ♦ and constants n, q and m (that bound the number of program lines, atoms and bound variables, respectively) and outputs a single planning problem P m n↪q . A solution to P m n↪q corresponds to a planning program ⇧ with conjunctive queries such that ⇧ solves P.

Since programming and executing sequential and termination instructions is identical to the original compilation, we only describe here the part of P m n↪q that corresponds to programming and evaluating conjunctive queries. We define a set of bound variables X = ¶x1↪ ▷ ▷ ▷ ↪ xm♦ and a set of slots ⌃ = ¶σ1↪ ▷ ▷ ▷ ↪ σq♦. Each slot is a placeholder for an atom of a conjunctive query, and we also define a dummy slot σ0. The compilation is extended with the following novel fluents:

• ÷ For each pair of program lines i↪ i0 such that i0 6= i + 1, a fluent insi↪goto(i0 ) indicating that the instruction on line i is a goto instruction goto(i0 ↪ !').
• ÷ For each slot σk 2 ⌃ [ ¶σ0♦, a fluent slotk indicating that σk is the current slot.
• ÷ For each line i and slot σk 2 ⌃, a fluent eslotki indicating that slot σk on line i is empty.
• ÷ For each line i, slot σk 2 ⌃, predicate p 2 , variable object v 2 ⌦v and variable tuple (y2↪ ▷ ▷ ▷ ↪ yar(p)) 2 Xar(p)-1 , a fluent atom-pki (v↪ y2↪ ▷ ▷ ▷ ↪ yar(p)) indicating that p(v↪ y2↪ ▷ ▷ ▷ ↪ yar(p)) is the atom in slot σk of line i.
• ÷ For each slot σk 2 ⌃ and object tuple (o1↪ ▷ ▷ ▷ ↪ om) 2 ⌦mo , a fluent possk (o1↪ ▷ ▷ ▷ ↪ om) indicating that at σk, (o1↪ ▷ ▷ ▷ ↪ om) is a possible joint assignment of objects to the bound variables x1↪ ▷ ▷ ▷ ↪ xm.
• ÷ A fluent eval indicating that we are done evaluating a conjunctive query and a fluent acc representing the outcome of the evaluation (true or false).

In the initial state, all fluents above appear as false except slot0 , indicating that we are ready to program and unify the atoms of any conjunctive query. The initial state on other fluents is identical to the original compilation, as is the goal condition. We next describe the set of actions that have to be added to the original compilation to implement the mechanism for programming and evaluating conjunctive queries.

A conjunctive query ' is activated by programming a goto instruction goto(i0 ↪ !') on a given line i. As a result of programming the goto instruction, all slots on line i are marked as empty. For each pair of program lines i↪ i0 , the action pgotoi↪i0 for programming goto(i0 ↪ !') on line i is defined as

The precondition contains two fluents from the original compilation: pci, modeling that the program counter equals i, and insi↪nil, modeling that the instruction on line i is empty.

Once activated, we have to program the individual atoms in the slots of the conjunctive query '. After programming an atom, the slot is no longer empty. For each line i, slot σk 2 ⌃, predicate p 2 , variable object v 2 ⌦v and tuple of bound variables (y2↪ ▷ ▷ ▷ ↪ yar(p)) 2 Xar(p)-1 , the action patom-pki (v↪ y2↪ ▷ ▷ ▷ ↪ yar(p)) is defined as

Note that the action patom-pki (v↪ y2↪ ▷ ▷ ▷ ↪ yar(p)) assigns a concrete variable object v to its only free variable, i.e. the conjunctive queries that we generate already assign variable objects to free variables.

The key ingredient of the compilation are step actions that iterate over the atoms in each slot while propagating the remaining possible values of the bound variables. For each line i, slot σk 2 ⌃, predicate p 2 , variable object v 2 ⌦v and tuple of bound variables (y2↪ ▷ ▷ ▷ ↪ yar(p)) 2 Xar(p)-1 , step action step-pki (v↪ y2↪ ▷ ▷ ▷ ↪ yar(p)) is defined as

To apply a step action, an atom has to be programmed first. The unconditional effect is moving from slot σk-1 to slot σk. In addition, the step action updates the possible assignments to the bound variables x1↪ ▷ ▷ ▷ ↪ xm.

For an assignment (o1↪ ▷ ▷ ▷ ↪ om) to be possible at slot σk , it has to be possible at σk-1 , and the atom p(v↪ y2↪ ▷ ▷ ▷ ↪ yar(p)) programmed at slot k has to induce a fluent that is currently true. Let o(y) denote the object among o1↪ ▷ ▷ ▷ ↪ om that is associated with the bound variable y. For example, if y = x2, then o(y) = o(x2) = o2. Then the induced fluent is given by p(v↪ o(y2)↪ ▷ ▷ ▷ ↪ o(yar(p))). Note that there is one conditional effect for each possible assignment (o1↪ ▷ ▷ ▷ ↪ om). If k = 1, the condition possk-1 (o1↪ ▷ ▷ ▷ ↪ om) is removed since all assignments are possible prior to evaluating the first atom.

Once we have iterated over all atoms, we have to check whether there remains at least one possible assignment, thereby evaluating the entire conjunctive query. For each line i, let evali be an action defined as

pre(evali) = ¶pci↪ slotq ♦↪ cond(evali) = ¶; B ¶eval♦♦ [ ¶¶possq (o1↪ ▷ ▷ ▷ ↪ om)♦ B ¶acc♦ : (o1↪ ▷ ▷ ▷ ↪ om) 2 ⌦mo ♦▷

Action evali is only applicable once we are at the last slot σq. The conditional effects add the fluent acc if and only if there remains a possible assignment to x1↪ ▷ ▷ ▷ ↪ xm at σq.

Finally, we can now use the result of the evaluation to determine the program line that we jump to. For each pair of lines i↪ i0 , let jmpi↪i0 be an action defined as

The effect is to jump to line i0 if acc is false, else continue execution on line i + 1. We also delete fluents eval and acc, as well as all instances of possk (o1↪ ▷ ▷ ▷ ↪ om) in order to reset the evaluation mechanism prior to the next evaluation of a conjunctive feature. The current slot is also reset to σ0.

4 Classification with Planning Programs

Our extension of planning programs with conjunctive queries allows us to model supervised classification tasks as if they were generalized planning problems. Formally, the learning of a noise-free classifier from a set of labeled examples ¶e1↪ ▷ ▷ ▷ ↪ eT ♦, where each example et, 1  t  T , is labeled with a class in ¶c1↪ ▷ ▷ ▷ ↪ cZ♦, can be viewed as a generalized planning problem P = ¶P1↪ ▷ ▷ ▷ ↪ PT ♦ such that each individual planning problem Pt = h ↪⌦↪A↪ Ii↪Gii, 1  t  T, models the classification of the tth example:

• ÷ ↪⌦ induces the set of fluents F representing the learning examples and their labels.
• ÷ A contains the actions necessary to associate a given example with a class. For instance, in a binary classification task, A = ¶setPositive↪ setNegative♦.
• ÷ It contains the fluents that describe the tth example and Gt the fluent that describes the label of the tth example.

The solution ⇧ to a generalized planning problem P that models a classification task is a noise-free classifier that covers all learning examples.

This model is particularly natural for classification tasks in which both the examples and the classifier are described using logic. Michalski's train [Michalski et al., 2013] is a good example of such tasks. It defines 10 different trains (5 traveling east and 5 traveling west) and the classification target is finding rules that cause a train to travel east or west. Trains are defined using the following relations: which wagon is in a given train, which wagon is in front, the wagon's shape, its number of wheels, whether it has a roof or not (closed or open), whether it is long or short, the shape of the objects the wagon is loaded with and the class of the train.

In more detail, the generalized planning problem encoding the Michalski's train task would be:

• ÷ Fluents F induced from = ¶(wagons ?Number), (hasCar ?Car), (infront ?Car ?Car), (shape ?Car ?Shape), (wheels ?Car ?Number), (closed ?Car), (open ?Car), (long ?Car), (short ?Car), (double ?Car), (jagged ?Car), (load ?Car ?Shape ?Number), (eastbound), (westbound)♦.
• ÷ Actions A = ¶setWest♦. We assume that any example has initial class eastbound, causing the resulting planning programs to be more compact.

• ÷ Each initial state It defines the tth train and Gt defines its associated class (east or west).

Figure 3 shows a planning program encoding a noisefree classifier for the Michalski's train problem. As explained, the program assumes that examples initially have class eastbound. Line 1 of the program is an unconditional jump to line 3.

5 Evaluation

In all experiments, we run the classical planner Fast Downward [Helmert, 2006] with the LAMA-2011 setting [Richter and Westphal, 2010] on a Intel Core i5 3.10GHz x 4 with a 4GB memory bound and time limit of 3600s.

We evaluate our method in two kinds of benchmarks. We first consider benchmarks from generalized planning where the target is generating a plan that generalizes without providing any prior high-level representation of the states. This set of benchmarks include iterating over a list and computing the nth term of the summatory series. On the other hand, we consider binary classification tasks which include Michalski's train (cf. Section 4) as well as generating the classifiers corresponding to the logic functions and(X1↪X2), or(X1↪X2) and xor(X1↪X2). Table 1 summarizes the obtained results. We report the number of program lines used to solve the generalized planning problem, the number of slots and bound variables required to learn the features (a list means that more than one feature was learned), the time taken to generate the program, and the plan length.

We briefly describe the features and the programs learned for the different domains. In the list domain we learn the feature i == n for the program (0. visit, 1. inc(i), 2. goto(0↪ i!=n)). In the summatory domain we learn the feature b = 0 for the program (0. sum(a↪ b), 1. dec(b), 2. goto(0↪ b!=0)). For Michalski's train we learn the program and features shown in Figure 3. The programs for and(X1↪X2), or(X1↪X2) and xor(X1↪X2) have the same structure: they learn a first feature that captures if a variable is false (true for the or function, and one true and one false for xor) and a second feature to capture that the class of the example was set to negative. This is the 4-line program for the and(X1↪X2) function: (0. goto(3↪ !X = False), 1. setFalse, 2. goto(4↪ class = False), 3. setTrue, 4. end).

6 RelatedWork

Our approach for learning high-level state features (and classifiers) is inspired by version space learning [Mitchell, 1982]. The hypothesis to learn consists of logic clauses and examples are logic facts that restrict the hypothesis forcing it to be consistent with the examples. Inductive Logic Programming (ILP) [Muggleton, 1999] also intersects Machine Learning (ML) and Logic Programming to generate hypotheses from examples. ILP has traditionally been considered a binary classification task but, in recent years, it covers the whole spectrum of ML such as regression, clustering and association analysis. The main contribution of our approach with respect to version space learning and ILP is the use of a classical planner to build and validate the learned hypotheses.

Previous work on computing generalized plans in the form of generalized policies already attempted to automatically generate higher-level state representations [Khardon, 1999]. Two examples are learning generalized policies from solved instances using description logic [Mart´ın and Geffner, 2004] and taxonomic syntax [Yoon et al., 2008] to represent and reason about classes of objects. In these works, planning and learning were clearly separate phases producing noisy learning examples in many cases. In contrast, our approach tightly integrates planning and learning.

Generating high-level state features for generalized planning is also related to previous work on First Order MDPs [Boutilier et al., 2001; Gretton and Thi´ebaux, 2004]. These works adapt traditional dynamic programming algorithms to the symbolic setting and automatically generate first-order representations of the value function with firstorder regression. The main contribution of our approach with respect to this research line is that we follow a compilation approach to generate useful state abstractions with off-theshelf planners.

7 Conclusion

In generalized planning problems, high-level state features are traditionally hand-coded which requires significant human expertise. We have proposed a novel approach to automatically generating these features by tightly integrating the computation of planning programs with the computation of the features. This integration is achieved incorporating conjunctive queries into planning programs and extending an existing compilation from generalized planning to classical planning [Jim´enez and Jonsson, 2015; Segovia-Aguas et al., 2016] such that it can be exploited by an off-the-shelf planner.

Currently we are only able to generate high-level state features in the form of conjunctive queries, and hence we cannot model features with unbounded transitive or recursive closures. This kind of features are known to be useful for some planning domains, e.g. the above feature, the transitive closure of on, for the Blocksworld domain. In the near future we would like to extend our approach to generating more expressive features.

In addition, our approach naturally models classification tasks in which both examples and classifiers are represented using logic. The aim of this research direction is not competing with existing ML algorithms; indeed, we cannot deal with noisy examples. Instead, our aim is to provide a new formalism capable of representing tasks that integrate classification and planning. Moreover, we bring a new landscape of challenging benchmarks to classical planning.

Acknowledgment

This work is partially supported by grant TIN2015-67959 and the Maria de Maeztu Units of Excellence Programme MDM2015-0502, MEC, Spain. Sergio Jim´enez is partially supported by the Juan de la Cierva program funded by the Spanish government.