tcb@breakable

# On Policy Reuse: An Expressive Language for Representing and Executing
General Policies that Call Other Policies

Blai Bonet1, Dominik Drexler2, Hector Geffner3,2

###### Abstract

Recently, a simple but powerful language for expressing and learning general
policies and problem decompositions (sketches) has been introduced in terms of
rules defined over a set of Boolean and numerical features. In this work, we
consider three extensions of this language aimed at making policies and
sketches more flexible and reusable: internal memory states, as in finite
state controllers; indexical features, whose values are a function of the
state and a number of internal registers that can be loaded with objects; and
modules that wrap up policies and sketches and allow them to call each other
by passing parameters. In addition, unlike general policies that select state
transitions rather than ground actions, the new language allows for the
selection of such actions. The expressive power of the resulting language for
policies and sketches is illustrated through a number of examples.

## Introduction

A new language for representing problem structure explicitly has been
introduced recently in the form of _sketches_ (Bonet and Geffner 2021, 2023).
Sketches are collections of rules of the form $C\mapsto E$ which are defined
over a set of Boolean and numerical domain features $\Phi$, where $C$
expresses Boolean conditions on the features, and $E$ expresses qualitative
changes in their values. Each sketch rule captures a subproblem: the problem
of going from a state $s$ whose feature values satisfy the condition $C$, to a
state $s^{\prime}$ where the feature values change with respect to $s$ in
agreement with $E$. The language of sketches is powerful as it can encode
everything from simple goal serializations to full general policies.

The width of a sketch for a class of problems bounds the complexity of solving
the resulting subproblems (Bonet and Geffner 2021, 2023). For example, a
sketch of width $k$ decomposes problems into subproblems that are solved by
the IW algorithm in time exponential in $k$ (Lipovetzky and Geffner 2012).
Sketches provide a direct generalization of policies, which are sketches of
width $0$ that result in subproblems that can be solved in a single step.

Combinatorial optimization methods for learning policies and sketches of this
form has been developed by Francès, Bonet, and Geffner (2021) and Drexler,
Seipp, and Geffner (2022) where both the rules and the features are obtained.

The current language of policies and sketches, however, does not support the
_reuse_ of other policies and sketches, and assumes instead that the top goals
are set up externally.111For each predicate $p$ appearing in the goal, a new
predicate $p_{G}$ is introduced with the same arity as $p$. The atom $p(c)$ in
the state $s$ means that $p(c)$ is true in $s$, while $p_{G}(c)$ in $s$ means
that $p(c)$ must be true in the goal. Yet for _reusing_ policies and sketches,
goals must be set up internally as well; e.g., for reusing a general policy
$\pi_{on}$ that achieves the atom $on(x,y)$ for any blocks $x$ and $y$ within
a policy $\pi_{T}$ that builds a tower, it is necessary for $\pi_{T}$ to
repeatedly call $\pi_{on}$ on the right sequence of blocks $x$ and $y$.

In this work, we develop an extension of the language of policies and sketches
that accommodates reuse. In the resulting framework, policies and sketches may
call other policies and sketches while passing them arguments. For example,
one can learn a policy $\pi_{T}$ for building towers of blocks that uses a
policy $\pi_{on}$ for putting one block on top of another, and then reuse
$\pi_{T}$ for learning a policy that builds any configuration of blocks.

The language extensions involved are basically three: _memory states_ , as in
finite state controllers for sequencing behaviors, _indexical features_ ,
whose values are a function of the state and a number of _internal registers_
that can be loaded with objects, and _modules,_ that wrap policies and
sketches so that they can be reused by other policies or sketches. In this
paper, we do not address the _learning_ problem, but the _representation_
problem, as in order to learn these policies bottom up, one must be able to
represent them.

The paper is structured as follows. The next two sections cover related work
and review planning and sketches. Then, two sections introduce extended
policies and sketches, and their semantics, and the following section
introduces modules, call rules, and action calls. The last section contains a
discussion with conclusions and directions for future work.

## Related Work

General policies. The paper builds on notions of width, generalized rule-based
policies and sketches of bounded width, and methods for learning them
(Lipovetzky and Geffner 2012; Bonet and Geffner 2018, 2023; Francès, Bonet,
and Geffner 2021; Drexler, Seipp, and Geffner 2022, 2023). The problem of
representing and learning general policies has a long history (Khardon 1999;
Martín and Geffner 2004; Fern, Yoon, and Givan 2006), and general plans have
also been represented in logic (Srivastava, Immerman, and Zilberstein 2011;
Illanes and McIlraith 2019), and neural nets (Groshev et al. 2018; Toyer et
al. 2020; Bueno et al. 2019; Rivlin, Hazan, and Karpas 2020; Garg, Bajpai, and
Mausam 2020; Ståhlberg, Bonet, and Geffner 2022a, b; Ståhlberg, Bonet, and
Geffner 2023).

Planning programs and inductive programming. Planning programs have been
proposed as a language for representing and learning general policies that
make use of a number of programming language constructs (Aguas, Celorrio, and
Jonsson 2016; Segovia-Aguas, Jiménez, and Jonsson 2019, 2021). However,
without a rich feature language for talking about goals, states, and their
relation, planning programs are basically limited to families of tasks where
the goal is fixed; like “putting all blocks on the table”, but not for
“building a given tower”.222 The goal is fixed in a class $\mathcal{Q}$ of
planning problems when for any $P$ in $\mathcal{Q}$, the goal $G$ of $P$ is
determined by its initial state. The problem of program reuse, which is
related to the problem of policy reuse, has been considered in program
synthesis and inductive programming (Dumancic, Guns, and Cropper 2021; Ellis
et al. 2023).

Deictic representations. The use of registers to store objects in the extended
language of policies and sketches is closely related to the use of indices and
visual markers in deictic or indexical representations (Chapman 1989; Agre and
Chapman 1990; Ballard et al. 1996). The computational value of such
representations, however, has not been clear (Finney et al. 2013). In our
setting, indices (registers) make policies (and sketches) parametric and more
expressive, as (sub)policies can be reused by setting and resetting the values
of registers as needed.

Hierarchical RL. Hierarchical structures have been used in RL in the form of
options (Sutton, Precup, and Singh 1999), hierarchies of machines (Parr and
Russell 1997) and MaxQ hierarchies (Dietterich 2000), and a vast literature
has explored methods for learning hierarchical policies (McGovern and Barto
2001; Machado, Bellemare, and Bowling 2017), in some cases, representing goals
and subgoals as part of an extended state (Kulkarni et al. 2016; Hafner et al.
2022). In almost all cases, however, policies and subpolicies are learned
jointly, not bottom up, and the information that is conveyed by parameters, if
they exist, is limited.

## Planning Problems and Sketches

A planning problem refers to a classical planning problem $P=\langle
D,I\rangle$ where $D$ is the planning domain and $I$ contains information
about the instance; namely, the objects in the instance, the initial
situation, and the goal. A class $\mathcal{Q}$ of planning problems is a set
of instances over a common domain $D$. A sketch for a class of problems
$\mathcal{Q}$ is a set of rules of the form $C\mapsto E$ based on features
over the domain $D$ which can be Boolean or numerical (i.e. non-negative
integer valued) (Bonet and Geffner 2023). The condition $C$ is a conjunction
of expressions like $p$ and $\neg p$ for Boolean features $p$, and
$n{\,{>}\,}0$ and $n{\,{=}\,}0$ for numerical features $n$, while the effect
$E$ is a conjunction of expressions like $p$, $\neg p$, and $p?$, and
$n\raisebox{0.6458pt}{$\downarrow$}$, $n\raisebox{0.6458pt}{$\uparrow$}$ and
$n?$ for Boolean and numerical features $p$ and $n$, respectively. A state
pair $(s,s^{\prime})$ over an instance $P$ in $\mathcal{Q}$ is compatible with
a rule $r$ if the state $s$ satisfies the condition $C$, and the change of
feature values from $s$ to $s^{\prime}$ is consistent with $E$. This is
written as $s^{\prime}\prec_{r}s$ and $s^{\prime}\prec_{R}s$ if $R$ is a set
of rules that contains $r$.

A sketch $R$ for a class $\mathcal{Q}$ splits the problems $P$ in
$\mathcal{Q}$ into subproblems $P[s]$ that are like $P$ but with initial state
$s$ (where $s$ is a reachable state in $P$), and goal states $s^{\prime}$ that
are either goal states of $P$, or states $s^{\prime}$ such that
$s^{\prime}\prec_{R}s$. The algorithm $\text{SIW}_{\text{R}}$ shown in Alg 1
uses this problem decomposition to solve problems $P$ in $\mathcal{Q}$ by
solving subproblems $P[s]$ via the IW algorithm (Lipovetzky and Geffner 2012).
If the sketch has bounded serialized width over $\mathcal{Q}$ and is
terminating, $\text{SIW}_{\text{R}}$ solves any problem $P$ in $\mathcal{Q}$
in polynomial time (Bonet and Geffner 2023; Srivastava et al. 2011).

1:Input: Sketch $R$ over features $\Phi$ that induces relation $\prec_{R}$

2:Input: Planning problem $P$ with initial state $s_{0}$ on which the features
in $\Phi$ are well defined

3:$s\leftarrow s_{0}$

4:while $s$ is not a goal state of $P$ do

5: Run IW search from $s$ to find goal state $s^{\prime}$ of $P$, or state

6: $s^{\prime}$ such that $s^{\prime}\prec_{R}s$

7: if $s^{\prime}$ is not found, return FAILURE

8: $s\leftarrow s^{\prime}$

9:return path from $s_{0}$ to the goal state $s$

Algorithm 1 $\text{SIW}_{\text{R}}$: sketch $R$ is used to decompose problem
into subproblems, each solved with the IW algorithm.

### Serialized Width, Acyclicity, and Termination

The width of a planning problem $P$ provides a complexity measure for finding
an optimal plan for $P$. If $P$ has $N$ ground atoms and its width is bounded
by $k$, written $w(P)\leq k$, an optimal plan for $P$ can be found in
$\mathcal{O}(N^{2k-1})$ time and $\mathcal{O}(N^{k})$ space by running the
algorithm $\text{IW}(k)$, which is a simple breadth-first search where newly
generated states are pruned if they do not make a tuple (set) of $k$ or less
atoms true for the first time in the search (Lipovetzky and Geffner 2012). If
the width of $P$ is bounded but its value is unknown, a plan (not necessarily
optimal) can be found by running the algorithm IW with the same complexity
bounds. IW calls $\text{IW}(i)$ iteratively with $i=0,\ldots,N$, until $P$ is
solved (Lipovetzky and Geffner 2012). If $P$ has no solution, its width is
defined as $w(P)\doteq\infty$, and if it has a plan of length one, as
$w(P)\doteq 0$. The width notion extends to classes $\mathcal{Q}$ of problems:
$w(\mathcal{Q})\leq k$ iff $w(P)\leq k$ for each problem $P$ in $\mathcal{Q}$.
If $w(\mathcal{Q})\leq k$ holds for class $\mathcal{Q}$, then any problem $P$
in $\mathcal{Q}$ can be solved in polynomial time as $k$ is independent of the
size of $P$.

A sketch $R$ has serialized width bounded by $k$ on a class $\mathcal{Q}$,
denoted as $w_{R}(\mathcal{Q})\leq k$, if for any $P$ in $\mathcal{Q}$, the
possible subproblems $P[s]$ have width bounded by $k$. In such a case, every
subproblem $P[s]$ that arises when running the $\text{SIW}_{\text{R}}$
algorithm on $P$ can be solved in polynomial time.

Finally, a sketch $R$ is acyclic in $P$ if there is no state sequence
$s_{0},s_{1},\ldots,s_{n}$ in $P$ such that $s_{i+1}{\,\prec_{R}\,}s_{i}$, for
$0\leq i<n$, and $s_{n}=s_{0}$, and it is acyclic in $\mathcal{Q}$ if it is
acyclic in each problem $P$ in $\mathcal{Q}$. The Sieve algorithm (Srivastava
et al. 2011) can check whether a sketch $R$ is terminating, and hence acyclic,
by just considering the rules in $R$ and the graph that they define. For a
terminating sketch $R$ with a bounded serialized width over $\mathcal{Q}$,
$\text{SIW}_{\text{R}}$ is guaranteed to find a solution to any problem $P$ in
$\mathcal{Q}$ in polynomial time (Bonet and Geffner 2023).

Example 1. A sketch of width $0$ (i.e., a policy) for achieving the atom
$on(x,y)$ for two blocks $x$ and $y$, on any Blocksworld instance, can be
defined with the numerical feature $n$ that counts the number of blocks above
$x$, $y$, or both, and the Boolean features On that represents whether the
goal holds (i.e., $x$ on $y$), $H$ that represents whether a block is being
held, and $H_{x}$ that represents whether the block $x$ is being held. The set
of features is $\Phi=\\{\textit{On},H,H_{x},n\\}$, and the rules are:

$r_{0}\ =\ \\{\neg\textit{On},n{\,{>}\,}0,\neg H,\neg
H_{x}\\}\mapsto\\{n\raisebox{0.6458pt}{$\downarrow$},H,H_{x}?\\}$
---
$r_{1}\ =\ \\{\neg\textit{On},n{\,{>}\,}0,H\\}\mapsto\\{\neg H,\neg H_{x}\\}$
$r_{2}\ =\ \\{\neg\textit{On},n{\,{=}\,}0,\neg H,\neg
H_{x}\\}\mapsto\\{H,H_{x}\\}$
$r_{3}\ =\
\\{\neg\textit{On},n{\,{=}\,}0,H,H_{x}\\}\mapsto\\{\textit{On},n\raisebox{0.6458pt}{$\uparrow$},\neg
H,\neg H_{x}\\}$

Rule $r_{0}$ says that in states where no block is being held and
$n{\,{>}\,}0$, picking a block above $x$ or $y$ is good, as it would decrement
$n$ and make $H$ true. Rule $r_{1}$ says that in states where a block is being
held and $n{\,{>}\,}0$, putting the block away from $x$ or $y$ is good, as the
resulting state transition would not change the value of $n$. Last, rule
$r_{2}$ says that in states where no block is held and $n{\,{=}\,}0$, picking
up $x$ is good, and $r_{3}$, that in states where block $x$ is held and
$n{\,{=}\,}0$, putting $x$ on $y$ is good, as it results in On being true,
while also increasing $n$ and making $H$ and $H_{x}$ false.

A sketch of width 2 for $\mathcal{Q}_{on}$ is obtained instead by replacing
$r_{0}$ and $r_{1}$ with the rule
$\\{\neg\textit{On},n{\,{>}\,}0\\}\mapsto\\{n\raisebox{0.6458pt}{$\downarrow$},\neg
H\\}$, and $r_{2}$ and $r_{3}$ with the rule
$\\{\neg\textit{On},n{\,{=}\,}0\\}\mapsto\\{\textit{On},n\raisebox{0.6458pt}{$\uparrow$},\neg
H\\}$. $\blacksquare$

## Extended Sketches

The first two extensions of sketches are introduced next.

### Finite Memory

The first language extension adds memory in the form of a finite number of
_memory states_ $m$:

######  Definition 1 (Sketches with Memory).

A sketch with finite memory is a tuple $\langle M,\Phi,m_{0},R\rangle$ where
$M$ is a finite set of memory states, $\Phi$ is a set of features, $m_{0}\in
M$ is the initial memory state, and $R$ is a set of rules extended with memory
states. Such rules have the form $(m,C)\mapsto(E,m^{\prime})$ where $C\mapsto
E$ is a standard sketch rule, and $m$ and $m^{\prime}$ are memory states in
$M$.

When the current memory state is $m$, only rules of the form
$(m,C)\mapsto(E,m^{\prime})$ apply. If $s$ and $m$ are the current state and
memory, respectively, and $s^{\prime}$ is a state reachable from $s$ such that
the pair $(s,s^{\prime})$ is compatible with the rule $C\mapsto E$, then
moving to state $s^{\prime}$ and setting the memory to $m^{\prime}$ is
compatible with the extended rule $(m,C)\mapsto(E,m^{\prime})$. In displayed
listings, rules $(m,c)\mapsto(E,m^{\prime})$ are written as $m\,\|\,C\mapsto
E\,\|\,m^{\prime}$ to improve readability.

Example 2. Liu et al. (2023) describe a simple policy for solving the class
$\mathcal{Q}_{Hanoi}$ of Towers-of-Hanoi instances with 3 pegs, where a tower
in the first peg is to be moved to the third peg. In this policy, actions
alternate between moving the smallest top disk and moving the second smallest
top disk. When moving the smallest top disk, it is always moved to the “left”,
towards the first peg, except when it is in the first peg that is then moved
to the third peg. In the alternate step, the second smallest top disk is moved
on top of the third smallest top disk, as no other choice is available.

The movements can be expressed in the language of sketches with three Boolean
features $p_{i,j}$, $1\leq i<j\leq 3$, that are true if the top disk at peg
$i$ is smaller than the top disk at peg $j$. For example, the smallest disk is
at the first (resp. third) peg iff $p_{1,2}\land p_{1,3}$ (resp. $\neg
p_{1,3}\land\neg p_{2,3}$) holds.

The alternation of actions is obtained with two memory states $m_{0}$ and
$m_{1}$ of which $m_{0}$ is the initial memory state. The rules implementing
the policy are then:

% Movements of the smallest disk
---
$r_{0}\ =\ m_{0}\,\|\,\\{p_{1,2},p_{1,3}\\}\mapsto\\{p_{1,2}?,\neg
p_{1,3},\neg p_{2,3}\\}\,\|\,m_{1}$
$r_{1}\ =\ m_{0}\,\|\,\\{\neg
p_{1,2},p_{2,3}\\}\mapsto\\{p_{1,2},p_{1,3},p_{2,3}?\\}\,\|\,m_{1}$
$r_{2}\ =\ m_{0}\,\|\,\\{\neg p_{1,3},\neg p_{2,3}\\}\mapsto\\{\neg
p_{1,2},p_{1,3}?,p_{2,3}\\}\,\|\,m_{1}$
% Movements of the second smallest disk
$r_{3}\ =\ m_{1}\,\|\,\\{p_{1,2},p_{1,3},p_{2,3}\\}\mapsto\\{\neg
p_{2,3}\\}\,\|\,m_{0}$
$r_{4}\ =\ m_{1}\,\|\,\\{p_{1,2},p_{1,3},\neg
p_{2,3}\\}\mapsto\\{p_{2,3}\\}\,\|\,m_{0}$
$r_{5}\ =\ m_{1}\,\|\,\\{\neg p_{1,2},p_{1,3},p_{2,3}\\}\mapsto\\{\neg
p_{1,3}\\}\,\|\,m_{0}$
$r_{6}\ =\ m_{1}\,\|\,\\{\neg p_{1,2},\neg
p_{1,3},p_{2,3}\\}\mapsto\\{p_{1,3}\\}\,\|\,m_{0}$
$r_{7}\ =\ m_{1}\,\|\,\\{p_{1,2},\neg p_{1,3},\neg p_{2,3}\\}\mapsto\\{\neg
p_{1,2}\\}\,\|\,m_{0}$
$r_{8}\ =\ m_{1}\,\|\,\\{\neg p_{1,2},\neg p_{1,3},\neg
p_{2,3}\\}\mapsto\\{p_{1,2}\\}\,\|\,m_{0}$

The policy corresponds to the sketch with memory $\langle
M,\Phi,m_{0},R\rangle$ where $M{\,=\,}\\{m_{0},m_{1}\\}$,
$\Phi{\,=\,}\\{p_{i,j}:1\leq i<j\leq 3\\}$, and $R$ is the set of above rules.
Notice that this policy is guaranteed to solve only instances of Towers-of-
Hanoi with 3 pegs where the initial state contains a single tower in the first
peg that is to be moved to the third peg. $\blacksquare$

### Registers, Indexicals, Concepts, and Roles

The second extension introduces internal memory in the form of _registers_.
Registers store objects, which can be referred to in features that become
indexical or parametric, as their value changes when the object in the
register changes; e.g., the number of blocks above the block in register zero.
The objects that can be placed into the registers
$\mathfrak{R}=\\{\mathfrak{r}_{0},\mathfrak{r}_{1},\ldots\\}$ are selected by
two new classes of features called _concepts_ and _roles_ that denote sets of
objects and set of object pairs, respectively (Baader et al. 2003).

Concept features or simply concepts are denoted in sans-serif font such as
‘C’, and in a state $s$, they denote the set of objects in the problem $P$
that satisfy the unary predicate ‘C’. Role features or simply roles are also
denoted in sans-serif font such as ‘R’, and in a state $s$, they denote the
set of object pairs in the problem $P$ that satisfy the binary relation ‘R’.
Concept and role features are also used as numerical features, e.g., as
conditions ‘$\textsf{C}{\,{>}\,}0$’ or effects ‘R$\downarrow$’, with the
understanding that the corresponding numerical feature is given by the
cardinality of the concept C or role R in the state; namely, the number of
objects or object pairs in their denotation.

While a plain feature is a function of the problem state, an indexical or
parametric feature is a function of the problem state and the value of the
registers; like “the distance of the agent to the object stored in
$\mathfrak{r}_{0}$”. When the value of a register $\mathfrak{r}$ changes, the
denotation of indexical features that depend on the value of the register may
change as well. We denote by $\Phi(\mathfrak{r})$ the subset of features in
$\Phi$ that refer to (i.e., depend on the value of) register $\mathfrak{r}$.
The set of features $\Phi$ is assumed to contain a (parametric) concept for
each register $\mathfrak{r}$, whose denotation is the singleton that contains
the object in $\mathfrak{r}$, and that is also denoted by $\mathfrak{r}$.

The extended sketch language provides _load effects_ of the form
$\textit{Load}(\textsf{C},\mathfrak{r})$ for updating the value of registers
for a concept C and register $\mathfrak{r}$; an expression that indicates that
the content of the register $\mathfrak{r}$ is to be set to _any object_ in the
(current) denotation of C, a choice that is _non-deterministic_. Loading an
object into register $\mathfrak{r}$ can be thought as placing the _marker_
$\mathfrak{r}$ on the object. A rule with effect
$\textit{Load}(\textsf{C},\mathfrak{r})$ has the condition
$\textsf{C}{\,{>}\,}0$ to ensure that C contains some object. Likewise, since
a load may change the denotation of features, the effect of a load rule on
register $\mathfrak{r}$ is assumed to contain also the extra effects $\phi?$
for the features $\phi$ in $\Phi(\mathfrak{r})$, and no other effects.
Formally,

######  Definition 2 (Extended Sketch Rules).

An extended rule over the features $\Phi$ and memory $M$ has the form
$(m,C)\mapsto(E,m^{\prime})$ where $m$ and $m^{\prime}$ are memory states, $C$
is a Boolean condition on the features, and either $E$ expresses changes in
the feature values, as usual, or $E$ contains one load effect of the form
$\textit{Load}(\textsf{C},\mathfrak{r})$ for some concept C and register
$\mathfrak{r}$. If the latter case, $E$ must also contain uncertain effects
$\phi?$ on the features $\phi$ in $\Phi(\mathfrak{r})$, but no other effects.

Rules with a load effect are called _internal rules_ , as they capture changes
in the internal memory, while the other rules are called _external._ For
simplicity, it is assumed, that each load rule contains a single load effect,
and that internal and external rules apply in different memory states, from
now called _internal_ and _external_ memory states. For convenience, rules of
the form $(m,C)\mapsto(true,m^{\prime})$, abbreviated as
$(m,C)\mapsto(\\{\\},m^{\prime})$, are allowed to enable a change from memory
state $m$ to memory state $m^{\prime}$ under the condition $C$. Extended
sketches are comprised of extended sketch rules:

######  Definition 3 (Extended Sketch).

An extended sketch is a tuple $\langle M,\mathfrak{R},\Phi,m_{0},R\rangle$
where $M$ and $\mathfrak{R}$ are finite sets of memory states and registers,
respectively, $\Phi$ is a set of features, $m_{0}{\,\in\,}M$ is the initial
memory state, and $R$ is a set of extended $\Phi$-rules over memory $M$. If
$m$ is a memory state, $R(m)$ denote the subset of rules in $R$ of form
$(m,C)\mapsto(E,m^{\prime})$.

Extended sketches are also called indexical sketches, and those of width 0 are
called extended or indexical policies.

Example 3. A different, indexical, policy $\pi_{\textit{on}}^{*}$ for the
class $\mathcal{Q}_{on}$ of Blocksworld problems considered in Example 1,
where the goal is to achieve the atom $on(x,y)$, is expressed as the sketch
$\langle M,\textsf{R},\Phi,m_{0},R\rangle$ where
$M{\,=\,}\\{m_{i}{\,:\,}0{\,\leq\,}i{\,\leq\,}8\\}$ has 9 memory states, and
$\textsf{R}{\,=\,}\\{\mathfrak{r}_{0},\mathfrak{r}_{1}\\}$ has two registers.
The set of features is
$\Phi{\,=\,}\\{\textit{On},H,H_{x},A,\textsf{N},\textsf{T}_{0},\textsf{T}_{1}\\}$
where On, $H$ and $H_{x}$ are as in Example 1, $A$ is true if the block in
$\mathfrak{r}_{1}$ is above $x$ or $y$, N is the subset of blocks in
$\\{x,y\\}$ that are _not clear,_ and the concept $\textsf{T}_{0}$ (resp.
$\textsf{T}_{1}$) contains the block, if any, that is directly above the block
in $\mathfrak{r}_{0}$ (resp. $\mathfrak{r}_{1}$). The set $R$ has the
following 14 rules:

% Internal rules (update registers and internal memory)
---
% Initial border case when holding some block: apply rule $r_{8}$
$r_{0}\ =\ m_{0}\,\|\,\\{H\\}\mapsto\\{\\}\,\|\,m_{4}$
% Blocks $x$ and $y$ already clear: apply rule $r_{12}$
$r_{1}\ =\ m_{0}\,\|\,\\{\neg
H,\textsf{N}{\,{=}\,}0\\}\mapsto\\{\\}\,\|\,m_{7}$
% Place $\mathfrak{r}_{0}$ on some block in N, and $\mathfrak{r}_{1}$ on
topmost above $\mathfrak{r}_{0}$
$r_{2}\ =\ m_{0}\,\|\,\\{\neg
H,\textsf{N}{\,{>}\,}0\\}\mapsto\\{\textit{Load}(\textsf{N},\mathfrak{r}_{0}),\textsf{T}_{0}?\\}\,\|\,m_{1}$
$r_{3}\ =\
m_{1}\,\|\,\\{\textsf{T}_{0}{\,{>}\,}0\\}\mapsto\\{\textit{Load}(\textsf{T}_{0},\mathfrak{r}_{1}),\textsf{T}_{1}?,A?\\}\,\|\,m_{2}$
$r_{4}\ =\
m_{2}\,\|\,\\{\textsf{T}_{1}{\,{>}\,}0\\}\mapsto\\{\textit{Load}(\textsf{T}_{1},\mathfrak{r}_{1}),\textsf{T}_{1}?,A?\\}\,\|\,m_{2}$
$r_{5}\ =\ m_{2}\,\|\,\\{\textsf{T}_{1}{\,{=}\,}0\\}\mapsto\\{\\}\,\|\,m_{5}$
% Iterate over next block above $\mathfrak{r}_{0}$, or next block in N
$r_{6}\ =\ m_{3}\,\|\,\\{\textsf{T}_{0}{\,{>}\,}0\\}\mapsto\\{\\}\,\|\,m_{1}$
$r_{7}\ =\ m_{3}\,\|\,\\{\textsf{T}_{0}{\,{=}\,}0\\}\mapsto\\{\\}\,\|\,m_{0}$
% External rules (involve state transitions)
% Handle initial border case: drop block being held
$r_{8}\ =\ m_{4}\,\|\,\\{H\\}\mapsto\\{\neg H,\neg
H_{x},\textit{On}?,A?,\textsf{N}?,\textsf{T}_{0}?,\textsf{T}_{1}?\\}\,\|\,m_{0}$
% Pick block $\mathfrak{r}_{1}$ (topmost above $\mathfrak{r}_{0}$) and put it
away
$r_{9}\ =\ m_{5}\,\|\,\\{\neg H,A\\}\mapsto\\{H,\neg
A,\textsf{N}?,\textsf{T}_{0}?\\}\,\|\,m_{6}$
$r_{10}\ =\ m_{6}\,\|\,\\{H,\neg A\\}\mapsto\\{\neg H\\}\,\|\,m_{3}$
$r_{11}\ =\ m_{6}\,\|\,\\{H,\neg A\\}\mapsto\\{\neg
H,\textsf{N}\raisebox{0.6458pt}{$\downarrow$}\\}\,\|\,m_{3}$
% Pick up block $x$ and place on block $y$
$r_{12}\ =\ m_{7}\,\|\,\\{\neg
H_{x}\\}\mapsto\\{H,H_{x},\textsf{N}?\\}\,\|\,m_{8}$
$r_{13}\ =\ m_{8}\,\|\,\\{H_{x},\neg\textit{On}\\}\mapsto\\{\neg H,\neg
H_{x},\textit{On}\\}\,\|\,m_{8}$

The policy $\pi_{\textit{on}}^{*}$ is _indexical_ (Agre and Chapman 1990;
Ballard et al. 1996), as it puts the _“mark”_ $\mathfrak{r}_{0}$ on a block in
N (rule $r_{2}$), while a second _mark_ $\mathfrak{r}_{1}$ is moved up from
the block on $\mathfrak{r}_{0}$ to the topmost block above $\mathfrak{r}_{0}$
(rules $r_{3}$–$r_{5}$). The block marked as $\mathfrak{r}_{1}$ is then picked
and put away (rules $r_{9}$–$r_{11}$), and the process repeats (loop on rules
$r_{6},r_{3},r_{4}^{+},r_{5},r_{9},r_{10},r_{6}$) until the block in
$\mathfrak{r}_{0}$ becomes clear. Then, another block in N, if any, is loaded
into $\mathfrak{r}_{0}$ (rules $r_{7},r_{2}$). Once $x$ and $y$ become clear
(i.e., $\textsf{N}{\,{=}\,}0$), the block $x$ is picked and placed on $y$
(rules $r_{1}$, $r_{12}$ and $r_{13}$). The rule $r_{0}$ handles the special
case when initially some block is being held.

The new policy, unlike the one in Example 1, does not use features for
counting blocks. The features used are indeed computationally simpler as they
refer to “markers” (i.e., registers that store or mark specific objects) that
_fix the attention_ on specific blocks, something which non-indexical features
cannot do. Figure 1 illustrates the use of markers on a tower of 4 blocks
where $x$ is at the bottom. $\blacksquare$

$b_{3}$$b_{2}$$b_{1}$$x$(a)$\mathfrak{r}_{0}$$b_{3}$$b_{2}$$b_{1}$$x$(b)$\mathfrak{r}_{0}$$\mathfrak{r}_{1}$$b_{3}$$b_{2}$$b_{1}$$x$(c)$\mathfrak{r}_{0}$$\mathfrak{r}_{1}$$b_{3}$$b_{2}$$b_{1}$$x$(d)$\mathfrak{r}_{0}$$\mathfrak{r}_{1}$
Figure 1: Policy $\pi_{\textit{on}}^{*}$ places markers $\mathfrak{r}_{0}$ and
$\mathfrak{r}_{1}$ on blocks $x$ and $b_{3}$, respectively, for an example
tower with 4 blocks. (a) The rule $r_{2}$ puts the marker $\mathfrak{r}_{0}$
on the block $x{\,\in\,}\textsf{N}$; side effect is
$\textsf{T}_{0}{\,=\,}\\{b_{1}\\}$. (b) Rule $r_{3}$ initializes marker
$\mathfrak{r}_{1}$ on block $b_{1}{\,\in\,}\textsf{T}_{0}$; side effect is
$\textsf{T}_{1}{\,=\,}\\{b_{2}\\}$. (c) Rule $r_{4}$ moves marker
$\mathfrak{r}_{1}$ one step above to block $b_{2}{\,\in\,}\textsf{T}_{1}$;
side effect is $\textsf{T}_{1}{\,=\,}\\{b_{3}\\}$. (d) Another application of
$r_{4}$ moves $\mathfrak{r}_{1}$ on block $b_{3}{\,\in\,}\textsf{T}_{1}$; side
effect is $\textsf{T}_{1}{\,=\,}\emptyset$, and $r_{5}$ is the next rule to
apply.

## Formal Semantics and Termination

Extended sketches are evaluated on planning states augmented with memory
states and register values.

######  Definition 4 (Augmented states).

An augmented state for a problem $P$ given an extended sketch $\langle
M,\mathfrak{R},\Phi,m_{0},R\rangle$ is a tuple $\bar{s}=(s,m,\boldsymbol{v})$
where $s$ is a reachable state in $P$, $m$ is a memory state in $M$, and
$\boldsymbol{v}$ is a vector of objects in $\text{Obj}(P)^{\mathfrak{R}}$ that
tells the content of each register $\mathfrak{r}$, denoted as
$\boldsymbol{v}[\mathfrak{r}]$.

Features $\phi$ are evaluated over pairs $(s,\boldsymbol{v})$ made up of a
state $s$ and a value $\boldsymbol{v}$ for the registers. The value for $\phi$
at such a pair is denoted by $\phi(s,\boldsymbol{v})$.

######  Definition 5 (Compatible pairs).

Let $r$ be an external $\Phi$-rule $(m,C)\mapsto(E,m^{\prime})$, and let
$\boldsymbol{v}$ be a valuation for the registers. A state $s$ satisfies the
condition $C$ given $\boldsymbol{v}$ if the feature conditions in $C$ are all
true in $(s,\boldsymbol{v})$. A state pair $(s,s^{\prime})$ satisfies the
effect $E$ given $\boldsymbol{v}$ if the values for the features in $\Phi$
change from $s$ to $s^{\prime}$ according to $E$; i.e., the following holds
where $p$ is a Boolean feature, $n$ is a numerical, concept or role feature,
and $\phi$ is any type of feature,

  1. 1.

if $p$ (resp. $\neg p$) is in $E$, $p(s^{\prime},\boldsymbol{v})=1$ (resp.
$p(s^{\prime},\boldsymbol{v})=0$),

  2. 2.

if $n\raisebox{0.6458pt}{$\downarrow$}$ (resp.
$n\raisebox{0.6458pt}{$\uparrow$}$) is in $E$,
$n(s,\boldsymbol{v}){\,>\,}n(s^{\prime},\boldsymbol{v})$ (resp.
$n(s,\boldsymbol{v}){\,<\,}n(s^{\prime},\boldsymbol{v})$), and

  3. 3.

if $\phi$ is not mentioned in $E$,
$\phi(s,\boldsymbol{v})=\phi(s^{\prime},\boldsymbol{v})$.

The pair $(s,s^{\prime})$ is compatible with an external rule
$r=(m,C)\mapsto(E,m^{\prime})$ given $\boldsymbol{v}$, denoted as
$s^{\prime}\prec_{r/\boldsymbol{v}}s$, if given $\boldsymbol{v}$, $s$
satisfies $C$ and the pair satisfies $E$. The pair is compatible with a set of
rules $R$ given $\boldsymbol{v}$, denoted as
$s^{\prime}\prec_{R/\boldsymbol{v}}s$, if it is compatible with some external
rule in $R$ given $\boldsymbol{v}$.

The search algorithm for extended sketches, called $\text{SIW}^{*}_{\text{R}}$
and shown in Alg. 2, maintains the current memory state and register values,
implements the internal rules, and performs IW searches to solve the
subproblems that arise when the memory state are external.

######  Definition 6 (Subproblems).

If $\bar{s}=(s,m,\boldsymbol{v})$ is an augmented state for $P$, where $m$ is
external memory, the subproblem $P[\bar{s}]$ induced by $\bar{s}$ in $P$ is a
planning problem which is like $P$ but with initial state $s$, and goal states
that are either goal states of $P$, or states $s^{\prime}$ such that
$s^{\prime}\prec_{r/\boldsymbol{v}}s$ for some rule $r$ in $R(m)$.

Internal rules do not generate classical subproblems and do not change the
planning state $s$ but they affect the memory state and the register values,
and with that, the definition of the subproblems that follow. The notion of
reduction captures how internal rules are processed:

######  Definition 7 (Reduction).

Let $\langle M,\mathfrak{R},\Phi,m_{0},R\rangle$ be an extended sketch for a
planning problem $P$, and let $(s,m,\boldsymbol{v})$ be an augmented state for
$P$ where $m$ is an internal memory state in $M$. The pair
$\langle(s,m,\boldsymbol{v}),(s,m^{\prime},\boldsymbol{v}^{\prime})\rangle$ is
a reduction step if there is a rule $r$ in $R$ of form
$(m,C)\mapsto(E,m^{\prime})$ such that 1) $s$ satisfies the condition $C$
given $\boldsymbol{v}$, and 2) either $E$ is a dummy true effect and
$\boldsymbol{v}^{\prime}=\boldsymbol{v}$, or $E$ contains
$\textit{Load}(\textsf{C},\mathfrak{r})$, and
$\boldsymbol{v}^{\prime}[\mathfrak{r}]\in\textsf{C}(s,\boldsymbol{v})$. A
sequence of reduction steps starting at $(s,m,\boldsymbol{v})$ and ending at
$(s,m^{\prime},\boldsymbol{v}^{\prime})$ where $m^{\prime}$ is external is
called a reduction, and it is denoted by
$(s,m,\boldsymbol{v})\rightarrow^{*}(s,m^{\prime},\boldsymbol{v}^{\prime})$.
For convenience, if $m$ is external, the triplet $(s,m,\boldsymbol{v})$ is
assumed to reduce to itself, written
$(s,m,\boldsymbol{v})\rightarrow^{*}(s,m,\boldsymbol{v})$.

An initial augmented state for problem $P$ is of the form
$(s_{0},m,\boldsymbol{v})$ where $s_{0}$ is the initial state in $P$, and
$(s_{0},m_{0},\boldsymbol{v}_{0})\rightarrow^{*}(s_{0},m,\boldsymbol{v})$ for
the initial memory $m_{0}$ and some $\boldsymbol{v}_{0}$ in
$\text{Obj}(P)^{\mathfrak{R}}$. There may be different initial augmented
states for $P$ that differ in their memory and/or the contents of the
registers. Each such initial augmented state defines an initial subproblem
$P[s_{0},m,\boldsymbol{v}]$ (cf. Definition 6).

######  Definition 8 (Induced subproblems).

Let $\langle M,\mathfrak{R},\Phi,m_{0},R\rangle$ be an extended sketch for a
planning problem $P$ with initial state $s_{0}$. Let us consider a subproblem
$P[\bar{s}]$ for $\bar{s}=(s,m,\boldsymbol{v})$ where $m$ is external, and let
$s^{\prime}$ be a state reachable from $s$ with
$s^{\prime}\prec_{r/\boldsymbol{v}}s$ for some rule $r$ in $R(m)$. Then,

  1. 1.

subproblem $P[s^{\prime},m^{\prime},\boldsymbol{v}]$ is induced by subproblem
$P[\bar{s}]$ if $r=(m,C)\mapsto(E,m^{\prime})$ and $m^{\prime}$ is external
memory.

  2. 2.

Subproblem $P[s^{\prime},m^{\prime\prime},\boldsymbol{v}^{\prime}]$ is induced
by subproblem $P[\bar{s}]$ if $r\,{=}\,(m,C)\,{\mapsto}\,(E,m^{\prime})$,
$m^{\prime}$ is internal memory, and
$(s^{\prime},m^{\prime},\boldsymbol{v})\rightarrow^{*}(s^{\prime},m^{\prime\prime},\boldsymbol{v}^{\prime})$.

The collection $P^{\circ}$ of induced subproblems is the smallest set such
that 1) $P^{\circ}$ contains all the initial subproblems, and 2)
$P[s^{\prime},m^{\prime},\boldsymbol{v}^{\prime}]$ is in $P^{\circ}$ if
$P[s,m,\boldsymbol{v}]$ is in $P^{\circ}$ and the first subproblem is induced
by the second.

In this definition, subproblems $P[s,m,v]$ where $m$ is internal are “jumped
over” so that the subproblems that make it into $P^{\circ}$ all have memory
states $m$ that are external, and hence represent classical planning problems
and not bookkeeping operations. The extended sketch $R$ is said to be
reducible in $P$ if for any reachable augmented state $(s,m,\boldsymbol{v})$
in $P$ where $m$ is an internal state, there is an augmented state
$(s,m^{\prime},\boldsymbol{v}^{\prime})$ such that
$(s,m,\boldsymbol{v})\rightarrow^{*}(s,m^{\prime},\boldsymbol{v}^{\prime})$. A
non-reducible sketch is one in which the executions can cycle or get stuck
while performing internal memory operations.

######  Definition 9 (Sketch width).

The width of a reducible sketch $R$ over a planning problem $P$ is bounded by
non-negative integer $k$, denoted by $w_{R}(P)\leq k$, if the width of each
subproblem in $P^{\circ}$ is bounded by $k$. The width of a reducible sketch
$R$ over a class of problems $\mathcal{Q}$ is bounded by $k$, denoted by
$w_{R}(\mathcal{Q})\leq k$, if $w_{R}(P)\leq k$ for each $P$ in $\mathcal{Q}$.

The width is zero for the indexical sketch $\pi_{\textit{on}}^{*}$ in Example
3, as the sketch represents a policy where each subproblem is solved in a
single step.

### Termination for Extended Sketches

Termination is a key property for sketches that guarantees acyclicity, and
that only a polynomial number of subproblems may appear when solving _any_
problem $P$ where the features are well defined (Bonet and Geffner 2023).
Termination can be tested in polynomial time by a suitable adaptation of the
Sieve algorithm (Srivastava et al. 2011; Bonet and Geffner 2023). If the
extended sketch is reducible, terminating, and has bounded serialized width
over a class $\mathcal{Q}$, any problem $P$ in $\mathcal{Q}$ can be solved in
polynomial time with the procedure $\text{SIW}^{*}_{\text{R}}$ shown in Alg.
2.

1:Input: Extended sketch $\langle M,\mathfrak{R},\Phi,m_{0},R\rangle$

2:Input: Planning problem $P$ with initial state $s_{0}$ on which the features
in $\Phi$ are well defined

3:$\bar{s}\leftarrow(s_{0},m_{0},\boldsymbol{v})$ for some
$\boldsymbol{v}\in\text{Obj}(P)^{\mathfrak{R}}$

4:while $s$ in $\bar{s}=(s,m,\boldsymbol{v})$ is not a goal state of $P$

5: if $m$ is internal memory

6: Find rule $r=(m,C)\mapsto(E,m^{\prime})$ with $s,\boldsymbol{v}\vDash C$

7: if $r$ is not found, return FAILURE % Irreducible

8: if $\textit{Load}(\textsf{C},\mathfrak{r})$ in $E$,
$\boldsymbol{v}[\mathfrak{r}]\leftarrow o$ for some
$o\in\textsf{C}(s,\boldsymbol{v})$

9: $\bar{s}\leftarrow(s,m^{\prime},\boldsymbol{v})$

10: else % $m$ is external, solve subproblem

11: Run IW search from $s$ to find goal state $s^{\prime}$ of $P$, or

12: state $s^{\prime}$ such that $s^{\prime}\prec_{r/\boldsymbol{v}}s$ for
some (external)

13: rule $r=(m,C)\mapsto(E,m^{\prime})$ in $R$

14: if no such state is found, return FAILURE

15: $\bar{s}\leftarrow(s^{\prime},m^{\prime},\boldsymbol{v})$

16:return path from $s_{0}$ to the goal state $s$

Algorithm 2 $\text{SIW}^{*}_{\text{R}}$ uses the extended sketch $R$ to
decompose problem $P$ into subproblems that are solved with IW. Completeness
of $\text{SIW}^{*}_{\text{R}}$ is captured in Theorem 10.

######  Theorem 10 (Termination).

If the extended sketch $R$ is reducible, terminating, and has a serialized
width bounded by $k$ over the class of problems $\mathcal{Q}$, then
$\text{SIW}^{*}_{\text{R}}$ finds plans for any problem $P$ in $\mathcal{Q}$
in polynomial time.

## Reusable Modules

Policies and sketches are wrapped into _modules_ to enable calls among them. A
module is a named tuple
$\langle\text{args},Z,M,\mathfrak{R},\Phi,m_{0},R\rangle$ where
$\text{args}=\langle x_{1},x_{2},\ldots,x_{n}\rangle$ is a tuple of arguments,
each one being either a _static concept or role_ , $Z$ and $\Phi$ are sets of
features, $M$ is a set of memory states, $\mathfrak{R}$ is a set of registers,
$m_{0}\in M$ is the initial memory state, and $R$ is a set of rules. The
features in $\Phi$ are the ones mentioned in the sketch rules in $R$, and
their denotation may depend on the value of the arguments and the features in
$Z$, and the contents of the registers. The sketch $R$ in a module may also
contain two new types of _external_ rules, _call rules_ and _do rules_. The
first type permits to call other modules; the second type permits the _direct
execution of ground actions of the planning problem_. The value for the
arguments in either case is given by the features in $\Phi$ or $Z$, and the
arguments of the module; the difference between $\Phi$ and $Z$ is that the
rules in $R$ must track the changes for the features in $\Phi$, while $Z$ can
be used to define features in $\Phi$, appear in conditions of rules, and
provide values to arguments in call and do rules. If the name of the module is
name, a _call_ to the module is expressed as
$\texttt{name}(x_{1},x_{2},\ldots,x_{n})$ where $x_{1},\ldots,x_{n}$ are the
module arguments.

Call and do _rules_ are of the form
$(m,C)\mapsto(\texttt{name}(v_{1},v_{2},\ldots,v_{n}),m^{\prime})$ where $m$
is internal memory, $C$ is a condition, name is a module or action schema
name, and each value $v_{i}$ is of an appropriate type: for _do rules_ ,
$v_{i}$ must be a concept, while for _call rules_ , $v_{i}$ can be either a
concept or a role. The idea is that if a _call rule_ is used, the sketch
associated with the module name is executed until no rules are applicable, and
the control is then returned back to the caller at the memory state
$m^{\prime}$. For _do rules_ , an applicable ground action of the form
$\texttt{name}(o_{1},o_{2},\ldots,o_{n})$, where the object $o_{i}$ belongs to
the denotation of concept $v_{i}$, must be applied at the current state to
make a transition to a successor state, and control is then returned back to
the caller at the memory state $m^{\prime}$.

The execution model for handling modules involves a stack as described below.
Modules call each other by passing arguments but do not get back any values.
The “side effects” of a module are in the problem state $s$ that must be
driven eventually to a goal state.

Example 4. Module $\texttt{on}(\textsf{X},\textsf{Y})$ for a policy for the
class $\mathcal{Q}_{on}$ that implements a variant of the policy
$\pi_{\textit{on}}^{*}$ in Example 3. Indeed, _by directly executing ground
actions_ , the policy uses simpler features and can be executed model-free:
there is no need to generate the possible successors for choosing the ground
action to do. This is directly encoded in the policy. For example, the
indexical Boolean feature $A$ is no longer needed because the block being held
is put away on the table with a Putdown action.

The module $\texttt{on}(\textsf{X},\textsf{Y})$ has as parameters the concepts
X and Y that are assumed to be singletons containing the blocks $x$ and $y$,
respectively. The module uses _do rules_ to avoid references to complex
concepts; it only uses the concepts B for all blocks, N for the blocks in
$\textsf{X}\cup\textsf{Y}$ that are not clear, and the indexical concept
$\textsf{T}_{0}$ (resp. $\textsf{T}_{1}$) for the block directly above
$\mathfrak{r}_{0}$ (resp. $\mathfrak{r}_{1}$), if any. The other feature is
the Boolean $T_{\textsf{x}}$ that is true iff X is on the table. The module
uses 9 memory states, two registers, and the following rules:

% Internal rules (update registers and internal memory)
---
$r_{0}\ =\ m_{0}\,\|\,\\{H\\}\mapsto\\{\\}\,\|\,m_{4}$
$r_{1}\ =\ m_{0}\,\|\,\\{\neg
H,\textsf{N}{\,{=}\,}0\\}\mapsto\\{\\}\,\|\,m_{7}$
$r_{2}\ =\ m_{0}\,\|\,\\{\neg
H,\textsf{N}{\,{>}\,}0\\}\mapsto\\{\textit{Load}(\textsf{N},\mathfrak{r}_{0}),\textsf{T}_{0}?\\}\,\|\,m_{1}$
$r_{3}\ =\
m_{1}\,\|\,\\{\textsf{T}_{0}{\,{>}\,}0\\}\mapsto\\{\textit{Load}(\textsf{T}_{0},\mathfrak{r}_{1}),\textsf{T}_{1}?\\}\,\|\,m_{2}$
$r_{4}\ =\
m_{2}\,\|\,\\{\textsf{T}_{1}{\,{>}\,}0\\}\mapsto\\{\textit{Load}(\textsf{T}_{1},\mathfrak{r}_{1}),\textsf{T}_{1}?\\}\,\|\,m_{2}$
$r_{5}\ =\ m_{2}\,\|\,\\{\textsf{T}_{1}{\,{=}\,}0\\}\mapsto\\{\\}\,\|\,m_{5}$
$r_{6}\ =\ m_{3}\,\|\,\\{\textsf{T}_{0}{\,{>}\,}0\\}\mapsto\\{\\}\,\|\,m_{1}$
$r_{7}\ =\ m_{3}\,\|\,\\{\textsf{T}_{0}{\,{=}\,}0\\}\mapsto\\{\\}\,\|\,m_{0}$
% External rules (involve state transitions)
$r_{8}\ =\ m_{4}\,\|\,\\{\\}\mapsto\texttt{Putdown}(\textsf{B})\,\|\,m_{0}$
$r_{9}\ =\
m_{5}\,\|\,\\{\\}\mapsto\texttt{Unstack}(\mathfrak{r}_{1},\textsf{B})\,\|\,m_{6}$
$r_{10}\ =\
m_{6}\,\|\,\\{\\}\mapsto\texttt{Putdown}(\mathfrak{r}_{1})\,\|\,m_{3}$
$r_{11}\ =\
m_{7}\,\|\,\\{T_{\textsf{x}}\\}\mapsto\texttt{Pickup}(\textsf{X})\,\|\,m_{8}$
$r_{12}\ =\ m_{7}\,\|\,\\{\neg
T_{\textsf{x}}\\}\mapsto\texttt{Unstack}(\textsf{X},\textsf{B})\,\|\,m_{8}$
$r_{13}\ =\
m_{8}\,\|\,\\{\\}\mapsto\texttt{Stack}(\textsf{X},\textsf{Y})\,\|\,m_{8}$

Rules $r_{0}$–$r_{7}$ are like the ones for the indexical policy
$\pi_{\textit{on}}^{*}$. The external rules, however, are do-rules that apply
ground actions to remove blocks above $\mathfrak{r}_{0}$, and to pick X and
put it on Y. The Boolean $T_{\textsf{x}}$ is used to decide whether to use a
Pickup or Unstack action to grab X. $\blacksquare$

Example 5. The module $\texttt{tower}(\textsf{O},\textsf{X})$ is aimed at the
class $\mathcal{Q}_{tower}$ of problems where blocks are to be stacked into a
_single tower_ resting on the table. The goal of such a problem is described
by a conjunction of atoms $\wedge_{i=1}^{k}on(x_{i},x_{i-1})$ and
$ontable(x_{0})$. The module is the tuple
$\langle\langle\textsf{O},\textsf{X}\rangle,Z,M,\mathfrak{R},\Phi,m_{0},R\rangle$
where O is a role argument whose denotation contains the pairs
$\\{(x_{i},x_{i-1}):i=1,...,k\\}$, and X is a concept argument that denotes
the lowest block in the target tower that is misplaced.333Block $x$ is _well-
placed_ in state $s$ iff $on(x,y)$ holds in $s$ when $(x,y)$ is in O, and
recursively $y$ is well-placed; it is _misplaced_ iff it is not well-placed.
In the example, it is also assumed that the lowest block of the target tower
must be placed on the table.  The other elements in the module are
$Z{\,=\,}\emptyset$, $M{\,=\,}\\{m_{0},m_{1},\ldots,m_{3}\\}$,
$\mathfrak{R}{\,=\,}\\{\mathfrak{r}_{0}\\}$, and a set of features
$\Phi=\\{\textsf{M},\textsf{W}\\}$ where M is the indexical concept that
contains the block to be placed above the block in $\mathfrak{r}_{0}$
according to O, if any, and, W is the indexical concept that contains the
block directly below the block in $\mathfrak{r}_{0}$, if any, also according
to the target tower O. The rules are:

% Module $\texttt{tower}(\textsf{O},\textsf{X})$
---
$r_{0}\ =\
m_{0}\,\|\,\\{\textsf{X}{\,{>}\,}0\\}\mapsto\\{\textit{Load}(\textsf{X},\mathfrak{r}_{0}),\textsf{M}?,\textsf{W}?\\}\,\|\,m_{1}$
$r_{1}\ =\ m_{1}\,\|\,\\{\textsf{W}{\,{=}\,}0\\}\mapsto\texttt{on-
table}(\mathfrak{r}_{0})\,\|\,m_{2}$
$r_{2}\ =\
m_{1}\,\|\,\\{\textsf{W}{\,{>}\,}0\\}\mapsto\texttt{on}(\mathfrak{r}_{0},\textsf{W})\,\|\,m_{2}$
$r_{3}\ =\
m_{2}\,\|\,\\{\textsf{M}{\,{>}\,}0\\}\mapsto\texttt{tower}(\textsf{O},\textsf{M})\,\|\,m_{3}$

The rule $r_{0}$ puts the lowest misplaced block in $\mathfrak{r}_{0}$,
$r_{1}$ calls the module $\texttt{on-table}(\mathfrak{r}_{0})$ to place
$\mathfrak{r}_{0}$ on the table, $r_{2}$ calls the module on to place
$\mathfrak{r}_{0}$ on W, and $r_{3}$ recursively calls the module with the
block that is supposed to be on $\mathfrak{r}_{0}$. The module $\texttt{on-
table}(\textsf{X})$, that puts the block in the singleton X on the table, is
not spelled out. $\blacksquare$

Example 6. The module $\texttt{blocks}(\textsf{O})$ solves arbitrary instances
of Blocksworld. It works by calling the module
$\texttt{tower}(\textsf{O},\textsf{X})$ with the parameter X being the
singleton that contains the _lowest misplaced block_ in one of the current
towers. The module takes a single role argument O whose denotation encodes the
pairs $(x,y)$ corresponding to the goal atoms $on(x,y)$ as in Example 5. The
module is the tuple
$\langle\langle\textsf{O}\rangle,Z,M,\mathfrak{R},\Phi,m_{0},R\rangle$ where
$Z=\emptyset$, $M=\\{m_{0},m_{1}\\}$, $\mathfrak{R}=\\{r_{0}\\}$, and
$\Phi=\\{\textsf{L}\\}$, where L contains the lowest misplaced blocks
according to the pairs in O. The set $R$ contains only 2 rules:

% Module $\texttt{blocks}(\textsf{O})$
---
$r_{0}\ =\
m_{0}\,\|\,\\{\textsf{L}{\,{>}\,}0\\}\mapsto\\{\textit{Load}(\textsf{L},\mathfrak{r}_{0})\\}\,\|\,m_{1}$
$r_{1}\ =\
m_{1}\,\|\,\\{\\}\mapsto\texttt{tower}(\textsf{O},\mathfrak{r}_{0})\,\|\,m_{0}$

The concept L is a high-complexity concept, meaning that computing its
denotation at the current state is non-trivial. However, L can be removed as
follows. First, a new marker $\mathfrak{r}$ is put on a block $x$ such that
the atoms $on_{G}(x,y)$ and $on(x,y^{\prime})$, with $y\neq y^{\prime}$, hold
at the current state $s$; i.e., $\mathfrak{r}$ is put on a misplaced block
$x$. Second, move the marker $\mathfrak{r}$ to $y$ if $y$ is also misplaced,
and keep moving it down until the marked block is on a well-placed block. At
this moment, the marked block is a lowest misplaced block. $\blacksquare$

### Execution Model: $\text{SIW}_{\text{M}}$

The execution model for modules is captured by the $\text{SIW}_{\text{M}}$
algorithm in Alg. 3 which uses a stack and a caller/callee protocol, as it is
standard in programming languages. It assumes a collection
$\\{\texttt{mod}_{0},\texttt{mod}_{1},\ldots,\texttt{mod}_{N}\\}$ of modules
where the “entry” module $\texttt{mod}_{0}$ is assumed to take no arguments.
The execution involves solving classical planning subproblems, internal
operations on the registers, calls to other modules, and executions of ground
actions. The modules do not share memory states nor registers, but they all
act on the (external) planning states $s$.

At each time point during execution, there is a single active module
$\texttt{mod}_{\ell}$ that defines the current set of rules, and there is a
current augmented state $(s,m,\boldsymbol{v})$. While no call or do rule is
selected, $\text{SIW}_{\text{M}}$ behaves exactly as
$\text{SIW}^{*}_{\text{R}}$. However, if a call rule
$(m,C)\mapsto(\texttt{mod}_{j}(x_{1},x_{2},\ldots,x_{n}),m^{\prime})$ is
chosen, where $\texttt{mod}_{j}$ refers to
$\langle\text{args},Z,M,\mathfrak{R},\Phi,m_{0},R,\rangle$, the following
instructions are executed:

  1. 1.

Push context $(\ell,\boldsymbol{v},m^{\prime})$ where $\boldsymbol{v}$ is
value for registers,

  2. 2.

Set value of arguments of $\texttt{mod}_{j}$ to those given by $x_{i}$,

  3. 3.

Set memory state to $m_{0}$ (the initial state of $\texttt{mod}_{j}$),

  4. 4.

Set the current set of rules to $R$,

  5. 5.

[Cont. execution of $\texttt{mod}_{j}$ until no rule is applicable], and

  6. 6.

Pop context $(\ell,\boldsymbol{v},m^{\prime})$, set value of registers to
$\boldsymbol{v}$, memory state to $m^{\prime}$, and rules $R$ to those in
$\texttt{mod}_{\ell}$.

If a do rule
$(m,C)\mapsto(\texttt{name}(x_{1},x_{2},\ldots,x_{n}),m^{\prime})$ is chosen,
on the other hand, then an applicable ground action
$\texttt{name}(o_{1},o_{2},\ldots,o_{n})$ at the current state $s$ with the
object $o_{i}$ in $x_{i}$, $1\leq i\leq n$, is applied and the memory state is
set to $m^{\prime}$. If no such ground action exists, an error code is
returned. The implementation of the $\text{SIW}_{\text{M}}$ interpreter and
all extended, indexical policies and sketches, and modules that were discussed
in the paper are available online (Bonet, Drexler, and Geffner 2024).

1:Input: Collection
$\mathcal{M}=\\{\texttt{mod}_{0},\texttt{mod}_{1},\ldots,\texttt{mod}_{N}\\}$
of modules with entry module $\texttt{mod}_{0}$

2:Input: Planning problem $P$ with initial state $s_{0}$ on which the features
in $\Phi$ are well defined

3:Initialize stack

4:Let $\mathfrak{R}^{j}$, $m^{j}_{0}$, and $R^{j}$ be the set of registers,
initial memory, and rules of $\texttt{mod}_{j}$, $j=0,1,\ldots,N$

5:$\ell\leftarrow 0$, $R\leftarrow R^{\ell}$, and
$\bar{s}\leftarrow(s_{0},m^{\ell}_{0},\boldsymbol{v})$ for
$\smash{\boldsymbol{v}\in\text{Obj}(P)^{\mathfrak{R}^{\ell}}}$

6:while $s$ in $\bar{s}=(s,m,\boldsymbol{v})$ is not a goal state of $P$

7: if $m$ is internal memory

8: Find rule $r=(m,C)\mapsto(E,m^{\prime})$ with $s,\boldsymbol{v}\vDash C$

9: if $r$ is not found

10: if stack is empty, return FAILURE % Stalled

11: Pop context $(j,\boldsymbol{v}^{\prime},m^{\prime})$ from stack

12: $\ell\leftarrow j$, $R\leftarrow R^{\ell}$, $m\leftarrow m^{\prime}$ and
$\boldsymbol{v}\leftarrow\boldsymbol{v}^{\prime}$

13: else

14: if $\textit{Load}(\textsf{C},\mathfrak{r})$ in $E$,
$\boldsymbol{v}[\mathfrak{r}]\leftarrow o$ for some
$o\in\textsf{C}(s,\boldsymbol{v})$

15: $\bar{s}\leftarrow(s,m^{\prime},\boldsymbol{v})$

16: else % $m$ is external memory

17: Find call/do rule $r{=}(m,C){\mapsto}(E,m^{\prime})$ with
$s,\boldsymbol{v}\vDash C$

18: if $r=(m,C)\mapsto(\texttt{mod}_{j}(x_{1},x_{2}\ldots,x_{n}),m^{\prime})$

19: Push context $(\ell,\boldsymbol{v},m^{\prime})$ into stack

20: $R\leftarrow R^{j}$, $m\leftarrow m^{j}_{0}$ % Hand control to
$\texttt{mod}_{j}$

21: elsif $r=(m,C)\mapsto(\texttt{name}(x_{1},x_{2}\ldots,x_{n}),m^{\prime})$

22: Find ground action $a=\texttt{name}(o_{1},o_{2},\ldots,o_{n})$ appli-

23: cable at $s$ with $o_{i}\in x_{i}(s,\boldsymbol{v})$, $i=1,2,\ldots,n$

24: if there is no such action, return FAILURE

25: $\bar{s}\leftarrow(s^{\prime},m^{\prime},\boldsymbol{v})$ where
$(s,a,s^{\prime})$ is transition in $P$

26: else % No such rule is found

27: Run IW search from $s$ to find goal state $s^{\prime}$ of $P$, or

28: state $s^{\prime}$ such that $s^{\prime}\prec_{r/\boldsymbol{v}}s$ for
some (external) rule

29: $r=(m,C)\mapsto(E,m^{\prime})$ in $R$

30: if no such state is found, return FAILURE

31: $\bar{s}\leftarrow(s^{\prime},m^{\prime},\boldsymbol{v})$

32:return path from $s_{0}$ to the goal state $s$

Algorithm 3 $\text{SIW}_{\text{M}}$ uses set of modules $M$ (extended
sketches) for solving a problem $P$ via possibly nested calls, execution of
ground actions, and IW searches.

## Discussion

A basic, concrete question about policy reuse in a planning setting is: can a
policy for putting one block on top of another be used for building any given
tower of blocks, and eventually any block configuration? The question is
relevant because it tells us that policies for building given towers and block
configurations do not have to be learned from scratch, but that they can be
learned bottom up, from simpler to complex, one after the other (Ellis et al.
2023). The subtlety is that in order for complex policies to use simpler
policies, the former must pass the right parameters to the latter depending on
the context defined by the top goal and the current state. In this work, we
have developed a language for representing such policies and sketches, and
this form of hierarchical composition.

We have also addressed another source of complexity when learning general
policies and sketches: the complexity of the features involved. We have shown
that indexical features whose values depend on the content of registers that
can be dynamically loaded with objects, can be used to drastically reduce the
complexity of the features needed, in line with the intuition of the so-called
deictic representations, where a constant number of “visual marks” are used to
mark objects so that they can be easily referred to (Chapman 1989; Ballard et
al. 1996; Finney et al. 2013). In our setting, an object can be regarded as
marked with “mark” $\mathfrak{r}$ when the object is loaded into register
$\mathfrak{r}$.

The use of registers and concept features allows for general policies that map
states into ground actions too, even if the set of ground actions change from
instance to instance. This is different than general policies defined as
filters on state transitions (Bonet and Geffner 2018; Francès, Bonet, and
Geffner 2021), which require a model for determining the possible transitions
from a state. Policies that map states into actions are more conventional and
can be applied model-free.

The achieved expressivity is the result of three extensions in the language of
policies and sketches: internal memory states, like in finite state
controllers for sequencing behaviors, indexical concepts and features, whose
denotation depends on the value of registers that can be updated, and modules
that wrap up policies and sketches and allow them to call each other by
passing parameters as a function of the state, the registers, and the goals
(represented in the state).

The language of extended policies and sketches adds an interface for calling
policies and sketches from other policies and sketches, even recursively, as
illustrated in the examples. The resulting language has elements in common
with programming languages and planning programs (Aguas, Celorrio, and Jonsson
2016; Segovia-Aguas, Jiménez, and Jonsson 2019, 2021), but there are key
differences too. In particular, the use of a rich feature language does not
limit policies and sketches to deal with classes of problems with a fixed goal
and the policy and sketch modules do not have to represent full procedures or
policies; they can also represent sketches where “holes” are filled in with
polynomial IW searches when the sketches have bounded width.

Provided with this richer language for policies and sketches, the next step is
learning them from small problem instances, adapting the methods developed for
learning policies and sketches (Francès, Bonet, and Geffner 2021; Drexler,
Seipp, and Geffner 2022). The new, extended language also opens the
possibility of learning hierarchical policies bottom-up by generating and
reusing policies, instead of the more common approach of learning them top-
down (Drexler, Seipp, and Geffner 2023). Finally, the study of theoretical
properties of the modular framework, like acyclicity and termination, is also
important and left for future work.

## Acknowledgments

The research of H. Geffner has been supported by the Alexander von Humboldt
Foundation with funds from the Federal Ministry for Education and Research. It
has also received funding from the European Research Council (ERC), Grant
agreement No. No 885107, and Project TAILOR, Grant agreement No. 952215, under
EU Horizon 2020 research and innovation programme, the Excellence Strategy of
the Federal Government and the NRW Länder, Germany, and the Knut and Alice
Wallenberg (KAW) Foundation under the WASP program.

## References

  * Agre and Chapman (1990) Agre, P. E.; and Chapman, D. 1990.  What are plans for?  _Robotics and Autonomous Systems_ , 6: 17–34.
  * Aguas, Celorrio, and Jonsson (2016) Aguas, J. S.; Celorrio, S. J.; and Jonsson, A. 2016.  Generalized planning with procedural domain control knowledge.  In _Proc. ICAPS_ , 285–293.
  * Baader et al. (2003) Baader, F.; Calvanese, D.; McGuinness, D. L.; Nardi, D.; and Patel-Schneider, P. F., eds. 2003.  _The Description Logic Handbook: Theory, Implementation and Applications_.  Cambridge University Press.
  * Ballard et al. (1996) Ballard, D. H.; Hayhoe, M. M.; Pook, P. K.; and Rao, R. P. N. 1996.  Deictic codes for the embodiment of cognition.  _Behavioral and Brain Sciences_ , 20: 723–742.
  * Bonet, Drexler, and Geffner (2024) Bonet, B.; Drexler, D.; and Geffner, H. 2024.  Code and Data for the Paper titled “On Policy Reuse: An Expressive Language for Representing and Executing General Policies that Call Other Policies”.  https://doi.org/10.5281/zenodo.10814690.
  * Bonet and Geffner (2018) Bonet, B.; and Geffner, H. 2018.  Features, Projections, and Representation Change for Generalized Planning.  In _Proc. IJCAI_ , 4667–4673.
  * Bonet and Geffner (2021) Bonet, B.; and Geffner, H. 2021.  General Policies, Representations, and Planning Width.  In _Proc. AAAI_ , 11764–11773.
  * Bonet and Geffner (2023) Bonet, B.; and Geffner, H. 2023.  General Policies, Subgoal Structure, and Planning Width.  _arXiv preprint arxiv:2311.05490_.
  * Bueno et al. (2019) Bueno, T. P.; de Barros, L. N.; Mauá, D. D.; and Sanner, S. 2019.  Deep Reactive Policies for Planning in Stochastic Nonlinear Domains.  In _Proc. AAAI_ , 7530–7537.
  * Chapman (1989) Chapman, D. 1989.  Penguins can make cake.  _AI magazine_ , 10(4): 45–45.
  * Dietterich (2000) Dietterich, T. G. 2000.  Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition.  _Journal of Artificial Intelligence Research_ , 13: 227–303.
  * Drexler, Seipp, and Geffner (2022) Drexler, D.; Seipp, J.; and Geffner, H. 2022.  Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width.  In _Proc. ICAPS_ , 62–70.
  * Drexler, Seipp, and Geffner (2023) Drexler, D.; Seipp, J.; and Geffner, H. 2023.  Learning Hierarchical Policies by Iteratively Reducing the Width of Sketch Rules.  In _Proc. KR_ , 208–218.
  * Dumancic, Guns, and Cropper (2021) Dumancic, S.; Guns, T.; and Cropper, A. 2021.  Knowledge refactoring for inductive program synthesis.  In _Proc. AAAI_ , 7271–7278.
  * Ellis et al. (2023) Ellis, K.; Wong, L.; Nye, M.; Sable-Meyer, M.; Cary, L.; Anaya Pozo, L.; Hewitt, L.; Solar-Lezama, A.; and Tenenbaum, J. B. 2023.  DreamCoder: growing generalizable, interpretable knowledge with wake–sleep Bayesian program learning.  _Phil. Trans. R. Soc. A_ , 381: 20220050.
  * Fern, Yoon, and Givan (2006) Fern, A.; Yoon, S.; and Givan, R. 2006.  Approximate policy iteration with a policy language bias: Solving relational Markov decision processes.  _Journal of Artificial Intelligence Research_ , 25: 75–118.
  * Finney et al. (2013) Finney, S.; Gardiol, N.; Kaelbling, L. P.; and Oates, T. 2013.  The Thing That We Tried Didn’t Work Very Well : Deictic Representation in Reinforcement Learning.  _CoRR_ , abs/1301.0567.
  * Francès, Bonet, and Geffner (2021) Francès, G.; Bonet, B.; and Geffner, H. 2021.  Learning General Planning Policies from Small Examples Without Supervision.  In _Proc. AAAI_ , 11801–11808.
  * Garg, Bajpai, and Mausam (2020) Garg, S.; Bajpai, A.; and Mausam. 2020.  Generalized Neural Policies for Relational MDPs.  In _Proc. ICML_.
  * Groshev et al. (2018) Groshev, E.; Goldstein, M.; Tamar, A.; Srivastava, S.; and Abbeel, P. 2018.  Learning Generalized Reactive Policies Using Deep Neural Networks.  In _Proc. ICAPS_ , 408–416.
  * Hafner et al. (2022) Hafner, D.; Lee, K.-H.; Fischer, I.; and Abbeel, P. 2022.  Deep hierarchical planning from pixels.  In _Proc. NeurIPS_ , 26091–26104.
  * Illanes and McIlraith (2019) Illanes, L.; and McIlraith, S. A. 2019.  Generalized Planning via Abstraction: Arbitrary Numbers of Objects.  In _Proc. AAAI_ , 7610–7618.
  * Khardon (1999) Khardon, R. 1999.  Learning action strategies for planning domains.  _Artificial Intelligence_ , 113: 125–148.
  * Kulkarni et al. (2016) Kulkarni, T. D.; Narasimhan, K.; Saeedi, A.; and Tenenbaum, J. 2016.  Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation.  In _Proc. NeurIPS_ , 3675–3683.
  * Lipovetzky and Geffner (2012) Lipovetzky, N.; and Geffner, H. 2012.  Width and Serialization of Classical Planning Problems.  In _Proc. ECAI 2012_ , 540–545.
  * Liu et al. (2023) Liu, A.; Xu, H.; Van den Broeck, G.; and Liang, Y. 2023.  Out-of-distribution generalization by neural-symbolic joint training.  In _Proc. AAAI_ , 12252–12259.
  * Machado, Bellemare, and Bowling (2017) Machado, M. C.; Bellemare, M. G.; and Bowling, M. 2017.  A Laplacian Framework for Option Discovery in Reinforcement Learning.  In _Proc. ICML_ , 2295–2304.
  * Martín and Geffner (2004) Martín, M.; and Geffner, H. 2004.  Learning Generalized Policies from Planning Examples Using Concept Languages.  _Applied Intelligence_ , 20(1): 9–19.
  * McGovern and Barto (2001) McGovern, A.; and Barto, A. G. 2001.  Automatic Discovery of Subgoals in Reinforcement Learning using Diverse Density.  In _Proc. ICML_ , 361–368.
  * Parr and Russell (1997) Parr, R.; and Russell, S. 1997.  Reinforcement Learning with Hierarchies of Machines.  In _Proc. NeurIPS_ , 1043–1049.
  * Rivlin, Hazan, and Karpas (2020) Rivlin, O.; Hazan, T.; and Karpas, E. 2020.  Generalized Planning With Deep Reinforcement Learning.  In _ICAPS Workshop PRL_ , 16–24.
  * Segovia-Aguas, Jiménez, and Jonsson (2019) Segovia-Aguas, J.; Jiménez, S.; and Jonsson, A. 2019.  Computing programs for generalized planning using a classical planner.  _Artificial Intelligence_ , 272: 52–85.
  * Segovia-Aguas, Jiménez, and Jonsson (2021) Segovia-Aguas, J.; Jiménez, S.; and Jonsson, A. 2021.  Generalized planning as heuristic search.  In _ICAPS_ , 569–577.
  * Srivastava, Immerman, and Zilberstein (2011) Srivastava, S.; Immerman, N.; and Zilberstein, S. 2011.  A new representation and associated algorithms for generalized planning.  _Artificial Intelligence_ , 175(2): 393–401.
  * Srivastava et al. (2011) Srivastava, S.; Zilberstein, S.; Immerman, N.; and Geffner, H. 2011.  Qualitative Numeric Planning.  In _Proc. AAAI 2011_ , 1010–1016.
  * Ståhlberg, Bonet, and Geffner (2022a) Ståhlberg, S.; Bonet, B.; and Geffner, H. 2022a.  Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits.  In _Proc. ICAPS_ , 629–637.
  * Ståhlberg, Bonet, and Geffner (2022b) Ståhlberg, S.; Bonet, B.; and Geffner, H. 2022b.  Learning Generalized Policies without Supervision Using GNNs.  In _Proc. KR_ , 474–483.
  * Ståhlberg, Bonet, and Geffner (2023) Ståhlberg, S.; Bonet, B.; and Geffner, H. 2023.  Learning General Policies with Policy Gradient Methods.  In _Proc. KR_ , 647–657.
  * Sutton, Precup, and Singh (1999) Sutton, R. S.; Precup, D.; and Singh, S. 1999.  Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning.  _Artificial Intelligence_ , 112: 181–211.
  * Toyer et al. (2020) Toyer, S.; Thiébaux, S.; Trevizan, F.; and Xie, L. 2020.  ASNets: Deep Learning for Generalised Planning.  _Journal of Artificial Intelligence Research_ , 68: 1–68.