Computing Programs for Generalized Planning as Heuristic Search (Extended Abstract)

1 Introduction

Heuristic search is one of the most successful approaches to classical planning [Bonet and Geffner, 2001; Hoffmann, 2003; Helmert, 2006; Lipovetzky and Geffner, 2017]. Unfortunately, it is not straightforward to adopt state-of-the-art search algorithms and heuristics from classical planning to Generalized Planning (GP). The planning as heuristic search approach traditionally addresses the computation of sequential plans implementing a grounded state-space search. GP requires however reasoning about the synthesis of algorithmlike solutions that, in addition to action sequences, contain branching and looping constructs [Winner and Veloso, 2003; Hu and Levesque, 2011; Siddharth et al., 2011; Hu and De Giacomo, 2013; Segovia-Aguas et al., 2016; Illanes and McIlraith, 2019; Franc`es et al., 2021]. Furthermore, GP aims to synthesize solutions that generalize to a (possibly infinite) set of planning instances. The domain of the state variables may then be large, making unfeasible the grounding traditionally implemented by of off-the-shelf classical planners.

This paper adapts the planning as heuristic search paradigm to the particularities of GP, and presents the first native heuristic search approach to GP. Given a GP problem, that comprises an input set of classical planning instances from a given domain, our GP as heuristic search approach computes an algorithm-like plan that solves the full set of input instances. The contribution of the paper is two-fold:

∗This is an extended abstract of the "Generalized Planning as Heuristic Search" paper that appeared at ICAPS 2021 conference.

• A tractable solution space for GP. We leverage the computational models of the Random-Access Machine [Skiena, 1998] and the Intel x86 FLAGS register [Dandamudi, 2005] to define an innovative programbased solution space that is independent of the number of input planning instances in a GP problem, and the size of these instances (i.e. the number of state variables and their domain size).
• A heuristic search algorithm for GP. We present the BFGP algorithm that implements a best-first search in our solution space for GP. We also define several evaluation and heuristic functions to guide BFGP; evaluating these functions does not require to ground states/actions in advance, so they allow to addressing GP problems where state variables have large domains (e.g. integers).

The paper is structured as follows. First we formalize the classical planning model. Then we show how to extend this model with a Random-Access Machine (RAM) and formalize GP with planning programs, our representation formalism for GP solutions. Last, we describe the implementation of our GP as heuristic search approach and report results on its empirical performance. More details on the GP as heuristic search approach can be found in Segovia-Aguas et al. [2021].

2 Classical Planning

Let X be a set of state variables, each x ∈ X with domain Dx. A state is a total assignment of values to the set of state variables. For a variable subset X′ ⊆ X, let D[X′ ] = ×x∈X′Dx denote its joint domain. The state space is then S = D[X]. Given a state s ∈ S and a subset of variables X′ ⊆ X, let s|X′ = ⟨xi = vi⟩xi∈X′ be the projection of s onto X′ i.e. the partial state defined by the values that s assigns to the variables in X′ . The projection of s onto X′ defines the subset of states {s | s ∈ S, s|X′ ⊆ s} that are consistent with the corresponding partial state.

Let A be a set of deterministic actions. An action a ∈ A has an associated set of variables par(a) ⊆ X, called parameters, and is characterized by two functions: an applicability function ρa : D[par(a)] → {0, 1}, and a successor function θa : D[par(a)] → D[par(a)]. Action a is applicable in a given state s iff ρa(s|par(a)) equals 1, and results in a successor state s′ = s ⊕ a, that is built replacing the values that s assigns to variables in par(a) with the values specified by θa(s|par(a)).

A classical planning instance is a tuple P = ⟨X, A, I, G⟩, where X is a set of state variables, A is a set of actions, I ∈ S is an initial state, and G is a goal condition on the state variables that induces the subset of goal states SG = {s | s ⊨ G, s ∈ S}. Given P, a plan is an action sequence π = ⟨a1, . . . , am⟩ whose execution induces a trajectory τ = ⟨s0, a1, s1, . . . , am, sm⟩ such that, for each 1 ≤ i ≤ m, ai is applicable in si-1 and results in the successor state si = si-1 ⊕ ai. A plan π solves P if the execution of π in s0 = I finishes in a goal state, i.e. sm ∈ SG.

3 Generalized Planning as Heuristic Search

This work builds on top of the inductive formalism for GP, where a GP problem is a set of classical planning instances with a common structure. Here we describe our heuristic search approach to GP.

3.1 Classical Planning with a RAM

To define a tractable solution space for GP, that is independent of the number (and domain size) of the planning state variables, we extend the classical planning model with: (i), a set of pointers over the state variables (ii), their primitive operations and (iii), two Boolean (the zero and carry FLAGS) to store the result of the primitive operations over pointers.

Formally a pointer is a finite domain variable z ∈ Z with domain Dz = [0..|X|). To formalize the primitive operations over pointers we leverage the notion of the RAM; the RAM is an abstract computation machine, that is polynomially equivalent to a Turing machine, and that enhances a multiple-register counter machine with indirect memory addressing [Boolos et al., 2002]. The indirect memory addressing of the RAM enables the definition of programs that access an unbounded number of state variables. Let z ∈ Z be a pointer over the state variables, and ∗z the content of that pointer, our GP as heuristic search implements the following primitive operations over pointers: {inc(z1), dec(z1), cmp(z1, z2), cmp(∗z1, ∗z2), set(z1, z2) | z1, z2 ∈ Z}. Respectively, these primitive operations increment/decrement a pointer, compare two pointers (or their content), and set the value of a pointer z1 to another pointer z2. Each primitive operation also updates two Boolean Y = {yz, yc}, the zero and carry FLAGS, according to the result (denoted here by res) of that primitive operation:

Given a classical planning instance P = ⟨X,A, I,G⟩, its extension with a RAM of |Z| pointers and two FLAGS is the classical planning instance PZ = ⟨XZ,AZ, IZ,G⟩, where the set of the state variables is extended with the FLAGS and the pointers, XZ = X ∪ Y ∪ Z. The set of actions AZ comprises the primitive pointer operations and the original actions A, but replacing their parameters by pointers in Z. The initial state IZ is extended to set the FLAGS to False, and the pointers to zero (by default). The goals of PZ are the same as those of the original instance. An extended instance PZ preserves the solution space of the original instance P [Segovia-Aguas et al., 2021].

3.2 Generalized Planning with a RAM

A GP problem is a set of classical planning instances with a common structure. In this work the common structure is given by the RAM extension; it provides a set of different classical planning instances with a common set of FLAGS, pointers, and actions defined over those pointers.

Definition 1 (GP problem). A GP problem is a set of T classical planning instances P = {P 1Z , . . . , P T Z } that share the same subset of state variables {Y ∪ Z}, and actions AZ, but may differ in their state variables, initial state, and goals. Formally, P 1Z = ⟨X1Z ,AZ, I 1Z ,G1⟩, . . . , P T Z = ⟨XT Z , AZ , I T Z , GT ⟩ where ∀t{Y ∪ Z} ⊂ XtZ , 1 ≤ t ≤ T .

Representations of GP solutions range from programs [Winner and Veloso, 2003; Jimenez and Jonsson, 2015; Segovia-Aguas et al., 2019] and generalized policies [Mart´ın and Geffner, 2004], to finite state controllers [Bonet et al., 2010; Segovia-Aguas et al., 2019] or formal grammars and hierarchies [Nau et al., 2003; Segovia-Aguas et al., 2017]. Each representation has its own expressiveness capacity, as well as its own computation complexity. We can however define a common condition under which a generalized plan is considered a solution to a GP problem [Jim´enez et al., 2019]. First, let us define exec(Π, P) = ⟨a1, . . . , am⟩ as the sequential plan produced by the execution of a generalized plan Π, on a classical planning instance P .

Definition 2 (GP solution). A generalized planΠ solves aGP problem P iff for every classical planning instance Pt ∈ P, 1 ≤ t ≤ T , it holds that exec(Π, Pt) solves Pt.

In this work we represent GP solutions as planning programs [Segovia-Aguas et al., 2019]. A planning program is a sequence of n instructions Π = ⟨w0, . . . ,wn-1⟩, where each instruction wi ∈ Π is associated with a program line 0 ≤ i < n and is either:

• A planning action wi ∈ A.
• A goto instruction wi = go(i′ , !y), where i′ is a program line 0 ≤ i′ < i or i + 1 < i′ < n, and y is a proposition.
• A termination instruction wi = end. The last instruction of a program Π is always wn-1 = end.

The execution model for a planning program is a program state (s, i), i.e. a pair of a planning state s ∈ S and program line 0 ≤ i < n. Given a program state (s, i), the execution of a programmed instruction wi is defined as:

• If wi ∈ A, the new program state is (s′ , i + 1), where s′ = s ⊕wi is the successor when applying wi in s.

REVERSE

• 0 . swap (z1 ,z2 )
• 1 . i nc (z1 )
• 2 . dec (z2 )
• 3 . cmp (z2 ,z1 )
• 4 . goto (0 ,¬(¬yz ∧¬yc ) )

• 5 . end

Figure 2: Generalized plan for reversing a list, no matter its length.

• If wi = go(i′ , !y), the new program state is (s, i + 1) if y holds in s, and (s, i′ ) otherwise 1 . Proposition y can be the result of an arbitrary expression on the state variables [Lotinac et al., 2016].
• If wi = end, program execution terminates.

To execute a planning program Π on a planning instance P, the initial program state is set to (I, 0), i.e. the initial state of P and the first program line of Π. A planning program Π solves P iff the execution terminates in a program state (s, i) that satisfies the goal condition, i.e. wi = end and s ∈ SG.

Example. Figure 1 shows the initial state and goals of two classical planning instances, P1 = ⟨X,A, I1,G1⟩ and P2 = ⟨X,A, I2,G2⟩, for reversing two lists. Both instances can be defined with a set of state variables X = {xi}l1 , where an integer is assigned to every xi and l is the list length, and a set of swap(xi, xj) actions that swap the content of two state variables. An example solution plan for P1 is π1 = ⟨swap(x1, x6), swap(x2, x5), swap(x3, x4)⟩ while π2 = ⟨swap(x1, x5), swap(x2, x4)⟩ is a solution plan for P2. This set of two classical planning instances can be extended with a RAM, and the resulting set P = {P 1Z , P 2Z } is an example GP problem. Figure 2 shows the generalized plan, represented as a planning program with six lines and two pointers Z = {z1, z2}. Initially, the first list element is pointed by z1 (default) and the last element by z2. The elements pointed by z1 and z2 are swapped in Line 0, and the pointers are moved forward and backward once respectively (Lines 1-2). Then, z2 and z1 are compared in Line 3, and the FLAGS are updated as follows: yz = ((z2 - z1) == 0) and yc = ((z2 - z1) > 0). This is repeated until ¬(¬yz ∧ ¬yc) is falsified, which only occurs when z2 is smaller than z1, thus reversing any list, no matter its length or content.

1 We adopt the convention of jumping to line i′ whenever y is false, inspired by jump instructions in the Random-Access Machine that jump when a register equals zero.

3.3 The BFGP Algorithm for GP

Given a GP problem P = {P1, . . . , PT}, a number of program lines n, and a number of pointers |Z|, the BFGP algorithm outputs a planning program Π that solves every classical planning instance Pt ∈ P, 1 ≤ t ≤ T. Otherwise BFGP reports that there is no solution within the given number of program lines and pointers.

Search space. BFGP searches in the space of planning programs with n program lines, and |Z| pointers, that can be built with the shared set of actions AZ, and goto instructions that are exclusively conditioned on the value of FLAGS Y = {yz, yc}. Since only the primitive operations over pointers update FLAGS Y , we have an observation space of 2|Y | × 2|Z|2 state observations implemented with only |Y | Boolean variables. The four joint values of {yz, yc} model then a large space of observations, including =0, ̸=0, < 0,> 0,≤ 0,≥ 0 as well as relations =, ̸=,<,>,≤,≥ on variable pairs.

Search algorithm. BFGP implements a Best First Search (BFS) that starts with an empty planning program. To generate a tractable set of successor nodes, child nodes in the search tree are restricted to planning programs that result from programming the PCMAX line (i.e. the maximum line reached after executing the current program on the classical planning instances in P). This procedure for successor generation guarantees that duplicate successors are not generated. BFGP is a frontier search algorithm, meaning that, to reduce memory requirements, BFGP stores only the open list of generated nodes, but not the closed list of expanded nodes [Korf et al., 2005]. BFS sequentially expands the best node in a priority queue (aka open list) sorted by an evaluation/heuristic function. If the planning program Π solves all the instances Pt ∈ P, then search ends, and Π is a valid solution for the GP problem P.

Evaluation functions. BFGP exploits two different sources of information to guide the search in the space of candidate planning programs:

• The program structure. These are evaluation functions computed in linear time in the size of programΠ.
• f1(Π), the number of goto instructions in Π.
• f2(Π), number of undefined program lines in Π.
• f3(Π), the number of repeated actions in Π.
• The program performance. These functions assess the performance of Π executing it on each of the classical planning instances Pt ∈ P, 1 ≤ t ≤ T; the execution of a planning program on a classical planning instance is a deterministic procedure that requires no variable instantiation. If the execution of Π on an instance Pt ∈ P fails, this means that the search node corresponding to the planning program Π is a dead-end, and hence it is not added to the open list:
• h4(Π,P) = n - PCMAX , where PCMAX is the maximum program line that is eventually reached after executing Π on all the instances in P.
• h5(Π,P) = ∑Pt∈P ∑v∈Gt (st[v] -Gt[v])2 . This function accumulates, for each instance Pt ∈ P,

the euclidean distance of state st to the goal state variables Gt. The state st is obtained applying the sequence of actions exec(Π, Pt) to the initial state It of that problem Pt ∈ P. Computing h5(Π, Pt) requires that goals are specified as a partial state. Note that for Boolean variables the squared difference becomes a simple goal counter.

• f6(Π,P) = ∑Pt∈P |exec(Π, Pt)|, where exec(Π, Pt) is the sequence of actions induced from executing the planning program Π on the planning instance Pt.

All these functions are cost functions (i.e. smaller values are preferred). Functions h4(Π,P) and h5(Π,P) are cost-to-go heuristics; they provide an estimate on how far a program is from solving the given GP problem. Functions h4(Π,P), h5(Π, P), and f6(Π, P) aggregate several costs that could be expressed as a combination of different functions, e.g. sum, max, average, weighted average, etc.

4 Evaluation

We evaluated the performance of our GP as heuristic search approach in eight domains [Segovia-Aguas et al., 2021]. Experiments performed in an Ubuntu 20.04 LTS, with AMD® Ryzen 7 3700x 8-core processor × 16 and 32GB of RAM.

Table 1 summarizes the results of BFGP with our six different evaluation/heuristic functions (best results in bold): i) f2 and h5 exhibited the best coverage; ii) there is no clear dominance of a structure evaluation function, f2 has the best memory consumption while f3 is the only structural function that solves Sorting; iii) the performance-based function h5 dominates h4 and f6. Interestingly, the base performance of BFGP with a single evaluation/heuristic function is improved guiding BFGP with a cost-to-go heuristic function and breaking ties with a structural evaluation function (or vice versa). Table 2 shows the performance of BFGP(f1, h5) and its reversed configuration BFGP (h5, f1) which actually resulted in the overall best configuration solving all domains.

The solutions synthesized by BFGP were successfully validated. Table 3 reports the CPU time, and peak memory, yield when running the solutions synthesized by BFGP(h5, f1) on a validation set. The largest CPU-times and memory peaks correspond to the configuration that implements the detection of infinite programs, which requires saving states to detect whether they are revisited during execution. Skipping this mechanism allows to validate non-infinite programs faster [Segovia-Aguas et al., 2020].

5 Conclusion

We presented the first native heuristic search approach for GP that leverages solutions represented as automated planning programs. We believe this work builds a stronger connection between the two closely related areas of planning and program synthesis [Gulwani et al., 2017; Alur et al., 2018]. A wide landscape of effective techniques, coming from heuristic search and classical planning, promise to improve the base performance of our approach [Segovia-Aguas et al., 2022]. For instance, better estimates may be obtained by building on top of better informed planning heuristics [Franc`es, 2017].

Acknowledgements

Javier Segovia-Aguas is supported by TAILOR, a project funded by EU H2020 research and innovation programme no. 952215. Sergio Jim´enez is supported by Spanish grants RYC2015-18009 and TIN2017-88476-C2-1-R. Anders Jonsson is supported by Spanish grant PID2019-108141GB-I00.