# Predicate Invention for Bilevel Planning

Tom Silver1, Rohan Chitnis2, Nishanth Kumar1, Willie McClinton1,
Tomás Lozano-Pérez1, Leslie Pack Kaelbling1, Joshua B. Tenenbaum1

###### Abstract

Efficient planning in continuous state and action spaces is fundamentally
hard, even when the transition model is deterministic and known. One way to
alleviate this challenge is to perform bilevel planning with abstractions,
where a high-level search for abstract plans is used to guide planning in the
original transition space. Previous work has shown that when state
abstractions in the form of symbolic predicates are hand-designed, operators
and samplers for bilevel planning can be learned from demonstrations. In this
work, we propose an algorithm for learning predicates from demonstrations,
eliminating the need for manually specified state abstractions. Our key idea
is to learn predicates by optimizing a surrogate objective that is tractable
but faithful to our real efficient-planning objective. We use this surrogate
objective in a hill-climbing search over predicate sets drawn from a grammar.
Experimentally, we show across four robotic planning environments that our
learned abstractions are able to quickly solve held-out tasks, outperforming
six baselines.

##  1 Introduction

Hierarchical planning is a powerful approach for decision-making in
environments with continuous states, continuous actions, and long horizons. A
crucial bottleneck in scaling hierarchical planning is the reliance on human
engineers to manually program domain-specific abstractions. For example, in
bilevel sample-based task and motion planning (Srivastava et al. 2014; Garrett
et al. 2021), an engineer must design (1) symbolic predicates; (2) symbolic
operators; and (3) samplers that propose different refinements of the symbolic
operators into continuous actions. However, recent work has shown that when
predicates are _given_ , operators and samplers can be learned from a modest
number (50–200) of demonstrations (Silver et al. 2021; Chitnis et al. 2022).
Our objective in this work is to _learn_ predicates that can then be used to
learn operators and samplers.

Figure 1: Overview of our framework. Given a small set of goal predicates
(first panel, top), we use demonstration data to learn new predicates (first
panel, bottom). In this Blocks example, the learned predicates P1 – P4
intuitively represent Holding, NotHolding, HandEmpty, and NothingAbove
respectively. Collectively, the predicates define a state abstraction that
maps continuous states $x$ in the environment to abstract states $s$. Object
types are omitted for clarity. After predicate invention, we learn
abstractions of the continuous action space and transition model via planning
operators (second panel). For each operator, we learn a sampler (third panel),
a neural network that maps continuous object features in a given state to
continuous action parameters for controllers which can be executed in the
environment. In this example, the sampler proposes different placements on the
table for the held block. With these learned representations, we perform
bilevel planning (fourth panel), with search in the abstract spaces guiding
planning in the continuous spaces.

Predicates in bilevel planning represent a discrete state abstraction of the
underlying continuous state space (Li, Walsh, and Littman 2006; Abel,
Hershkowitz, and Littman 2017). For example, On(block1, block2) is an
abstraction that discards the exact continuous poses of block1 and block2.
State abstraction alone is useful for decision-making, but predicates go
further: together with operators, predicates enable the use of highly-
optimized domain-independent AI planners (Helmert 2006).

We consider a problem setting where a small set of _goal predicates_ are
available and sufficient for describing task goals, but practically
insufficient for bilevel planning. For example, in a block stacking domain
(Figure 1), we start with On and OnTable, but have no predicates for
describing whether a block is currently held or graspable. Our aim is to
invent new predicates to enrich the state abstraction beyond what can be
expressed with the goal predicates alone, leading to stronger reasoning at the
abstract level.

What objective should we optimize to learn predicates for bilevel planning?
First, consider our real objective: we want a predicate set such that bilevel
planning is fast and successful, in expectation over a task distribution, when
we use those predicates to learn operators and samplers for planning.
Unfortunately, this real objective is far too expensive to use directly, since
even a single evaluation requires neural network sampler training and bilevel
planning.

In this work, we propose a novel surrogate objective that is deeply connected
to our real bilevel-planning objective, but is tractable for predicate
learning. Our main insight is that demonstrations can be used to analytically
approximate bilevel planning time. To leverage this objective for predicate
learning, we take inspiration from the program synthesis literature (Menon et
al. 2013; Ellis et al. 2020), and learn predicates via a hill-climbing search
through a grammar, with the search guided by the objective. After predicate
learning, we use the predicates to learn operators and samplers. All three
components can then be used for efficient bilevel planning on new tasks.

In experiments across four robotic planning environments, we find predicates,
operators, and samplers learned from 50–200 demonstrations enable efficient
bilevel planning on held-out tasks that involve different numbers of objects,
longer horizons, and larger goal expressions than seen in the demonstrations.
Furthermore, predicates learned with our proposed surrogate objective
substantially outperform those learned with objectives inspired by previous
work, which are based on prediction error (Pasula, Zettlemoyer, and Kaelbling
2007; Jetchev, Lang, and Toussaint 2013), bisimulation (Konidaris, Kaelbling,
and Lozano-Perez 2018; Curtis et al. 2021), and inverse planning (Baker, Saxe,
and Tenenbaum 2009; Ramírez and Geffner 2010; Zhi-Xuan et al. 2020). We
compare against several other baselines and ablations of our system to further
validate our results.

##  2 Problem Setting

We consider learning from demonstrations in deterministic planning problems.
These problems are goal-based and object-centric, with continuous states and
hybrid discrete-continuous actions. Formally, an _environment_ is a tuple
$\langle\Lambda,d,\mathcal{C},f,\Psi_{G}\rangle$, and is associated with a
distribution $\mathcal{T}$ over _tasks_ , where each task $T\in\mathcal{T}$ is
a tuple $\langle\mathcal{O},x_{0},g\rangle$.

$\Lambda$ is a finite set of object _types_ , and the map
$d:\Lambda\to\mathbb{N}$ defines the dimensionality of the real-valued feature
vector for each type. Within a task, $\mathcal{O}$ is an _object set_ , where
each object has a type drawn from $\Lambda$; this $\mathcal{O}$ can (and
typically will) vary between tasks. $\mathcal{O}$ induces a state space
$\mathcal{X}_{\mathcal{O}}$ (going forward, we simply write $\mathcal{X}$ when
clear from context). A _state_ $x\in\mathcal{X}$ in a task is a mapping from
each $o\in\mathcal{O}$ to a feature vector in
$\mathbb{R}^{d(\text{type}(o))}$; $x_{0}$ is the initial state of the task.

$\mathcal{C}$ is a finite set of _controllers_. A controller
$C((\lambda_{1},\dots,\lambda_{v}),\Theta)\in\mathcal{C}$ can have both
discrete typed parameters $(\lambda_{1},\ldots,\lambda_{v})$ and a continuous
real-valued vector of parameters $\Theta$. For instance, a controller Pick for
picking up a block might have one discrete parameter of type block and a
$\Theta$ that is a placeholder for a specific grasp pose. The controller set
$\mathcal{C}$ and object set $\mathcal{O}$ induce an action space
$\mathcal{A}_{\mathcal{O}}$ (going forward, we write $\mathcal{A}$ when
clear). An _action_ $a\in\mathcal{A}$ in a task is a controller
$C\in\mathcal{C}$ with both discrete and continuous arguments:
$a=C((o_{1},\ldots o_{v}),\theta)$, where the objects $(o_{1},\ldots o_{v})$
are drawn from the object set $\mathcal{O}$ and must have types matching the
controller’s discrete parameters $(\lambda_{1},\ldots,\lambda_{v})$.
Transitions through states and actions are governed by
$f:\mathcal{X}\times\mathcal{A}\to\mathcal{X}$, a known, deterministic
transition model that is shared across tasks.

A _predicate_ $\psi$ is characterized by an ordered list of types
$(\lambda_{1},\dots,\lambda_{m})$ and a lifted binary state classifier
$c_{\psi}:\mathcal{X}\times\mathcal{O}^{m}\to\\{\text{true},\text{false}\\}$,
where $c_{\psi}(x,(o_{1},\dots,o_{m}))$ is defined only when each object
$o_{i}$ has type $\lambda_{i}$. For instance, the predicate Holding may, given
a state and two objects, robot and block, describe whether the block is held
by the robot in this state. A _lifted atom_ is a predicate with typed
variables (e.g., Holding(?robot, ?block)). A _ground atom_ $\underline{\psi}$
consists of a predicate $\psi$ and objects $(o_{1},\dots,o_{m})$, again with
all $\text{type}(o_{i})=\lambda_{i}$ (e.g., Holding(robby, block7)). Note that
a ground atom induces a binary state classifier
$c_{\underline{\psi}}:\mathcal{X}\to\\{\text{true},\text{false}\\}$, where
$c_{\underline{\psi}}(x)\triangleq c_{\psi}(x,(o_{1},\dots,o_{m}))$.

$\Psi_{G}$ is a small set of _goal predicates_ that we assume are given and
sufficient for representing task goals, but insufficient practically as
standalone state abstractions. Specifically, the goal $g$ of a task is a set
of ground atoms over predicates in $\Psi_{G}$ and objects in $\mathcal{O}$. A
goal $g$ is said to _hold_ in a state $x$ if for all ground atoms
$\underline{\psi}\in g$, the classifier $c_{\underline{\psi}}(x)$ returns
true. A solution to a task is a _plan_ $\pi=(a_{1},\ldots,a_{n})$, a sequence
of actions $a\in\mathcal{A}$ such that successive application of the
transition model $x_{i}=f(x_{i-1},a_{i})$ on each $a_{i}\in\pi$, starting from
$x_{0}$, results in a final state $x_{n}$ where $g$ holds.

The agent is provided with a set of _training tasks_ from $\mathcal{T}$ and a
set of demonstrations $\mathcal{D}$, with _one demonstration per task_. We
assume action costs are unitary and demonstrations are near-optimal. Each
demonstration consists of a training task $\langle\mathcal{O},x_{0},g\rangle$
and a plan $\pi^{*}$ that solves the task. Note that for each $\pi^{*}$, we
can recover the associated state sequence starting at $x_{0}$, since $f$ is
known and deterministic. The agent’s objective is to _efficiently_ solve held-
out tasks from $\mathcal{T}$ using anything it chooses to learn from
$\mathcal{D}$.

##  3 Predicates, Operators, and Samplers

Since the agent has access to the transition model $f$, one approach for
optimizing the objective described in Section 2 is to forgo learning entirely,
and solve any held-out task by running a planner over the state state
$\mathcal{X}$ and action space $\mathcal{A}$. However, searching for a
solution directly in these large spaces is highly infeasible. Instead, we
propose to _learn abstractions_ using the provided demonstrations. In this
section, we will describe representations that allow for fast bilevel planning
with abstractions (Section 4). In Section 5, we then describe how to learn
these abstractions.

We adopt a very general definition of an abstraction (Konidaris and Barto
2009): mappings from $\mathcal{X}$ and $\mathcal{A}$ to alternative state and
action spaces. We first characterize an abstract state space
$\mathcal{S}_{\Psi}$ and a transformation from states in $\mathcal{X}$ to
abstract states. Next, we describe an abstract action space
$\underline{\Omega}$ and an abstract transition model
$F:\mathcal{S}_{\Psi}\times\underline{\Omega}\to\mathcal{S}_{\Psi}$ that can
be used to plan in the abstract space. Finally, we define samplers $\Sigma$
for refining abstract actions back into $\mathcal{A}$, i.e., actions that can
be executed. See the diagram on the right for a summary.

(1) An abstract state space. We use a set of predicates $\Psi$ (as defined in
Section 2) to induce an abstract state space $\mathcal{S}_{\Psi}$. Recalling
that a ground atom $\underline{\psi}$ induces a classifier
$c_{\underline{\psi}}$ over states $x\in\mathcal{X}$, we have:

######  Definition 1 (Abstract state).

An _abstract state_ $s$ is the set of ground atoms under $\Psi$ that hold true
in $x$:

$s=\textsc{Abstract}(x,\Psi)\triangleq\\{\underline{\psi}:c_{\underline{\psi}}(x)=\text{\emph{true}},\forall\psi\in\Psi\\}.$

The (discrete) abstract state space induced by $\Psi$ is denoted
$\mathcal{S}_{\Psi}$. Throughout this work, we use predicate sets $\Psi$ that
are supersets of the given goal predicates $\Psi_{G}$. However, only the goal
predicates are given, and they alone are typically very limited; in Section 5,
we will discuss how the agent can use data to _invent predicates_ that will
make up the rest of $\Psi$. See Figure 1 (first panel) for an example.

(2) An abstract action space and abstract transition model. We address both by
having the agent learn _operators_ :

######  Definition 2 (Operator).

An _operator_ is a tuple
$\omega=\langle\textsc{Par},\textsc{Pre},\textsc{Eff}^{+},\textsc{Eff}^{-},\textsc{Con}\rangle$
where:

  * $\bullet$

Par is an ordered list of _parameters_ : variables with types drawn from the
type set $\Lambda$.

  * $\bullet$

$\textsc{Pre},\textsc{Eff}^{+},\textsc{Eff}^{-}$ are _preconditions_ , _add
effects_ , and _delete effects_ , each a set of lifted atoms over $\Psi$ and
Par.

  * $\bullet$

Con is a tuple $\langle C,\textsc{Par}_{\textsc{Con}}\rangle$ where
$C((\lambda_{1},\dots,\lambda_{v}),\Theta)$ is a controller and
$\textsc{Par}_{\textsc{Con}}$ is an ordered list of _controller arguments_ ,
each a variable from Par. Furthermore, $|\textsc{Par}_{\textsc{Con}}|=v$, and
each argument $i$ must be of the respective type $\lambda_{i}$.

We denote the set of operators as $\Omega$. See Figure 1 (second panel) for an
example. Unlike in STRIPS (Fikes and Nilsson 1971), our operators are
augmented with controllers and controller arguments, which will allow us to
connect to the task actions in (3) below. Now, given a task with object set
$\mathcal{O}$, the set of all _ground operators_ defines our (discrete)
abstract action space for a task:

######  Definition 3 (Ground operator / abstract action).

A _ground operator_ $\underline{\omega}=\langle\omega,\delta\rangle$ is an
operator $\omega$ and a substitution $\delta:\textsc{Par}\to\mathcal{O}$
mapping parameters to objects. We use
$\underline{\textsc{Pre}},\underline{\textsc{Eff}^{+}},\underline{\textsc{Eff}^{-}}$,
and $\underline{\textsc{Par}_{\textsc{Con}}}$ to denote the ground
preconditions, ground add effects, ground delete effects, and ground
controller arguments of $\underline{\omega}$, where variables in Par are
substituted with objects under $\delta$.

We denote the set of ground operators (the abstract action space) as
$\underline{\Omega}$. Together with the abstract state space
$\mathcal{S}_{\Psi}$, the preconditions and effects of the operators induce an
abstract transition model for a task:

######  Definition 4 (Abstract transition model).

The _abstract transition model_ induced by predicates $\Psi$ and operators
$\Omega$ is a partial function
$F:\mathcal{S}_{\Psi}\times\underline{\Omega}\to\mathcal{S}_{\Psi}$.
$F(s,\underline{\omega})$ is only defined if $\underline{\omega}$ is
_applicable_ in $s$: $\underline{\textsc{Pre}}\subseteq s$. If defined,
$F(s,\underline{\omega})\triangleq(s-\underline{\textsc{Eff}^{-}})\cup\underline{\textsc{Eff}^{+}}$.

(3) A mechanism for refining abstract actions into task actions. A ground
operator $\underline{\omega}$ induces a partially specified controller,
$C((o_{1},\ldots o_{v}),\Theta)$ with $(o_{1},\ldots
o_{v})=\underline{\textsc{Par}_{\textsc{Con}}}$, where object arguments have
been selected but continuous parameters $\Theta$ have not. To _refine_ this
abstract action $\underline{\omega}$ into a task-level action
$a=C((o_{1},\ldots o_{v}),\theta)$, we use _samplers_ :

######  Definition 5 (Sampler).

Each operator $\omega\in\Omega$ is associated with a _sampler_
$\sigma:\mathcal{X}\times\mathcal{O}^{|\textsc{Par}|}\to\Delta(\Theta)$, where
$\Delta(\Theta)$ is the space of distributions over $\Theta$, the continuous
parameters of the operator’s controller.

######  Definition 6 (Ground sampler).

For each ground operator $\underline{\omega}\in\underline{\Omega}$, if
$\underline{\omega}=\langle\omega,\delta\rangle$ and $\sigma$ is the sampler
associated with $\omega$, then the ground sampler associated with
$\underline{\omega}$ is a state-conditioned distribution
$\underline{\sigma}:\mathcal{X}\to\Delta(\Theta)$, where
$\underline{\sigma}(x)\triangleq\sigma(x,\delta(\textsc{Par}))$.

We denote the set of samplers as $\Sigma$. See Figure 1 (third panel) for an
example.

What connects the transition model $f$, abstract transition model $F$, and
samplers $\Sigma$? While previous works enforce the downward refinability
property (Marthi, Russell, and Wolfe 2007; Pasula, Zettlemoyer, and Kaelbling
2007; Jetchev, Lang, and Toussaint 2013; Konidaris, Kaelbling, and Lozano-
Perez 2018), it is important in robotics to be robust to violations of this
property, since learned abstractions will typically lose critical geometric
information. Therefore, we only require our learned abstractions to satisfy
the following _weak semantics_ : for every ground operator
$\underline{\omega}$ with partially specified controller
$C((o_{1},\dots,o_{v}),\Theta)$ and associated ground sampler
$\underline{\sigma}$, there exists some $x\in\mathcal{X}$ and some $\theta$ in
the support of $\underline{\sigma}(x)$ such that $F(s,\underline{\omega})$ is
defined and equals $s^{\prime}$, where $s=\textsc{Abstract}(x,\Psi)$,
$a=C((o_{1},\dots,o_{v}),\theta)$, and
$s^{\prime}=\textsc{Abstract}(f(x,a),\Psi)$. Note that downward refinability
(Marthi, Russell, and Wolfe 2007) makes a much stronger assumption: that this
statement holds for _every_ $x\in\mathcal{X}$ where $F(s,\underline{\omega})$
is defined.

##  4 Bilevel Planning

To use the components of an abstraction — predicates $\Psi$, operators
$\Omega$, and samplers $\Sigma$ — for efficient planning, we build on
_bilevel_ planning techniques (Srivastava et al. 2014; Garrett et al. 2021).
We conduct an outer search over _abstract plans_ using the predicates and
operators, and an inner search over refinements of an abstract plan into a
task solution $\pi$ using the predicates and samplers.

######  Definition 7 (Abstract plan).

An _abstract plan_ $\hat{\pi}$ for a task $\langle\mathcal{O},x_{0},g\rangle$
is a sequence of ground operators
$(\underline{\omega}_{1},\ldots,\underline{\omega}_{n})$ such that applying
the abstract transition model $s_{i}=F(s_{i-1},\underline{\omega}_{i})$
successively starting from $s_{0}=\textsc{Abstract}(x_{0},\Psi)$ results in a
sequence of abstract states $(s_{0},\ldots,s_{n})$ that achieves the goal,
i.e., $g\subseteq s_{n}$. This $(s_{0},\ldots,s_{n})$ is called the _expected
abstract state sequence_.

Because downward refinability does not hold in our setting, an abstract plan
$\hat{\pi}$ is _not_ guaranteed to be refinable into a solution $\pi$ for the
task, which necessitates bilevel planning. We now describe the planning
algorithm in detail.

The overall structure of the planner is outlined in Algorithm 1. For the outer
search that finds abstract plans $\hat{\pi}$, denoted GenAbstractPlan (Alg. 1,
Line 2), we leverage the STRIPS-style operators and predicates (Fikes and
Nilsson 1971) to automatically derive a domain-independent heuristic
popularized by the AI planning community, such as LMCut (Helmert and Domshlak
2009). We use this heuristic to run an A∗ search over the abstract state space
$\mathcal{S}_{\Psi}$ and abstract action space $\underline{\Omega}$. This A∗
search is used as a generator (hence the name GenAbstractPlan) of abstract
plans $\hat{\pi}$, outputting one at a time111This usage of A∗ search as a
generator is related to top-$k$ planning (Katz et al. 2018; Ren, Chalvatzaki,
and Peters 2021). We experimented with off-the-shelf top-$k$ planners, but
chose A∗ because it was faster in our domains. Note that the abstract plan
generator is used heavily in learning (Section 5).. Parameter
$n_{\text{abstract}}$ governs the maximum number of abstract plans that can be
generated before the planner terminates with failure.

_Plan( $x_{0}$, $g$, $\Psi$, $\Omega$, $\Sigma$ )_

// Parameters: $n_{\text{abstract}}$, $n_{\text{samples}}$.

1 $s_{0}\leftarrow\textsc{Abstract}(x_{0},\Psi)$

2 for  _$\hat{\pi}$ in GenAbstractPlan($s_{0}$, $g$, $\Omega$,
$n_{\text{abstract}}$)_

3if  _$\pi\sim$ Refine($\hat{\pi}$, $x_{0}$, $\Psi$, $\Sigma$,
$n_{\text{samples}}$)_ then

4 return $\pi$

Algorithm 1 Pseudocode for our bilevel planning algorithm. The inputs are an
initial state $x_{0}$, goal $g$, predicates $\Psi$, operators $\Omega$, and
samplers $\Sigma$; the output is a plan $\pi$. An outer loop runs
GenAbstractPlan, which generates plans in the abstract state and action
spaces. An inner loop runs Refine, which attempts to refine each abstract plan
$\hat{\pi}$ into a plan $\pi$. If Refine succeeds, then the found plan $\pi$
is returned as the solution; if Refine fails, then GenAbstractPlan continues.

For each abstract plan $\hat{\pi}$, we conduct an inner search that attempts
to Refine (Alg. 1, Line 3) it into a solution $\pi$ (a plan that achieves the
goal under the transition model $f$). While various implementations of Refine
are possible (Chitnis et al. 2016), we follow Srivastava et al. (2014) and
perform a backtracking search over the abstract actions
$\underline{\omega}_{i}\in\hat{\pi}$. Recall that each
$\underline{\omega}_{i}$ induces a partially specified controller
$C_{i}((o_{1},\dots,o_{v})_{i},\Theta_{i})$ and has an associated ground
sampler $\underline{\sigma}_{i}$. To begin the search, we initialize an
indexing variable $i$ to 1. On each step of search, we sample continuous
parameters $\theta_{i}\sim\underline{\sigma}_{i}(x_{i-1})$, which fully
specify an action $a_{i}=C_{i}((o_{1},\dots,o_{v})_{i},\theta_{i})$. We then
check whether $x_{i}=f(x_{i-1},a_{i})$ obeys the expected abstract state
sequence, i.e., whether $s_{i}=\textsc{Abstract}(x_{i},\Psi)$. If so, we
continue on to $i\leftarrow i+1$. Otherwise, we repeat this step, sampling a
new $\theta_{i}\sim\underline{\sigma}_{i}(x_{i-1})$. Parameter
$n_{\text{samples}}$ governs the maximum number of times we invoke the sampler
for a single value of $i$ before backtracking to $i\leftarrow i-1$. Refine
succeeds if the goal $g$ holds when $i=|\hat{\pi}|$, and fails when $i$
backtracks to 0.

If Refine succeeds given a candidate $\hat{\pi}$, the planner terminates with
success (Alg. 1, Line 4) and returns the plan
$\pi=(a_{1},\ldots,a_{|\hat{\pi}|})$. Crucially, if Refine fails, we continue
with GenAbstractPlan to generate the next candidate $\hat{\pi}$. In the
taxonomy of task and motion planners (TAMP), this approach is in the “search-
then-sample” category (Srivastava et al. 2014; Dantam et al. 2016; Garrett et
al. 2021). As we have described it, this planner is _not_ probabilistically
complete, because abstract plans are not revisited. Extensions to ensure
completeness are straightforward (Chitnis et al. 2016), but are not our focus
in this work.

##  5 Learning from Demonstrations

To use bilevel planning at evaluation time, we must learn predicates,
operators, and samplers at training time. We use the methods of Chitnis et al.
(2022) for operator learning and sampler learning; see Section A.1 and Section
A.3 for descriptions. For what follows, it is important to understand that
operator learning is fast ($O(|\mathcal{D}|)$), but sampler learning is slow,
and both require a given set of predicates. Our main contribution is a method
for predicate invention that precedes operator and sampler learning in the
training pipeline.

_ETPT( $x_{0}$, $g$, $\Psi$, $\Omega$, $\pi^{*}$)_

// Note: does not take in samplers!

// Parameters:  $n_{\text{abstract}}$, $t_{\text{upper}}$.

1 $s_{0}\leftarrow\textsc{Abstract}(x_{0},\Psi)$

2 $p_{\text{terminate}}\leftarrow 0.0$

3 $t_{\text{expected}}\leftarrow 0.0$

4 for  _ $\hat{\pi}$ in GenAbstractPlan($s_{0}$, $g$, $\Omega$,
$n_{\text{abstract}}$)_

5 $p_{\text{refined}}\leftarrow$ EstimateRefineProb($\hat{\pi}$, $\pi^{*}$)

6 $p_{\text{terminate}}\leftarrow(1-p_{\text{terminate}})\cdot
p_{\text{refined}}$

7 $t_{\text{iter}}\leftarrow$ EstimateTime($\hat{\pi}$, $x_{0}$, $\Psi$,
$\Omega$)

8 $t_{\text{expected}}\leftarrow t_{\text{expected}}+p_{\text{terminate}}\cdot
t_{\text{iter}}$

9$t_{\text{expected}}\leftarrow
t_{\text{expected}}+(1-p_{\text{terminate}})\cdot t_{\text{upper}}$

10 return $t_{\text{expected}}$

Algorithm 2 Pseudocode for Estimate Total Planning Time in our predicate
invention surrogate objective. Commonalities with Algorithm 1 are shown in
blue. See Section 5 for details.

Inspired by prior work (Bonet and Geffner 2019; Loula et al. 2019; Curtis et
al. 2021), we approach the predicate invention problem from a program
synthesis perspective (Stahl 1993; Lavrac and Dzeroski 1994; Cropper and
Muggleton 2016; Ellis et al. 2020). First, we define a compact representation
of an infinite space of predicates in the form of a _grammar_. We then
enumerate a large pool of _candidate predicates_ from this grammar, with
simpler candidates enumerated first. Next, we perform a _local search_ over
subsets of candidates, with the aim of identifying a good final subset to use
as $\Psi$. The crucial question in this step is: what _objective function_
should we use to guide the search over candidate predicate sets?

Figure 2: Predicate invention via hill climbing. (Left) An example task in
Blocks. (Middle) Hill climbing over predicate sets, starting with the goal
predicates $\Psi_{G}$. On each iteration, the single predicate that improves
$J_{\text{surr}}$ the most is added to the set. The rightmost table column
shows success rates on held-out evaluation tasks. Each iteration of hill
climbing adds a predicate that causes all abstract plans above the dotted line
to be pruned from consideration. At iteration 0, the robot believes it can
achieve the goal by simply stacking b2 on b3 and b1 on b2, even though it
hasn’t picked up either block. The first step of this abstract plan (shown in
red) is thus unrefinable. At iteration 1, a predicate with the intuitive
meaning Holding is added, which makes the A∗ only consider abstract plans that
pick up blocks before stacking them. Still, the abstract plan shown is
unrefinable on the first step because b4 is obstructing b2 in the initial
state. At iteration 2, a predicate with the intuitive meaning NothingAbove is
added, which allows the agent to realize that it must move b4 out of the way
if it wants to pick up b2. This plan is still unrefinable, though: the second
step fails, because the abstraction still does not recognize that the robot
cannot be holding two blocks simultaneously. Finally, at iteration 3, a
predicate with the intuitive meaning HandEmpty is added, and planning
succeeds.

###  5.1 Scoring a Candidate Predicate Set

Ultimately, we want to find a set of predicates $\Psi$ that will lead to
efficient planning, after we use the predicates to learn operators $\Omega$
and samplers $\Sigma$. I.e., our real objective is:

$J_{\text{real}}(\Psi)\triangleq\mathbb{E}_{(\mathcal{O},x_{0},g)\sim\mathcal{T}}[\textsc{Time}(\textsc{Plan}(x_{0},g,\Psi,\Omega,\Sigma))],$

where $\Omega$ and $\Sigma$ are learned using $\Psi$ as we described in
Sections A.1 and A.3, Plan is the algorithm described in Section 4, and
$\textsc{Time}(\cdot)$ measures the time that Plan takes to find a
solution222If no plan can be found (e.g., a task is infeasible under the
abstraction), Time would return a large constant representing a timeout..
However, we need an objective that can be used to guide a _search_ over
candidate predicate sets, meaning the objective must be evaluated many times.
$J_{\text{real}}$ is far too expensive for this, due to two speed bottlenecks:
sampler learning, which involves training several neural networks; and the
repeated calls to Refine from within Plan, which each perform backtracking
search to refine an abstract plan. To overcome this intractability, we will
use a _surrogate objective_ $J_{\text{surr}}$ that is cheaper to evaluate than
$J_{\text{real}}$, but that approximately preserves the ordering over
predicate sets, i.e.,
$J_{\text{surr}}(\Psi)<J_{\text{surr}}(\Psi^{\prime})\iff
J_{\text{real}}(\Psi)<J_{\text{real}}(\Psi^{\prime})$.

We propose a surrogate objective that uses the demonstrations $\mathcal{D}$ to
_estimate_ the time it would take to solve the training tasks under the
abstraction induced by a candidate predicate set $\Psi$, without using
samplers or doing refinement. Recalling that $\mathcal{D}$ has one
demonstration $\pi^{*}$ for each training task
$\langle\mathcal{O},x_{0},g\rangle$, the objective is defined as follows:

$J_{\text{surr}}(\Psi)\triangleq\frac{1}{|\mathcal{D}|}\sum_{(\mathcal{O},x_{0},g,\pi^{*})\in\mathcal{D}}[\textsc{ETPT}(x_{0},g,\Psi,\Omega,\pi^{*})],$

where ETPT abbreviates Estimate Total Planning Time (Algorithm 2). ETPT uses
the candidate predicates and induced operators to perform the first part of
bilevel planning: A∗ search over abstract plans. However, for each generated
abstract plan, rather than learning samplers and calling Refine, we use the
available demonstrations to estimate the probability that refinement _would_
succeed if we _were_ to learn samplers and call Refine. Since bilevel planning
terminates upon the successful refinement of an abstract plan, we can use
these probabilities to approximate the total expected planning time. We now
describe these steps in detail.

#### Estimating Refinement Probability

ETPT maintains a probability $p_{\text{terminate}}$, initialized to $0$ (Line
2), that planning would terminate after each generated abstract plan. To
update $p_{\text{terminate}}$ (Lines 5-6), we must estimate both whether Plan
would have terminated _before_ this step, and whether Plan would terminate
_on_ this step. For the former, we can use $(1-p_{\text{terminate}})$. For the
latter, since Plan terminates only if Refine succeeds, we use a helper
function EstimateRefineProb to approximate the probability of successfully
refining the given abstract plan, if we were to learn samplers $\Sigma$ and
then call Refine. We use the following implementation:

$\textsc{EstimateRefineProb}(\hat{\pi},\pi^{*})\triangleq(1-\epsilon)\epsilon^{|\textsc{Cost}(\hat{\pi})-\textsc{Cost}(\pi^{*})|}.$

Here, $\epsilon>0$ is a small constant ($10^{-5}$ in our experiments), and
$\textsc{Cost}(\cdot)$ is in our case simply the number of actions in the
plan, due to unitary costs. The intuition for this geometric distribution is
as follows. Since the demonstration $\pi^{*}$ is assumed to be near-optimal,
an abstract plan $\hat{\pi}$ that is cheaper than $\pi^{*}$ should look
suspicious; if such a $\hat{\pi}$ were refinable, then the demonstrator would
have likely used it to produce a better demonstration. If $\hat{\pi}$ is more
expensive than $\pi^{*}$, then even though this abstraction would eventually
produce a refinable abstract plan, it may take a long time for the outer loop
of the planner, GenAbstractPlan, to get to it (Section 4). We note that this
scheme for estimating refinability is surprisingly minimal, in that it needs
only the cost of each demonstration rather than its contents.

#### Estimating Time

To approximate the total planning time, ETPT estimates the time required for
each generated abstract plan, conditioned on its successful refinement, and
then uses the refinement probabilities to compute the total expectation. The
time estimate is maintained in $t_{\text{expected}}$, initialized to 0 (Line
3). To update $t_{\text{expected}}$ on each abstract plan (Lines 7-8), we use
a helper function EstimateTime, which sums together estimates of the _abstract
search time_ and of the _refinement time_. Since we are running abstract
search, we could exactly measure its time; however, to avoid noise due to CPU
speed, we instead use the cumulative number of nodes created by the A∗ search.
To estimate refinement time, recall that Refine performs a backtracking
search, and so over many calls to Refine, the potentially several that fail
will dominate the one or zero that succeed. Therefore, we estimate refinement
time as a large constant ($10^{3}$ in our experiments) that captures the
average cost of an exhaustive backtracking search. Finally, we use a large
constant $t_{\text{upper}}$ ($10^{5}$ in our experiments) to penalize in the
case where no abstract plan succeeds (Line 9).

What is the ideal choice for $n_{\text{abstract}}$, the maximum number of
abstract plans to consider within ETPT? From an efficiency perspective,
$n_{\text{abstract}}=1$ is ideal, but otherwise, it is not obvious whether to
prefer the value of $n_{\text{abstract}}$ that will eventually be used with
Plan at evaluation time, or to instead prefer $n_{\text{abstract}}=\infty$. On
one hand, we want ETPT to be as much of a mirror image of Plan as possible; on
the other hand, some experimentation we conducted suggests that a larger value
of $n_{\text{abstract}}$ can smooth the objective landscape, which makes
search easier. In practice, it may be advisable to treat $n_{\text{abstract}}$
as a hyperparameter.

In summary, our surrogate objective $J_{\text{surr}}$ calculates and combines
two characteristics of a candidate predicate set $\Psi$: (1) abstract plan
cost “error,” i.e., $|\textsc{Cost}(\hat{\pi})-\textsc{Cost}(\pi^{*})|$; and
(2) abstract planning time, i.e., number of nodes created during A∗. The first
feature uses only the costs of the demonstrated plans, while the second
feature does not use the demonstrated plans at all. In Appendix A.7, we
conduct an empirical analysis to further unpack the contribution of these two
features to the overall surrogate objective, finding them to be helpful
together but insufficient individually.

###  5.2 Local Search over Candidate Predicate Sets

With our surrogate objective $J_{\text{surr}}$ established, we turn to the
question of how to best optimize it. We use a simple hill-climbing search,
initialized with $\Psi_{0}\leftarrow\Psi_{G}$, and adding a single new
predicate $\psi$ from the pool on each step $i$:

$\Psi_{i+1}\leftarrow\operatorname*{argmin}_{\psi\not\in\Psi_{i}}J_{\text{surr}}(\Psi_{i}\cup\\{\psi\\}).$

We repeat until no improvement can be found, and use the last predicate set as
our final $\Psi$. See Figure 2 for an example taken from our experiments in
the Blocks environment.

#### Designing a Grammar of Predicates

Designing a grammar of predicates can be difficult, since there is a tradeoff
between the expressivity of the grammar and the practicality of searching over
it. For our experiments, we found that a simple grammar similar to that of
Pasula, Zettlemoyer, and Kaelbling (2007) suffices, which includes single-
feature inequalities, logical negation, and universal quantification. See
Section A.4 for a full description and Figure 1 and Appendix A.7 for examples.

The costs accumulated over the production rules lead us to a final cost
associated with each predicate $\psi$, denoted $\textsc{pen}(\psi)$, where a
higher cost represents a predicate with higher complexity. We use the costs to
regularize $J_{\text{surr}}$ during local search, with a weight small enough
to primarily prevent the addition of “neutral” predicates that neither harm
nor hurt $J_{\text{surr}}$. The regularization term is
$J_{\text{reg}}(\Psi)\triangleq
w_{\text{reg}}\sum_{\psi\in\Psi}\textsc{pen}(\psi)$, where
$w_{\text{reg}}=10^{-4}$ in our experiments. To generate our candidate
predicate set for local search, we enumerate $n_{\text{grammar}}$ (200 in
experiments) predicates from the grammar, in order of increasing cost.

##  6 Experiments

Figure 3: Ours versus baselines. Percentage of 50 evaluation tasks solved
under a 10-second timeout, for all four environments. All results are averaged
over 10 seeds. Black bars denote standard deviations. Learning times and
additional metrics are reported in Appendix A.7.

| Ours | Manual | Down Eval | No Invent
---|---|---|---|---
Environment |  Succ |  Node |  Time |  Succ |  Node |  Time |  Succ |  Node |  Time |  Succ |  Node |  Time
PickPlace1D |  98.6 |  4.8 |  0.006 |  98.4 |  6.5 |  0.045 |  98.6 |  4.8 |  0.008 |  39.6 |  14.1 |  1.369
Blocks |  98.4 |  2949 |  0.296 |  98.6 |  2941 |  0.251 |  98.2 |  2949 |  0.318 |  3.2 |  427.7 |  1.235
Painting |  100.0 |  501.8 |  0.470 |  99.6 |  2608 |  0.464 |  98.8 |  489.0 |  0.208 |  0.0 |  – |  –
Tools |  96.8 |  1897 |  0.457 |  100.0 |  4771 |  0.491 |  42.8 |  152.5 |  0.060 |  0.0 |  – |  –

Table 1: Ours versus Manual and ablations. Percentage of 50 evaluation tasks
solved under a 10-second timeout (Succ), number of nodes created during
GenAbstractPlan (Node), and wall-clock planning time in seconds (Time). All
results are averaged over 10 seeds. The Node and Time columns average over
_solved tasks only_. Standard deviations are provided in Appendix A.7.

Our experiments are designed to answer the following questions: (Q1) To what
extent do our learned abstractions help both the effectiveness and the
efficiency of planning, and how do they compare to abstractions learned using
other objective functions? (Q2) How do our learned state abstractions compare
in performance to manually designed state abstractions? (Q3) How data-
efficient is learning, with respect to the number of demonstrations? (Q4) Do
our abstractions vary as we change the planner configuration, and if so, how?

#### Experimental Setup

We evaluate 10 methods across four robotic planning environments. All results
are averaged over 10 random seeds. For each seed, we sample a set of 50
_evaluation tasks_ that involve more objects and harder goals than were seen
at training. Demonstrations are collected by bilevel planning with manually
defined abstractions (see Manual method below). Planning is always limited to
a 10-second timeout. See Appendix A.6 for additional details.

#### Environments

We now briefly describe the environments, with further details in Appendix
A.5. The first three environments were established in prior work by Silver et
al. (2021), but in that work, all predicates were manually defined; we use the
same predicates in the Manual baseline.

  * $\bullet$

PickPlace1D. A robot must pick blocks and place them onto target regions along
a table surface. All pick and place poses are in a 1D line. Evaluation tasks
require 1-4 actions to solve.

  * $\bullet$

Blocks. A robot in 3D must interact with blocks on a table to assemble them
into towers. This is a robotic version of the classic blocks world domain.
Evaluation tasks require 2-20 actions to solve.

  * $\bullet$

Painting. A robot in 3D must pick, wash, dry, paint, and place widgets into
either a box or a shelf. Evaluation tasks require 11-25 actions to solve.

  * $\bullet$

Tools. A robot operating on a 2D table surface must assemble contraptions with
screws, nails, and bolts, using a provided set of screwdrivers, hammers, and
wrenches respectively. This environment has physical constraints that cannot
be modeled by our predicate grammar. Evaluation tasks require 7-20 actions to
solve.

#### Methods

We evaluate our method, six baselines, a manually designed state abstraction,
and two ablations. Note that the Bisimulation, Branching, Boltzmann, and
Manual baselines differ from Ours only in predicate learning.

  * $\bullet$

Ours. Our main approach.

  * $\bullet$

Bisimulation. A baseline that learns abstractions by approximately optimizing
the _bisimulation criteria_ (Givan, Dean, and Greig 2003), as in prior work
(Curtis et al. 2021). Specifically, this baseline learns abstractions that
minimize the number of transitions in the demonstrations where the abstract
transition model $F$ is applicable but makes a misprediction about the next
abstract state. Note that because goal predicates are given, goal
distinguishability is satisfied under any abstraction.

  * $\bullet$

Branching. A baseline that learns abstractions by optimizing the _branching
factor_ of planning. Specifically, this baseline learns predicates that
minimize the number of applicable operators over demonstration states.

  * $\bullet$

Boltzmann. A baseline that assumes the demonstrator is acting _noisily
rationally_ under (unknown) optimal abstractions (Baker, Saxe, and Tenenbaum
2009). For any candidate abstraction, we compute the likelihood of the
demonstration under a Boltzmann policy using the planning heuristic as a
surrogate for the true cost-to-go.

  * $\bullet$

GNN Shooting. A baseline that trains a graph neural network (Battaglia et al.
2018) policy. This GNN takes in the current state $x$, abstract state $s$, and
goal $g$. It outputs an action $a$, via a one-hot vector over $\mathcal{C}$
corresponding to which controller to execute, one-hot vectors over all objects
at each discrete argument position, and a vector of continuous arguments. We
train the GNN using behavior cloning on the data $\mathcal{D}$. At evaluation
time, we sample trajectories by treating the outputted continuous arguments as
the mean of a Gaussian with fixed variance. We use the transition model $f$ to
check if the goal is achieved, and repeat until the planning timeout is
reached.

  * $\bullet$

GNN Model-Free. A baseline that uses the same GNN, but directly executes the
policy instead of shooting.

  * $\bullet$

Random. A baseline that simply executes a random controller with random
arguments on each step. No learning.

  * $\bullet$

Manual. An oracle approach that plans with manually designed predicates for
each environment.

  * $\bullet$

Down Eval. An ablation of Ours that uses $n_{\text{abstract}}=1$ during
evaluation only, in Plan (Algorithm 1).

  * $\bullet$

No Invent. An ablation of Ours that uses $\Psi=\Psi_{G}$, i.e., only goal
predicates are used for the state abstraction.

#### Results and Discussion

We provide real examples of learned predicates and operators for all
environments in Appendix A.7. Figure 3 shows that our method solves many more
held-out tasks within the timeout than the baselines. A major reason for this
performance gap is that our surrogate objective $J_{\text{surr}}$ explicitly
approximates the efficiency of planning. The lackluster performance of the
bisimulation baseline is especially notable because of its prevalence in the
literature (Pasula, Zettlemoyer, and Kaelbling 2007; Jetchev, Lang, and
Toussaint 2013; Bonet and Geffner 2019; Curtis et al. 2021). We examined its
failure modes more closely and found that it consistently selects good
predicates, but not _enough_ of them. This is because requiring the operators
to be a perfect predictive model in the abstract spaces is often not enough to
ensure good planning performance. For example, in the Blocks environment, the
goal predicates together with the predicate Holding(?block) are enough to
satisfy bisimulation on our data, while other predicates like Clear(?block)
and HandEmpty() are useful from a planning perspective. Examining the GNN
baselines, we see that while shooting is beneficial versus using the GNN
model-free, the performance is generally far worse than Ours. Additional
experimentation we conducted suggests that the GNN gets better with around an
order of magnitude more data.

The figure on the right illustrates the data efficiency of Ours. Each point
shows a mean over 10 seeds, with standard deviations shown as vertical bars.
We often obtain very good evaluation performance within just 50
demonstrations.

In Table 1, the results for No Invent show that, as expected, the goal
predicates alone are completely insufficient for most tasks. Comparing Ours to
Down Eval shows that assuming downward refinability at evaluation time works
for PickPlace1D, Blocks, and Painting, but not for Tools. We also find that
the learned predicates (Ours) are on par with, and sometimes _better than_ ,
hand-designed predicates (Manual). For instance, consider PickPlace1D, where
the learned predicates are 7.5x better. The manually designed predicates were
Held(?block) and HandEmpty(), and the always-given goal predicate
Covers(?block, ?target). In addition to inventing two predicates that are
equivalent to Held and HandEmpty, Ours invented two more:
$\texttt{P3(?block)}\triangleq\forall\texttt{?t}\ .\
\lnot\texttt{Covers(?block, ?t)}$, and
$\texttt{P4(?target)}\triangleq\forall\texttt{?b}\ .\ \lnot\texttt{Covers(?b,
?target)}$. Intuitively, P3 means “the given block is not on any target,”
while P4 means “the given target is clear.” P3 gets used in an operator
precondition for picking, which reduces the branching factor of abstract
search. This precondition is sensible because there is no use in moving a
block once it is already on its target. P4 prevents considering non-refinable
abstract plans that “park” objects on targets that must be covered by other
objects.

In Appendix A.8, we describe an additional experiment where we vary the AI
planning heuristic used in abstract search. We analyze a case in Blocks where
variation in the invented predicates appears inconsequential upon initial
inspection, but actually has substantial impact on planning efficiency. This
result underscores the benefit of using a surrogate objective for predicate
invention that is sensitive to downstream planning efficiency.

##  7 Related Work

Our work continues a long line of research on learning state abstractions for
decision-making (Bertsekas, Castanon et al. 1988; Andre and Russell 2002; Jong
and Stone 2005; Li, Walsh, and Littman 2006; Abel, Hershkowitz, and Littman
2017; Zhang et al. 2020). Most relevant are works that learn symbolic
abstractions compatible with AI planners (Lang, Toussaint, and Kersting 2012;
Jetchev, Lang, and Toussaint 2013; Ugur and Piater 2015; Asai and Fukunaga
2018; Bonet and Geffner 2019; Asai and Muise 2020; Ahmetoglu et al. 2020;
Umili et al. 2021). Our work is particularly influenced by Pasula,
Zettlemoyer, and Kaelbling (2007), who use search through a concept language
to invent symbolic state and action abstractions, and Konidaris, Kaelbling,
and Lozano-Perez (2018), who discover symbolic abstractions by leveraging the
initiation and termination sets of options that satisfy an abstract subgoal
property. The objectives used in these prior works are based on variations of
auto-encoding, prediction error, or bisimulation, which stem from the
perspective that the abstractions should _replace_ planning in the original
transition space, rather than _guide_ it.

Recent works have also considered learning abstractions for multi-level
planning, like those in the task and motion planning (TAMP) (Gravot, Cambon,
and Alami 2005; Garrett et al. 2021) and hierarchical planning (Bercher,
Alford, and Höller 2019) literature. Some of these efforts consider learning
symbolic action abstractions (Zhuo et al. 2009; Nguyen et al. 2017; Silver et
al. 2021; Aineto, Jiménez, and Onaindia 2022) or refinement strategies
(Chitnis et al. 2016; Mandalika et al. 2019; Chitnis, Kaelbling, and Lozano-
Pérez 2019; Wang et al. 2021; Chitnis et al. 2022; Ortiz-Haro et al. 2022);
our operator and sampler learning methods take inspiration from these prior
works. Recent efforts by Loula et al. (2019) and Curtis et al. (2021) consider
learning both state and action abstractions for TAMP, like we do (Loula et al.
2019, 2020; Curtis et al. 2021). The main distinguishing feature of our work
is that our abstraction learning framework explicitly optimizes an objective
that considers downstream planning efficiency.

##  8 Conclusion and Future Work

In this paper, we have described a method for learning predicates that are
explicitly optimized for efficient bilevel planning. Key areas for future work
include (1) learning better abstractions from even fewer demonstrations by
performing active learning to gather more data online; (2) expanding the
expressivity of the grammar to learn more sophisticated predicates; (3)
applying these ideas to partially observed planning problems; and (4) learning
the controllers that we assumed given in this work.

For (1), we hope to investigate how relational exploration algorithms (Chitnis
et al. 2020) might be useful as a mechanism for an agent to decide what
actions to execute, toward the goal of building better state and action
abstractions. For (2), we can take inspiration from program synthesis,
especially methods that can learn programs with continuous parameters (Ellis
et al. 2020). For (3) we could draw insights from recent advances in task and
motion planning in the partially observed setting (Garrett et al. 2020).
Finally, for (4), we recently proposed a method for learning controllers from
demonstrations assuming known predicates (Silver et al. 2022). If we can
remove the latter assumption, we will have a complete pipeline for learning
predicates, operators, samplers, and controllers for bilevel planning.

## Acknowledgements

We gratefully acknowledge support from NSF grant 2214177; from AFOSR grant
FA9550-22-1-0249; from ONR MURI grant N00014-22-1-2740; from the MIT-IBM
Watson Lab; and from the MIT Quest for Intelligence. Tom, Nishanth and Willie
are supported by NSF Graduate Research Fellowships. We thank Michael Katz,
Christian Muise, Aidan Curtis, Jiayuan Mao, Zhutian Yang, and Amber Li for
helpful comments on an earlier draft.

## References

  * Abel, Hershkowitz, and Littman (2017) Abel, D.; Hershkowitz, D. E.; and Littman, M. L. 2017.  Near optimal behavior via approximate state abstraction.  _arXiv preprint arXiv:1701.04113_.
  * Ahmetoglu et al. (2020) Ahmetoglu, A.; Seker, M. Y.; Piater, J.; Oztop, E.; and Ugur, E. 2020.  Deepsym: Deep symbol generation and rule learning from unsupervised continuous robot interaction for planning.  _arXiv preprint arXiv:2012.02532_.
  * Aineto, Jiménez, and Onaindia (2022) Aineto, D.; Jiménez, S.; and Onaindia, E. 2022.  A Comprehensive Framework for Learning Declarative Action Models.  _Journal of Artificial Intelligence Research_ , 74: 1091–1123.
  * Alkhazraji et al. (2020) Alkhazraji, Y.; Frorath, M.; Grützner, M.; Helmert, M.; Liebetraut, T.; Mattmüller, R.; Ortlieb, M.; Seipp, J.; Springenberg, T.; Stahl, P.; and Wülfing, J. 2020.  Pyperplan.
  * Andre and Russell (2002) Andre, D.; and Russell, S. J. 2002.  State abstraction for programmable reinforcement learning agents.  In _AAAI/IAAI_ , 119–125.
  * Asai and Fukunaga (2018) Asai, M.; and Fukunaga, A. 2018.  Classical planning in deep latent space: Bridging the subsymbolic-symbolic boundary.  In _AAAI_.
  * Asai and Muise (2020) Asai, M.; and Muise, C. 2020.  Learning neural-symbolic descriptive planning models via cube-space priors: The voyage home (to STRIPS).  _arXiv preprint arXiv:2004.12850_.
  * Bacchus (2001) Bacchus, F. 2001.  AIPS 2000 planning competition: The fifth international conference on artificial intelligence planning and scheduling systems.  _Ai magazine_ , 22(3): 47–47.
  * Baker, Saxe, and Tenenbaum (2009) Baker, C. L.; Saxe, R.; and Tenenbaum, J. B. 2009.  Action understanding as inverse planning.  _Cognition_.
  * Battaglia et al. (2018) Battaglia, P. W.; Hamrick, J. B.; Bapst, V.; Sanchez-Gonzalez, A.; Zambaldi, V.; Malinowski, M.; Tacchetti, A.; Raposo, D.; Santoro, A.; Faulkner, R.; et al. 2018.  Relational inductive biases, deep learning, and graph networks.  _arXiv preprint arXiv:1806.01261_.
  * Bercher, Alford, and Höller (2019) Bercher, P.; Alford, R.; and Höller, D. 2019.  A Survey on Hierarchical Planning-One Abstract Idea, Many Concrete Realizations.  In _IJCAI_ , 6267–6275.
  * Bertsekas, Castanon et al. (1988) Bertsekas, D. P.; Castanon, D. A.; et al. 1988.  Adaptive aggregation methods for infinite horizon dynamic programming.  _IEEE Transactions on Automatic Control_.
  * Bonet and Geffner (2001) Bonet, B.; and Geffner, H. 2001.  Planning as heuristic search.  _Artificial Intelligence_ , 129(1-2): 5–33.
  * Bonet and Geffner (2019) Bonet, B.; and Geffner, H. 2019.  Learning first-order symbolic representations for planning from the structure of the state space.  _arXiv preprint arXiv:1909.05546_.
  * Chitnis et al. (2016) Chitnis, R.; Hadfield-Menell, D.; Gupta, A.; Srivastava, S.; Groshev, E.; Lin, C.; and Abbeel, P. 2016.  Guided search for task and motion plans using learned heuristics.  In _2016 IEEE International Conference on Robotics and Automation (ICRA)_ , 447–454. IEEE.
  * Chitnis, Kaelbling, and Lozano-Pérez (2019) Chitnis, R.; Kaelbling, L. P.; and Lozano-Pérez, T. 2019.  Learning quickly to plan quickly using modular meta-learning.  In _2019 International Conference on Robotics and Automation (ICRA)_ , 7865–7871. IEEE.
  * Chitnis et al. (2020) Chitnis, R.; Silver, T.; Tenenbaum, J.; Kaelbling, L. P.; and Lozano-Pérez, T. 2020.  GLIB: Efficient exploration for relational model-based reinforcement learning via goal-literal babbling.  _arXiv preprint arXiv:2001.08299_.
  * Chitnis et al. (2022) Chitnis, R.; Silver, T.; Tenenbaum, J. B.; Lozano-Pérez, T.; and Kaelbling, L. P. 2022.  Learning Neuro-Symbolic Relational Transition Models for Bilevel Planning.  In _The IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_.
  * Clevert, Unterthiner, and Hochreiter (2015) Clevert, D.-A.; Unterthiner, T.; and Hochreiter, S. 2015.  Fast and accurate deep network learning by exponential linear units (elus).  _arXiv preprint arXiv:1511.07289_.
  * Cropper and Muggleton (2016) Cropper, A.; and Muggleton, S. H. 2016.  Learning Higher-Order Logic Programs through Abstraction and Invention.  In _IJCAI_ , 1418–1424.
  * Curtis et al. (2021) Curtis, A.; Silver, T.; Tenenbaum, J. B.; Lozano-Perez, T.; and Kaelbling, L. P. 2021.  Discovering State and Action Abstractions for Generalized Task and Motion Planning.  _arXiv preprint arXiv:2109.11082_.
  * Dantam et al. (2016) Dantam, N. T.; Kingston, Z. K.; Chaudhuri, S.; and Kavraki, L. E. 2016.  Incremental task and motion planning: A constraint-based approach.  In _Robotics: Science and systems_ , volume 12, 00052. Ann Arbor, MI, USA.
  * Ellis et al. (2020) Ellis, K.; Wong, C.; Nye, M.; Sable-Meyer, M.; Cary, L.; Morales, L.; Hewitt, L.; Solar-Lezama, A.; and Tenenbaum, J. B. 2020.  Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning.  _arXiv preprint arXiv:2006.08381_.
  * Fikes and Nilsson (1971) Fikes, R. E.; and Nilsson, N. J. 1971.  STRIPS: A new approach to the application of theorem proving to problem solving.  _Artificial intelligence_ , 2(3-4): 189–208.
  * Garrett et al. (2021) Garrett, C. R.; Chitnis, R.; Holladay, R.; Kim, B.; Silver, T.; Kaelbling, L. P.; and Lozano-Pérez, T. 2021.  Integrated task and motion planning.  _Annual review of control, robotics, and autonomous systems_ , 4: 265–293.
  * Garrett et al. (2020) Garrett, C. R.; Paxton, C.; Lozano-Pérez, T.; Kaelbling, L. P.; and Fox, D. 2020\.  Online replanning in belief space for partially observable task and motion problems.  In _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 5678–5684. IEEE.
  * Givan, Dean, and Greig (2003) Givan, R.; Dean, T.; and Greig, M. 2003.  Equivalence notions and model minimization in Markov decision processes.  _Artificial Intelligence_ , 147(1-2): 163–223.
  * Gravot, Cambon, and Alami (2005) Gravot, F.; Cambon, S.; and Alami, R. 2005.  aSyMov: a planner that deals with intricate symbolic and geometric problems.  In _Robotics Research. The Eleventh International Symposium_ , 100–110.
  * Helmert (2006) Helmert, M. 2006.  The fast downward planning system.  _Journal of Artificial Intelligence Research_ , 26: 191–246.
  * Helmert and Domshlak (2009) Helmert, M.; and Domshlak, C. 2009.  Landmarks, critical paths and abstractions: what’s the difference anyway?  In _Nineteenth International Conference on Automated Planning and Scheduling_.
  * Jetchev, Lang, and Toussaint (2013) Jetchev, N.; Lang, T.; and Toussaint, M. 2013.  Learning grounded relational symbols from continuous data for abstract reasoning.  In _Proceedings of the 2013 ICRA Workshop on Autonomous Learning_.
  * Jong and Stone (2005) Jong, N. K.; and Stone, P. 2005.  State Abstraction Discovery from Irrelevant State Variables.  In _IJCAI_.
  * Katz et al. (2018) Katz, M.; Sohrabi, S.; Udrea, O.; and Winterer, D. 2018.  A Novel Iterative Approach to Top-k Planning.  In _Proceedings of the Twenty-Eigth International Conference on Automated Planning and Scheduling (ICAPS 2018)_. AAAI Press.
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Konidaris and Barto (2009) Konidaris, G.; and Barto, A. 2009.  Efficient skill learning using abstraction selection.  In _Twenty-First International Joint Conference on Artificial Intelligence_.
  * Konidaris, Kaelbling, and Lozano-Perez (2018) Konidaris, G.; Kaelbling, L. P.; and Lozano-Perez, T. 2018.  From skills to symbols: Learning symbolic representations for abstract high-level planning.  _Journal of Artificial Intelligence Research_ , 61: 215–289.
  * Lang, Toussaint, and Kersting (2012) Lang, T.; Toussaint, M.; and Kersting, K. 2012.  Exploration in relational domains for model-based reinforcement learning.  _The Journal of Machine Learning Research_ , 13(1): 3725–3768.
  * Lavrac and Dzeroski (1994) Lavrac, N.; and Dzeroski, S. 1994.  Inductive Logic Programming.  In _Logic Programming Workshop_ , 146–160.
  * Li, Walsh, and Littman (2006) Li, L.; Walsh, T. J.; and Littman, M. L. 2006.  Towards a Unified Theory of State Abstraction for MDPs.  _ISAIM_.
  * Loula et al. (2020) Loula, J.; Allen, K.; Silver, T.; and Tenenbaum, J. 2020.  Learning constraint-based planning models from demonstrations.  In _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 5410–5416. IEEE.
  * Loula et al. (2019) Loula, J.; Silver, T.; Allen, K. R.; and Tenenbaum, J. 2019.  Discovering a symbolic planning language from continuous experience.  In _Annual Meeting of the Cognitive Science Society (CogSci)_ , 2193\.
  * Mandalika et al. (2019) Mandalika, A.; Choudhury, S.; Salzman, O.; and Srinivasa, S. 2019.  Generalized lazy search for robot motion planning: Interleaving search and edge evaluation via event-based toggles.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 29, 745–753.
  * Marthi, Russell, and Wolfe (2007) Marthi, B.; Russell, S. J.; and Wolfe, J. A. 2007.  Angelic Semantics for High-Level Actions.  In _ICAPS_ , 232–239.
  * Menon et al. (2013) Menon, A.; Tamuz, O.; Gulwani, S.; Lampson, B.; and Kalai, A. 2013.  A machine learning framework for programming by example.  In _International Conference on Machine Learning_ , 187–195. PMLR.
  * Nguyen et al. (2017) Nguyen, C.; Reifsnyder, N.; Gopalakrishnan, S.; and Munoz-Avila, H. 2017.  Automated learning of hierarchical task networks for controlling minecraft agents.  In _2017 IEEE Conference on Computational Intelligence and Games (CIG)_ , 226–231. IEEE.
  * Ortiz-Haro et al. (2022) Ortiz-Haro, J.; Ha, J.-S.; Driess, D.; and Toussaint, M. 2022.  Structured deep generative models for sampling on constraint manifolds in sequential manipulation.  In _Conference on Robot Learning_ , 213–223. PMLR.
  * Pasula, Zettlemoyer, and Kaelbling (2007) Pasula, H. M.; Zettlemoyer, L. S.; and Kaelbling, L. P. 2007.  Learning symbolic models of stochastic domains.  _Journal of Artificial Intelligence Research_ , 29: 309–352.
  * Ramírez and Geffner (2010) Ramírez, M.; and Geffner, H. 2010.  Probabilistic plan recognition using off-the-shelf classical planners.  In _Twenty-Fourth AAAI Conference on Artificial Intelligence_.
  * Ren, Chalvatzaki, and Peters (2021) Ren, T.; Chalvatzaki, G.; and Peters, J. 2021.  Extended Tree Search for Robot Task and Motion Planning.  _arXiv preprint arXiv:2103.05456_.
  * Silver et al. (2022) Silver, T.; Athalye, A.; Tenenbaum, J. B.; Lozano-Perez, T.; and Kaelbling, L. P. 2022.  Learning Neuro-Symbolic Skills for Bilevel Planning.  In _Conference on Robot Learning_.
  * Silver et al. (2021) Silver, T.; Chitnis, R.; Tenenbaum, J.; Kaelbling, L. P.; and Lozano-Pérez, T. 2021.  Learning symbolic operators for task and motion planning.  In _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 3182–3189. IEEE.
  * Srivastava et al. (2014) Srivastava, S.; Fang, E.; Riano, L.; Chitnis, R.; Russell, S.; and Abbeel, P. 2014\.  Combined task and motion planning through an extensible planner-independent interface layer.  In _2014 IEEE international conference on robotics and automation (ICRA)_ , 639–646. IEEE.
  * Stahl (1993) Stahl, I. 1993.  Predicate invention in ILP—an overview.  In _European Conference on Machine Learning_ , 311–322.
  * Ugur and Piater (2015) Ugur, E.; and Piater, J. 2015.  Bottom-up learning of object categories, action effects and logical rules: From continuous manipulative exploration to symbolic planning.  In _2015 IEEE International Conference on Robotics and Automation (ICRA)_ , 2627–2633. IEEE.
  * Umili et al. (2021) Umili, E.; Antonioni, E.; Riccio, F.; Capobianco, R.; Nardi, D.; and De Giacomo, G. 2021.  Learning a Symbolic Planning Domain through the Interaction with Continuous Environments.  _ICAPS PRL Workshop_.
  * Wang et al. (2021) Wang, Z.; Garrett, C. R.; Kaelbling, L. P.; and Lozano-Pérez, T. 2021.  Learning compositional models of robot skills for task and motion planning.  _The International Journal of Robotics Research_ , 40(6-7): 866–894.
  * Zhang et al. (2020) Zhang, A.; McAllister, R.; Calandra, R.; Gal, Y.; and Levine, S. 2020.  Learning invariant representations for reinforcement learning without reconstruction.  _arXiv preprint arXiv:2006.10742_.
  * Zhi-Xuan et al. (2020) Zhi-Xuan, T.; Mann, J.; Silver, T.; Tenenbaum, J.; and Mansinghka, V. 2020.  Online bayesian goal inference for boundedly rational planning agents.  _Advances in Neural Information Processing Systems_ , 33: 19238–19250.
  * Zhuo et al. (2009) Zhuo, H. H.; Hu, D. H.; Hogg, C.; Yang, Q.; and Munoz-Avila, H. 2009.  Learning HTN method preconditions and action models from partial observations.  In _Twenty-First International Joint Conference on Artificial Intelligence_.

##  Appendix A Appendix

###  A.1 Operator Learning

Here we describe how to learn operators $\Omega$, assuming that the full set
of predicates $\Psi$ is already learned (Chitnis et al. 2022). This method
makes two restrictions on the representation that together lead to very
efficient operator learning (linear time in the number of transitions in
$\mathcal{D}$). First, for each Con and each possible effect set pair
$(\textsc{Eff}^{+},\textsc{Eff}^{-})$, there is at most one operator with that
$(\textsc{Con},\textsc{Eff}^{+},\textsc{Eff}^{-})$. This restriction makes it
impossible to learn multiple operators with different preconditions for the
same controller and effect sets. Second, each parameter in Par must appear in
$\textsc{Par}_{\textsc{Con}},\textsc{Eff}^{+}$, or $\textsc{Eff}^{-}$. This
restriction prevents modeling “indirect effects,” where some object impacts
the execution of a controller without its own state being changed. Though
these two restrictions are limiting, we are willing to accept them because
predicate invention can compensate. For example, an invented predicate can
quantify out an object that does not appear in the controller or the effects,
to capture indirect effects.

With these restrictions established, we learn operators from our
demonstrations $\mathcal{D}$ and predicates $\Psi$ in three steps. Note that
each demonstration can be expressed as a sequence of transitions
$\\{(x,a,x^{\prime})\\}$, with $x,x^{\prime}\in\mathcal{X}$ and
$a\in\mathcal{A}$. First, we use $\Psi$ to Abstract all states $x,x^{\prime}$
in the demonstrations $\mathcal{D}$, creating a dataset of transitions
$\\{(s,a,s^{\prime})\\}$ with $s,s^{\prime}\in\mathcal{S}_{\Psi}$. Next, we
partition these transitions using the following equivalence relation:
$(s_{1},a_{1},s_{1}^{\prime})\equiv(s_{2},a_{2},s_{2}^{\prime})$ if the
effects and partially specified controllers _unify_ , that is, if there exists
a mapping between the objects such that $a_{1}$, $(s_{1}-s_{1}^{\prime})$, and
$(s_{1}^{\prime}-s_{1})$ are equivalent to $a_{2}$, $(s_{2}-s_{2}^{\prime})$,
and $(s_{2}^{\prime}-s_{2})$ respectively. This partitioning step
automatically determines the number of operators that will ultimately be
learned: each equivalence class will induce one operator. Furthermore, the
parameters Par, controller tuple Con, and effects
$(\textsc{Eff}^{+},\textsc{Eff}^{-})$ of the operators can now be established
as follows. For each equivalence class, we create Par by selecting an
arbitrary transition $(s,a,s^{\prime})$ and replacing each object that appears
in the controller or effects with a variable of the same type. This further
induces a substitution $\delta:\textsc{Par}\to\mathcal{O}$ for the objects
$\mathcal{O}$ in this transition; the Con, $\textsc{Eff}^{+}$, and
$\textsc{Eff}^{-}$ are then created by applying $\delta$ to
$a,(s^{\prime}-s)$, and $(s-s^{\prime})$ respectively. By construction, for
all other transitions $\tau$ in the same equivalence class, there exists an
injective substitution $\delta_{\tau}$ under which the controller arguments
and effects are equivalent to the newly created
$\textsc{Con},\textsc{Eff}^{+}$, and $\textsc{Eff}^{-}$. We use these
substitutions for the third and final step of operator learning: precondition
learning. For this, we perform an intersection over all abstract states in
each equivalence class (Bonet and Geffner 2019; Chitnis et al. 2022; Curtis et
al. 2021):
$\textsc{Pre}\leftarrow\bigcap_{\tau=(s,\cdot,\cdot)}\delta^{-1}_{\tau}(s),$
where $\delta^{-1}_{\tau}(s)$ substitutes all occurrences of the objects in
$s$ with the parameters in Par following an inversion of $\delta_{\tau}$, and
discards any atoms involving objects that are not in the image of
$\delta_{\tau}$. By this construction, only the parameters in Par will be
involved in Pre, as desired. With
$\textsc{Par},\textsc{Pre},\textsc{Eff}^{+},\textsc{Eff}^{-}$, and Con now
established for each equivalence class, we have completed the operators
$\Omega$.

Soundness. We note that for any predicates $\Psi$, the operator learning
procedure is _sound_ (Konidaris, Kaelbling, and Lozano-Perez 2018) over the
data, in the following sense: for each transition $\tau=(x,a,x^{\prime})$,
there exists some $\underline{\omega}$, a learned operator ground with objects
in $x$, such that $F(\textsc{Abstract}(x,\Psi),\underline{\omega})$ is defined
and equals $\textsc{Abstract}(x^{\prime},\Psi)$. To see this, recall that
$\tau$ belongs to an equivalence class, and that this equivalence class was
used to learn an operator $\omega$. Now, we show that the desired
$\underline{\omega}$ is $\langle\omega,\delta_{\tau}\rangle$, where
$\delta_{\tau}$ is the injective parameter-to-object substitution defined
above. The $\underline{\textsc{Con}}$, $\underline{\textsc{Eff}^{+}}$, and
$\underline{\textsc{Eff}^{-}}$ of $\underline{\omega}$ exactly equal those in
$\tau$, by construction of the substitution $\delta_{\tau}$. Additionally,
because $\underline{\textsc{Pre}}$ was formed by taking an intersection of
abstract states that included $\textsc{Abstract}(x,\Psi)$, it must be the case
that $\underline{\textsc{Pre}}\subseteq\textsc{Abstract}(x,\Psi)$, since an
intersection must be a subset of every constituent set. By Definition 4, then,
the statement is satisfied. A corollary of this soundness property is that our
learned abstractions are guaranteed to obey the semantics we defined in
Section 3 with respect to the training data.

As a byproduct of operator learning, we have also determined “local” datasets
for each operator, with each transition in the respective equivalence class
defining an example of the operator’s preconditions, controller, and effects.
We will use these local datasets and the corresponding substitutions
$\delta_{\tau}$ during sampler learning Section A.3.

###  A.2 Operator Learning Extended Example

We conclude our discussion of operator learning with an extended example. We
start with a small toy dataset and use it to walk through each of the three
steps in the procedure.

Step 1: Generate Dataset. In this example, our demonstrations contain four
transitions, which are tuples $(x,a,x^{\prime})$. For clarity, we will not
write out the task-level states $x$ and $x^{\prime}$. Additionally, for the
sake of the example, we will assume that in this environment there is only one
controller C, with no discrete arguments. We abstract these states with the
predicate set $\Psi$ includes Held, On, IsPurple, IsRed, IsGreen, IsStowable,
and IsStowed, which leads to four $(s,a,s^{\prime})$ tuples:

  1. 1.

({On$(o_{1},o_{2})$, On$(o_{2},o_{3})$, IsPurple$(o_{1})$},
C$(\theta_{1})$,{Held$(o_{1})$, On$(o_{2},o_{3})$, IsPurple$(o_{1})$})

  2. 2.

({On$(o_{4},o_{5})$, On$(o_{5},o_{6})$, IsRed$(o_{4})$},
C$(\theta_{2})$,{Held$(o_{4})$, On$(o_{5},o_{6})$, IsRed$(o_{4})$})

  3. 3.

({Held$(o_{1})$, IsStowable$(o_{1})$, IsGreen$(o_{2})$},
C$(\theta_{3})$,{IsStowed$(o_{1})$, IsStowable$(o_{1})$, IsGreen$(o_{2})$})

  4. 4.

({Held$(o_{8})$, IsStowable$(o_{8})$, IsGreen$(o_{9})$},
C$(\theta_{4})$,{IsStowed$(o_{8})$, IsStowable$(o_{8})$, IsGreen$(o_{9})$})

Intuitively, the first and second transitions might occur when picking up an
object ($o_{1}$ or $o_{4}$ respectively), while the third and fourth might
occur when stowing an object ($o_{1}$ or $o_{8}$ respectively). We begin by
noting that we can ignore the continuous parameters $\theta_{i}$ of C, since
they do not matter for operator learning (they would be used in sampler
learning).

Step 2: Produce Equivalence Classes. Recall that two transitions are in the
same equivalence class if there exists a mapping between objects such that the
controller, controller discrete arguments, and effects are equivalent. Since
we only have one controller C with no discrete arguments in this example, we
must only check for effect equivalence. The first transition has effects
$(\textsc{Eff}^{+},\textsc{Eff}^{-})=(\\{\texttt{Held}(o_{1})\\},\\{\texttt{On}(o_{1},o_{2})\\})$,
while the second has effects
$(\textsc{Eff}^{+},\textsc{Eff}^{-})=(\\{\texttt{Held}(o_{4})\\},\\{\texttt{On}(o_{4},o_{5})\\})$.
These can be unified with the mapping $\\{o_{1}\leftrightarrow
o_{4},o_{2}\leftrightarrow o_{5}\\}$. Similarly, the third transition has
effects
$(\textsc{Eff}^{+},\textsc{Eff}^{-})=(\\{\texttt{IsStowed}(o_{1})\\},\\{\texttt{Held}(o_{1})\\})$,
while the fourth has effects
$(\textsc{Eff}^{+},\textsc{Eff}^{-})=(\\{\texttt{IsStowed}(o_{8})\\},\\{\texttt{Held}(o_{1})\\})$.
These can be unified with the mapping $\\{o_{1}\leftrightarrow o_{8}\\}$.

Note that in this unification procedure, the atoms which were unchanged, such
as IsPurple$(o_{1})$, do not play a role. Furthermore, the fact that the
objects are the same between transitions 1 and 3 is unimportant, because these
transitions belong to different equivalence classes.

Selecting an arbitrary transition from each equivalence class and substituting
objects with variables, we get the following:

  * •

Equivalence class 1:

    * –

Par: [?x, ?y]

    * –

$\textsc{Eff}^{+}$: {Held(?x)}

    * –

$\textsc{Eff}^{-}$: {On(?x, ?y)}

    * –

Con: $\langle$ C, [] $\rangle$

    * –

Transitions contained: 1 and 2

    * –

$\delta_{1}$ (substitution for transition 1): {?x $\to o_{1}$, ?y $\to o_{2}$}

    * –

$\delta_{2}$ (substitution for transition 2): {?x $\to o_{4}$, ?y $\to o_{5}$}

  * •

Equivalence class 2:

    * –

Par: [?z]

    * –

$\textsc{Eff}^{+}$: {IsStowed(?z)}

    * –

$\textsc{Eff}^{-}$: {Held(?z)}

    * –

Con: $\langle$ C, [] $\rangle$

    * –

Transitions contained: 3 and 4

    * –

$\delta_{3}$ (substitution for transition 3): {?z $\to o_{1}$}

    * –

$\delta_{4}$ (substitution for transition 4): {?z $\to o_{8}$}

Note that the parameter list Par for each equivalence class contains all
parameters that appear in $\textsc{Par}_{\textsc{Con}},\textsc{Eff}^{+}$, or
$\textsc{Eff}^{-}$.

Step 3: Learn Operator Preconditions. We now have all the ingredients of the
operators except for their preconditions. For each transition in each
equivalence class, we first discard any atom from the abstract state $s$ which
involves objects _not_ in the image of that transition’s substitution
$\delta$. For instance, the first transition has $\delta_{1}=$ {?x $\to
o_{1}$, ?y $\to o_{2}$}. The image is $\\{o_{1},o_{2}\\}$, which excludes
$o_{3}$. This means that the atom On$(o_{2},o_{3})$ is discarded from $s$.

After discarding atoms appropriately, we end up with these abstract states for
each transition:

  1. 1.

{On$(o_{1},o_{2})$, IsPurple$(o_{1})$}

  2. 2.

{On$(o_{4},o_{5})$, IsRed$(o_{4})$}

  3. 3.

{Held$(o_{1})$, IsStowable$(o_{1})$}

  4. 4.

{Held$(o_{8})$, IsStowable$(o_{8})$}

Now, the preconditions for each equivalence class are obtained by applying
each $\delta_{i}^{-1}$ to these abstract states and taking intersections. This
produces the final operator set $\Omega$, which does not contain any
extraneous atoms related to object color:

  * •

Operator 1 (from equivalence class 1):

    * –

Par: [?x, ?y]

    * –

Pre: {On(?x, ?y)}

    * –

$\textsc{Eff}^{+}$: {Held(?x)}

    * –

$\textsc{Eff}^{-}$: {On(?x, ?y)}

    * –

Con: $\langle$ C, [] $\rangle$

  * •

Operator 2 (from equivalence class 2):

    * –

Par: [?z]

    * –

Pre: {Held(?z), IsStowable(?z)}

    * –

$\textsc{Eff}^{+}$: {IsStowed(?z)}

    * –

$\textsc{Eff}^{-}$: {Held(?z)}

    * –

Con: $\langle$ C, [] $\rangle$

###  A.3 Learning Samplers

The role of a sampler $\sigma\in\Sigma$ is to _refine_ its associated operator
$\omega$, suggesting continuous parameters of actions that will transition the
environment from a state where the preconditions hold to a state where the
effects follow. Recall that a sampler
$\sigma:\mathcal{X}\times\mathcal{O}^{|\textsc{Par}|}\to\Delta(\Theta)$
defines a conditional distribution $P(\theta\mid x,o_{1},\dots,o_{k})$, where
$\theta$ are continuous parameters for the controller $C$ in $\omega$, and
$(o_{1},\ldots,o_{k})$ represent a set of objects that could be used to ground
$\omega$, with $|\textsc{Par}|=k$. Using the same demonstration dataset
$\mathcal{D}$, we learn samplers of the following form, one per operator:

$\sigma(x,o_{1},\dots,o_{k})=r_{\sigma}(x[o_{1}]\oplus\cdots\oplus x[o_{k}]),$

where $x[o]$ denotes the feature vector for $o$ in $x$, the $\oplus$ denotes
concatenation, and $r_{\sigma}$ is the model to be learned.

To learn samplers, we use the local datasets created during operator learning
(Section A.1), to create datasets for supervised sampler learning, with one
dataset per sampler. Consider any (non-abstract) transition $\tau=(x,a,\cdot)$
in the equivalence class associated with an operator $\omega$. To create a
datapoint for the associated sampler, we can reuse the substitution
$\delta_{\tau}$ found during operator learning to create an input vector
$x[\delta_{\tau}(v_{1})]\oplus\cdots\oplus x[\delta_{\tau}(v_{k})]$, where
$(v_{1},\dots,v_{k})=\textsc{Par}$. The corresponding output for supervised
learning is the continuous parameter vector $\theta$ in the action $a$.

With these datasets created, one could use any method for multidimensional
distributional regression to learn each $r_{\sigma}$. In this work, we learn
two neural networks to parameterize each sampler. The first neural network
takes in $x[o_{1}]\oplus\cdots\oplus x[o_{k}]$ and regresses to the mean and
covariance matrix of a Gaussian distribution over $\theta$; here, we are
assuming that the desired distribution has nonzero measure, but the
covariances can be arbitrarily small in practice. This neural network is a
sampler in its own right, but its expressive power is limited, e.g., to
unimodal distributions. To improve representational capacity, we learn a
second neural network that takes in $x[o_{1}]\oplus\cdots\oplus x[o_{k}]$
_and_ $\theta$, and returns true or false. This classifier is then used to
rejection sample from the first network. To create negative examples, we use
all transitions $\tau^{\prime}$ such that the controller in $\tau^{\prime}$
matches that in Con, but the effects in $\tau^{\prime}$ are different from
$(\textsc{Eff}^{+},\textsc{Eff}^{-})$.

###  A.4 Predicate Grammar Details

Here we detail the grammar over predicate candidates used in our experiments.
Note that the grammar is the same for all environments (up to the object types
and goal predicates).

  * $\bullet$

The base grammar includes two kinds of predicates: all the goal predicates
$\Psi_{G}$, and _single-feature inequality classifiers_. These inequality
classifiers are less-than-or-equal-to expressions that compare a constant
against an individual feature dimension from $\\{1,\ldots,d(\lambda)\\}$, for
some object type $\lambda\in\Lambda$. For the constant, we consider an
infinite stream of numbers in the pattern
$0.5,0.25,0.75,0.125,0.375,0.625,0.875,\ldots$, which represent _normalized_
values of the feature, based on the range of values it takes on across all
states in the dataset $\mathcal{D}$. We use this pattern because we want our
grammar to describe an infinite stream of classifiers, starting from the
median values in $\mathcal{D}$. As an example, a type block might have a
feature dimension corresponding to its size, and a classifier could be
block.size $\leq$ 0.5. All goal predicates have cost 0. All single-feature
inequality classifiers have cost computed based on the normalized constant,
with cost 0 for constant $0.5$, cost 1 for constants $0.25$ and $0.75$, cost 2
for constants $0.125$, $0.375$, $0.625$, $0.875$, etc.

  * $\bullet$

We include all negations of predicates in the base grammar. Negating a
predicate adds a cost of 1.

  * $\bullet$

We include two types of universally quantified predicates over the predicates
thus far: (1) quantifying over all variables, and (2) quantifying over all but
one variable. An example of the first is P() = $\forall$ ?x, ?y . On(?x, ?y),
while an example of the second is P(?y) = $\forall$ ?x . On(?x, ?y).
Universally quantifying adds a cost of 1.

  * $\bullet$

We include all negations of universally quantified predicates. Negating a
predicate adds a cost of 1.

  * $\bullet$

Following prior work (Curtis et al. 2021), we prune out candidate predicates
if they are equivalent to any previously enumerated predicate, in terms of all
groundings that hold in every state in the dataset $\mathcal{D}$. Finally, we
discard the goal predicates $\Psi_{G}$ from the grammar, since they are
included in every candidate predicate set $\Psi$ of our search already.

###  A.5 Additional Environment Details

  * $\bullet$

PickPlace1D. In this toy environment, a robot must pick blocks and place them
onto target regions along a table surface. All pick and place poses are in a
1D line. The three object types are block, target, and robot. Blocks and
targets have two features for their pose and width, and robots have one
feature for the gripper joint state. The block widths are larger than the
target widths, and the goal requires each block to be placed so that it
completely covers the respective target region, so
$\Psi_{G}=\\{\texttt{Covers}\\}$, where Covers is an arity-2 predicate. There
is only one controller, PickPlace, with no discrete arguments; its $\Theta$ is
a single real number denoting the location to perform either a pick or a
place, depending on the current state of the robot’s gripper. Each action
updates the state of at most one block, based on whether any is in a small
radius from the continuous parameter $\theta$. Both training tasks and
evaluation tasks involve 2 blocks, 2 targets, and 1 robot. In each task, with
75% probability the robot starts out holding a random block; otherwise, both
blocks start out on the table. Evaluation tasks require 1-4 actions to solve.
This environment was established by Silver et al. (2021), but that work
involved manually defined state abstractions, which we do not provide in this
paper.

  * $\bullet$

Blocks. In this environment, a robot in 3D must interact with blocks on a
table to assemble them into towers. This is a robotics adaptation of the
blocks world domain in AI planning. The two object types are block and robot.
Blocks have four features: an x/y/z pose and a bit for whether it is currently
grasped. Robots have four features: x/y/z end effector pose and the
(symmetric) value of the finger joints. The goals involve assembling towers,
so $\Psi_{G}=\\{\texttt{On},\texttt{OnTable}\\}$, where the former has arity 2
and describes one block being on top of another, while the latter has arity 1.
There are three controllers: Pick, Stack, and PutOnTable. Pick is
parameterized by a robot and a block to pick up. Stack is parameterized by a
robot and a block to stack the currently held one onto. PutOnTable is
parameterized by a robot and a 2D place pose representing normalized
coordinates on the table surface at which to place the currently held block.
Training tasks involve 3 or 4 blocks, while evaluation tasks involve 5 or 6
blocks; all tasks have 1 robot. In all tasks, all blocks start off in
collision-free poses on the table. Evaluation tasks require 2-20 actions to
solve. This environment was established by Silver et al. (2021), but that work
involved manually defined state abstractions, which we do not provide in this
paper.

  * $\bullet$

Painting. In this challenging environment, a robot in 3D must pick, wash, dry,
paint, and place widgets into either a box or a shelf, as specified by the
goal. The five object types are widget, box, shelf, box lid, and robot.
Widgets have eight features: an x/y/z pose, a dirtiness level (requiring
washing), a wetness level (requiring drying), a color, a bit for whether it is
currently grasped, and the 1D gripper rotation with which it is grasped if so.
Boxes and shelves have one feature for their color. Box lids have one feature
for whether or not they are open. Robots have one feature for the gripper
joint state. The goals involve painting the widgets to be the same color as
either a box or a shelf, and then placing each widget into the appropriate
one, so
$\Psi_{G}=\\{\texttt{InBox},\texttt{InShelf},\texttt{IsBoxColor},\texttt{IsShelfColor}\\}$,
all of which have arity 2 (a widget, and either a box or a shelf). There are
two physical constraints in this environment: (1) placing into a box can only
succeed if the robot is top-grasping a widget, while placing into a shelf can
only succeed if the robot is side-grasping it; (2) a box can only be placed
into if its respective lid is open. There are six controllers: Pick, Wash,
Dry, Paint, Place, and OpenLid. All six are discretely parameterized by a
robot argument; Pick is additionally parameterized by a widget to pick up, and
OpenLid by a lid to open. Pick has 4 continuous parameters: a 3D grasp pose
delta from that widget’s center of mass, and a gripper rotation. Wash, Dry,
and Paint have 1 continuous parameter each: the amount of washing, the amount
of drying, and the desired new color, respectively. Place has 3 continuous
parameters: a 3D place pose corresponding to where the currently held widget
should be placed. Training tasks involve 2 or 3 widgets, while evaluation
tasks involve 3 or 4 blocks; all tasks have 1 box, 1 shelf, and 1 robot. In
each task, with 50% probability the robot starts out holding a random widget;
otherwise, all widgets start out on the table. Also, in each task, with 30%
probability the box lid starts out open. Evaluation tasks require 11-25
actions to solve. This environment was established by Silver et al. (2021),
but that work involved manually defined state abstractions, which we do not
provide in this paper.

  * $\bullet$

Tools. In this challenging environment, a robot operating on a 2D table
surface must assemble contraptions by fastening screws, nails, and bolts,
using a provided set of screwdrivers, hammers, and wrenches respectively. This
environment has physical constraints outside the scope of our predicate
grammar, and therefore tests the learner’s ability to be robust to an
insurmountable lack of downward refinability. The eight object types are
contraption, screw, nail, bolt, screwdriver, hammer, wrench, and robot.
Contraptions have two features: an x/y pose. Screws, nails, bolts, and the
three tools have five features: an x/y pose, a shape, a size, and a bit
indicating whether it is held. Robots have one feature for the gripper joint
state. The goals involve fastening the screws, nails, and bolts onto target
contraptions, so $\Psi_{G}$ includes ScrewPlaced, NailPlaced, BoltPlaced,
ScrewFastened, NailFastened, and BoltFastened. The first three have arity 2 (a
screw/nail/bolt and which contraption it is placed on); the last three have
arity 1. There are three physical constraints in this environment: (1) a
screwdriver can only be used to fasten a screw if its shape is close enough to
that of the screw; (2) some screws have a shape that does not match any
screwdriver’s, and so these screws must be fastened by hand; (3) the three
tools cannot be picked up if their sizes are too large. There are eleven
controllers: Pick{Screw, Nail, Bolt, Screwdriver, Hammer, Wrench}, Place,
FastenScrewWithScrewdriver, FastenScrewByHand, FastenNailWithHammer, and
FastenBoltWithWrench. All eleven are discretely parameterized by a robot
argument; Pick controllers are additionally parameterized by an object to pick
up, and Fasten controllers by a screw/nail/bolt and tool (except
FastenScrewByHand, which does not have a tool argument). Place has 2
continuous parameters: a 2D place pose corresponding to where the currently
held object should be placed, which can be either onto the table or onto a
contraption (only if the currently held object is not a tool). Training tasks
involve 2 screws/nails/bolts and 2 contraptions, while evaluation tasks
involve 2 or 3 screws/nails/bolts and 3 contraptions; all tasks have 3
screwdrivers, 2 hammers, 1 wrench, and 1 robot. Evaluation tasks require 7-20
actions to solve.

###  A.6 Additional Experimental Details

All experiments were conducted on a quad-core Intel Xeon Platinum 8260
processor. All sampler neural networks are fully connected, with two hidden
layers of size 32 each, and trained with the Adam optimizer (Kingma and Ba
2014) for 1K epochs using learning rate 1e-3. The regressor networks are
trained to predict a mean and covariance matrix of a multivariate Gaussian;
this covariance matrix is restricted to be diagonal and PSD with an
exponential linear unit (Clevert, Unterthiner, and Hochreiter 2015). For
training the classifier networks, we subsample data to ensure a 1:1 balance
between positive and negative examples. All AI planning heuristics are
implemented using Pyperplan (Alkhazraji et al. 2020); all experiments use the
LMCut heuristic unless otherwise specified. The planning parameters are
$n_{\text{abstract}}=1000$ for Tools and $8$ for the other environments, and
$n_{\text{samples}}=1$ for Tools and $10$ for the other environments.

###  A.7 Additional Experimental Results

Table 3 provides learning times for all experiments. Tables 4, 5, and 6 report
success rates, nodes created, and wall-clock time respectively for all
evaluation tasks.

Figure 4 analyzes the two main features used by our surrogate objective
function. See caption for further description.

Figure 4: Decomposing the surrogate objective. In these plots, each column
corresponds to one environment. The x-axes correspond to sets of manually
designed predicates. The predicate sets grow in size from left to right,
starting with the goal predicates alone, adding one predicate at each tick
mark, and concluding with the full set of manual predicates for the respective
environment. The order that the predicates are added was determined by hill
climbing with respect to the surrogate objective. The top row shows the
surrogate objective itself; the middle row shows the plan cost error
$|\textsc{Cost}(\hat{\pi})-\textsc{Cost}(\pi^{*})|$ minimized over the first 8
skeletons generated by abstract search; and the bottom row shows the total
number of nodes created by the abstract search (our measure of abstract search
time), cumulative over the 8 skeletons. _There are two key takeaways from this
plot._ (1) The surrogate objective (first row) monotonically decreases in all
environments; this smoothness makes local search over candidate predicate sets
an attractive option. (2) Neither of the two components that make up the
surrogate objective — plan cost error (second row) or abstract search time
(third row) — has the same monotonically decreasing property on its own,
suggesting that both parts are necessary for making our predicate invention
pipeline work. All results are means over 10 seeds.

We now go through each of our four environments, providing an example of
learned predicates and operators from a single seed randomly chosen among
successful ones. We also provide additional statistics for our main method, to
supplement the other results we have provided. Note that the evaluation plan
length statistics are averaged over both 10 seeds and 50 evaluation tasks per
seed, _with standard deviations over seed only_.

#### PickPlace1D

Statistics for our main method, averaged over 10 random seeds (standard
deviations parenthesized):

  * $\bullet$

Average number of predicates in $\Psi$ (both invented and goal predicates):
5.9 (0.54)

  * $\bullet$

Average number of operators in $\Omega$: 2.1 (0.3)

  * $\bullet$

Average plan length during evaluation: 2.44 (0.09)

See Figure 5 for example learned predicates and operators for a randomly
chosen successful seed.

#### Blocks

Statistics for our main method, averaged over 10 random seeds (standard
deviations parenthesized):

  * $\bullet$

Average number of predicates in $\Psi$ (both invented and goal predicates):
6.0 (0.0)

  * $\bullet$

Average number of operators in $\Omega$: 4.0 (0.0)

  * $\bullet$

Average plan length during evaluation: 9.17 (0.69)

See Figure 6 for example learned predicates and operators for a randomly
chosen successful seed.

#### Painting

Statistics for our main method, averaged over 10 random seeds (standard
deviations parenthesized):

  * $\bullet$

Average number of predicates in $\Psi$ (both invented and goal predicates):
22.1 (1.45)

  * $\bullet$

Average number of operators in $\Omega$: 11.2 (0.6)

  * $\bullet$

Average plan length during evaluation: 14.76 (0.29)

See Figures 7 and 8 for example learned predicates and operators for a
randomly chosen successful seed.

#### Tools

Statistics for our main method, averaged over 10 random seeds (standard
deviations parenthesized):

  * $\bullet$

Average number of predicates in $\Psi$ (both invented and goal predicates):
27.4 (4.39)

  * $\bullet$

Average number of operators in $\Omega$: 17.8 (0.98)

  * $\bullet$

Average plan length during evaluation: 10.1 (0.12)

See Figures 9 and 10 for example learned predicates and operators for a
randomly chosen successful seed.

| Ours | Manual
---|---|---
Heuristic | Succ | Node | Time | Succ | Node | Time
LMCut | 98.4 | 2949 | 0.296 | 98.6 | 2941 | 0.251
hAdd | 98.6 | 121.6 | 0.115 | 97.8 | 3883 | 0.235
Table 2: Varying planning heuristic. See text for details. Environment | Ours | Bisimulation | Branching | Boltzmann | GNN Sh | GNN MF | Manual | No Invent
---|---|---|---|---|---|---|---|---
PickPlace1D | 625 (134) | 176 (3) | 219 (145) | 264 (17) | 1951 (85) | 1951 (85) | 177 (147) | 66 (0)
Blocks | 10237 (853) | 800 (44) | 1561 (98) | 9798 (1688) | 4047 (209) | 4047 (209) | 102 (5) | 84 (2)
Painting | 18395 (28153) | 872 (380) | 2883 (144) | 9457 (3421) | 9185 (166) | 9185 (166) | 565 (457) | 260 (2)
Tools | 18666 (2815) | 573 (20) | 5524 (747) | 9716 (1000) | 7362 (197) | 7362 (197) | 167 (3) | 141 (3)
Table 3: Learning times in seconds for all experiments. All numbers are means over 10 seeds, with standard deviations in parentheses. For the GNN-based methods, learning time encompasses training the neural networks. For the other methods, learning time encompasses learning predicates, operators, and samplers (i.e., all components of the abstraction). Even though our main method performs well (Ours), this does come at the cost of increased learning time (although the learning is purely offline). Note that the Manual approach only manually specifies a _state_ abstraction (predicates); operators and samplers must still be learned, contributing to the non-zero learning time. Thus, comparing Ours and Manual shows that the large majority of learning time in our system is spent on predicate invention. Environment | Ours | Bisimulation | Branching | Boltzmann | GNN Sh | GNN MF | Random | Manual | Down Eval | No Invent
---|---|---|---|---|---|---|---|---|---|---
PickPlace1D | 98.6 (1.6) | 98.4 (1.5) | 98.4 (1.5) | 98.4 (1.5) | 100.0 (0.0) | 15.2 (8.7) | 19.2 (5.4) | 98.4 (1.5) | 98.6 (1.6) | 39.6 (4.8)
Blocks | 98.4 (1.5) | 19.0 (4.9) | 98.4 (1.5) | 64.8 (23.5) | 27.8 (4.0) | 35.4 (6.8) | 0.6 (0.9) | 98.6 (1.6) | 98.2 (1.4) | 3.2 (2.0)
Painting | 100.0 (0.0) | 0.0 (0.0) | 20.2 (7.1) | 88.6 (29.7) | 59.2 (17.3) | 0.6 (0.9) | 0.0 (0.0) | 99.6 (0.8) | 98.8 (1.8) | 0.0 (0.0)
Tools | 96.8 (4.7) | 26.2 (5.6) | 75.8 (8.4) | 64.2 (3.7) | 25.6 (9.0) | 22.0 (8.9) | 0.0 (0.0) | 100.0 (0.0) | 42.8 (10.4) | 0.0 (0.0)
Table 4: Percentage of evaluation tasks solved for all experiments. All numbers are means over 10 seeds, with 50 evaluation tasks per seed, and with standard deviations in parentheses. Environment | Ours | Bisimulation | Branching | Boltzmann | Manual | Down Eval | No Invent
---|---|---|---|---|---|---|---
PickPlace1D | 4.8 (0.2) | 4.7 (0.2) | 4.7 (0.2) | 5.3 (0.2) | 6.5 (0.3) | 4.8 (0.2) | 14.1 (4.0)
Blocks | 2948.5 (1293.2) | 46.9 (18.0) | 2948.5 (1293.2) | 7844.0 (6655.4) | 2940.5 (1299.1) | 2948.5 (1293.2) | 427.7 (83.7)
Painting | 501.8 (180.0) |  – | 876.6 (509.7) | 4008.8 (3851.3) | 2607.5 (1117.2) | 489.0 (190.2) |  –
Tools | 1897.2 (1404.0) | 5247.7 (2560.6) | 167.8 (78.4) | 909.9 (174.1) | 4770.9 (886.8) | 152.5 (27.6) |  –
Table 5: Number of nodes created by abstract search during planning in evaluation tasks. All numbers are means over _solved tasks only_ across 10 seeds, with 50 evaluation tasks per seed, and with standard deviations in parentheses. Environment | Ours | Bisimulation | Branching | Boltzmann | GNN Sh | GNN MF | Random | Manual | Down Eval | No Invent
---|---|---|---|---|---|---|---|---|---|---
PickPlace1D | 0.006 (0.0) | 0.006 (0.0) | 0.006 (0.0) | 0.005 (0.0) | 0.436 (0.1) | 0.014 (0.0) | 0.004 (0.0) | 0.045 (0.0) | 0.008 (0.0) | 1.369 (0.6)
Blocks | 0.296 (0.1) | 0.158 (0.1) | 0.284 (0.1) | 0.954 (0.3) | 0.138 (0.1) | 0.249 (0.1) | 0.006 (0.0) | 0.251 (0.1) | 0.318 (0.1) | 1.235 (1.3)
Painting | 0.470 (0.2) |  – | 4.186 (0.9) | 0.600 (0.3) | 2.077 (1.2) | 0.073 (0.0) |  – | 0.464 (0.1) | 0.208 (0.0) |  –
Tools | 0.457 (0.3) | 0.699 (0.3) | 0.109 (0.0) | 0.247 (0.0) | 0.311 (0.2) | 0.043 (0.0) |  – | 0.491 (0.1) | 0.060 (0.0) |  –
Table 6: Total time in seconds for evaluation tasks. These results encompass
planning time (when applicable) and policy or plan inference time (the time
taken to produce an action at each step, given the current state). All numbers
are means over _solved tasks only_ across 10 seeds, with 50 evaluation tasks
per seed, and with standard deviations in parentheses.

###  A.8 Varying the Planner Heuristic

Table 2 shows an additional experiment we conducted where we varied the AI
planning heuristic used by the GenAbstractPlan routine of our bilevel planner
in the Blocks environment. Recall that our predicate invention method uses
GenAbstractPlan as well, so it too is affected by this heuristic change. All
numbers show a mean over 10 seeds. Interestingly, while the gap in performance
is limited when using LMCut, our system shows a massive improvement (over 30x
fewer nodes created) versus Manual when using hAdd. These results are
especially surprising because A∗ with hAdd is generally considered inferior to
other heuristic search algorithms.333We also experimented with GBFS instead of
A∗, and hFF, hSA, and hMax instead of hAdd. A∗ with hAdd performed best.
Inspecting the learned abstractions, we find that our approach invents four
unary predicates with the intuitive meanings Holding, NothingAbove, HandEmpty,
and NotOnAnyBlock, to supplement the given goal predicates On and OnTable.
Comparing these to Manual, which has the same predicates and operators as
those in the International Planning Competition (IPC) (Bacchus 2001), we see
the following differences: Clear is omitted444In the standard encoding,
“clear” means “nothing above and not holding.”, and NothingAbove and
NotOnAnyBlock are added.

We observe that NothingAbove and NotOnAnyBlock are logical transformations of
predicates used in the standard IPC representation. This motivated us to run a
separate, symbolic-only experiment, where we collected IPC blocks world
problems and transformed them to use these learned predicates. We found that
using A∗ and hAdd, planning with our learned representations is much faster
than planning with the IPC representations. For example, in the hardest
problem packaged with Pyperplan, which contains 17 blocks, planning with our
operators requires approximately 30 seconds and 841 node expansions, whereas
planning with the standard encoding requires 560 seconds and 17,795
expansions. We also tried Fast Downward (Helmert 2006) (again with A∗ and
hAdd) on a much harder problem from IPC 2000 with 36 blocks. With our learned
representations, planning succeeds in 12.5 seconds after approximately 7,000
expansions, whereas under the standard encoding the planner fails to find a
plan within a 2 _hour_ timeout. Note that all of these results are specific to
Blocks, A∗, and hAdd, and that is exactly the point: even when using an
unconventional combination of search algorithm and heuristic, our _planner-
aware_ method learns abstractions that optimize the efficiency of the given
planner in the given environment.

Why exactly do our learned predicates and operators outperform the standard
ones when planning with A∗ and hAdd? First, we note that it is highly uncommon
to use hAdd with A∗ in practice with hand-defined PDDL representations,
because hAdd is inadmissible and suffers greatly from overestimation issues
(Bonet and Geffner 2001). Nevertheless, the interesting phenomenon in our work
is that our system is able to _learn an abstraction_ that copes with the
faults of this combination of search algorithm and heuristic. To understand
this further, we make the following observations:

  * •

In both cases, the planner must escape from a local minimum with almost every
pick operation. For example, in a small problem with 5 blocks where the hand
is initially empty, the hAdd values of the states in the plan found are [9,
13, 9, 11, 6, 8, 4, 5, 2, 1, 0] when planning with the standard operators, and
[14, 16, 11, 10, 6, 7, 4, 4, 2, 1, 0] when planning with our learned
operators. Note the alternation of increasing and decreasing values; the ideal
scenario for planning would instead be that these values decrease smoothly.

  * •

In states that follow a pick, the hAdd values consistently _overestimate_ the
true cost-to-go, in both cases. For example, after the first pick with the
standard operators, the hAdd value and true cost-to-go are 13 and 9
respectively; for the learned operators, they are 16 and 9 respectively.

  * •

Here is the main difference: in states that _precede_ a pick, the hAdd values
from the standard operators sometimes _underestimate_ the true cost-to-go. In
the example above, the initial state has an hAdd value of 9, but the true
cost-to-go is 10. In harder problems, these underestimations occur with higher
frequency; for example, in a problem with 20 blocks, there are 8 cases in the
plan found where states preceding picks underestimate the true cost-to-go. In
contrast, the hAdd values from our _learned_ operators do not ever seem to
underestimate the true cost-to-go, in the problems that we analyzed.

  * •

Furthermore, this underestimation occurs regularly in states that are local
minima, immediately preceding states where the heuristic will be an
overestimate, so A∗ struggles greatly. Since nodes are expanded in order of
$f=g+h$, that is, cost of the plan so far plus heuristic value, A∗ will spend
time exploring large subtrees rooted at nodes that underestimate true cost-to-
go before moving onto the nodes that overestimate it, including those that
will ultimately be included in the plan.

For reproducibility, we provide the complete operators used to conduct this
experiment. We started from the standard blocks domain PDDL downloaded from
the planning.domains Github repository, removed the Clear predicate, and added
the two predicates our system learned, with the intuitive meanings
NothingAbove and NotOnAnyBlock. Problem files were updated accordingly. We ran
Fast Downward with the \--search astar(add) option. Here is the domain file,
with changes highlighted in red (deletion) and green (addition):  (define
(domain blocks) (:predicates (on ?v0 ?v1) (ontable ?v0) (clear ?v0)
(nothingabove ?v0) (notonanyblock ?v0) (handempty) (holding ?v0) ) (:action
pick-up :parameters (?x) :precondition (and (clear ?x) (nothingabove ?x)
(notonanyblock ?x) (ontable ?x) (handempty)) :effect (and (not (clear ?x))
(not (ontable ?x)) (not (handempty)) (holding ?x)) ) (:action put-down
:parameters (?x) :precondition (and (holding ?x) (nothingabove ?x)
(notonanyblock ?x)) :effect (and (clear ?x) (not (holding ?x)) (handempty)
(ontable ?x)) ) (:action stack :parameters (?x ?y) :precondition (and (holding
?x) (clear ?y) (nothingabove ?x) (notonanyblock ?x) (nothingabove ?y)) :effect
(and (not (holding ?x)) (not (clear ?y)) (clear ?x) (not (nothingabove ?y))
(not (notonanyblock ?x)) (handempty) (on ?x ?y)) ) (:action unstack
:parameters (?x ?y) :precondition (and (on ?x ?y) (clear ?x) (nothingabove ?x)
(handempty)) :effect (and (holding ?x) (clear ?y) (not (clear ?x))
(nothingabove ?y) (notonanyblock ?x) (not (handempty)) (not (on ?x ?y))) ))

Figure 5: PickPlace1D learned abstractions (top: predicates, bottom:
operators). Figure 6: Blocks learned abstractions (top: predicates, bottom:
operators). Figure 7: Painting learned abstractions (top: predicates, bottom:
operators part 1 of 2). Figure 8: Painting learned abstractions (operators
part 2 of 2). Figure 9: Tools learned abstractions (top: predicates, bottom:
operators part 1 of 2). Figure 10: Tools learned abstractions (operators part
2 of 2).