# Sampling from Pre-Images to Learn Heuristic Functions for Classical Planning

Stefan O’Toole1, Miquel Ramirez2, Nir Lipovetzky 1, Adrian R. Pearce 1

###### Abstract

We introduce a new algorithm, _Regression based Supervised Learning_ (RSL),
for learning per instance Neural Network (NN) defined heuristic functions for
classical planning problems. RSL uses regression to select relevant sets of
states at a range of different distances from the goal. RSL then formulates a
Supervised Learning problem to obtain the parameters that define the NN
heuristic, using the selected states labeled with exact or estimated distances
to goal states. Our experimental study shows that RSL outperforms, in terms of
coverage, previous classical planning NN heuristics functions while requiring
two orders of magnitude less training time.

## Introduction

Heuristics for automated planning can be formulated following a number of
approaches. Heuristics such as Fast-Forward (FF) (Hoffmann and Nebel 2001),
$h\textsuperscript{max}$ and $h\textsuperscript{add}$ (Bonet, Loerincs, and
Geffner 1997) follow from analyzing the structure of many planning instances,
and coming up with a mathematical framework to automatically compute functions
that capture important structural information about instances from the
symbolic descriptions of causal laws (actions) and domain constraints (Helmert
2006). Alternatively, Pattern database (Edelkamp 2014) and _merge-and-shrink_
(Helmert et al. 2007) heuristics are defined as generic functions that
evaluate states by projecting them onto many smaller sub-problems, that are
solved optimally, and combining their solutions in some specific way. These
are chosen on a per-instance basis, and typically involve solving a discrete
optimization problem to select which projection is deemed to be most
informative according to some suitably defined criterion. A third approach has
attracted attention recently, where heuristic functions are searched for in a
family of functions described by a Neural Network (NN) (Ferber et al. 2021;
Ferber, Helmert, and Hoffmann 2020; Shen, Trevizan, and Thiébaux 2020). These
efforts are mainly driven by the suggestive results in Computer Vision and
Reinforcement Learning of novel, general, and scalable stochastic algorithms
for convex optimization to select NN parameters that minimize a suitably
defined notion of _empirical risk_ (Kingma and Ba 2015; Goodfellow, Bengio,
and Courville 2016; Hardt and Recht 2021). Currently, the most successful
methods for learning NN heuristics for classical planning problems require
vast amounts of computational resources for training and are usually
outperformed by heuristics that do not require any offline training time
(Ferber et al. 2021).

In this work, we introduce the _Regression based Supervised Learning_ (RSL)
algorithm in order to learn per instance NN defined heuristic functions. Like
other methods (Ferber et al. 2021; Yu, Kuroiwa, and Fukunaga 2020) do, RSL
selects a set of _regressions_ , trajectories of _sets of states_ , or _pre-
images_ , found via the application of well-known and efficient pre-imaging
operators (Rintanen 2008) that rely on symbolic action descriptions. These
trajectories found along a given regression, always start from the set of goal
states of an instance, and then training states are sampled from each set
along the trajectory. Our method takes many samples from each pre-image found
in a regression, instead of performing many trajectories or longer regressions
to increase the number of training states for the NN, using the observed goal
distances for each pre-image to label the sampled states.

Through a sensitivity analysis over RSL’s hyper-parameters we explore the
impact of its key mechanisms. We also benchmark the NN heuristics learnt by
RSL against existing methods to provide insight into the ability of RSL to
learn effective heuristics. The paper’s contributions are threefold: (1)
introducing a new method for training NN defined heuristic functions, (2)
introducing a new novelty measure for a regression based search, and (3) an
experimental analysis of RSL’s hyper-parameters and components.

## Background

Classical Planning. We consider classical planning problems as defined by the
STRIPS formulation (Fikes and Nilsson 1971). STRIPS defines a planning problem
as the tuple $\Pi=\langle F,O,I,G\rangle$, where $F$ is a set of atoms, $O$ is
a set of actions, $I\subseteq F$ is the initial state and $G\subseteq F$ is
the goal set. Each action $a\in O$ is represented by the tuple $\langle
Add(a),Del(a),Pre(a)\rangle$ which are each a set of atoms over $F$. $Add(a)$
and $Del(a)$ describe the atoms that are added and removed from the state
respectively, and $Pre(a)$ describes the atoms that must be true in a state in
order to apply action $a$. The STRIPS problem $\Pi$ implicitly represents in a
compact form a deterministic transition system (Geffner and Bonet 2013). The
classical planning state-transition model for progression is
$\mathcal{S}(\Pi)=\langle S,s_{0},S_{G},A,f,c\rangle$, where $S\subseteq
2^{F}$, $s_{0}$ is the initial state $I$, $S_{G}$ is the set of goal states
described as the set $\\{s\ |\ s\supseteq G,s\in S\\}$, the actions $a\in
A(s)$ are the actions in $O$ that are applicable in $s$, that is
$Pre(a)\subseteq s$, $f$ is the transition function where for action $a$ and
state $s$, the resulting state is $s^{\prime}=f(a,s)=(s\setminus Del(a))\cup
Add(a)$, and finally $c(a,s)$ is the cost of selecting the transition out of
$s$ via action $a$. The problems we consider in this paper all have a uniform
cost $c(a,s)=1$. A solution for a classical planning problem is a sequence of
actions $a_{0}$,…,$a_{n}$ that select transitions connecting the initial state
$s_{0}$ to a state within the goal set $S_{G}$. The progression state-
transition model can be used to find a solution through a forward search for a
goal state from $s_{0}$.

Heuristics. The objective of the heuristics introduced in this paper is to
approximate the optimal value function $V^{*}$ as described through the
Bellman optimality equation (Bellman 1957),

$\displaystyle V^{*}(s)=\min_{a\in A(s)}\bigg{[}c(a,s)+V^{*}(f(a,s))\bigg{]}$
(1)

for all states $s\not\in S_{G}$ and $V^{*}(s)=0$ for $s\in S_{G}$. Similar to
many of the existing heuristics such as $h\textsuperscript{FF}$ the heuristics
introduced in this paper are not guaranteed to be lower or upper bounds on the
optimal value function.

Regression. Planners can also search backwards from the goal through the
regression state-transition model (Geffner and Bonet 2013). The regression
state-transition model is $R(\Pi)=\langle S,s_{0},S_{G},A,f,c\rangle$, where
$s_{0}$ is the partially assigned state $G$, the goal set $S_{G}$ is the set
$\\{s\ |\ s\subseteq I,s\in S\\}$, $A(s)$ are the actions in $O$ that are
relevant and consistent for the partial state $s$, that is $Add(a)\cap
s\not=\emptyset$ and $Del(a)\cap s=\emptyset$, and the state transition
function to pre-image state $s$ is $f(a,s)=(s\setminus Add(a))\cup Pre(a)$. A
key difference between the regression and progression state-transition models
is that the regression model searches over partial truth assignments, which
represent sets of states as opposed to complete truth-assignments. For the
progression state-transition model every atom not in a state is false, while
for the regression state-transition model the atoms not in a state are simply
undefined. From this point forward we refer to such “partial states” as _pre-
images_ and denote them as $x$ to distinguish them from complete truth-
assignment state denoted as $s$. The regression model is required to search
over pre-images $x\subseteq F$ as the initial pre-image $x_{0}$ coincides with
the set of goal states from the progression state-transition model $S_{G}$.
Regression operators also compute _weaker preconditions_ so the only atoms
being asserted in a pre-image $x$ are those in the precondition $Pre(a)$,
while retracting any commitments on the truth value of atoms in $Add(a)$.
Conversely, the progression state model will always search over full states
$s\in\mathcal{S}(\Pi)$ as $I$ prescribes the truth value of every atom, and
the progression transition function $f(a,s)$ provides an explicit mapping
between states $s,s^{\prime}\in\mathcal{S}(\Pi)$.

Supervised Learning. In this paper we take advantage of the pre-images
explored by a regression search in order to sample a set of training states
labelled with approximations $\tilde{V}$ of $V^{*}$ (Equation 1), to learn a
heuristic defined through a NN using a Supervised Learning (SL) algorithm.

SL is a common approach for creating predictors from data samples through
empirical risk minimisation (Hardt and Recht 2021) with a goal of generalising
to out-of-sample data. That is, the objective of SL given a function class
$\mathcal{H}\subseteq\mathcal{X}\to\mathcal{Y}$ and a set of data samples
$(\bar{x}_{1},y_{1}),(\bar{x}_{2},y_{2}),\ldots,(\bar{x}_{i},y_{i})$ is
defined as,

$\displaystyle\min_{h\in\mathcal{H}}\frac{1}{n}\sum_{i=1}^{n}{\mathit{loss}}(h(\bar{x}_{i}),y_{i})$
(2)

In this paper, ${\cal H}$ is a NN, each $h\in{\cal H}$ is a unique set of NN
parameters $\theta$, training examples $\bar{x}_{i}$ are states $s$, and
labels $y_{i}$ are cost-to-go estimates $\tilde{V}$ between $s$ and $S_{G}$.

Per-instance heuristics. Ferber et al. (2021) describe two different methods
for learning heuristics for classical planning problems. The first is _per
domain_ learning, where a heuristic is learnt that is applicable to any
instance of a particular domain, where a domain defines a set of action
schemas and predicates which are used to formulate instances $\Pi$. Our paper
focuses on the second framework introduced by Ferber et al. (2021), which is
to learn instance-based heuristics. That is, given some instance
$\mathcal{S}(\Pi)$ with initial state $s_{0}$, we seek heuristics $h$ that
apply to instances $\mathcal{S}(\Pi_{1})$, $\mathcal{S}(\Pi_{2})$, …,
$\mathcal{S}(\Pi_{i})$ where all the instances $\mathcal{S}(\Pi_{i})$ share
all structural elements with $\mathcal{S}(\Pi)$ but initial states. That is,
each $\mathcal{S}(\Pi_{i})$ features a distinct initial state $s^{i}_{0}$,
which is reachable from $s_{0}$ in $\mathcal{S}(\Pi)$. Our objective in this
work is to efficiently, in terms of computation time, create a data sample of
states labelled with $\tilde{V}$ such that an optimisation of the NN
parameters $\theta$ using Equation 2 generalises to the population set of
states $s^{i}_{0}$ reachable from $s_{0}$ .

## Related Work

Ferber et al. (2020) introduce a method, Teacher-based Supervised Learning
(TSL), that constructs a training set out of states found in the trace of the
execution of plans from a teacher planner. TSL performs 200 step random walks
from the initial state of an instance and then uses a Greedy Best First Search
(GBFS) with $h$FF to search for a plan. The states along the solution path (if
found) are labeled with an estimate of their distance from the goal according
to the solution. TSL then performs Supervised Learning (SL) on the states and
goal-distance estimates to learn a heuristic.

Yu et al. (Yu, Kuroiwa, and Fukunaga 2020) introduced an alternative SL method
for learning per-instance heuristic functions. Yu et al.’s algorithm (SING)
performs backwards depth-first searches (DFS) with fixed node expansion
budgets, to search from fully assigned randomly sampled goal states $s_{g}\in
S_{G}$. SING then uses SL on states visited within the DFS labeled with the
depth at which the states were visited for an estimate of their goal distance.

The algorithm we introduce in this work differs from both TSL and SING in a
number of ways. First, RSL samples training states through a regression over
partially assigned states starting from the goal rather than a DFS starting at
a fully assigned goal state (SING) or a forward search from the instance’s
initial state (TSL). Second, RSL additionally samples random states that are
added to the training set. Third, for goal distance estimates TSL uses a
teacher planner and SING uses the depth at which the state was visited while
RSL uses the tightest upper bound found for the state’s goal distance derived
through the pre-images visited by a number of regressions. Last, as RSL
searches and labels goal distance estimates over pre-images, it samples many
different training states from each pre-image.

More recently Ferber et al. (2021) introduced three new NN heuristics. Two of
the approaches introduced, $h$Boot and $h$BExp, are based on the idea of
training a heuristic on successively harder to solve states (Arfaee, Zilles,
and Holte 2011). $h$Boot and $h$BExp, perform regressions from the goal
following random walks, and solve using GBFS with the current $h$Boot or
$h$BExp heuristic from a fully assigned state randomly sampled from the pre-
image discovered by the regression. $h$Boot uses the plan’s length while
$h$BExp uses the number of states expanded by GBFS as the state training
labels for the estimated goal distance. $h$Boot and $h$BExp use the states and
labels to iteratively train their NNs, and once the GBFS is solving 95% of the
states found from the regressions, the maximum length of the regression is
doubled. Ferber et al. (2021) also introduced the $h$AVI heuristic which is
trained using approximate value iteration. $h$AVI, also discovers states
through regressions but instead of solving for the state, $h$AVI performs
Bellman updates on a 2 step lookahead from the state, evaluating the leaf
states of the lookahead with the current $h$AVI heuristic or as 0 if they are
goal states. Ferber et al.’s motivation for these Active Learning (AL)
approaches verse SL ones is that SL is limited to instances small enough for
training data generation.

Beyond learning per-instance NN defined heuristics, Shen et al.’s (2020)
STRIPS Hypergraphs Networks (HGNs) learns per-domain and even domain
independent NN defined heuristics. In this work we do not focus on domain
independent NN defined heuristic functions, but we do compare against a
STRIPS-HGN heuristic trained in a per-domain framework as described by Ferber
et al. (2021).

In this paper we also explore a version of the RSL algorithm that aims to
maximise the structural diversity of the states in its selected sample. Width-
based planning is one method that has been particularly effective in
increasing the structural diversity of states considered during search
(Lipovetzky and Geffner 2012; Lipovetzky, Ramírez, and Geffner 2015; Frances
et al. 2017; Katz et al. 2017). Width-based planning prunes states considered
as non-novel by a defined measure. The original width-based measure introduced
by Lipovetzky et al. (2012) is that the novelty of a state is evaluated by the
smallest tuple of atoms $t\subseteq s$, where $s$ is the first state that
makes $t$ true in the search. Inspired by the success of the width-based
novelty algorithms in classical planning, both in progression and regression
(Lei and Lipovetzky 2021), we create and experiment with a new novelty based
regression algorithm.

## Regression Based Supervised Learning

Given a planning problem $\Pi=\langle F,O,I,G\rangle$, RSL produces a training
set ${\cal{D}}=\\{(s_{1},h_{1}),\dots(s_{N},h_{N})\\}$ which is a set of
states $s\in S$ paired with goal distance estimates $h$. To produce
${\cal{D}}$ RSL performs $N_{r}$ rollouts, each starting at the goal $G$ and
applying $L$ times the classical planning regression operator. Each rollout
from $G$ is a sequence of actions $\pi^{j}=(a^{j}_{i})_{i=0}^{L-1}$, for
$j=1,\ldots,N_{r}$. Each $\pi^{j}$ produces a sequence of pre-images
$x^{j}_{0},x^{j}_{1},\ldots,x^{j}_{L}$, where $x^{j}_{0}=G$ and
$x^{j}_{i}\subseteq F$. The sequence of pre-images denotes a sequence of sets
of states $\mathcal{R}^{j}=X^{j}_{0},X^{j}_{1},\ldots,X^{j}_{L}$, where
$X^{j}_{i}=\\{s\ |\ x^{j}_{i}\subseteq s,s\in S\\}$. See Figure 1 for an
example of this mapping of a pre-image represented by a partial truth
assignment into its corresponding set of fully assigned states. By the
definition of the regression operator, $X^{j}_{i-1}$ corresponds with the
_pre-image_ , conditioned on $a^{j}_{i-1}$, of $X^{j}_{i}$. Therefore any
state within $X^{j}_{i}$ can be reached from $X^{j}_{i-1}$ by applying action
$a^{j}_{i-1}$. It follows that any state within $X^{j}_{i}$ can reach
$X^{j}_{0}$ in at most $i$ transitions. Using this observation, RSL labels
each state $s$ within its training set of states, $T_{s}$, with

$\displaystyle d(s)=\mbox{min}(i\ |\ s\in X^{j}_{i},j\in\\{1,\ldots,N_{r}\\})$
(3)

that is, the smallest goal distance estimate of any of the state sets visited
by the regressions which $s$ is also a member of.

Algorithm 1 Overview of the RSL Algorithm

Input: $\Pi$
Parameter: $P_{r},L,N_{r},N_{t},\mu$
Output: $h$RSL

1: $\mathcal{R}\leftarrow\textsc{regression}(\Pi,L,N_{r},\mu$)

2: $T_{s}\leftarrow\textsc{sample\\_states}(\mathcal{R},P_{r},N_{t})$

3: $\cal{D}\leftarrow\textsc{label}(\mathcal{R},T_{s})$

4: $h$RSL$\leftarrow\textsc{supervised\\_learning}(\cal{D})$

Algorithm 1, provides an overview of RSL. The hyper-parameters of RSL are the
length of each regression $L$, the number of regressions to perform $N_{r}$,
the number of training states to use $N_{t}$, the percentage of training
states that are randomly sampled from the entire state space $P_{r}$, and a
function that maps state regression trajectories into novelty levels $\mu$.
RSL has three distinct steps, 1: extracting sets of state sets,
$\mathcal{R}=\bigcup_{j=1}^{N_{r}}\mathcal{R}^{j}$, through performing
regressions from the goal set (Alg. 1 line 1), 2: sampling training states
$T_{s}$ and labeling them with goal distance estimates using (3) (Alg. 1 lines
2-3), and 3: training the NN defined heuristic function (Alg. 1 line 4) using
empirical risk minimisation (2).

Figure 1: An example rollout performed by N-RSL with $L=2$ on a 3 block
Blocksworld problem. Each square represents a per-image through a partially
assigned state with its assigned atoms written within the square. The purple
squares represent the example rollout trajectory selected by N-RSL and the
possible Blocksworld states for each pre-image along the trajectory are shown
on the left. Green atoms are atoms assigned for the first time in the
trajectory, and the $\mu^{+}$ value is calculated using Equation 7.

### Extracting state sets through regression

As previously explained RSL performs $N_{r}$ regressions to extract the set of
state sets $\mathcal{R}$ over which the training set $\mathcal{D}$ is defined.
At step $i$ of a rollout with a pre-image $x^{j}_{i}$ corresponding to the set
of states $X^{j}_{i}$, as previously defined, the actions we consider valid
for pre-imaging $X^{j}_{i}$ with are $a\in\nu(x^{j}_{i})$, defined as follows

$\displaystyle\begin{aligned} \nu(x^{j}_{i})=\\{a\
&|\;a\in\textsc{reachable}(O,I),\\\
&\;x^{j}_{i}\cap\mbox{e-Del}(a)=\emptyset,\\\
&\;x^{j}_{i}\cap\mbox{Del}(a)=\emptyset,x^{j}_{i}\cap\mbox{Add(a)}\neq\emptyset\\}\end{aligned}$
(4)

and e-Del$(a)$ is

$\displaystyle\begin{aligned} \mbox{e-Del}(a)=\\{\ q\ |&\ q\in F\setminus
Add(a),\\\ &\exists{p\in Pre(a)}:\textsc{mutex}(p,q)\\}.\end{aligned}$ (5)

$\textsc{reachable}(O,I)$ maps the operator set $O$ and initial state $I$ to
the set of actions with reachable preconditions in the delete relaxation of
$\Pi$ (Bonet and Geffner 2001) given the initial state of the progression
state-transition model $I$. The $\textsc{mutex}(p,q)$ function in (5) maps the
pair of atoms ($p$, $q$) to true if $p$ and $q$ are mutually exclusive, that
is, it is impossible for $p$ and $q$ to both be true in any state $s\in S$
that can be reached from $I$. Note that the Ferber et al. (2021) algorithms
that use regression also filter the valid actions in the same way through
using the mutex groups and applicable operations found by the Fast Downward
(FD) (Helmert 2006) Translator111See the is_valid_walk parameter in line 848
in code/src/search/task_utils/sampling_technique.cc in Ferber et al.’s (2021)
Supplementary Material available at https://zenodo.org/record/5345958 .

The baseline option for performing the rollout, and the method used by Ferber
et al. (2021), is to randomly select actions $a$ for which applying the
regression operator is valid. In addition to testing RSL using random action
selection we instantiate a version of RSL we name Novelty guided Regression
based Learning (N-RSL) that aims to increase the structural diversity of
operators selected in its regression.

#### Preferring actions with novel preconditions

For N-RSL at step $i$ of a rollout with a pre-image $x^{j}_{i}$, and a state
trajectory of $\tau=G,x^{j}_{1},\ldots,x^{j}_{i}$, N-RSL uses the novelty
function $\mu$ to select the action $a_{i}$ to pre-image $X^{j}_{i}$.

$\displaystyle\begin{aligned} a_{i}=\mbox{argmax}_{a}\\{\mu(a,\tau)\ |\
a\in\nu(x^{j}_{i})\\}\end{aligned}$ (6)

where ties are broken randomly and $\nu(x^{j}_{i})$ is a set of valid actions
as described above. Note that for the plain RSL algorithm, which uses random
action selection, $\mu=\mu(a,\tau)=0$ for any $a\in O$ and any state
trajectory $\tau$.

In order to increase the structural diversity of the states in sets
$X^{j}_{i}$ in ${\cal R}^{j}$ we consider how the pre-images $x^{j}_{i}$
evolve as we repeatedly apply the regression operator. At each step $i$ of the
regression we have a set of valid operators $\nu(x^{j}_{i})$ and a state set
$X^{j}_{i}$ derived from the pre-image $x^{j}_{i}\subseteq F$, where
$x^{j}_{0}=G$. We propose increasing the structural diversity of the sets
extracted by counting the number of atoms an action will assign as true in a
pre-image for the first time in the current trajectory. In order to apply this
criterion, $\mu$ in (6) is replaced by $\mu^{+}$ below,

$\displaystyle\begin{aligned}
\mu^{+}(a,\tau)=|Pre(a)\setminus\bigcup_{x^{j}_{i}\in\tau}x^{j}_{i}|\end{aligned}$
(7)

This $\mu^{+}$ measure means N-RSL prefers actions with pre-conditions which
contain atoms that are not specified in the goal $G$ and are not a member of
the pre-condition set of any of the actions executed in the trajectory up
until that point. Note that $\mu^{+}$ relies only on the current trajectory
and is independent of any previously executed regression trajectories. Figure
1 shows an example of a rollout performed on a simple Blocksworld problem with
the one-step lookahead method described by (6) using the measure $\mu^{+}$
defined in (7).

### Sampling and Labeling Training Data

The training data for RSL is sampled from the sets of states $\mathcal{R}$.
States are sampled from each set $X_{i}^{j}\in{\cal R}$, and sampled states
that contain mutex atom pairs $(p,q)$ are modified by removing either the $p$
or $q$ atom from the state. Note that if a sampled state from the set
$X_{i}^{j}$ has a mutex pair $(p,q)$ and $p\in x_{i}^{j}$, $q$ will be removed
from the state, that is, an atom that is a member of the partial state
$x_{i}^{j}$ that a state is sampled from will never be removed from the state.
As previously described, the labelled heuristic value for a sampled state is
given by $d(s)$, which returns the distance of the closest state set in
$\mathcal{R}$ to the goal according to the regression.

As we report later, some domains benefited from adding randomly sampled states
from $S$. The random states have mutexes enforced using the same method as
above, and are also labeled with $d(s)$. In the case that the state is not a
member of any of the sets of states in $\mathcal{R}$, we define $d(s)$ to
equal $L+1$.

######  Theorem 1.

Given a problem $\Pi=\langle F,O,I,G\rangle$, N-RSL obtains a training set
$\cal{D}$ in $\mathcal{O}(|F|(|O|N_{r}L+N_{t}LN_{r}))$ time and
$\mathcal{O}(|F|(N_{r}L+N_{t}))$ space.

###### Proof sketch.

RSL performs $N_{r}$ rollouts and by definition the number of state
transitions in each $\pi^{j}$ is $L$. For each state transition the one step
lookahead (Equation 6) considers a maximum of $|O|$ actions and $|O|$ pre-
images. Therefore the total number of pre-images considered by RSL is
$L\times|O|\times N_{r}$. Note that both $L$ and $N_{r}$ are set as constant
hyper-parameters and for each pre-image a maximum of $|F|$ atoms need to be
considered by the novelty definition $\mu^{+}$, therefore the regression
algorithm has a time complexity of $\mathcal{O}(|F||O|N_{r}L)$. Also for each
pre-image a maximum of $|F|$ atoms need to be assigned, hence regression runs
in $\mathcal{O}(|F|N_{r}L)$ space. Sampling states requires the assignment of
at most $|F|\times N_{t}$ atoms and checking a state’s membership requires at
most $|F|\times N_{t}\times L\times N_{r}$ comparisons meaning both the
sample_states and label algorithms run in $\mathcal{O}(|F||O|N_{r}L)$ time and
$\mathcal{O}(|F|N_{t})$ space. ∎

Given the training set, $\cal{D}$, any suitable off-the-shelf SL algorithm can
be used to obtain a heuristic estimator through optimising the SL objective
function (2). We discuss the specifics of one such algorithm in our
Experimental Study.

## Experimental Study

The experimental study of RSL has two objectives: (1) evaluate the effect of
the different mechanisms within the RSL algorithm, and (2) provide a direct
comparison to existing NN and model-based heuristic functions.

### Methodology

Our benchmark set of domains, instances and initial states is the same as
Ferber et al. (2021). As we are learning per instance heuristics, a unique
heuristic is trained for each problem instance and then evaluated over a set
of 50 different initial states. The 50 initial states were produced by Ferber
et al. (2020; 2021), through performing 50 $200$-step random-walks from the
original initial state of the instance. The benchmark instances have also been
separated by Ferber et al. (2020; 2021) into “Moderate Tasks”, which are
solved by GBFS guided by $h$FF in less than 900 seconds but more than 1
second, and “Hard Tasks” which are not solved within 900 seconds.

We evaluate $h$RSL heuristic using the same method as Ferber et al. (2021).
Each heuristic is evaluated over 50 different initial states guiding GBFS
implemented in FD (Helmert 2006). It is known that a lack of accuracy in
heuristics can lead to blow ups in the size of search trees (Helmert, Röger et
al. 2008), therefore we can test the relative accuracy of the heuristics by
using them in the GBFS and comparing their coverage. The coverage of a planner
is defined as the percent of initial states for which a solution path is found
within the given planning budget. Ferber et al. (2021) report observing that
in general the coverage superiority between the different NN heuristics tested
did not vary over time. That is, the planning time used and the relative
coverage superiority between the algorithms were not correlated. Given this
observation and constraints on our available compute resources we reduce the
overall 10 hour planning time-limit that Ferber et al. used by 99% down to
just 6 minutes, and compare with the NN defined heuristic baseline algorithms
results as provided by Ferber et al. (2021) which use the 10 hour planning
time-limit.

As our results are run on different hardware and Ferber et al.’s algorithms
use the Keras (Chollet et al. 2015) and the TensorFlow (Abadi et al. 2015)
libraries to train and evaluate their NN while we use PyTorch (Paszke et al.
2019), we preformed a comparison of the evaluations per second used for
commonly solved instances between Ferber et al.’s (2021) methods and $h$N-RSL.
Ferber et al.’s algorithms use the same NN architecture meaning that for the
same instance, and assuming the relationship between evaluations and planning
time is linear, the evaluations per second should be similar. The data logs
provided by Ferber et al. only provide the number of evaluations completed by
FD if the problem is solved, therefore we can only compare the ratios of
commonly solved instances. Depending on the domain the ratios averaged between
0.3 to 16.1, meaning $h$RSL’s evaluations per second were sometimes less but
could also be up to 16.1 times higher. A full table of the minimum, maximum
and average ratios found for each domain and algorithm can be found in the
Supplementary Material. We also benchmark on our hardware an implementation of
the SING (Yu, Kuroiwa, and Fukunaga 2020) algorithm which Ferber et al. (2021)
did not test and has not previously been applied to this benchmark set.
Details of our implementation of the SING algorithm are provided in the
Supplementary Material. Finally, we ran the baselines that do not require
offline training, $h$FF and LAMA, on our hardware with the 6 minute time
budget.

We define each $h$RSL heuristic through the same NN architecture used by
Ferber et al. (2021). The NN is a _residual network_ (He et al. 2016) made up
of two dense 250 neuron layers followed by a single residual block with two
dense 250 neuron layers followed by a single neuron output. Each neuron in the
NN uses the rectified linear activation function. The inputs of the NN are
full states of $S(\Pi)$ represented by a Boolean vector $\\{0,1\\}^{|F|}$. As
Ferber et al. do, we set the $loss$ function of the SL optimization problem
(2) to be the _mean squared error_ (MSE). We use the Adam (Kingma and Ba 2015)
stochastic optimization algorithm to find locally optimal solutions of (2),
using the following hyper-parameters: learning rate is $10^{-4}$, batch size
is $64$, and maximum number of epochs is set to $1,000$. Additionally, we use
the _early stopping_ heuristic (Duvenaud, Maclaurin, and Adams 2016) setting
the _patience_ parameter to $2$. We split each instance data set into training
and validations sets, taking the former $80$% and the latter $20$% of
available samples.

Figure 2: A summary of the average coverage over the “Moderate” and “Hard” tasks for 16 different configurations of RSL. The 4 boxes each show a different segmentation of the 16 configurations according to the value of a single hyper-parameter. Each configuration’s coverage is marked with a blue dot and the lines show the range of coverage over the configurations with the mean marked with a square. | Ave. over Trials | Methods using Validation |  |
---|---|---|---|---
Planning Budget | 6 minutes | 6 minutes | 600 minutes* | 6 minutes
|  $h$RSL |  $h$N-RSL |  $h$RSL |  $h$N-RSL |  $h$Boot |  $h$BExp |  $h$AVI |  $h$TSL |  $h$HGN |  $h$FF | LAMA
Moderate Tasks |  |
blocks | 80.0 | 91.5 | 99.2 | 100 | 18.0 | 0.0 | 0.0 | 80.4 | 100 | 100 | 100
depot | 48.7 | 58.8 | 77.0 | 89.0 | 60.3 | 32.7 | 54.7 | 90.3 | 0.0 | 93.7 | 99.3
grid | 71.0 | 60.3 | 100 | 97.0 | 100 | 100 | 51.0 | 93.0 | 0.0 | 90.0 | 100
npuzzle | 15.3 | 18.9 | 25.2 | 46.8 | 28.0 | 0.0 | 1.0 | 0.0 | 0.3 | 92.8 | 97.8
pipesworld | 70.7 | 69.6 | 85.8 | 82.6 | 57.8 | 68.4 | 50.2 | 92.2 | 7.6 | 63.0 | 98.6
rovers | 12.6 | 12.5 | 15.0 | 15.8 | 48.2 | 21.8 | 45.0 | 26.0 | 14.0 | 79.5 | 100
scanalyzer | 87.4 | 94.1 | 100 | 100 | 33.3 | 70.7 | 67.3 | 82.7 | 11.0 | 91.7 | 100
storage | 16.1 | 16.4 | 17.0 | 18.0 | 89.0 | 57.5 | 69.5 | 24.5 | 0.0 | 27.5 | 34.0
transport | 74.8 | 70.8 | 100 | 93.8 | 100 | 100 | 87.5 | 99.2 | 94.7 | 100 | 100
visitall | 93.6 | 95.4 | 99.7 | 98.0 | 55.3 | 0.0 | 0.0 | 0.0 | 100 | 89.0 | 100
Average | 57.0 | 58.8 | 71.9 | 74.1 | 59.0 | 45.1 | 42.6 | 58.8 | 32.8 | 82.7 | 93.0
Average Train Time/Inst. (Hr) | 0.37 | 0.38 | 3.68 | 3.75 | 112* | 13.1* | -
Hard Tasks |  |
blocks | 18.5 | 45.3 | 36.4 | 68.0 | 0.0 | 0.0 | 0.0 | 0.0 | 50.0 | 46.4 | 96.0
depot | 4.0 | 3.3 | 14.6 | 12.6 | 8.3 | 4.3 | 12.9 | 35.4 | 0.0 | 9.4 | 69.4
grid | 21.9 | 32.1 | 67.2 | 69.0 | 87.8 | 95.0 | 70.5 | 60.2 | 0.0 | 31.0 | 100
npuzzle | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 5.8 | 12.8
pipesworld | 27.4 | 25.0 | 33.8 | 33.1 | 23.4 | 19.1 | 8.0 | 48.7 | 0.0 | 20.4 | 68.0
rovers | 0.0 | 0.1 | 0.1 | 0.1 | 2.8 | 0.8 | 6.5 | 1.5 | 0.3 | 8.3 | 100
scanalyzer | 86.4 | 89.7 | 100 | 100 | 3.3 | 0.0 | 60.7 | 60.0 | 0.0 | 83.3 | 100
storage | 3.7 | 2.5 | 1.8 | 0.2 | 27.2 | 13.2 | 15.8 | 0.0 | 0.0 | 9.2 | 9.0
transport | 0.0 | 1.2 | 0.0 | 8.8 | 0.0 | 0.0 | 2.4 | 0.0 | 0.0 | 0.0 | 59.6
visitall | 82.4 | 91.8 | 100 | 100 | 28.0 | 0.0 | 0.0 | 0.0 | 100 | 40.0 | 100
Average | 24.4 | 29.1 | 35.4 | 39.2 | 18.1 | 13.3 | 17.7 | 20.6 | 15.0 | 25.4 | 71.5
Average Train Time/Inst. (Hr) | 0.69 | 0.69 | 6.88 | 6.88 | 112* | 10.4* | -
Table 1: Comparison of the coverage of $h$RSL with other Neural Network
defined heuristics functions introduced by Ferber et al. (2021) $h$Boot,
$h$BExp, $h$AVI, as well as the $h$TSL introduced by Ferber et al. (2020), and
$h$HGN from Shen et al. (2020). The table also shows the coverage of
$h$ff(Hoffmann and Nebel 2001) and LAMA (Richter and Westphal 2010) (run on
same hardware as RSL). Note that $h$HGN trains one heuristic per domain not
instance with training budgets between 14.7 and 112 CPU hours. The bold
numbers indicate the highest coverage among the Neural Network methods. *Note
that the baseline learning methods that use a 600 minute planning budget are
the values as reported by Ferber et al. (2021). According to standard single
thread CPU benchmarks, our vCPU can be 20% faster. We provide a discussion of
the impact of discrepancies in hardware and software in the Methodology
Section.

Due to computational constraints we do not tune the architecture or any
training parameters of the NN. Note that Ferber et al.’s TSL method trains 10
heuristics functions and selects the best performing heuristic on a set of
validation states. We follow this method by running RSL 10 times with
different random seeds on each instance to produce 10 heuristic functions. We
then test each heuristic over a set of validation states, which are collected
using the same method as Ferber et al. (2021), to select the best performing
heuristic for each instance. We report both the average coverage of the 10
heuristics learnt and the best heuristic found via the validation method.

Expansions
---
|  |
Plan Length
|  |
Figure 3: Pairwise comparisons over commonly solved tasks between $h$N-RSL
using the validation method, and the best performing baseline NN based
heuristic function $h$TSL and model-based methods $h$FF and LAMA over the
“Hard Tasks” benchmark set. The top row shows the scatter plot of the number
of expansions used by each search algorithm while the bottom row shows the
plan length found by each algorithm. The percentage value, shown in the axis
titles, is the percentage of the commonly solved tasks that the relevant
algorithm required fewer expansions or discovered a shorter plan than the
algorithm it is being compared to. Note that tasks which are not solved by at
least one of the algorithms in the pair are not included in these graphs.
Graphs were generated using Downward Lab (Seipp et al. 2017). Figure 4: The
number of heuristic evaluations per second versus the number of relevant atoms
as determined by FD translator’s reachability analysis for a set of commonly
solved problem instances between $h$RSL, $h$FF and LAMA. Each dot represents
the values for a single problem instance and the line represents the moving
average with a window size of 2000 atoms.

Training is run simultaneously for 80 instances over 40 Intel®Xeon®Gold 6138
CPU @ 2.00GHz processor cores with 720GB of shared RAM, limiting each training
instance to run on a single vCPU (each CPU core has 2 vCPUs). For training the
$h$RSL heuristic, the Tarski framework (Francés and Ramírez 2021) is used to
ground each problem instance in order to get the $F$,$O$, and $G$ sets used
for the regressions. In line with the $h$Boot, $h$BExp, $h$AVI and $h$SL
heuristics, the FD translator is used for identifying a set of state mutexes
to enforce, for both the state sampling and valid actions for the regression
operator as described in the previous Section. For evaluation we use the same
hardware, along with Downward lab (Seipp et al. 2017) to run 80 FD searches at
once limiting each FD search to run on a single vCPU with a maximum of 3.8 GB
of memory. The PyTorch library (Paszke et al. 2019) is used for the training
and evaluations of RSL’s NN. The RSL code, result files and additional
implementation details are included in the Supplementary Material.

### Results

First we present the results from a grid search over the hyper-parameters of
RSL. To maximise the number of hyper-parameter combinations we could test with
our limited computational resources, we evaluated each trained heuristic from
the grid search on 10 out of the 50 initial states for each of the 143
instances in the benchmark set. Figure 2 summarises the impact of each of the
hyper-parameter values tested on the average coverage of $h$RSL across the
benchmark set. For the hyper-parameter grid search we tested 16 different
settings over the different combinations of $N_{t}=$10,000 or 100,000,
$P_{r}=$ 0 or 50, $N_{r}=$ 1 or 5, and $L=$ 50 or 500. The Supplementary
Material includes a table detailing the different configurations tested along
with their average coverage over each domain. Figure 2 shows that the value of
$P_{r}$ has the biggest influence on the average coverage over the benchmark
set of $h$RSL used in GBFS. This observation shows the importance of including
states in the training set that are not within any of the sets of states
visited by the rollouts from the goal set. Figure 2 also suggests that RSL
benefits from using more than one rollout for extracting training states and
considering 500 applications of the regression operator instead of 50.
Interestingly, Figure 2 shows that training with 10,000 or 100,000 states does
not influence the performance in an obvious way. However, overall the best
performing set of hyper-parameters over the “Hard Tasks” which we use for all
experiments from this point forth are $N_{t}=$100,000, $P_{r}=$50, $N_{r}$=5,
and $L=$500.

Table 1 shows a comparison of existing methods with respect to RSL and N-RSL,
using the best performing configuration from the hyper-parameter grid search.
The SING algorithm is omitted from Table 1 due to poor performance but its
results are included in the Supplementary Material. The first notable
difference is the average training times used by each algorithm. $h$RSL
without validation uses less than 1% of the training CPU time used by all the
other per-instance NN defined heuristics functions for both the “Moderate” and
“Hard” task sets. Even when using the validation method which requires 10 RSL
executions the training time used is less than 7% of the per-instance NN
methods. The overall average coverage over the benchmark set shows that $h$RSL
and $h$N-RSL outperform the other NN defined heuristic functions for the “Hard
Tasks” with and without using the validation method. $h$RSL and $h$N-RSL when
using the validation method also outperform the other NN heuristics on the
“Moderate Tasks”. The model-based method LAMA clearly dominates all other
methods. The model-based heuristic $h$FF also outperforms $h$RSL and $h$N-RSL
on the “Moderate Tasks”, however on the “Hard Tasks” $h$RSL with validation
and $h$N-RSL with and without validation have better overall performance.
While $h$N-RSL has better average coverage than $h$RSL the difference is small
with a 1.8% and 4.7% average improvement over the “Moderate” and “Hard Tasks”
respectively when no validation is used.

Figure 3 provides additional insights into the performance of $h$N-RSL
compared to the best performing baseline algorithms. For commonly solved
tasks, $h$TSL on average produces higher quality plans than $h$N-RSL. This
observation could be a result of $h$TSL having higher quality labels used in
training. $h$TSL uses $h$FF with GBFS to label sampled states in the train
set, while $h$N-RSL labels states with goal distance estimates derived from
the state sets visited by N-RSL’s regressions. The objective of $h$FF with
GBFS is to find the shortest path from a state to the goal state, while the
objective of N-RSL’s regression is to maximise a defined novelty measure
(Equation 6) with the aim of finding the shortest path that visits the most
number of reachable atoms $a\in F$. This trade-off between exploration and
exploitation shows through in the results where $h$N-RSL has a higher coverage
than $h$TSL over a diverse set of initial states but produces lower quality
plans in terms of plan length among the commonly solved tasks. This behaviour
is also displayed when comparing directly to the $h$FF heuristic, while LAMA
dominates $h$N-RSL in both coverage and plan quality.

Figure 4 shows that for smaller problem instances the model-based methods
$h$FF, and LAMA are able to compute a higher number of evaluations per second
than $h$RSL. However, $h$RSL’s evaluations per second stays relatively
constant while the model-based methods evaluations per second decreases as
problem instances become larger.

## Discussion

The heuristic values from the NN defined heuristic functions we report in this
paper are calculated by taking the linear combination of the outputs of the
last hidden layer of the NN. We note that the NN heuristics discussed in this
paper and those of Ferber et al. (2020; 2021) are an application of _state
aggregation_ (Bertsekas 2018), a well-known technique in Approximate Dynamic
Programming. For each of the different problem instances we explored in this
paper, the size of the last hidden layer was fixed at 250 neurons. It is
possible that for harder problem instances a feature vector larger than 250 is
required in order to produce more useful heuristics. Ferber et al. (2020) have
performed an investigation into effects of the NN architecture in terms of the
activation functions used and the number of hidden layers, however they did
not explore the number of neurons used within the hidden layers. One avenue of
future work is to investigate the impact of scaling the number of neurons used
within the hidden layers of the NN so the capacity (Goodfellow, Bengio, and
Courville 2016) of the NN scales too with the size of the planning instance.

However, one advantage we observed of the NN heuristic functions over the
model-based heuristics in Figure 4 is that the gap in number of evaluated
states per second narrows until it eventually disappears, so the NN heuristic
becomes significantly faster in comparison (and less informed too, probably)
as the problem size increases. This is because only the input layer size
changes according to $|F|$ for the NN architecture used in this work, while
the rest of the neurons and edges remain constant. That is, as the input layer
has $|F|$ neurons and the first hidden layer has 250 neurons there are
$|F|\times 250$ edges joining the two layers resulting in the NN evaluations
being in $O(|F|)$ time. Conversely, $h$FF requires completing a search over
the problem with the delete relaxation which has time-complexity that is
polynomial over the number of actions and reachable atoms (Hoffmann and Nebel
2001).

Future work should investigate NN heuristics like $h$RSL over problems that
are too large for $h$FF or LAMA to produce enough evaluations per second to be
useful. It is possible that a NN defined heuristic function will be able to
produce a large enough number of evaluations per second to be useful over
these large domains, even if the heuristic is less informed than the model-
based heuristics. Last, we have shown that $h$RSL and $h$N-RSL have good
performance while requiring significantly smaller resources than the NN-based
baselines considered in the paper. We think that this encouraging result
supports the assumption that RSL and follow-up methods can be used to obtain
useful heuristic functions for large instances of challenging combinatorial
optimization problems.

## References

  * Abadi et al. (2015) Abadi, M.; Agarwal, A.; Barham, P.; Brevdo, E.; Chen, Z.; Citro, C.; Corrado, G. S.; Davis, A.; Dean, J.; Devin, M.; Ghemawat, S.; Goodfellow, I.; Harp, A.; Irving, G.; Isard, M.; Jia, Y.; Jozefowicz, R.; Kaiser, L.; Kudlur, M.; Levenberg, J.; Mané, D.; Monga, R.; Moore, S.; Murray, D.; Olah, C.; Schuster, M.; Shlens, J.; Steiner, B.; Sutskever, I.; Talwar, K.; Tucker, P.; Vanhoucke, V.; Vasudevan, V.; Viégas, F.; Vinyals, O.; Warden, P.; Wattenberg, M.; Wicke, M.; Yu, Y.; and Zheng, X. 2015.  TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems.  Software available from tensorflow.org.
  * Arfaee, Zilles, and Holte (2011) Arfaee, S. J.; Zilles, S.; and Holte, R. C. 2011.  Learning heuristic functions for large state spaces.  _Artificial Intelligence_ , 175(16-17): 2075–2098.
  * Bellman (1957) Bellman, R. 1957.  _Dynamic Programming_.  Princeton University Press.
  * Bertsekas (2018) Bertsekas, D. P. 2018.  Feature-based aggregation and deep reinforcement learning: A survey and some new implementations.  _IEEE/CAA Journal of Automatica Sinica_ , 6(1): 1–31.
  * Bonet and Geffner (2001) Bonet, B.; and Geffner, H. 2001.  Planning as heuristic search.  _Artificial Intelligence_ , 129(1): 5–33.
  * Bonet, Loerincs, and Geffner (1997) Bonet, B.; Loerincs, G.; and Geffner, H. 1997.  A robust and fast action selection mechanism for planning.  In _AAAI/IAAI_ , 714–719.
  * Chollet et al. (2015) Chollet, F.; et al. 2015.  Keras.  https://keras.io.
  * Duvenaud, Maclaurin, and Adams (2016) Duvenaud, D.; Maclaurin, D.; and Adams, R. 2016.  Early stopping as nonparametric variational inference.  In _Artificial Intelligence and Statistics (AISTATS)_ , 1070–1077.
  * Edelkamp (2014) Edelkamp, S. 2014.  Planning with pattern databases.  In _Sixth European Conference on Planning_ , 84–90.
  * Ferber et al. (2021) Ferber, P.; Geiber, F.; Trevizan, F.; Helmert, M.; and Hoffmann, J. 2021.  Neural Network Heuristic Functions for Classical Planning: Reinforcement Learning and Comparison to Other Methods.  In _2nd PRL Workshop, International Conference on Automated Planning and Scheduling_.
  * Ferber, Helmert, and Hoffmann (2020) Ferber, P.; Helmert, M.; and Hoffmann, J. 2020.  Neural network heuristics for classical planning: A study of hyperparameter space.  In _European Conference on Artificial Intelligence_ , 2346–2353.
  * 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.
  * Francés and Ramírez (2021) Francés, G.; and Ramírez, M. 2021.  Tarski - An AI Planning Modeling Framework.  https://github.com/aig-upf/tarski.
  * Frances et al. (2017) Frances, G.; Ramírez, M.; Lipovetzky, N.; and Geffner, H. 2017.  Purely declarative action descriptions are overrated: Classical planning with simulators.  In _International Joint Conference on Artificial Intelligence_ , 4294–4301.
  * Geffner and Bonet (2013) Geffner, H.; and Bonet, B. 2013.  A concise introduction to models and methods for automated planning.  _Synthesis Lectures on Artificial Intelligence and Machine Learning_ , 8(1): 1–141.
  * Goodfellow, Bengio, and Courville (2016) Goodfellow, I.; Bengio, Y.; and Courville, A. 2016.  _Deep learning_.  MIT press.
  * Hardt and Recht (2021) Hardt, M.; and Recht, B. 2021.  _Patterns, predictions, and actions: A story about machine learning_.  https://mlstory.org.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep residual learning for image recognition.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 770–778.
  * Helmert (2006) Helmert, M. 2006.  The fast downward planning system.  _Journal of Artificial Intelligence Research_ , 26: 191–246.
  * Helmert et al. (2007) Helmert, M.; Haslum, P.; Hoffmann, J.; et al. 2007.  Flexible Abstraction Heuristics for Optimal Sequential Planning.  In _International Conference on Automated Planning and Scheduling_ , 176–183.
  * Helmert, Röger et al. (2008) Helmert, M.; Röger, G.; et al. 2008.  How Good is Almost Perfect?.  In _AAAI_ , volume 8, 944–949.
  * Hoffmann and Nebel (2001) Hoffmann, J.; and Nebel, B. 2001.  The FF planning system: Fast plan generation through heuristic search.  _Journal of Artificial Intelligence Research_ , 14: 253–302.
  * Katz et al. (2017) Katz, M.; Lipovetzky, N.; Moshkovich, D.; and Tuisov, A. 2017.  Adapting novelty to classical planning as heuristic search.  In _International Conference on Automated Planning and Scheduling_ , 172–180.
  * Kingma and Ba (2015) Kingma, D. P.; and Ba, J. 2015.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations_.
  * Lei and Lipovetzky (2021) Lei, C.; and Lipovetzky, N. 2021.  Width-Based Backward Search.  In _International Conference on Automated Planning and Scheduling_ , 219–224.
  * Lipovetzky and Geffner (2012) Lipovetzky, N.; and Geffner, H. 2012.  Width and Serialization of Classical Planning Problems.  In _European Conference on Artificial Intelligence_ , 540–545.
  * Lipovetzky, Ramírez, and Geffner (2015) Lipovetzky, N.; Ramírez, M.; and Geffner, H. 2015.  Classical planning with simulators: results on the Atari video games.  In _International Joint Conference on Artificial Intelligence_ , 1610–1616.
  * Paszke et al. (2019) Paszke, A.; Gross, S.; Massa, F.; Lerer, A.; Bradbury, J.; Chanan, G.; Killeen, T.; Lin, Z.; Gimelshein, N.; Antiga, L.; Desmaison, A.; Kopf, A.; Yang, E.; DeVito, Z.; Raison, M.; Tejani, A.; Chilamkurthy, S.; Steiner, B.; Fang, L.; Bai, J.; and Chintala, S. 2019.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  In _Advances in Neural Information Processing Systems 32_ , 8024–8035.
  * Richter and Westphal (2010) Richter, S.; and Westphal, M. 2010.  The LAMA planner: Guiding cost-based anytime planning with landmarks.  _Journal of Artificial Intelligence Research_ , 39: 127–177.
  * Rintanen (2008) Rintanen, J. 2008.  Regression for classical and nondeterministic planning.  In _European Conference on Artificial Intelligence_ , 568–572.
  * Seipp et al. (2017) Seipp, J.; Pommerening, F.; Sievers, S.; and Helmert, M. 2017.  Downward Lab.  https://doi.org/10.5281/zenodo.790461.
  * Shen, Trevizan, and Thiébaux (2020) Shen, W.; Trevizan, F.; and Thiébaux, S. 2020.  Learning domain-independent planning heuristics with hypergraph networks.  In _International Conference on Automated Planning and Scheduling_ , 574–584.
  * Yu, Kuroiwa, and Fukunaga (2020) Yu, L.; Kuroiwa, R.; and Fukunaga, A. 2020.  Learning Search-Space Specific Heuristics Using Neural Network.  _12th HSDIP Workshop, International Conference on Automated Planning and Scheduling_ , 1–8.

## Supplementary Material

## Additional RSL Implementation Details

For the NN training we use the Adam optimizer (Kingma and Ba 2015) with a
learning rate of $10^{-4}$, initial decay rates of $\beta^{1}=0.9$ and
$\beta^{2}=0.999$, and $\epsilon=10^{-8}$. Additionally we use a batch size of
64, a maximum of 1,000 training epochs, and early stopping with a patience of
2, using a split of training samples of 80-20 for training and validation,
respectively.

## Comparison of Evaluations per Second of Baseline Results

Table 3 shows the evaluations per second ratios between our $h$RSL
FastDownward runs and the baseline algorithms run by Ferber et al. (2021).

## SING Implementation Details

We implemented the configuration C4 of the SING algorithm (Yu, Kuroiwa, and
Fukunaga 2020) as described by Yu et al. but using the same NN architecture,
loss function and training hyper-parameters as used for RSL. $10^{5}$ samples
were used for training, which were collected using a budget of 500 samples per
DFS resulting in 200 total DFS rollouts.

## Additional Results

The results for our implementation of SING are shown in Table 2. The
performance of SING is very poor compared to the results of the other
baselines shown in Table 1 in the main paper. We also performed individual
runs of instances using SING with the same NN architecture, loss function,
number of training samples, and number of samples per DFS as d escribed by Yu
et al. (2020), however the performance observed was still poor. Yu et al.
mention that they perform manual tuning of hyper-parameters but do not provide
the selected parameters used by the NN training algorithm, which could be the
reason for the poor performance observed in our results.

Table 4 shows the results of each configuration tested in the RSL hyper-
parameter grid search.

| Moderate Tasks | Hard Tasks
---|---|---
blocks | 17.6 | 0.8
depot | 0.0 | 0.0
grid | 0.0 | 0.0
npuzzle | 0.0 | 0.0
pipesworld | 13.8 | 0.1
rovers | 6.2 | 0.0
scanalyzer | 16.7 | 0.0
storage | 0.0 | 1.0
transport | 0.0 | 0.0
visitall | 1.3 | 0.0
Average | 5.6 | 0.2
Average Train Time/Inst. (Hr) | 1.6 | 2.6
Table 2: Coverage of the heuristic learnt by SING (as detailed in the “SING
Implementation Details” Section) in GBFS using a planning time limit of 6
minutes.

|  $h$Boot |  $h$BExp |  $h$AVI |  $h$TSL
---|---|---|---|---
| Ave | Min | Max | Ave | Min | Max | Ave | Min | Max | Ave | Min | Max
blocks | 1.2 | 0.7 | 5.0 | - | - | - | - | - | - | 2.3 | 0.4 | 6.8
depot | 1.2 | 0.8 | 1.4 | 1.2 | 1.0 | 1.5 | 1.2 | 0.9 | 2.5 | 3.9 | 0.7 | 9.9
grid | 3.1 | 0.6 | 43.8 | 1.3 | 0.5 | 12.7 | 15.8 | 0.7 | 79.8 | 13.2 | 4.2 | 80.5
npuzzle | 1.1 | 0.8 | 2.3 | - | - | - | 1.5 | 1.0 | 2.5 | - | - | -
pipesworld | 1.4 | 0.3 | 8.0 | 1.4 | 0.7 | 10.8 | 1.4 | 0.3 | 19.7 | 7.8 | 0.8 | 82.6
rovers | 14.6 | 0.9 | 70.1 | 15.3 | 0.9 | 72.3 | 16.1 | 0.9 | 85.6 | 13.7 | 0.3 | 43.4
scanalyzer | 1.1 | 0.1 | 23.2 | 0.3 | 0.03 | 0.9 | 1.2 | 0.1 | 9.5 | 8.6 | 0.2 | 45.8
storage | 1.5 | 0.8 | 4.5 | 1.3 | 0.8 | 2.0 | 1.2 | 0.8 | 1.6 | 3.3 | 1.0 | 6.4
transport | 1.3 | 0.8 | 3.8 | 1.1 | 0.9 | 1.7 | 1.0 | 0.7 | 2.9 | 5.0 | 0.6 | 11.2
visitall | 0.9 | 0.4 | 1.5 | - | - | - | - | - | - | - | - | -

Table 3: Ratios of evaluations per second of our $h$RSL verse the baseline
methods run by Ferber et al. (2021)

for commonly solved instances.

$N_{t}$ | 10,000 | 100,000
---|---|---
$P_{r}$ | 0 | 50 | 0 | 50
$N_{r}$ | 1 | 5 | 1 | 5 | 1 | 5 | 1 | 5
$L$ | 50 | 500 | 50 | 500 | 50 | 500 | 50 | 500 | 50 | 500 | 50 | 500 | 50 | 500 | 50 | 500
Moderate Tasks
blocks | 0.0 | 58.4 | 20.8 | 99.2 | 99.2 | 93.6 | 92.4 | 100.0 | 0.0 | 60.0 | 0.0 | 99.6 | 94.8 | 99.6 | 100.0 | 98.8
depot | 0.0 | 0.3 | 20.3 | 12.3 | 59.7 | 61.3 | 79.3 | 79.3 | 2.3 | 0.0 | 0.7 | 1.7 | 34.3 | 43.7 | 69.3 | 51
grid | 0.0 | 0.0 | 0.0 | 1.0 | 21.0 | 84.0 | 50.0 | 40.0 | 0.0 | 0.0 | 0.0 | 5.0 | 16.0 | 9.0 | 1.0 | 48
npuzzle | 0.0 | 0.0 | 0.0 | 0.0 | 0.2 | 28.8 | 1.2 | 28.8 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 17.2 | 1.2 | 34.8
pipesworld-nt | 11.8 | 15.8 | 17.6 | 23.6 | 28.6 | 41.4 | 27.2 | 48 | 21.6 | 26 | 31.4 | 23.4 | 27 | 41 | 30 | 39
rovers | 6.5 | 6.2 | 6.5 | 7.2 | 11.5 | 3 | 12.5 | 12.8 | 6.5 | 6.2 | 4.5 | 5.2 | 7.5 | 1.8 | 10 | 8.5
scanalyzer | 100.0 | 65.3 | 100.0 | 87 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0
storage | 0.0 | 0.0 | 12 | 0.0 | 24.5 | 7 | 24 | 0.0 | 1 | 0.0 | 7 | 0.0 | 8.0 | 0.0 | 29 | 35.5
transport | 8.2 | 0.0 | 11.5 | 42.8 | 98.8 | 97 | 99.2 | 100.0 | 0.0 | 0.0 | 1.8 | 32.8 | 49 | 70.8 | 62.8 | 84.8
visitall | 0.0 | 13 | 4.3 | 94 | 86.7 | 92 | 92 | 100.0 | 0.0 | 5 | 1.7 | 79 | 17.3 | 80.7 | 26.7 | 99
Average | 12.7 | 15.9 | 19.3 | 36.7 | 53.0 | 60.8 | 57.8 | 60.9 | 13.1 | 19.7 | 14.7 | 34.7 | 35.4 | 46.4 | 43.0 | 59.9
Hard Tasks
blocks | 0.0 | 0.0 | 0.0 | 18.4 | 41.6 | 44.4 | 34.4 | 34.4 | 0.0 | 0.0 | 0.0 | 12.8 | 27.6 | 42 | 24 | 41.2
depot | 0.0 | 0.0 | 0.0 | 0.0 | 6 | 8 | 13.1 | 8.3 | 0.0 | 0.0 | 0.0 | 0.0 | 0.3 | 5.4 | 4.9 | 10.6
grid | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 8 | 0.2 | 0.8 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 5.2
npuzzle | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
pipesworld-nt | 0.1 | 0.1 | 0.8 | 4.5 | 5.3 | 8.6 | 5.5 | 12.1 | 2.2 | 5.4 | 4.4 | 8.1 | 4.8 | 12.4 | 8.8 | 8.8
rovers | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.1 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
scanalyzer | 48 | 34 | 83.3 | 66 | 100.0 | 96.7 | 100.0 | 100.0 | 66.7 | 54 | 98.7 | 81.3 | 100.0 | 70.7 | 100.0 | 100.0
storage | 0.0 | 0.0 | 0.0 | 0.0 | 6.8 | 8 | 8.2 | 0.0 | 0.0 | 0.0 | 2.5 | 3 | 0.8 | 0.2 | 2 | 12.5
transport | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 3.6 | 0.0 | 14 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.8
visitall | 0.0 | 0.0 | 0.0 | 10 | 0.0 | 6 | 8 | 100.0 | 0.0 | 0.0 | 0.0 | 2 | 0.0 | 44 | 0.0 | 100
Average | 4.81 | 3.41 | 8.41 | 9.89 | 15.97 | 18.33 | 16.94 | 26.97 | 6.89 | 5.94 | 10.56 | 10.72 | 13.35 | 17.47 | 13.97 | 27.91
Table 4: Comparison of the coverage given a 6 minute planning time budget of
$h$RSL using a range of different hyper-parameter values. Each run uses only a
single trial and is evaluated over 10 of the 50 initial states for each
instance in the benchmark set.