Hierarchical Finite State Controllers for Generalized Planning

1 Introduction

Finite state controllers (FSCs) are a compact and effective representation commonly used in AI; prominent examples include robotics [Brooks, 1989] and video-games [Buckland, 2004]. In planning, FSCs offer two main benefits: 1) solution compactness [B¨ackstr¨om et al., 2014]; and 2) the ability to represent generalized plans that solve a range of similar planning problems. This generalization capacity allows FSCs to represent solutions to arbitrarily large problems, as well as 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].

Even FSCs have limitations, however. Consider the problem of traversing all nodes of a binary tree as in Figure 1. A classical plan for this task consists of an action sequence whose length is linear in the number of nodes, and hence exponential in the depth of the tree. In contrast, the recursive definition of Depth-First Search (DFS) only requires a few lines of code. However, a standard FSC cannot implement recursion, and the iterative definition of DFS is considerably more complicated, involving an external data structure.

In this paper we introduce a novel formalism for representing and computing compact and generalized planning solutions that we call hierarchical FSCs. Our formalism extends standard FSCs for planning in three ways. First, a hierarchical FSC can involve multiple individual FSCs. Second, each FSC can call other FSCs. Third, each FSC has a parameter list, and when an FSC is called, it is necessary to specify the arguments assigned to the parameters. As a special case, our formalism makes it possible to implement recursion by allowing an FSC to call itself with different arguments.

To illustrate this idea, Figure 2 shows an example hierarchical FSC C[n] that implements DFS traversal of binary trees using recursion. Here, n is the lone parameter of the controller and represents the current node of the binary tree. Condition leaf(n) tests whether n is a leaf node, while a hyphen '-' indicates that the transition fires no matter what. Action visit(n) visits node n, while copyL(n↪m) and copyR(n↪ m) assign the left and right child of node n to m, respectively. Action call(m) is a recursive call to the FSC itself, assigning argument m to the only parameter of the controller and restarting execution from its initial node Q0.

Intuitively, by repeatedly assigning the right child of n to n itself (using the action copyR(n↪ n)) and following the cycle of controller states Q0↪ Q1↪ Q2↪ Q3↪ Q0↪ ▷ ▷ ▷, the FSC C[n] has the effect of visiting all nodes on the rightmost branch of the tree until a leaf node is reached. Moreover, by assigning the left child of n to child (using the action copyL(n↪ child)) and making the recursive call call(child), the FSC C[n] is recursively executed on all left sub-trees. The controller state Q4 is a terminal state, and the action visit(child) on the transition to Q4 is in fact not needed and could be removed. However, the FSC is automatically generated by our approach, so we present conditions and actions exactly as they appear.

Compared to previous work on the automatic generation of FSCs for planning the contributions of this paper are:

1. A reformulation of the transition function of FSCs that allows binary branching only in order to reduce the space of possible controllers.
2. A formal definition of hierarchical FSCs for planning that allows controllers to call other controllers and that includes recursion as a special case.
3. A novel compilation that enables the automatic generation of hierarchical FSCs for challenging generalized planning tasks. The compilation takes as input a set of planning problems from a given domain and outputs a single classical planning problem whose solution corresponds to a hierarchical FSC. This output is expressed in PDDL, thus an off-the-shelf classical planner can be used to generate hierarchical FSCs. The compilation also makes it possible to incorporate prior knowledge in the form of existing FSCs to automatically complete the definition of the remaining FSCs.

2 Background

This section defines our model for classical planning and presents the formalism we use to define FSCs for planning.

2.1 Classical Planning with Conditional Effects

We describe states and actions in terms of literals. Formally, given a set of fluents F, a literal l is a valuation of a fluent in F, i.e. l = f or l = ≻f for some f 2 F. A set of literals L thus 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 is a tuple P = hF↪ A↪ I↪ Gi, where F is a set of fluents, 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). We often describe the initial state I ✓ F compactly as the subset of fluents that are true.

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 Finite State Controllers

Given a planning problem P = hF↪A↪ I↪Gi, an FSC is defined as a tuple C = hQ↪ T↪ q0↪ q?i, where Q is a set of controller states, T : Q ⇥ 2F ! Q ⇥ A is a (partial) transition function that assumes full observability, and q0 2 Q and q? 2 Q are the initial and terminal controller states, respectively. This definition relates to previous work on FSCs for generalized planning [Bonet et al., 2010; Hu and De Giacomo, 2013] as follows:

• ÷ Just like in previous approaches (and unlike Mealy machines), transitions do not depend on explicit input sequences but on the current planning state.
• ÷ Previous approaches assume partial observability of the current planning state, defining the transition function T on Q⇥O, where O is the observation set. We instead define T on Q⇥ 2F , i.e. on the full set of fluents.
• ÷ We define an explicit terminal state q?, while previous approaches terminate upon reaching the goal condition G. The reason is that we will later extend our definition to hierarchies of FSCs where goals G are not necessarily satisfied when the execution of an FSC terminates.

We briefly describe the execution semantics of an FSC C on planning problem P. The current world state is a pair (q↪ s) 2 Q ⇥ 2F of a controller state and a planning state. From a pair (q↪ s), the system transitions to (q0 ↪ s0 ), where (q0 ↪ a) = T(q↪ s) is the result of applying the transition function in (q↪ s) and s0 = ✓(s↪ a) is the result of applying action a in s. Execution starts at (q0↪ I) and repeatedly transitions until reaching a pair (q?↪ s?) that contains the terminal controller state q?. An FSC C solves P iff G ✓ s? upon termination, i.e. if the goal condition holds in s?. The execution of C fails if it reaches a pair (q↪ s) that was already visited.

A generalized planning problem P = ¶P1↪ ▷ ▷ ▷ ↪ PT♦ is a set of multiple individual planning problems that share fluents and actions. Each individual planning problem Pt 2 P is thus defined as Pt = hF↪ A↪ It↪ Gti, where only the initial state It and goal condition Gt differ from other planning problems in P. An FSC C solves a generalized planning problem P if and only if it solves every problem Pt 2 P.

3 Generating Finite State Controllers

This section presents a compilation that takes as input a classical planning problem P = hF↪A↪ I↪Gi and a bound n on the maximum number of controller states, and produces as output a classical planning problem Pn. Actions in Pn are defined such that any plan that solves Pn has to both generate an FSC C and simulate the execution of C on P, thus verifying that C solves P. We later extend this compilation to generalized planning problems and hierarchies of FSCs.

To generate an FSC C = hQ↪ T↪ q0↪ q?i using this compilation we first define Q = ¶q0↪ ▷ ▷ ▷ ↪ qn♦ and set q? ⌘ qn. The only thing that remains is to construct the transition function T . Our approach is to reduce the space of possible controllers by compactly representing T : Q⇥ 2F ! Q⇥A using the following three functions Γ, ⇤ and Φ:

• ÷ Γ : Q ! F associates a fluent f = Γ(q) to each q 2 Q.
• ÷ Φ : Q ⇥ ¶0↪ 1♦ ! A returns an action in A.
• ÷ ⇤ : Q ⇥ ¶0↪ 1♦ ! Q returns a successor state in Q.

The transition from a world state (q↪ s) depends on the truth value of Γ(q) in s, hence allowing binary branching only. Let Γ(q) 2 s be a test whose outcome is interpreted as a Boolean value in ¶0↪ 1♦. The transition function is then defined as T (q↪ s) = (⇤(q↪ Γ(q) 2 s)↪ Φ(q↪ Γ(q) 2 s)).

We proceed to define Pn = ¶Fn↪An↪ In↪Gn♦. The idea behind the compilation is to define two types of actions: program actions that program the three functions Γ, ⇤ and Φ for each controller state of C, and execute actions that simulate the execution of C on P by evaluating the functions in the current planning state.

The set of fluents is Fn = F [ FT [ Faux, where FT contains the fluents needed to encode the transition function:

• ÷ For each q 2 Q and f 2 F, a fluent condfq that holds iff f is the condition of q, i.e. if Γ(q) = f.
• ÷ For each q↪ q0 2 Q and b 2 ¶0↪ 1♦, a fluent succbq↪q0 that holds iff ⇤(q↪ b) = q0 .
• ÷ For each q 2 Q, b 2 ¶0↪ 1♦ and a 2 A, a fluent actbq↪a that holds iff Φ(q↪ b) = a.
• ÷ For each q 2 Q and b 2 ¶0↪ 1♦, fluents nocondq, nosuccbq and noactbq that hold iff we have yet to program the functions Γ, ⇤ and Φ, respectively.

Moreover, Faux contains the following fluents:

• ÷ For each q 2 Q, a fluent csq that holds iff q is the current controller state.
• ÷ Fluents evl and app that hold iff we are done evaluating the condition or applying the action corresponding to the current controller state, and fluents o0 and o1 representing the outcome of the evaluation.

The initial state and goal condition are defined as In = I [ ¶csq0 ♦ [ ¶nocondq↪ noactbq ↪ nosuccbq : q 2 Q↪ b 2 ¶0↪ 1♦♦ and Gn = G[¶csqn ♦. Finally, the set of actions An replaces the actions in A with the following actions:

• ÷ For each q 2 Q and f 2 F, an action pcondfq for programming Γ(q) = f :

• ÷ For each q 2 Q and f 2 F, an action econdfq that evaluates the condition of the current controller state:

• ÷ For each q 2 Q, b 2 ¶0↪ 1♦ and a 2 A, an action pactbq↪a for programming Φ(q↪ b) = a:

• ÷ For each q 2 Q, b 2 ¶0↪ 1♦ and a 2 A, an action eactbq↪a that applies the action of the current controller state:

• ÷ For each q↪ q0 2 Q and b 2 ¶0↪ 1♦, an action psuccbq↪q0 for programming ⇤(q↪ b) = q0 :

• ÷ For each q↪ q0 2 Q and b 2 ¶0↪ 1♦, an action esuccbq↪q0 that transitions to the next controller state:

Actions pcondfq , pactbq↪a and psuccbq↪q0 program the three functions Γ, Φ and ⇤, respectively, while econdfq , eactbq↪a and esuccbq↪q0 execute the corresponding function. Fluents evl and app control the order of the execution such that Γ is always executed first, then Φ, and finally ⇤.

Theorem 1. Any plan ⇡ that solves Pn induces an FSC C that solves P.

Proof sketch. The only way to change the current controller state is to apply an action of type esuccbq↪q0 , which first requires programming and executing the functions Γ, Φ and ⇤ in that order. Once programmed, the plan ⇡ can no longer change these functions since there are no actions that add fluents among nocondq, noactbq and nosuccbq . Once programmed for all states and Boolean values b 2 ¶0↪ 1♦, the three functions Γ, Φ and ⇤ together define an FSC C.

We show that ⇡ simulates an execution of C on P . The initial state I [ ¶csqo ♦ corresponds to the world state (q0↪ I). In any world state (q↪ s), the plan has to apply the partial action sequence hecondfq ↪ eactbq↪a ↪ esuccbq↪q0 i. Action econdfq adds ob where b 2 ¶0↪ 1♦ is the truth value of f in s. Action eactbq↪a applies the action a in s to obtain a new state s0 = ✓(s↪ a). Finally, action esuccbq↪q0 transitions to controller state q0 . This deterministic execution continues until we reach a terminal state (qn↪ sn) or revisit a world state. If ⇡ solves Pn, execution finishes in (qn↪ sn) and the goal condition G holds in sn, which is the definition of C solving P .

We extend the compilation to address generalized planning problems P = ¶P1↪ ▷ ▷ ▷ ↪ PT♦. In this case a solution to Pn builds an FSC C and simulates the execution of C on all the individual planning problems Pt 2 P. The extension introduces actions endt, 1  t < T, with precondition Gt [ ¶csqn ♦ and conditional effects that reset the world state to (q0↪ It+1) after solving Pt. In addition, the initial state and goal condition are redefined as In = I1 [ ¶csq0 ♦ [ ¶nocondq↪ noactbq ↪ nosuccbq : q 2 Q↪ b 2 ¶0↪ 1♦♦ and Gn = GT [ ¶csqn ♦.

4 Hierarchical Finite State Controllers

This section extends our formalism for FSCs to hierarchical FSCs. We do so by allowing FSCs to call other FSCs. An FSC C can now have parameters, and calls to C specify the arguments passed to the parameters of C. Again, we first describe hierarchical FSCs for solving a single planning problem P = hF↪ A↪ I↪ Gi, and then extend the idea to generalized planning.

As in PDDL, we assume that fluents in F are instantiated from predicates. Moreover, we assume that there exist a set of variable objects ⌦v and a set of value objects ⌦x, and that for each v 2 ⌦v and x 2 ⌦x, F contains a fluent assignv↪x that models an assignment of type v = x. Let Fa ✓ F be the set of such assignment fluents and let Fr = F ∩ Fa be the remaining fluents.

Given a planning problem P with fluents Fa ✓ F induced from sets ⌦v and ⌦x, a hierarchical FSC is a tuple H = hC↪ C1i, where C = ¶C1↪ ▷ ▷ ▷ ↪ Cm♦ is the set of FSCs in the hierarchy and C1 2 C is the root FSC. We assume that all FSCs in C share the same set of controller states Q and that each Ci 2 C has an associated parameter list Li 2 ⌦ki v consisting of ki variable objects in ⌦v. The set of possible FSC calls is then given by Z = ¶Ci[p] : Ci 2 C↪ p 2 ⌦ki v ♦, i.e. all ways to select an FSC Ci from C and assign arguments to its parameters. The transition function Ti of each FSC Ci is redefined as Ti : Q⇥ 2F ! Q⇥ (A[Z) to include possible calls to the FSCs in C. As before, we represent Ti compactly using functions Γi, ⇤i and Φi.

To define the execution semantics of a hierarchical FSC H we introduce a call stack. Execution starts in the root FSC, at state (q0↪ I) and on level 0 of the stack. In general, for an FSC Ci and a world state (q↪ s) and given that Ti(q↪ s) = (q0 ↪ a) returns an action a 2 A, the execution semantics is as explained in Section 2 for single FSCs. However, when Ti(q↪ s) = (q0 ↪Cj[p]) returns a call to controller Cj[p] 2 Z, we set the state on the next level of the stack to (q0↪ s[p]), where s[p] is obtained from s by copying the value of each variable object in p to the corresponding parameter of Cj . Execution then proceeds on the next level of the stack following transition function Tj, which can include other FSC calls that invoke higher stack levels. If Tj reaches a terminal state (q?↪ s?), control is returned to the parent controller Ci. Specifically, the state of Ci becomes (q0 ↪ s0 ), where s0 is obtained from s? by substituting the original assignments of values to variables on the previous stack level. The execution of a hierarchical FSC H terminates when it reaches a terminal state (q?↪ s?) on stack level 0, and H solves P iff G ✓ s?.

4.1 An Extended Compilation for Hierarchical Finite State Controllers

We now describe a compilation from P to a classical planning problem P `n↪m = hF `n↪m↪A`n↪m↪ I `n↪m↪G`n↪mi, such that solving P `n↪m amounts to programming a hierarchical FSC

H = hC↪ C1i and simulating its execution on P . As before, n bounds the number of controller states, while m is the maximum number of FSCs in C and ` bounds the size of the call stack. The set of fluents is F `n↪m = Fr [F ` a [F m T [F ` aux [FH where

• ÷ F ` a = ¶f l : f 2 Fa↪ 0  l  `♦, i.e. each fluent of type assignv↪x has a copy for each stack level l.
• ÷ F m T = ¶f i : f 2 FT ↪ 1  i m♦, i.e. each fluent in FT has a copy for each FSC Ci 2 C defining its corresponding transition function Ti.
• ÷ F ` aux = ¶f l : f 2 Faux↪ 0  l  `♦, i.e. each fluent in Faux has a copy for each stack level l.

Moreover, FH contains the following additional fluents:

• ÷ For each l, 0  l  `, a fluent lvll that holds iff l is the current stack level.
• ÷ For each Ci 2 C and l, 0  l  `, a fluent fsci↪l that holds iff Ci is the FSC being executed on stack level l.
• ÷ For each q 2 Q, b 2 ¶0↪ 1♦, Ci↪ Cj 2 C and p 2 ⌦kj v , a fluent callb↪i q↪j (p) that holds iff Φi(q↪ b) = Cj[p].

The initial state and goal condition are now defined as I `n↪m = (I \ Fr) [ ¶f 0 : f 2 I \ Fa♦ [ ¶cs0q0 ↪ lvl0 ↪ fsc1↪0 ♦ [ ¶nocondiq ↪ noactb↪i q ↪ nosuccb↪i q : q 2 Q↪ b 2 ¶0↪ 1♦↪Ci 2 C♦ and G`n↪m = G [ ¶cs0qn ♦. In other words, fluents of type assignv↪x 2 Fa are initially marked with stack level 0, the controller state on level 0 is q0, the current stack level is 0, the FSC on level 0 is C1, and functions Γi, ⇤i and Φi are yet to be programmed for any FSC Ci 2 C. To satisfy the goal we have to reach the terminal state qn on level 0 of the stack.

To establish the actions in the set A`n↪m, we first adapt all actions in An by parameterizing on the FSC Ci 2 C and stack level l, 0  l  `, adding preconditions lvll and fsci↪l , and modifying the remaining preconditions and effects accordingly. As an illustration we provide the definition of the resulting action pcondf↪i↪l q :

Compared to the old version of pcondfq , the current controller state cslq 2 F ` aux refers to the stack level l, and fluents nocondiq and condf↪i q in F m T refer to the FSCCi. The precondition models the fact that we can only program the function Γi of Ci in controller state q on stack level l when l is the current stack level, Ci is being executed on level l, the current controller state on level l is q, and Γi has not been previously programmed in q.

In addition to the actions adapted from An, the set A`n↪m also contains the following new actions:

• ÷ For each q 2 Q, b 2 ¶0↪ 1♦, Ci↪ Cj 2 C, p 2 ⌦kj v and l, 0  l < `, an action pcallb↪i↪l q↪j (p) to program a call from the current FSC, Ci, to FSC Cj:

• ÷ For each q 2 Q, b 2 ¶0↪ 1♦, Ci↪ Cj 2 C, p 2 ⌦kj v and l, 0  l < `, an action ecallb↪i↪l q↪j (p) that executes a call:

As an alternative to pactb↪i↪l q↪a , the action pcallb↪i↪l q↪j (p) programs an FSC call Cj[p], i.e. defines the function as Φi(q↪ b) = Cj[p]. Action ecallb↪i↪l q↪j (p) executes this FSC call by incrementing the current stack level to l + 1 and setting the controller state on level l + 1 to q0. The conditional effect

¶assignlpk ↪x ♦ B ¶assignl+1 Lkj ↪x ♦ effectively copies the value of the argument pk on level l to the corresponding parameter Lkj of Cj on level l +1. When in the terminal state qn, the termination action termi↪l decrements the stack level to l - 1 and

deletes all temporary information about stack level l.

Theorem 2. Any plan ⇡ that solves P `n↪m induces a hierarchical FSC H that solves P .

Proof sketch. Similar to the argument in the proof of Theorem 1, the plan ⇡ has to program the functions Γi, ⇤i and Φi of each FSC Ci 2 C. Because of the new actions pcallb↪i↪l q↪j (p), this includes the possibility of making FSC calls. Hence ⇡ implicitly defines a hierarchical FSC H.

Moreover, ⇡ simulates an execution of H on P starting from (q0↪ I) on stack level 0. In any world state (q↪ s) on stack level l while executing the FSC Ci, whenever the plan contains a partial action sequence hecondf↪i↪l q ↪ ecallb↪i↪l q↪j (p)↪ esuccb↪i↪l q↪q0 i that involves an FSC call, the effect of ecallb↪i↪l q↪j (p) is to increment the stack level, causing execution to proceed on stack level l + 1 for the FSC Cj . The only action that decrements the stack level is termj↪l+1 , which is only applicable once we reach the terminal state qn on stack level l +1. Once termj↪l+1 has been applied, we can now apply action esuccb↪i↪l q↪q0 to transition to the new controller state q0 .

If ⇡ solves P `n↪m, execution terminates in a state (qn↪ sn) on level 0 and the goal condition holds in sn, satisfying the condition that H solves P .

We remark that the action pcallb↪i↪l q↪j (p) can be used to implement recursion by setting i ⌘ j, making the FSC Ci call itself. We can also partially specify the functions Γi, ⇤i and Φi of an FSC Ci by adding fluents of type condf↪i q , actb↪i q↪a , succb↪i q↪q0 and callb↪i q↪j (p) to the initial state I `n↪m. This way we can incorporate prior knowledge regarding the configuration of some previously existing FSCs in C.

The compilation can be extended to a generalized planning problem P = ¶P1↪ ▷ ▷ ▷ ↪ PT ♦ in a way analogous to Pn. Specifically, each action endt, 1  t < T, should have precondition Gt [ ¶cs0qn ♦ and reset the state to It+1 [ ¶cs0q0 ♦, i.e. the system should reach the terminal state qn on stack level 0 and satisfy the goal condition Gt of Pt before execution proceeds on the next problem Pt+1 2 P. To solve P `n↪m, a plan hence has to simulate the execution of H on all planning problems in P.

5 Evaluation

We evaluate our approach in a set of generalized planning benchmarks and programming tasks taken from Bonet et al. [2010] and Segovia-Aguas et al. [2016]. In all experiments, we run the classical planner Fast Downward [Helmert, 2006] with the LAMA-2011 setting [Richter and Westphal, 2010] on a processor Intel Core i5 3.10GHz x 4 with a 4GB memory bound and time limit of 3600s.

We briefly describe each domain used in experiments. In Blocks, the goal is to unstack blocks from a single tower until a green block is found. In Gripper, the goal is to transport a set of balls from one room to another. In List, the goal is to visit all the nodes of a linked list. In Reverse, the goal is to reverse the elements of a list. In Summatory, the goal is to compute the sum Pni i for a given input n. In Tree/DFS, the goal is to visit all nodes of a binary tree. Finally, in Visitall, the goal is to visit all the cells of a square grid.

Table 1 summarizes the obtained experimental results. In all but two domains our compilation makes it possible to find a single FSC (OC=One Controller) that solves all planning instances in the input. Moreover, we manually verified that the resulting FSC solves all other instances from the same domain. These results reflect those of earlier approaches, but in the domains from Segovia-Aguas et al. [2016], the FSC is able to store generalized plans more compactly, and generation of the FSC is faster.

In Tree/DFS, as mentioned in the introduction, generating a single FSC that solves the problem iteratively without recursive calls is difficult. In contrast, since our compilation simulates a call stack, we are able to automatically generate the FSC in Figure 2. There are some discrepancies with respect to the compilation that we address below:

• ÷ As described, a solution to the compiled planning problem P `n↪m has to program a condition for each controller state, while the FSC in Figure 2 includes deterministic transitions. However, since all fluents in f are potential conditions, programming a condition on a fluent that is static is effectively equivalent to programming a deterministic transition, since the outcome of the evaluation will always be the same for this fluent.
• ÷ In the solution generated by the planner, the condition leaf(n) is actually emulated by a condition equals(n↪ n), where equals is a derived predicate that tests whether two variables have the same value. The reason this works is that when applied to a leaf node n, the action copyR(n↪ n) deletes the current value of n without

adding another value, since n does not have a right child. Hence evaluating equals(n↪ n) returns false, since there is no current value of n to unify over.

• ÷ As previously mentioned, the transition to the terminal state Q4 includes an action visit(child) which is not needed; the reason this action is generated by the planner is that there is no option for leaving the action "blank". Effectively, when executing the FSC the action in question has no effect.

Finally, in Visitall, attempting to generate a single controller for solving all input instances fails. Moreover, even if we set m > 1 and attempt to generate a hierarchical controller from scratch, the planner does not find a solution within the given time bound. Instead, our approach is to generate a hierarchical FSC incrementally. We first generate two single FSCs, where the first solves the subproblem of iterating over a single row, visiting all cells along the way, and the second solves the subproblem of returning to the first column. We then use the compilation to generate a planning problem P `n↪m in which two of the FSCs are already programmed, so the classical plan only has to automatically generate the root controller.

6 RelatedWork

The main difference with previous work on the automatic generation of FSCs [Bonet et al., 2010; Hu and De Giacomo, 2013] is that they generate single FSCs relying on a partially observable planning model. In contrast, our compilation generate hierarchical FSCs that can branch on any fluent since we consider all fluents as observable. Our approach also makes it possible to generate recursive slutions and to incorporate prior knowledge as existing FSCs, and automatically complete the definition of the remaining hierarchical FSC.

Hierarchical FSCs are similar to planning programs [Jim´enez and Jonsson, 2015; Segovia-Aguas et al., 2016]. Programs are a special case of FSCs, and in general, FSCs can represent a plan more compactly. Another related formalism is automaton plans [B¨ackstr¨om et al., 2014], which also store sequential plans compactly using hierarchies of finite state automata. However, automaton plans are Mealy machines whose transitions depend on the symbols of an explicit input string. Hence automaton plans cannot store generalized plans, and their focus is instead on the compression of sequential plans.

FSCs can also represent other objects in planning. Hickmott et al. [2007] and LaValle [2006] used FSCs to represent the entire planning instance. In contrast, Toropila and Bart´ak [2010] used FSCs to represent the domains of individual variables of the instance. Baier and McIlraith [2006] showed how to convert an LTL representation of temporally extended goals, i.e. conditions that must hold over the intermediate states of a plan, into a non-deterministic FSC.

7 Conclusion

In this paper we have presented a novel formalism for hierarchical FSCs in planning in which controllers can recursively call themselves or other controllers to represent generalized plans more compactly. We have also introduced a compilation into classical planning which makes it possible to use an off-the-shelf planner to generate hierarchical FSCs. Finally we have showed that hierarchical FSCs can be generated in an incremental fashion to address more challenging generalized planning problems.

Just as in previous work on the automatic generation of FSCs, our compilation takes as input a bound on the number of controller states. Furthermore, for hierarchical FSCs we specify bounds on the number of FSCs and stack levels. An iterative deepening approach could be implemented to automatically derive these bounds. Another issue is the specification of representative subproblems to generate hierarchical FSCs in an incremental fashion. Inspired by "Test Driven Development" [Beck et al., 2001], we believe that defining subproblems is a step towards automation.

Last but not least, we follow an inductive approach to generalization, and hence we can only guarantee that the solution generalizes over the instances of the generalized planning problem, much as in previous work on computing FSCs. With this said, all the controllers we report in the paper generalize. In machine learning, the validation of a generalized solution is traditionally done by means of statistics and validation sets. In planning this is an open issue, as well as the generation of relevant examples that lead to solutions that generalize.

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.