## Computing Programs for Generalized Planning as Heuristic Search (Extended Abstract)
Javier Segovia-Aguas 1 , Sergio Jim´ enez 2 and Anders Jonsson 1
1 Dept. Information and Communication Technologies, Universitat Pompeu Fabra, Spain 2 Valencian Research Institute for Artificial Intelligence, Universitat Polit` ecnica de Val` encia, Spain javier.segovia@upf.edu, serjice@dsic.upv.es, anders.jonsson@upf.edu
## Abstract
Although heuristic search is one of the most successful approaches to classical planning, this planning paradigm does not apply straightforwardly to Generalized Planning (GP). This paper adapts the planning as heuristic search paradigm to the particularities of GP, and presents the first native heuristic search approach to GP. First, the paper defines a program-based solution space for GP that is independent of the number of planning instances in a GP problem, and the size of these instances. Second, the paper defines the BFGP algorithm for GP, that implements a best-first search in our programbased solution space, and that is guided by different evaluation and heuristic functions.
## 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 algorithm-like 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 1 . Given a GP problem,
1 This is an extended abstract of the 'Generalized Planning as Heuristic Search' paper that appeared at ICAPS 2021 conference.
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:
- 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 D x . 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 ′ D x 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 ′ = 〈 x i = v i 〉 x i ∈ 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 S G = { s | s /satisfies G,s ∈ S } . Given P , a plan is an action sequence π = 〈 a 1 , . . . , a m 〉 whose execution induces a trajectory τ = 〈 s 0 , a 1 , s 1 , . . . , a m , s m 〉 such that, for each 1 ≤ i ≤ m , a i is applicable in s i -1 and results in the successor state s i = s i -1 ⊕ a i . A plan π solves P if the execution of π in s 0 = I finishes in a goal state, i.e. s m ∈ S G .
## 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 D z = [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 ( z 1 ) , dec ( z 1 ) , cmp ( z 1 , z 2 ) , cmp ( ∗ z 1 , ∗ z 2 ) , set ( z 1 , z 2 ) | z 1 , z 2 ∈ Z } . Respectively, these primitive operations increment/decrement a pointer, compare two pointers (or their content), and set the value of a pointer z 1 to another pointer z 2 . Each primitive operation also updates two Boolean Y = { y z , y c } , the zero and carry FLAGS, according to the result (denoted here by res ) of that primitive operation:
<!-- formula-not-decoded -->
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 P Z = 〈 X Z , A Z , I Z , G 〉 , where the set of the state variables is extended with the FLAGS and the pointers, X Z = X ∪ Y ∪ Z . The set of actions A Z comprises the primitive pointer operations and the original actions A , but replacing their parameters by pointers in Z . The initial state I Z is extended to set the FLAGS to False, and the pointers to zero (by default). The goals of P Z are the same as those of the original instance. An extended instance P Z 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 1 Z , . . . , P T Z } that share the same subset of state variables { Y ∪ Z } , and actions A Z , but may differ in their state variables, initial state, and goals. Formally, P 1 Z = 〈 X 1 Z , A Z , I 1 Z , G 1 〉 , . . . , P T Z = 〈 X T Z , A Z , I T Z , G T 〉 where ∀ t { Y ∪ Z } ⊂ X t Z , 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 ) = 〈 a 1 , . . . , a m 〉 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 a GP problem P iff for every classical planning instance P t ∈ P , 1 ≤ t ≤ T , it holds that exec (Π , P t ) solves P t .
In this work we represent GP solutions as planning programs [Segovia-Aguas et al. , 2019]. A planning program is a sequence of n instructions Π = 〈 w 0 , . . . , w n -1 〉 , where each instruction w i ∈ Π is associated with a program line 0 ≤ i < n and is either:
- A planning action w i ∈ A .
- A goto instruction w i = 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 w i = end . The last instruction of a program Π is always w n -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 w i is defined as:
- If w i ∈ A , the new program state is ( s ′ , i + 1) , where s ′ = s ⊕ w i is the successor when applying w i in s .
Figure 1: Classical planning instances for reversing the content of two lists by swapping their elements.
<details>
<summary>Image 1 Details</summary>
### Visual Description
\n
## Diagram: State Transition
### Overview
The image depicts a state transition diagram showing two permutations, labeled P1 and P2, transitioning from an "Initial State" to a "Goal State". Each permutation is represented as a sequence of numbers within a rectangular box. An arrow indicates the transformation from the initial to the goal state.
### Components/Axes
The diagram consists of two rows, each representing a permutation.
- **Row 1:** Labeled "P1"
- **Row 2:** Labeled "P2"
- **Column Headers:** "Initial State" and "Goal State"
Each permutation is represented by a sequence of numbers within a rectangular box.
### Detailed Analysis or Content Details
**P1:**
- **Initial State:** The sequence is 6, 3, 4, 2, 5, 1.
- **Goal State:** The sequence is 1, 5, 2, 4, 3, 6.
**P2:**
- **Initial State:** The sequence is 3, 2, 1, 5, 4.
- **Goal State:** The sequence is 4, 5, 1, 2, 3.
### Key Observations
The diagram illustrates two distinct permutations and their corresponding transformations. The transformation from the initial state to the goal state is not explicitly defined; it is simply shown as a transition. The permutations are of different lengths (P1 has 6 elements, P2 has 5 elements).
### Interpretation
The diagram likely represents a problem in permutation or sorting. The "Initial State" represents the starting arrangement of elements, and the "Goal State" represents the desired arrangement. The diagram does not provide the algorithm or method used to achieve the transformation, only the before and after states. The differing lengths of the permutations suggest that the problem may involve permutations of varying sizes, or that the two permutations are independent examples of the same problem. The diagram could be used to illustrate the concept of a state space in search algorithms, where the initial and goal states are defined, and the algorithm must find a path to transform one into the other.
</details>
## REVERSE
0. swap ( z 1 , z 2 )
1. i n c ( z 1 )
2. dec ( z 2 )
3. cmp( z 2 , z 1 )
4. goto (1 , ¬ ( ¬ y z ∧¬ y c ) )
5. end
Figure 2: Generalized plan for reversing a list, no matter its length.
- If w i = go ( i ′ , ! y ) , the new program state is ( s, i + 1) if y holds in s , and ( s, i ′ ) otherwise 2 . Proposition y can be the result of an arbitrary expression on the state variables [Lotinac et al. , 2016].
- If w i = 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. w i = end and s ∈ S G .
Example . Figure 1 shows the initial state and goals of two classical planning instances, P 1 = 〈 X,A,I 1 , G 1 〉 and P 2 = 〈 X,A,I 2 , G 2 〉 , for reversing two lists. Both instances can be defined with a set of state variables X = { x i } l 1 , where an integer is assigned to every x i and l is the list length, and a set of swap ( x i , x j ) actions that swap the content of two state variables. An example solution plan for P 1 is π 1 = 〈 swap ( x 1 , x 6 ) , swap ( x 2 , x 5 ) , swap ( x 3 , x 4 ) 〉 while π 2 = 〈 swap ( x 1 , x 5 ) , swap ( x 2 , x 4 ) 〉 is a solution plan for P 2 . This set of two classical planning instances can be extended with a RAM, and the resulting set P = { P 1 Z , P 2 Z } is an example GP problem. Figure 2 shows the generalized plan, represented as a planning program with six lines and two pointers Z = { z 1 , z 2 } . Initially, the first list element is pointed by z 1 (default) and the last element by z 2 . The elements pointed by z 1 and z 2 are swapped in Line 0, and the pointers are moved forward and backward once respectively (Lines 1-2). Then, z 2 and z 1 are compared in Line 3, and the FLAGS are updated as follows: y z = (( z 2 -z 1 ) == 0) and y c = (( z 2 -z 1 ) > 0) . This is repeated until ¬ ( ¬ y z ∧¬ y c ) is falsified, which only occurs when z 2 is smaller than z 1 , thus reversing any list, no matter its length or content.
2 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 Generalized Planning
Given a GP problem P = { P 1 , . . . , P T } , 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 P t ∈ P , 1 ≤ t ≤ T . Otherwise BFGP reports that there is no solution within the given number of program lines and pointers.
/negationslash
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 A Z , and goto instructions that are exclusively conditioned on the value of FLAGS Y = { y z , y c } . 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 { y z , y c } model then a large space of observations, including = 0, = 0, < 0 , > 0 , ≤ 0 , ≥ 0 as well as relations = , = , <, >, ≤ , ≥ on variable pairs.
/negationslash
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 PC MAX 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 P t ∈ 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 Π .
- -f 1 (Π) , the number of goto instructions in Π .
- -f 2 (Π) , number of undefined program lines in Π .
- -f 3 (Π) , the number of repeated actions in Π .
- The program performance . These functions assess the performance of Π executing it on each of the classical planning instances P t ∈ 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 P t ∈ 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:
- -h 4 (Π , P ) = n -PC MAX , where PC MAX is the maximum program line that is eventually reached after executing Π on all the instances in P .
- -h 5 (Π , P ) = ∑ P t ∈P ∑ v ∈ G t ( s t [ v ] -G t [ v ]) 2 . This function accumulates, for each instance P t ∈ P , the euclidean distance of state s t to the goal state variables G t . The state s t is obtained applying the
| Domain | n, | Z | | f 1 | f 1 | f 1 | f 1 | f 2 | f 2 | f 2 | f 2 | f 3 | f 3 | f 3 | f 3 |
|-----------|----------------------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| Domain | n, | Z | | Time | Mem. | Exp. | Eval. | Time | Mem. | Exp. | Eval. | Time | Mem. | Exp. | Eval. |
| T. Sum | 5, 2 | 0.24 | 4.2 | 4.8K | 5.8K | 0.30 | 3.8 | 6.4K | 6.4K | 0.13 | 3.9 | 2.2K | 2.8K |
| Corridor | 7, 2 | 3.04 | 6.6 | 12.4K | 26.7K | 0.41 | 3.8 | 2.2K | 2.2K | 3.66 | 4.2 | 24.2K | 25.9K |
| Reverse | 7, 3 | 82 | 61 | 0.28M | 0.57M | 181 | 4.0 | 0.95M | 0.95M | 170 | 23 | 0.75M | 0.84M |
| Select | 7, 3 | 198 | 110 | 0.83M | 1.10M | 27 | 3.9 | 0.12M | 0.12M | 76.49 | 11 | 0.34M | 0.38M |
| Find | 7, 3 | 195 | 175 | 0.50M | 1.36M | 271 | 4.0 | 1.46M | 1.46M | 86 | 12 | 0.41M | 0.45M |
| Fibonacci | 8, 3 | 496 | 922 | 2.48M | 6.79M | 1,082 | 3.9 | 11.8M | 11.8M | TO | - | - | - |
| Gripper | 8, 4 | TO | - | - | - | 3,439 | 4.1 | 19.9M | 19.9M | TO | - | - | - |
| Sorting | 9, 3 | TO | - | - | - | TO | - | - | - | 3,143 | 711 | 19.5M | 22.9M |
| Average | Average | 162 | 213 | 0.68M | 1.64M | 714 | 3.9 | 4.89M | 4.89M | 580 | 128 | 3.51M | 4.09M |
| Domain | n, | Z | | h 4 | h 4 | h 4 | h 4 | h 5 | h 5 | h 5 | h 5 | f 6 | f 6 | f 6 | f 6 |
| | | Time | Mem. | Exp. | Eval. | Time | Mem. | Exp. | Eval. | Time | Mem. | Exp. | Eval. |
| T. Sum | 5, 2 | 0.10 | 3.8 | 1.6K | 1.6K | 0.09 | 3.9 | 1.2K | 1.4K | 0.45 | 4.8 | 7.4K | 7.4K |
| Corridor | 7, 2 | 1.09 | 3.9 | 5.3K | 5.4K | 5.29 | 4.1 | 30.3K | 31.3K | 6.16 | 7.6 | 35.3K | 35.3K |
| Reverse | 7, 3 | 205 | 4.2 | 0.88M | 0.88M | 1.46 | 4.2 | 4.9K | 6.3K | 369 | 230 | 1.57M | 1.65M |
| Select | 7, 3 | 0.80 | 3.9 | 3.0K | 4.2K | 94 | 5.7 | 0.34M | 0.35M | 255 | 155 | 1.06M | 1.14M |
| Find | 7, 3 | 415 | 4.4 | 1.76M | 1.76M | 140 | 7.0 | 0.58M | 0.59M | 423 | 244 | 1.76M | 1.77M |
| Fibonacci | 8, 3 | TO | - | - | - | 1,500 | 120 | 11.3M | 11.8M | TO | - | - | - |
| Gripper | 8, 4 | TO | - | - | - | 83 | 5.5 | 0.34M | 0.35M | TO | - | - | - |
| Sorting | 9, 3 | TO | - | - | - | TO | - | - | - | TO | - | - | - |
| Average | Average | 125 | 4.0 | 0.53M | 0.53M | 260 | 21 | 1.80M | 1.88M | 211 | 128 | 0.89M | 0.92M |
Table 1: We report the number of program lines n , and pointers | Z | per domain, and for each evaluation/heuristic function, CPU (secs), memory peak (MBs), and the numbers of expanded and evaluated nodes. TO stands for Time-Out ( > 1h of CPU). Best results in bold.
Table 2: CPU time (secs), memory peak (MBs), num. of expanded and evaluated nodes. Best results in bold.
| Dom. | BFGP ( f 1 ,h 5 ) / BFGP ( h 5 , f 1 ) | BFGP ( f 1 ,h 5 ) / BFGP ( h 5 , f 1 ) | BFGP ( f 1 ,h 5 ) / BFGP ( h 5 , f 1 ) | BFGP ( f 1 ,h 5 ) / BFGP ( h 5 , f 1 ) |
|--------|------------------------------------------|------------------------------------------|------------------------------------------|------------------------------------------|
| | T. | M. | Exp. | Eval. |
| T. Sum | 0.2/ 0.1 | 4.3/ 3.8 | 2.8K/ 1.1K | 4.8K/ 1.4K |
| Corr. | 3.2 /4.5 | 6.6/ 5.9 | 6.5K /26.0K | 21.6K /27.5K |
| Rev. | 63/ 1.4 | 52/ 4.7 | 81.9K/ 3.7K | 0.3M/ 7.7K |
| Sel. | 203/ 80 | 110/ 7.0 | 0.6M/ 0.3M | 0.9M/ 0.3M |
| Find | 313/ 162 | 176/ 14 | 0.9M/ 0.7M | 1.5M/ 0.7M |
| Fibo. | 528/ 22 | 828/ 32 | 1.4M/ 75K | 5.3M/ 0.2M |
| Grip. | TO/ 6.9 | -/ 10 | -/ 5.8K | -/ 37.3K |
| Sort. | TO/ 713 | -/ 730 | -/ 4.4M | -/ 4.5M |
Table 3: Validation set, CPU-time (secs) and memory peak for program validation, with/out infinite program detection.
| Dom. | Inst. | Time ∞ | Mem ∞ | Time | Mem |
|--------|---------|----------|---------|--------|-------|
| T. Sum | 44,709 | 1,066.74 | 53MB | 574.08 | 47MB |
| Corr. | 1,000 | 0.23 | 5.0MB | 0.15 | 4.7MB |
| Rev. | 50 | 37.96 | 5.2GB | 2.7 | 0.3GB |
| Sel. | 50 | 144.75 | 19.6GB | 2.29 | 33MB |
| Find | 50 | 114.55 | 19.6GB | 2.12 | 33MB |
| Fibo. | 33 | 0.00 | 4.2MB | 0 | 3.9MB |
| Grip. | 1,000 | 2.71 | 0.1GB | 1.65 | 0.1GB |
| Sort. | 20 | 272.06 | 15.2GB | 52.04 | 3.8MB |
sequence of actions exec (Π , P t ) to the initial state I t of that problem P t ∈ P . Computing h 5 (Π , P t ) requires that goals are specified as a partial state. Note that for Boolean variables the squared difference becomes a simple goal counter.
- -f 6 (Π , P ) = ∑ P t ∈P | exec (Π , P t ) | , where exec (Π , P t ) is the sequence of actions induced from executing the planning program Π on the planning instance P t .
All these functions are cost functions (i.e. smaller values are preferred). Functions h 4 (Π , P ) and h 5 (Π , P ) are cost-to-go heuristics ; they provide an estimate on how far a program is from solving the given GP problem. Functions h 4 (Π , P ) , h 5 (Π , P ) , and f 6 (Π , 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) f 2 and h 5 exhibited the best coverage; ii) there is no clear dominance of a structure evaluation function, f 2 has the best memory consumption while f 3 is the only structural function that solves Sorting ; iii) the performance -based function h 5 dominates h 4 and f 6 . 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 ( f 1 , h 5 ) and its reversed configuration BFGP ( h 5 , f 1 ) 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 ( h 5 , f 1 ) 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 RYC-2015-18009 and TIN2017-88476-C2-1-R. Anders Jonsson is partially supported by Spanish grant PID2019-108141GB-I00.
## References
- [Alur et al. , 2018] Rajeev Alur, Rishabh Singh, Dana Fisman, and Armando Solar-Lezama. Search-based program synthesis. Communications of the ACM , 61(12):84-93, 2018.
- [Bonet and Geffner, 2001] Blai Bonet and H´ ector Geffner. Planning as heuristic search. Artificial Intelligence , 129:533, 2001.
- [Bonet et al. , 2010] Blai Bonet, Hector Palacios, and Hector Geffner. Automatic derivation of finite-state machines for behavior control. In AAAI , volume 24, 2010.
- [Boolos et al. , 2002] George S Boolos, John P Burgess, and Richard C Jeffrey. Computability and logic . Cambridge university press, 2002.
- [Dandamudi, 2005] Sivarama P Dandamudi. Installing and using nasm. Guide to Assembly Language Programming in Linux , 2005.
- [Franc` es et al. , 2021] Guillem Franc` es, Blai Bonet, and Hector Geffner. Learning general planning policies from small examples without supervision. In AAAI , 2021.
- [Franc` es, 2017] Guillem Franc` es. Effective planning with expressive languages . PhD thesis, Universitat Pompeu Fabra, 2017.
- [Gulwani et al. , 2017] Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. Program synthesis. Foundations and Trends in Programming Languages , 2017.
- [Helmert, 2006] Malte Helmert. The Fast Downward Planning System. JAIR , 26:191-246, 2006.
- [Hoffmann, 2003] J¨ org Hoffmann. The metric-ff planning system: Translating 'ignoring delete lists' to numeric state variables. JAIR , 20:291-341, 2003.
- [Hu and De Giacomo, 2013] Yuxiao Hu and Giuseppe De Giacomo. A generic technique for synthesizing bounded finite-state controllers. In ICAPS , 2013.
- [Hu and Levesque, 2011] Yuxiao Hu and Hector J. Levesque. A correctness result for reasoning about one-dimensional planning problems. In IJCAI , pages 2638-2643, 2011.
- [Illanes and McIlraith, 2019] Le´ on Illanes and Sheila A McIlraith. Generalized planning via abstraction: arbitrary numbers of objects. In AAAI , volume 33, pages 76107618, 2019.
- [Jimenez and Jonsson, 2015] Sergio Jimenez and Anders Jonsson. Computing plans with control flow and procedures using a classical planner. In International Symposium on Combinatorial Search , 2015.
- [Jim´ enez et al. , 2019] Sergio Jim´ enez, Javier SegoviaAguas, and Anders Jonsson. A review of generalized planning. KER , 34:1-28, 2019.
- [Korf et al. , 2005] Richard E Korf, Weixiong Zhang, Ignacio Thayer, and Heath Hohwald. Frontier search. Journal of the ACM , 52(5):715-748, 2005.
- [Lipovetzky and Geffner, 2017] Nir Lipovetzky and Hector Geffner. Best-first width search: Exploration and exploitation in classical planning. In AAAI , volume 31, 2017.
- [Lotinac et al. , 2016] Damir Lotinac, Javier Segovia-Aguas, Sergio Jim´ enez, and Anders Jonsson. Automatic generation of high-level state features for generalized planning. In IJCAI , pages 3199-3205, 2016.
- [Mart´ ın and Geffner, 2004] Mario Mart´ ın and Hector Geffner. Learning generalized policies from planning examples using concept languages. Applied Intelligence , 20:9-19, 2004.
- [Nau et al. , 2003] Dana S Nau, Tsz-Chiu Au, Okhtay Ilghami, Ugur Kuter, J William Murdock, Dan Wu, and Fusun Yaman. Shop2: An htn planning system. JAIR , 20:379-404, 2003.
- [Segovia-Aguas et al. , 2016] Javier Segovia-Aguas, Sergio Jim´ enez, and Anders Jonsson. Generalized planning with procedural domain control knowledge. In ICAPS , 2016.
- [Segovia-Aguas et al. , 2017] Javier Segovia-Aguas, Sergio Jim´ enez, and Anders Jonsson. Generating context-free grammars using classical planning. In IJCAI , 2017.
- [Segovia-Aguas et al. , 2019] Javier Segovia-Aguas, Sergio Jim´ enez, and Anders Jonsson. Computing programs for generalized planning using a classical planner. Artificial Intelligence , 272:52-85, 2019.
- [Segovia-Aguas et al. , 2020] Javier Segovia-Aguas, Sergio Jim´ enez, and Anders Jonsson. Generalized planning with positive and negative examples. In AAAI , volume 34, pages 9949-9956, 2020.
- [Segovia-Aguas et al. , 2021] Javier Segovia-Aguas, Sergio Jim´ enez, and Anders Jonsson. Generalized planning as heuristic search. In ICAPS , volume 31, pages 569-577, 2021.
- [Segovia-Aguas et al. , 2022] Javier Segovia-Aguas, Sergio Jim´ enez, Anders Jonsson, and Laura Sebasti´ a. Scaling-up generalized planning as heuristic search with landmarks. arXiv preprint arXiv:2205.04850 , 2022.
- [Siddharth et al. , 2011] Srivastava Siddharth, Immerman Neil, Zilberstein Shlomo, and Zhang Tianjiao. Directed search for generalized plans using classical planners. In ICAPS , volume 21, 2011.
- [Skiena, 1998] Steven S Skiena. The algorithm design manual: Text , volume 1. Springer Science & Business Media, 1998.
- [Winner and Veloso, 2003] Elly Winner and Manuela Veloso. Distill: Learning domain-specific planners by example. In ICML , pages 800-807, 2003.