N coNTIME coNSPACE coNPSPACE EXPTIME NEXPTIME coNEXPTIME NEXPSPACE coNEXPSPACE
ASPACE ATIME APSPACE AEXPTIME AEXPSPACE

#  Learning Domain-Independent Heuristics for Grounded and Lifted Planning

Dillon Z. Chen,1,2 Sylvie Thiébaux,1,2 Felipe Trevizan1

###### Abstract

We present three novel graph representations of planning tasks suitable for
learning domain-independent heuristics using Graph Neural Networks (GNNs) to
guide search. In particular, to mitigate the issues caused by large grounded
GNNs we present the first method for learning domain-independent heuristics
with only the lifted representation of a planning task. We also provide a
theoretical analysis of the expressiveness of our models, showing that some
are more powerful than STRIPS-HGN, the only other existing model for learning
domain-independent heuristics. Our experiments show that our heuristics
generalise to much larger problems than those in the training set, vastly
surpassing STRIPS-HGN heuristics.

##  1 Introduction

Graph Neural Networks (GNNs) have recently attracted the interest of the
planning community, for learning heuristic cost estimators, task orderings,
value functions, action policies, and portfolios, to name a few (Shen,
Trevizan, and Thiébaux 2020; Garg, Bajpai, and Mausam 2020; Karia and
Srivastava 2021; Ståhlberg, Bonet, and Geffner 2022a; Ma et al. 2020; Sharma
et al. 2022; Teichteil-Königsbuch et al. 2023). GNNs exhibit great
generalisation potential, since once trained, they offer outputs for any
graph, regardless of size or structure. Representing the structure of planning
domains as graphs, GNNs can train on a set of small problems to learn
generalised policies and heuristics that apply to all problems in a domain. As
noted by Shen, Trevizan, and Thiébaux (2020), this also allows for learning
heuristics applicable to multiple domains, or even domain-independent
heuristics that apply to domains unseen during training.

In this paper, we explore the use of GNNs for learning both domain-dependent
and domain-independent heuristics for classical planning, with an emphasis on
the latter. To the best of our knowledge, STRIPS-HGN (Shen, Trevizan, and
Thiébaux 2020) is the only existing model designed to learn domain-independent
heuristic functions from scratch. The models in (Ståhlberg, Bonet, and Geffner
2022a) are inherently domain-dependent, given that they use different update
functions for predicates of the planning problems, and hence cannot generalise
to unseen problems with a different number of predicates. Neural Logic
Machines (Dong et al. 2019; Gehring et al. 2022) are also domain-dependent
models as they assume a maximum arity of input predicates.

STRIPS-HGN has several drawbacks when learning domain-independent heuristics:
(1) its hypergraph representation of planning tasks ignores delete lists and
thus cannot theoretically learn $h^{*}$, (2) its aggregation function is not
permutation invariant due to ordering the neighbours of each node which may
prevent it from generalising effectively, (3) it assumes a bound on the sizes
of action preconditions and effects, meaning that it also has to discard
certain edges in its hypergraph in its message updating step, and (4) it
requires constructing the whole grounded hypergraph, whose size becomes
impractical for large problems.

Our contributions remedy these issues and make the following advances to the
state of the art. Building on well-known planning formalisms, namely
propositional STRIPS, FDR, and lifted STRIPS, we define novel grounded and
lifted graph representations of planning tasks suitable for learning domain-
independent heuristics. In particular, this results in the first domain-
independent GNN heuristic based on a lifted graph representation. We also
establish the theoretical expressiveness of Message-Passing Neural Networks
(MPNN) acting upon our graphs in terms of the known domain-independent
heuristics they are able to learn, and suggest further research directions for
learning $h^{*}$.

We then conduct two sets of experiments to complement our theory and evaluate
the effectiveness of learned heuristics. The first set aims to measure the
accuracy of learned heuristics on unseen tasks, while the second set evaluates
the effectiveness of such learned heuristics for heuristic search. Planners
guided by heuristics learnt using our new graphs solve significantly larger
problems than those considered by Shen, Trevizan, and Thiébaux (2020), Karia
and Srivastava (2021) and Ståhlberg, Bonet, and Geffner (2022b). In the
domain-dependent setting, planners guided by our lifted heuristics achieves
greater coverage than using $h^{\operatorname*{FF}}$ in several domains and
returns lower cost plans overall.

##  2 Background and Notation

#### Planning

A classical planning task (Geffner and Bonet 2013) is a state transition model
$\Pi=\langle S,A,s_{0},G\rangle$ consisting of a set $S$ of states, a set $A$
of actions, an initial state $s_{0}$, and a set $G$ of goal states. Each
action $a\in A$ is a function $a:S\to S\cup{\bot}$ mapping a state $s$ in
which the action is applicable to its successor $a(s)$, and states in which it
is not applicable to $\bot$. The cost of the action is $c(a)\in{\mathbb{N}}$.
A solution or a _plan_ in this model is a sequence of actions
$\pi=a_{1},\ldots,a_{n}$ such that $s_{i}=a_{i}(s_{i-1})\neq\bot$ for all
$i\in\\{1,\dots,n\\}$ and $s_{n}\in G$. In other words, a plan is a sequence
of applicable actions which when executed, progresses our initial state to a
goal state. The cost of $\pi$ is $c(\pi)=\sum_{i=1}^{n}c(a_{i})$. A planning
task is _solvable_ if there exists at least one plan. We now describe three
ways to represent planning tasks.

A _STRIPS planning task_ is a tuple $\Pi=\left<P,A,s_{0},G\right>$ with $P$ a
set of propositions (or facts), $A$ a set of actions, $s_{0}\subseteq P$ an
initial state, and $G\subseteq P$ the goal condition. A state $s$ is a subset
of $P$ and is a goal state if $G\subseteq s$. An action $a\in A$ is a tuple
$\left<\operatorname*{pre}(a),\operatorname*{add}(a),\operatorname*{del}(a)\right>$
with
$\operatorname*{pre}(a),\operatorname*{add}(a),\operatorname*{del}(a)\subseteq
P$ and $\operatorname*{add}(a)\cap\operatorname*{del}(a)=\emptyset$, and has
an associated cost $c(a)\in\mathbb{R}$. The action is applicable in a state
$s$ if $\operatorname*{pre}(a)\subseteq s$, and leads to the successor state
$s^{\prime}=(s\setminus\operatorname*{del}(a))\cup\operatorname*{add}(a)$.

An _FDR planning task_ (Helmert 2009) is a tuple
$\Pi=\left<\mathcal{V},A,s_{0},s_{\star}\right>$ where $\mathcal{V}$ is a
finite set of state variables $v$, each with a finite domain $D_{v}$. A fact
is a pair $\left<v,d\right>$ where $v\in\mathcal{V},d\in D_{v}$. A partial
variable assignment is a set of facts where each variable appears at most
once. A total variable assignment is a partial variable assignment where each
variable appears once. The initial state $s_{0}$ is a total variable
assignment and the goal condition $s_{\star}$ is a partial variable
assignment. Again, $A$ is a set of actions of the form
$a=\left<\operatorname*{pre}(a),\operatorname*{eff}(a)\right>$ where
$\operatorname*{pre}(a)$ and $\operatorname*{eff}(a)$ are partial variable
assignments. An action $a$ is applicable in $s$ if
$\operatorname*{pre}(a)\subseteq s$, and leads to the successor state
$s^{\prime}=(s\cup\operatorname*{eff}(a))\setminus\\{\left<v,d\right>\in
s\mid\exists d^{\prime}\in
D_{v},\left<v,d^{\prime}\right>\in\operatorname*{eff}(a)\wedge
d\not=d^{\prime}\\}.$

A _lifted planning task_ (Lauer et al. 2021) is a tuple
$\Pi=\left<\mathcal{P},\mathcal{O},\mathcal{A},s_{0},G\right>$ where
$\mathcal{P}$ is a set of first-order predicates, $\mathcal{A}$ is a set of
action schema, $\mathcal{O}$ is a set of objects, $s_{0}$ is the initial state
and $G$ is the goal condition. A predicate $P\in\mathcal{P}$ has parameters
$x_{1},\ldots,x_{n_{P}}$ for $n_{P}\in{\mathbb{N}}$, noting that $n_{P}$
depends on $P$ and it is possible for a predicate to have no parameters. A
predicate with $n$ parameters is an $n$-ary predicate. A predicate can be
instantiated by assigning some of the $x_{i}$ with objects from $\mathcal{O}$
or other defined variables. A predicate where all variables are assigned with
objects is grounded, and is called a ground proposition. The initial state and
goal condition are sets of ground propositions. An action schema
$a\in\mathcal{A}$ is a tuple
$\left<\Delta(a),\operatorname*{pre}(a),\operatorname*{add}(a),\operatorname*{del}(a)\right>$
where $\Delta(a)$ is a set of parameter variables and
$\operatorname*{pre}(a),\operatorname*{add}(a)$ and $\operatorname*{del}(a)$
are sets of predicates from $\mathcal{P}$ instantiated with either parameter
variables or objects in $\Delta(a)\cup\mathcal{O}$. Similarly to predicates,
an action schema with $n=\left|\Delta(a)\right|$ parameter variables is an
$n$-ary action schema. An action schema where each variable is instantiated
with an object is an action. Action application and successor states are
defined in the same way for both STRIPS and lifted planning.

#### Graph neural networks

The introduction of graph neural networks (GNN) requires additional
terminology. In the context of learning tasks, we define a graph with edge
labels to be a tuple $\left<V,E,{\mathbf{X}}\right>$ where $V$ is a set of
nodes, $E$ a set of undirected edges with labels where
$\left<v,u\right>_{\iota}=\left<u,v\right>_{\iota}\in E$ denotes an undirected
edge with label $\iota$ between nodes $u,v\in V$, and
${\mathbf{X}}:V\to\mathbb{R}^{d}$ a function representing the node features of
the graph. The edge neighbourhood of a node $u$ in a graph under edge label
$\iota$ is $\mathcal{N}_{\iota}(u)=\left\\{\left<u,v\right>_{\kappa}\in
E\mid\kappa=\iota\right\\}$. The edge neighbourhood of a node $u$ in a graph
is $\mathcal{N}(u)=\bigcup_{\iota\in\mathcal{R}}\mathcal{N}_{\iota}(u)$ where
$\mathcal{R}$ is the set of edge labels for the graph.

A Message-Passing Neural Network (MPNN) (Gilmer et al. 2017) is a type of GNN
which iteratively updates node embeddings of a graph with edge labels locally
in one-hop neighbourhoods with the general message passing equation

$\displaystyle{\mathbf{h}}_{u}^{(t+1)}=\textstyle\operatorname*{cmb}^{(t)}\bigl{(}{\mathbf{h}}_{u}^{(t)},\textstyle\operatorname*{agg}^{(t)}_{\left<u,v\right>_{\iota}\in{\mathcal{N}}(u)}f^{(t)}\bigl{(}{\mathbf{h}}_{u}^{(t)},{\mathbf{h}}_{v}^{(t)},\iota\bigr{)}\bigr{)}$

where in the $t$-th iteration or layer of the network,
${\mathbf{h}}_{u}^{(t)}\in\mathbb{R}^{F^{(t)}}$ is the embedding of node $u$
of dimension $F^{(t)}$, and ${\mathbf{h}}_{u}^{(0)}$ is given by the node
feature corresponding to $u$ in ${\mathbf{X}}$. We have that
$\operatorname*{cmb}^{(t)}$ and $f^{(t)}$ are arbitrary almost everywhere
differentiable functions and $\operatorname*{agg}^{(t)}$ is usually a
differentiable permutation invariant function acting on sets of vectors such
as sum, mean or component-wise max.

In order for an MPNN to produce a graph representation for an input, it is
then common to pool all the node embeddings after a number of message passing
updates with a _graph readout_ function $\Phi$ which is again usually given by
a differentiable permutation invariant function.

##  3 Representation

In this section, we introduce three novel graph representations designed for
learning heuristic functions for planning tasks. Each graph is tailored to a
specific task representation and all of them allow us to learn _domain-
independent_ heuristic functions.

### Grounded Graphs

A graph representation for grounded STRIPS problems already exists, namely the
STRIPS problem description graph (PDG) (Shleyfman et al. 2015). It was
originally used to study which classical heuristics were invariant under
symmetries in the planning task. In order to learn heuristics, we provide an
alternative graph representation for STRIPS problems which includes node
features and edge labels.

######  Definition 3.1.

The _STRIPS learning graph (SLG)_ of a STRIPS problem
$\left<P,A,s_{0},G\right>$ is the graph $\left<V,E,{\mathbf{X}}\right>$ with

  * •

$V=A\cup P$,

  * •

$E=E_{\operatorname*{pre}}\cup E_{\operatorname*{add}}\cup
E_{\operatorname*{del}}$ where for
$\iota\in\left\\{\operatorname*{pre},\operatorname*{add},\operatorname*{del}\right\\}$

$E_{\iota}=\left\\{\left<a,p\right>_{\iota}\mid p\in\iota(a),a\in A\right\\},$

  * •

${\mathbf{X}}:V\to\mathbb{R}^{3}$ defined by $u\mapsto[u\in P;u\in s_{0};u\in
G].$

By allowing for edge labels, we only require one node for each proposition to
encode the semantics of action effects in contrast to STRIPS PDG which
requires three nodes for each proposition. Thus SLG is smaller while not
losing any information. We also note that three dimensional node features are
sufficient for encoding whether a node corresponds to an action or
proposition, and in the latter case, whether it is true in the initial state
and present in the goal. Fig. 1 illustrates an example SLG subgraph.

$a$$p_{0}$$p_{1}$$p_{2}$$p_{3}$$p_{4}$

Figure 1: The SLG subgraph of an action $a$ defined by
$\operatorname*{pre}(a)=\left\\{p_{0},p_{1},p_{2}\right\\}$,
$\operatorname*{add}(a)=\left\\{p_{3},p_{4}\right\\}$ and
$\operatorname*{del}(a)=\left\\{p_{0},p_{2}\right\\}$, indicated by black,
blue and red edges respectively.

The FDR problem description graph (PDG) (Pochter, Zohar, and Rosenschein 2011)
is an existing graph representation designed to identify symmetrical states
during search for FDR problems. Since PDG is not designed for learning, it
lacks vector node features and edge labels. Def. 3.2 extends FDR PDG with
learning in mind by retaining its graph structure and adding node features and
edge labels. Fig. 2 illustrates an example of an FLG subgraph.

$a$$v_{1}$$v_{2}$$v_{3}$$d_{1,1}$$d_{1,2}$$d_{2,1}$$d_{2,2}$$d_{2,3}$$d_{3,1}$$d_{3,2}$

Figure 2: The FLG subgraph of an action $a$ defined by
$\operatorname*{pre}(a)=\left\\{\left<v_{2},d_{2,1}\right>,\left<v_{3},d_{3,2}\right>\right\\}$
and $\operatorname*{eff}(a)=\\{\left<v_{1},d_{1,1}\right>$,
$\left<v_{2},d_{2,2}\right>$, $\left<v_{3},d_{3,1}\right>\\}$, indicated by
black and blue edges respectively. Asparagus edges link variables and values.

######  Definition 3.2.

The _FDR learning graph (FLG)_ of an FDR problem
$\left<\mathcal{V},A,s_{0},s_{\star}\right>$ is the graph
$\left<V,E,{\mathbf{X}}\right>$ with

  * •

$V=\mathcal{V}\cup\bigcup_{v\in\mathcal{V}}D_{v}\cup A$,

  * •

$E=E_{\operatorname*{var:val}}\cup E_{\operatorname*{pre}}\cup
E_{\operatorname*{eff}}$ with

$\displaystyle E_{\operatorname*{var:val}}$
$\displaystyle=\textstyle\bigcup_{v\in\mathcal{V}}\\{\left<v,d\right>_{\operatorname*{var:val}}\mid
d\in D_{v}\\}$ $\displaystyle E_{\operatorname*{pre}}$
$\displaystyle=\textstyle\bigcup_{a\in
A}\\{\left<d,a\right>_{\operatorname*{pre}}\mid(v,d)\in\operatorname*{pre}(a)\\}$
$\displaystyle E_{\operatorname*{eff}}$ $\displaystyle=\textstyle\bigcup_{a\in
A}\\{\left<d,a\right>_{\operatorname*{eff}}\mid(v,d)\in\operatorname*{eff}(a)\\},$

  * •

${\mathbf{X}}:V\to\mathbb{R}^{5}$ defined by

$\displaystyle u\mapsto[u\in\mathcal{V};u\in
A;\operatorname*{val}(u);\operatorname*{true}(u);\operatorname*{goal}(u)]$

where $\operatorname*{val}(u)=\exists v\in\mathcal{V}$, $u\in D_{v}$,
$\operatorname*{true}(u)=\exists v\in\mathcal{V}$, $\left<v,u\right>\in s_{0}$
and $\operatorname*{goal}(u)=\exists v\in\mathcal{V}$, $\left<v,u\right>\in
s_{\star}$.

### Lifted Graphs

Lifted algorithms for planning offer an advantage by avoiding the need for
grounding thus saving both time and memory. To leverage these benefits for
heuristic learning, a lifted graph representation that is amenable to learning
is needed. However, designing such graphs is non-trivial due to the extra
relations to encode, namely the interactions between predicates, action
schema, propositions true in the current state, the goal condition and
objects. The only graph representation encoding all the information of a
lifted planning task is the _abstract structure graph_ (ASG) (Sievers et al.
2019). Similarly to PDG, ASG was designed to compute symmetries but it has
also been used for learning planning portfolios (Katz et al. 2018).

An ASG is constructed by first defining a coloured graph on _abstract
structures_ , a recursive structure defined with sets, tuples, and the input
objects, and then defining a lifted planning task as an abstract structure.
ASGs have several limitations when used with MPNNs for making predictions.
Their encoding of predicate and action schema arguments is done via a sequence
or directed path, where the graph uses a directed path of length $n$ to encode
$n$ arguments. There are also many more auxiliary nodes to encode the abstract
structures. These issues cause problems as a larger receptive field is
required for MPNNs to learn the structure and semantics of the planning
problem, and directed edges limit information flow and expressiveness when
used with MPNNs.

1212on(a,b)on(b,c)abcon(a)objectsground argsstate and goalpredicates

onhand-emptyclearhold-ing1211111(b)predicatesschema predicatespredicate
argsschema argsaction schemaxystack

Figure 3: LLG instance subgraph (a) and schema subgraph (b) with graph layer
descriptions of a Blocksworld instance.

To overcome the issues with ASGs, Def. 3.3 introduces a new graph
representation for lifted planning tasks designed to be used with MPNNs. It
consists of two main components: the schema subgraph which encodes the
domain’s action schemas and the instance subgraph which encodes the instance
specific information containing the current state and the goal condition. We
assume no partially instantiated action schema as is usual for most PDDL
domains, but the definition could be extended to allow partial grounding as a
tradeoff between expressiveness and graph size.

######  Definition 3.3.

Let $T\in{\mathbb{N}}$. The _lifted learning graph (LLG)_ of a lifted problem
$\Pi=\left<\mathcal{P},\mathcal{O},\mathcal{A},s_{0},G\right>$ is the graph
$G=\left<V,E,{\mathbf{X}}\right>$ with
$\bullet$ $V=\mathcal{P}\cup\mathcal{O}\cup N(\mathcal{A})\cup N(s_{0}\cup G)$
with

$\displaystyle N(s_{0}\cup G)$
$\displaystyle=\displaystyle\textstyle\bigcup_{p=P(o_{1},\ldots,o_{n_{P}})\in
s_{0}\cup G}\left\\{p,p_{1},\ldots,p_{n_{P}}\right\\}$ $\displaystyle
N(\mathcal{A})$
$\displaystyle=\textstyle\bigcup_{a\in\mathcal{A}}\bigl{(}\left\\{a\right\\}\cup\left\\{a_{\delta}\mid\delta\in\Delta(a)\right\\}\cup$
$\displaystyle\quad\;\;\textstyle\bigcup_{f\in\left\\{\operatorname*{pre},\operatorname*{add},\operatorname*{del}\right\\}}\textstyle\bigcup_{p=P(\delta_{1},\ldots,\delta_{n_{P}})\in
f(a)}$
$\displaystyle\quad\quad\bigl{\\{}p_{a,f},p_{a,f,1},\ldots,p_{a,f,n_{P}}\bigr{\\}}\bigr{)}$

$N(s_{0}\cup G)$ contains nodes corresponding to the state and goal, and
ground arguments layer as in Fig. 3(a), while $N(\mathcal{A})$ provides all
the nodes corresponding to the action schema, schema argument, predicate
argument and schema predicate layers in Fig. 3(b).
$\bullet$ $E=E_{\nu}\cup
E_{\gamma}\cup\textstyle\bigcup_{f\in\left\\{\operatorname*{pre},\operatorname*{add},\operatorname*{del}\right\\}}E_{f}$
where

$\displaystyle E_{\nu}$ $\displaystyle=\bigl{\\{}\left<o,P\right>_{\nu}\mid
o\in\mathcal{O},P\in\mathcal{P}\bigr{\\}}\;\cup$
$\displaystyle\quad\;\;\bigl{\\{}\left<a,a_{\delta}\right>_{\nu}\mid\delta\in\Delta(a),a\in\mathcal{A}\bigr{\\}}$
$\displaystyle E_{\gamma}$
$\displaystyle=\textstyle\bigcup_{p=P(o_{1},\ldots,o_{n_{P}})\in s_{0}\cup
G}\bigl{(}\bigl{\\{}\left<p,p_{i}\right>_{\gamma}\\!\mid\\!i\\!\in\\![n_{P}]\bigr{\\}}\;\cup$
$\displaystyle\quad\;\;\bigl{\\{}\left<p_{i},o_{i}\right>_{\gamma}\\!\mid\\!i\\!\in\\![n_{P}]\bigr{\\}}\cup\bigl{\\{}\left<p,P\right>_{\gamma}\bigr{\\}}\bigr{)}$
$\displaystyle E_{f}$ $\displaystyle=\textstyle\bigcup_{p=P()\in
f(a)}\bigl{\\{}\left<P,p_{a,f}\right>_{f},\left<p_{a,f},a\right>_{f}\bigr{\\}}\;\cup$
$\displaystyle\quad\;\;\textstyle\bigcup_{p=P(\delta_{1},\ldots,\delta_{n_{P}})\in
f(a),n_{P}\geq 1}\bigl{(}\bigl{\\{}\left<P,p_{a,f}\right>_{f}\bigr{\\}}\;\cup$
$\displaystyle\quad\quad\bigl{\\{}\left<p_{a,f},p_{a,f,i}\right>_{f},\left<p_{a,f,i},a_{\delta_{i}}\right>_{f}\\!\mid\\!i\\!\in\\![n_{P}]\bigr{\\}}\bigr{)}$

for
$f\in\left\\{\operatorname*{pre},\operatorname*{add},\operatorname*{del}\right\\}$.
$E_{\nu}$ connects objects to predicates and schemas to their arguments, as
indicated by gray edges in Fig. 3, $E_{\gamma}$ connects nodes in
$\mathcal{P}$, $\mathcal{O}$, and $N(s_{0}\cup G)$ in order to represent
propositions in the goal and true in the state as instantiated predicates with
objects in the correct arguments, and
$\textstyle\bigcup_{f\in\left\\{\operatorname*{pre},\operatorname*{add},\operatorname*{del}\right\\}}E_{f}$
connects nodes in $\mathcal{P}$ and $N(\mathcal{A})$ to encode the semantics
of action schema in the graph.
$\bullet$ ${\mathbf{X}}:V\to\mathbb{R}^{5+T}$ defined by

$\displaystyle u\mapsto[u\in\mathcal{P};u\in\mathcal{O};u\in\mathcal{A};u\in
s_{0};u\in G]\operatorname*{{\|}}\overline{\operatorname*{IF}}(u)$

where $\operatorname*{{\|}}$ denotes vector concatenation,
$\overline{\operatorname*{IF}}(u)=\operatorname*{IF}(i)$ for $u$ of the form
$p_{i}$ or $p_{a,f,i}$ with
$f\in\left\\{\operatorname*{pre},\operatorname*{add},\operatorname*{del}\right\\}$
and $\overline{\operatorname*{IF}}(u)=\vec{0}$ otherwise, and
$\operatorname*{IF}:{\mathbb{N}}\to\mathbb{R}^{T}$ is defined by a fixed
randomly chosen injective map from ${\mathbb{N}}$ to the sphere
$\left\\{x\in\mathbb{R}^{T}\mid\left\|x\right\|=1\right\\}$.

We use the index function $\operatorname*{IF}$ to encode the index at which an
object instantiates the argument of a predicate or action schemas. This usage
of $\operatorname*{IF}$ lets us address STRIPS-HGN’s limitation of having a
fixed maximum number of parameters for predicates and action schemas that is
chosen before training. Specifically, $\operatorname*{IF}$ provides a
numerically stable representation of an unbounded range of indexes that is
agnostic to the maximum arity of the problem. Moreover, $\operatorname*{IF}$
improves generalisation to large and unseen indexes as they are mapped to
normalised vectors already seen by the model.

IF draws inspiration from positional encoding functions used in Transformers
(Vaswani et al. 2017) and GNNs (Li et al. 2020; Dwivedi et al. 2022; Wang et
al. 2022) for encoding positions as vectors. However, while Transformers and
GNNs use positional encodings to encode all input tokens and graph nodes
respectively, we use $\operatorname*{IF}$ features only in the subset of nodes
required to encode argument indexes in the lifted planning task. Furthermore,
positional encodings aim to correlate positions and their corresponding
features, such that objects close to each other are given similar features. In
contrast, $\operatorname*{IF}$ generates features for each index that are
independent of one another. Hence, $\operatorname*{IF}$ features are randomly
generated i.i.d. for each index and also _a priori_ such that they can be used
for domain-independent learning.

##  4 Expressiveness

We have defined three novel graph representations of planning tasks for the
goal of learning domain-independent heuristics. In this section we will
categorise the expressiveness of such graph representations when used with
MPNNs by identifying which domain-independent heuristics they are able to
learn. Our study also includes characterising the expressiveness of STRIPS-HGN
(Shen, Trevizan, and Thiébaux 2020), the previous work on learning domain-
independent heuristics. Fig. 4 summarises the main theorems of this section
via an expressiveness hierarchy. Proofs of theorems are provided in a
technical report (Chen, Thiébaux, and Trevizan 2023b).

We begin with a lower bound on what MPNNs can learn by showing that they can
theoretically learn to imitate algorithms for computing $h^{\max}$ and
$h^{\operatorname*{add}}$ on our grounded graphs with the use of the
approximation theorem for neural networks (Cybenko 1989; Hornik, Stinchcombe,
and White 1989). We note that the theorem does not say anything about
generalisability.

$h^{\max\\!\\!/\\!\\!\operatorname*{add}}$STRIPS-HGN$h^{+}$$h^{*}$LLGSLGFLG
Figure 4:  Expressiveness hierarchy of MPNNs on graph representations with
respect to STRIPS-HGN and the heuristics $h^{\max}$,
$h^{\operatorname*{add}}$, $h^{+}$ and $h^{*}$. Bold outlines represent new
graphs.

######  Theorem 4.1 (MPNNs can learn $h^{\operatorname*{add}}$ and $h^{\max}$
on grounded graphs).

Let $L,B\in{\mathbb{N}}$, $\mathcal{G}\in\left\\{{SLG},{FLG}\right\\}$,
$\varepsilon>0$ and $h\in\\{h^{\operatorname*{add}},h^{\max}\\}$. Then there
exists a set of parameters ${\Theta}$ for an MPNN ${\mathcal{F}}_{{\Theta}}$
such that for all planning tasks $\Pi$, if naive dynamic programming for
computing $h$ converges within $L$ iterations for $\Pi$, and $h(\Pi)\leq B$,
then we have
$\left|h(\Pi)-{\mathcal{F}}_{{\Theta}}(\mathcal{G}(\Pi))\right|<\varepsilon$.

MPNNs acting on SLG and FLG are strictly more expressive than STRIPS-HGN. The
idea of the theorem is that STRIPS-HGN discards delete effects which prohibits
it from learning $h^{*}$. Furthermore, it is possible to imitate STRIPS-HGN
with minor assumptions on MPNN architectures acting on either of our grounded
graphs.

######  Theorem 4.2 (MPNNs on grounded graphs are strictly more expressive
than STRIPS-HGN).

Let $\mathcal{G}\in\left\\{{SLG},{FLG}\right\\}$. Given any set of parameters
$\Theta$ for a STRIPS-HGN model $\mathcal{S}_{\Theta}$, there is a set of
parameters $\Phi$ for an MPNN ${\mathcal{F}}_{\Phi}$ such that for any pair of
planning tasks $\Pi_{1}$ and $\Pi_{2}$ where
$\mathcal{S}_{\Theta}(\Pi_{1})\not=\mathcal{S}_{\Theta}(\Pi_{2})$, we have
${\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi_{1}))\not={\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi_{2}))$.
Furthermore, there exists a pair of planning problems $\Pi_{1}$ and $\Pi_{2}$
such that there exists $\Phi$ where
${\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi_{1}))\not={\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi_{2}))$
but $\mathcal{S}_{\Theta}(\Pi_{1})=\mathcal{S}_{\Theta}(\Pi_{2})$ for all
$\Theta$.

The first of our negative results is that MPNNs cannot learn
$h^{\operatorname*{add}}$ or $h^{\max}$ on the lifted LLG graph. This is due
to the graph being too condensed in the lifted version so that MPNNs cannot
extract certain information for computing these heuristics. The proof idea is
to find a pair of planning tasks which appear symmetric to MPNNs in the LLG
representation but have different $h^{\max}$ and $h^{\operatorname*{add}}$
values.

######  Theorem 4.3 (MPNNs cannot learn $h^{\operatorname*{add}}$ and
$h^{\max}$ on lifted graphs).

Let $h\in\left\\{h^{\operatorname*{add}},h^{\max}\right\\}$. There exists a
pair of planning tasks $\Pi_{1}$ and $\Pi_{2}$ with
$h(\Pi_{1})\not=h(\Pi_{2})$ such that for any set of parameters $\Theta$ for
an MPNN we have
${\mathcal{F}}_{\Theta}({LLG}(\Pi_{1}))={\mathcal{F}}_{\Theta}({LLG}(\Pi_{2}))$.

Next, we have that MPNNs cannot learn $h^{+}$ and thus $h^{*}$ on any of our
graphs. This result is not unexpected given that the expressiveness of MPNNs
is bounded by the graph isomorphism class $\GI$ whose hardness is known to be
in the low hierarchy of $\NP$, unlike $h^{+}$ which is $\NP$-complete.
Similarly to the previous theorem, the proof follows the technique of finding
a pair of planning tasks with different $h^{+}$ values that are
indistinguishable by MPNNs on any of our graphs.

######  Theorem 4.4 (MPNNs cannot learn $h^{+}$ or $h^{*}$ with our graphs).

Let $h\in\left\\{h^{+},h^{*}\right\\}$ and
$\mathcal{G}\in\left\\{{SLG},{FLG},{LLG}\right\\}$. There exists a pair of
planning tasks $\Pi_{1}$ and $\Pi_{2}$ with $h(\Pi_{1})\not=h(\Pi_{2})$ such
that for any set of parameters $\Theta$ for an MPNN we have
${\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{1}))={\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{2}))$.

One may ask if it is possible to learn any approximation of $h^{+}$ or $h^{*}$
on all planning problems. Unfortunately, it is not possible to learn either
absolute or relative approximations. This is formalised in the following
theorem, where the proof consists of a class of planning task pairs
generalising the previous example.

######  Theorem 4.5 (MPNNs cannot learn any approximation of $h^{+}$ or
$h^{*}$).

Let $h\in\left\\{h^{+},h^{*}\right\\}$,
$\mathcal{G}\in\left\\{{SLG},{FLG},{LLG}\right\\}$ and $c>0$. There exists a
pair of planning tasks $\Pi_{1}$ and $\Pi_{2}$ with
$h(\Pi_{1})\not=h(\Pi_{2})$ such that for any set of parameters $\Theta$ for
an MPNN we do not have
$\left|{\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{1}))-h(\Pi_{1})\right|\leq
c\wedge\left|{\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{2}))-h(\Pi_{2})\right|\leq
c$. Also, for any set of parameters we do not have
$\left|1-{{\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{1}))}/{h(\Pi_{1})}\right|\leq
c\wedge\left|1-{{\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{2}))}/{h(\Pi_{2})}\right|\leq
c$.

We note that our theorems provide extreme upper and lower bounds on what MPNNs
can learn with some of our graphs. Although in the general case we have the
negative result that we cannot learn $h^{+}$ or $h^{*}$, it is still possible
to learn $h^{*}$ on subclasses of planning tasks. For example, Ståhlberg,
Bonet, and Geffner (2022a) theoretically analyse which domains their MPNN
architecture can learn $h^{*}$ for, by using the well known result concerning
the connection between MPNNs and 2-variable counting logics (Cai, Fürer, and
Immerman 1992; Barceló et al. 2020). Furthermore, the results in this study
concern MPNNs but there exist more expressive graph representation learning
methods. For example, under additional assumptions, the universal
approximation theorem with random node initialisation by Abboud et al. (2021)
can be applied to learn $h^{*}$. Lastly, note that neither our results nor
previous works examine the generalisability of learned heuristic functions.

domain | train |  | validate |  | test |  | largest sol.
---|---|---|---|---|---|---|---
blocks | $b\in[3,10]$ | _40_ | $b\in[11]$ | _3_ | $b\in[15,100]$ | _90_ | $b=75^{\ast}$
ferry | $l,c\in[2,10]$ | _125_ | $l,c\in[11]$ | _3_ | $l,c\in[15,100]$ | _90_ | $l,c=100$
gripper | $b\in[1,10]$ | _10_ | $b\in[11]$ | _1_ | $b\in[15,100]$ | _18_ | $b=100$
n-puzzle | $n\in[2,4]$ | _100_ | $n\in[5]$ | _3_ | $n\in[5,9]$ | _50_ | $n=6^{\ast}$
sokoban | $n\in[5,7]$ | _60_ | $n\in[8]$ | _3_ | $n\in[8,12]$ | _90_ | $n=12^{\ast}$
spanner | $s,n\in[2,10]$ | _75_ | $s,n\in[11]$ | _3_ | $s,n\in[15,100]$ | _90_ | $s,n=75$
visitall | $n\in[3,10]$ | _24_ | $n\in[11]$ | _3_ | $n\in[15,100]$ | _90_ | $n=65$
visitsome | $n\in[3,10]$ | _24_ | $n\in[11]$ | _3_ | $n\in[15,100]$ | _90_ | $n=95^{*}$
Table 1:  Problem splits with sizes and number of tasks per domain. Right most
column indicates largest size problem solved with GOOSE. Problem size is not
completely correlated with difficult for domains marked $\ast$.

##  5 Experiments

We provide experiments in order to evaluate the effectiveness of our graph
representations for use with both domain-dependent and domain-independent
learning of heuristic functions, as well as to answer some open questions left
behind in our theoretical discussion. In order to do so, we introduce our
GOOSE planner which combines graph generation, graph representation learning
and domain-independent planning. Code is available at (Chen, Thiébaux, and
Trevizan 2023a).

#### GOOSE

The Graphs Optimised fOr Search Evaluation (GOOSE) architecture represents
planning tasks with one of the three graphs described previously (SLG, FLG,
LLG) and uses MPNNs to learn heuristic functions for search. During heuristic
evaluation, GOOSE treats each state $s$ of a planning task
$\left<S,A,s_{0},G\right>$ as a new planning subtask $\left<S,A,s,G\right>$
which is then transformed into the chosen graph and fed into an MPNN. We use a
RGCN (Schlichtkrull et al. 2018) message passing step:
${\mathbf{h}}_{u}^{(t+1)}=\\!\sigma\Bigl{(}\mathbf{W}_{0}^{(t)}{\mathbf{h}}_{u}^{(t)}+\sum_{\iota\in\mathcal{R}}\bigoplus_{\left<u,v\right>_{\iota}\in\mathcal{N}_{\iota}(u)}\mathbf{W}_{\iota}^{(t)}{\mathbf{h}}_{v}^{(t)}\Bigr{)},$
where $\oplus$ denotes the aggregator over neighbours under different edge
labels. GOOSE uses the eager GBFS component of Fast Downward (Helmert 2006)
for search, but calls the trained models for heuristic evaluation and
parallelises the evaluation of successor states on GPUs for each opened node.
GOOSE only constructs graphs from static propositions computed by Fast
Downward.

Figure 5:  (a) GOOSE learned heuristics ($y$-axis) vs. $h^{*}$ ($x$-axis). No
$n$-puzzle problem could have $h^{*}$ computed. (b) $h^{\operatorname*{FF}}$
($y$-axis) vs. GOOSE ($x$-axis) on number of expanded nodes (left) and plan
cost (right). Points on the bottom right triangles favour
$h^{\operatorname*{FF}}$ and on the top left triangles favour GOOSE. Problems
unsolved by a configuration get value set to the maximum of the plot’s axis.

#### Setup

For domain-dependent heuristic learning, we train 5 models for each domain on
optimal plans with problems specified in Tab. 1. Each plan of length $h^{*}$
contributes states $s_{0},s_{1},\ldots,s_{g}$ with corresponding labels
$h^{*},h^{*}-1,\ldots,0$. For domain-independent heuristic learning, we
consider the problems and domains of the 1998 to 2018 IPC dataset, excluding
the domains in Tab. 1. We train 5 models using optimal plans generated by
scorpion (Seipp, Keller, and Helmert 2020) with a 30min cutoff time and unit
costs. In both settings, a model is trained with the Adam optimiser (Kingma
and Ba 2015), batch size 16, initial learning rate of 0.001 and MSE loss. We
schedule our learning rate by extracting 25% of the training data and reducing
the learning rate by a factor of 10 if the loss on this data subset did not
decrease in the last 10 epochs. Training is stopped when the learning rate
becomes less than $10^{-5}$ on this subset, which often occurs within a few
minutes. Following a similar method to Ferber, Helmert, and Hoffmann (2020),
we select the best model for both settings by choosing the model which solves
the most problems in the validation set (Tab. 1). We break ties with the sum
of number of expanded nodes, and the training loss. We choose a hidden
dimension of 64 with 8 message passing layers and the mean aggregator. GOOSE
is run with a single NVIDIA GeForce RTX 3090 GPU.

#### Baselines

We evaluate against blind search, Fast Downward’s implementation of eager GBFS
with $h^{\operatorname*{FF}}$, and domain-dependent STRIPS-HGN. STRIPS-HGN was
trained using the parameters described in the original paper but with the same
dataset as GOOSE and is called from Fast Downward’s eager GBFS for heuristic
evaluation. The other baselines are run on CPUs only. All GOOSE configurations
and baselines are run with a 600 second timeout and 8GB main memory. We note
that we also evaluated Powerlifted’s (Corrêa et al. 2020) implementation of
lifted eager GBFS with both $h^{\operatorname*{FF}}$ and its extension with
GOOSE but they do not offer any advantage over Fast Downward on the chosen
problems.

### Results

We recall from our theoretical study that it is not possible to learn any
approximation of $h^{*}$ over all planning tasks, although it may still be
possible for certain planning subclasses or domains. Furthermore, we can learn
domain-dependent $h^{*}$ heuristics for certain domains similarly to
(Ståhlberg, Bonet, and Geffner 2022a). Thus, we propose and answer the
following question empirically.

#### How close to the optimal heuristic are our learned heurstics?

To answer this question, we report the heuristic of the initial state
$h(s_{0})$ computed by our models on all planning problems for which we can
compute the optimal heuristic either by a hard coded solver or an optimal
planner in Fig. 5(a). In the domain-dependent training setting, GOOSE with LLG
provides the best predictions over most domains except for Sokoban. GOOSE
achieves close to perfect heuristic estimates even as problems scale in size.
This can be explained by LLG encoding predicate information which the other
graph representations do not have access to and for some domains, it suffices
to count the predicates of true propositions to compute $h^{*}$. Meanwhile,
MPNNs are not expressive enough to decode predicate information from the
grounded graphs. In the domain-independent training setting, GOOSE heuristics
tend to overestimate $h^{*}$ on VisitAll, whose perfect heuristic can often be
computed by counting unreached goals, and underestimate on Sokoban. The
grounded graphs (SLG and FLG) underestimate on Gripper, Spanner and Sokoban.
This suggests GOOSE heuristics are overfitting on the training set for the
more expressive grounded graphs as it is not possible to compute $h^{*}$. In
particular, FLG is more prone to overfitting since it encodes additional
planning task structure in the conversion of STRIPS to FDR.

#### How useful are learned domain-dependent heuristics for search?

To answer this question, we refer to Fig. 6 for a coverage table over all
domains with various planners. We notice that GOOSE with LLG trained in a
domain-dependent fashion provides the best coverage on Blocksworld and
Spanner, and is tied with Fast Downward’s eager GBFS with
$h^{\operatorname*{FF}}$ on Gripper. GOOSE with SLG performs best on the grid
based path finding domains VisitAll and VisitSome. Meanwhile,
$h^{\operatorname*{FF}}$ performs best on the remaining Ferry, $n$-puzzle and
Sokoban domains. However, all GOOSE configurations perform worse than blind
search on Sokoban. Even though it expands fewer nodes than blind search, the
runtime cost of computing GOOSE heuristics is too high. This may be due to the
difficulty of the domain (-complete) as size increases, given that in problems
with similar size to the training set GOOSE outperforms the other baselines.
STRIPS-HGN solves significantly fewer problems due to its slower evaluation on
CPUs.

Fig. 5(b) shows the number of node expansions and returned plan quality of the
best performing domain-dependent GOOSE graph, LLG, against
$h^{\operatorname*{FF}}$. In domains where one planner solves significantly
more problems than the other, it also has fewer node expansions. We also note
that GOOSE generally has higher plan quality than $h^{\operatorname*{FF}}$
over all problems which both planners were able to solve.

| baselines | domain-dep. | domain-ind.
---|---|---|---
|  blind |  $h^{\text{FF}}$ |  HGN |  SLG |  FLG |  LLG |  SLG |  FLG |  LLG
blocks (90) |  - |  19 |  - |  - |  6 |  62 |  9 |  8 |  6
ferry (90) |  - |  90 |  - |  32 |  33 |  88 |  28 |  22 |  2
gripper (18) |  1 |  18 |  5 |  9 |  6 |  18 |  5 |  3 |  9
n-puzzle (50) |  - |  36 |  - |  10 |  10 |  - |  6 |  3 |  -
sokoban (90) |  74 |  90 |  10 |  31 |  29 |  34 |  45 |  40 |  15
spanner (90) |  - |  - |  - |  - |  - |  60 |  - |  - |  -
visitall (90) |  - |  6 |  25 |  46 |  50 |  44 |  16 |  41 |  -
visitsome (90) |  3 |  26 |  33 |  72 |  39 |  65 |  73 |  65 |  15
Figure 6:  Coverage of planners and GOOSE over various domains. Cell intensities indicate the top 3 planners per row.  |  | domain-dep. | domain-ind.
---|---|---|---
aggr. | L |  SLG |  FLG |  LLG |  SLG |  FLG |  LLG
mean | 4 |  0.40 |  0.43 |  0.94 |  0.19 |  0.15 |  0.18
8 |  0.53 |  0.40 |  1.00 |  0.38 |  0.32 |  0.33
12 |  0.44 |  0.37 |  0.85 |  0.37 |  0.32 |  0.21
16 |  0.31 |  0.18 |  0.75 |  0.36 |  0.32 |  0.12
max | 4 |  0.46 |  0.50 |  0.89 |  0.33 |  0.29 |  0.30
8 |  0.41 |  0.43 |  0.88 |  0.36 |  0.30 |  0.52
12 |  0.36 |  0.43 |  0.80 |  0.12 |  0.24 |  0.39
16 |  0.41 |  0.36 |  0.53 |  0.06 |  0.24 |  0.20
Figure 7:  Total coverage normalised per domain of GOOSE over various
parameters and training paradigms, and normalised again by the coverage of the
best performing configuration. Higher scores are better and the maximum score
is 1. The best scores per _column_ are highlighted in bold.

#### How useful are learned domain-independent heuristics for search?

We again refer to Fig. 6 for the coverage of GOOSE trained with domain-
independent heuristics. With the exception of Sokoban, domain-independent
GOOSE outperforms blind search which suggests that the learned domain-
independent heuristics have some informativeness. This is supported by Fig.
5(a) which shows that in most domains domain-independent heuristics provide a
mostly-linear approximation of $h^{*}$. Most notably, domain-independent
grounded graphs still outperform $h^{\operatorname*{FF}}$ on VisitAll and
VisitSome, and domain-independent LLG is able to solve some Spanner problems.

The best performing domain-independent GOOSE graph with 8 message passing
layers and mean aggregator is the grounded graph SLG. It provides enough
information to learn domain-independent heuristics with MPNNs in comparison to
LLG, but also does not provide too much information to prevent overfitting in
comparison to FLG which computes additional structure. Domain-independent
GOOSE with SLG returns better quality plans, and expands fewer nodes than
$h^{\operatorname*{FF}}$ on VisitAll, VisitSome, and more than half the
Blocksworld instances which both planners were able to solve. Domain-
independent GOOSE also outperforms or ties with _domain-dependent_ STRIPS-HGN
across all domains except VisitAll. However, domain-independent GOOSE
generally expands more nodes and returns lower quality plans than their
domain-dependent trained variants with the same graph.

#### How important is finding the right graph neural network parameters?

We report the normalised coverage of GOOSE with hyperparameters
$L\in\\{4,8,12,16\\}$ layers and $\oplus\in\\{\max,\text{mean}\\}$ aggregator
in Fig. 7. We omitted results with the sum aggregator as it yielded unstable
training and poor predictions. Increasing the number of layers theoretically
improves informativeness and accuracy of predictions but requires longer
evaluation time and is more difficult to train. There is no single set of
parameters that performs well over all graphs and training settings. Generally
4 or 8 layers result in similar coverages for domain-dependent training, and 8
or 12 layers for domain-independent training, while increasing the number of
layers beyond this results in worse performance due to the aforementioned
reasons. We note that the effectiveness of max and mean aggregations vary with
the graph representation and domain as both aggregators lose information in
different ways. However, in the domain-dependent setting, LLG with the mean
aggregator generally outperforms the max aggregator given that the model can
recover the information lost during normalisation through the grouping of edge
labels and node types.

#### How long do GOOSE evaluations take?

GOOSE on a single core CPU takes 0.2-0.9s to perform a full GNN evaluation on
grounded graphs, and 0.2-0.3s on lifted graphs. With _optimal_ GPU usage,
grounded graphs take 0.1-5ms per state evaluation and lifted graphs take
0.07-0.7ms. Optimal usage is achieved when the batch size is greater than 32
for lifted graphs and 4 for grounded graphs. In our experiments, the grounded
graphs were able to optimally use the GPU while the lifted graphs were not,
resulting in a higher average state evaluation time. We note that evaluating
states of successor nodes further in the queue to increase the batch size is
also not optimal as the expanded states may never be evaluated in sequential
GBFS. Evaluation of heuristics on GPUs is almost always faster than on CPU due
to the parallel execution of GNN matrix and scatter operations.

##  6 Conclusion

We have constructed various novel graph representations of planning problems
for the task of learning domain-independent heuristics. In particular we
provide the first domain-independent graph representation of lifted planning.
All our new models are also complemented by a theoretical analysis of their
expressive power in relation to domain-independent heuristics and the previous
work on learning domain-independent heuristics, STRIPS-HGN. We also construct
the GOOSE planner using heuristic search with heuristics learned from our new
graph representations. GOOSE has also been optimised for runtime with the use
of GPU batch evaluation and is able to solve significantly larger problems
than those seen in the training set, vastly surpassing STRIPS-HGN learned
heuristics, and outperforming the $h^{\operatorname*{FF}}$ heuristic on
several domains. It remains for future work to implement search algorithms
used by stronger satisficing planners in GOOSE, and to optimise GPU
utilisation when computing heuristics. Furthermore GOOSE can be extended to
predict deadends alongside a heuristic for further pruning the search space.
Lastly, we aim to improve the expressiveness of learned heuristics by
leveraging stronger graph representation learning techniques.

## Acknowledgements

The authors would like to thank the reviewers and Rostislav Horčík for their
comments. The computational resources for this project were partially provided
by the Australian Government through the National Computational Infrastructure
(NCI) under the ANU Startup Scheme. Sylvie Thiébaux’s work was supported by
Australian Research Council grant DP220103815, by the Artificial and Natural
Intelligence Toulouse Institute (ANITI), and by the European Union’s Horizon
Europe Research and Innovation program under the grant agreement TUPLES No.
101070149.

## References

  * Abboud et al. (2021) Abboud, R.; Ceylan, İ. İ.; Grohe, M.; and Lukasiewicz, T. 2021.  The Surprising Power of Graph Neural Networks with Random Node Initialization.  In _International Joint Conference on Artificial Intelligence (IJCAI)_.
  * Barceló et al. (2020) Barceló, P.; Kostylev, E. V.; Monet, M.; Pérez, J.; Reutter, J.; and Silva, J.-P. 2020.  The logical expressiveness of graph neural networks.  In _International Conference on Learning Representations (ICLR)_.
  * Cai, Fürer, and Immerman (1992) Cai, J.-Y.; Fürer, M.; and Immerman, N. 1992.  An optimal lower bound on the number of variables for graph identification.  _Combinatorica_ , 12(4): 389–410.
  * Chen, Thiébaux, and Trevizan (2023a) Chen, D. Z.; Thiébaux, S.; and Trevizan, F. 2023a.  Code for Learning Domain-Independent Heuristics for Grounded and Lifted Planning.  10.5281/zenodo.10404209.
  * Chen, Thiébaux, and Trevizan (2023b) Chen, D. Z.; Thiébaux, S.; and Trevizan, F. 2023b.  Learning Domain-Independent Heuristics for Grounded and Lifted Planning.  arXiv:2312.11143.
  * Corrêa et al. (2020) Corrêa, A. B.; Pommerening, F.; Helmert, M.; and Francès, G. 2020.  Lifted Successor Generation Using Query Optimization Techniques.  In _International Conference on Automated Planning and Scheduling (ICAPS)_ , 80–89.
  * Cybenko (1989) Cybenko, G. 1989.  Approximation by superpositions of a sigmoidal function.  _Mathematics of control, signals and systems_ , 2(4): 303–314.
  * Dong et al. (2019) Dong, H.; Mao, J.; Lin, T.; Wang, C.; Li, L.; and Zhou, D. 2019.  Neural Logic Machines.  In _International Conference on Learning Representations (ICLR)_.
  * Dwivedi et al. (2022) Dwivedi, V. P.; Luu, A. T.; Laurent, T.; Bengio, Y.; and Bresson, X. 2022.  Graph neural networks with learnable structural and positional representations.  In _International Conference on Machine Learning (ICML)_.
  * 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 Giacomo, G. D.; Catalá, A.; Dilkina, B.; Milano, M.; Barro, S.; Bugarín, A.; and Lang, J., eds., _European Conference on Artificial Intelligence (ECAI)_ , volume 325, 2346–2353.
  * Garg, Bajpai, and Mausam (2020) Garg, S.; Bajpai, A.; and Mausam. 2020.  Symbolic Network: Generalized Neural Policies for Relational MDPs.  In _International Conference on Machine Learning (ICML)_ , volume 119, 3397–3407.
  * 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. Morgan & Claypool Publishers.
  * Gehring et al. (2022) Gehring, C.; Asai, M.; Chitnis, R.; Silver, T.; Kaelbling, L. P.; Sohrabi, S.; and Katz, M. 2022.  Reinforcement Learning for Classical Planning: Viewing Heuristics as Dense Reward Generators.  In _International Conference on Automated Planning and Scheduling (ICAPS)_ , 588–596.
  * Gilmer et al. (2017) Gilmer, J.; Schoenholz, S. S.; Riley, P. F.; Vinyals, O.; and Dahl, G. E. 2017.  Neural Message Passing for Quantum Chemistry.  In _International Conference on Machine Learning (ICML)_ , volume 70, 1263–1272.
  * Helmert (2006) Helmert, M. 2006.  The Fast Downward Planning System.  _J. Artif. Intell. Res._ , 26: 191–246.
  * Helmert (2009) Helmert, M. 2009.  Concise finite-domain representations for PDDL planning tasks.  _Artif. Intell._ , 173(5-6): 503–535.
  * Hornik, Stinchcombe, and White (1989) Hornik, K.; Stinchcombe, M.; and White, H. 1989.  Multilayer feedforward networks are universal approximators.  _Neural networks_ , 2(5): 359–366.
  * Karia and Srivastava (2021) Karia, R.; and Srivastava, S. 2021.  Learning Generalized Relational Heuristic Networks for Model-Agnostic Planning.  In _AAAI Conference on Artificial Intelligence (AAAI)_ , 8064–8073.
  * Katz et al. (2018) Katz, M.; Sohrabi, S.; Samulowitz, H.; and Sievers, S. 2018.  Delfi: Online planner selection for cost-optimal planning.  _International Planning Competition_ , 57–64.
  * Kingma and Ba (2015) Kingma, D. P.; and Ba, J. 2015.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations (ICLR)_.
  * Lauer et al. (2021) Lauer, P.; Torralba, A.; Fiser, D.; Höller, D.; Wichlacz, J.; and Hoffmann, J. 2021.  Polynomial-Time in PDDL Input Size: Making the Delete Relaxation Feasible for Lifted Planning.  In _International Joint Conference on Artificial Intelligence (IJCAI)_.
  * Li et al. (2020) Li, P.; Wang, Y.; Wang, H.; and Leskovec, J. 2020.  Distance encoding: Design provably more powerful neural networks for graph representation learning.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 33: 4465–4478.
  * Ma et al. (2020) Ma, T.; Ferber, P.; Huo, S.; Chen, J.; and Katz, M. 2020.  Online Planner Selection with Graph Neural Networks and Adaptive Scheduling.  In _AAAI Conference on Artificial Intelligence (AAAI)_ , 5077–5084.
  * Pochter, Zohar, and Rosenschein (2011) Pochter, N.; Zohar, A.; and Rosenschein, J. S. 2011.  Exploiting Problem Symmetries in State-Based Planners.  In _AAAI Conference on Artificial Intelligence (AAAI)_.
  * Schlichtkrull et al. (2018) Schlichtkrull, M. S.; Kipf, T. N.; Bloem, P.; van den Berg, R.; Titov, I.; and Welling, M. 2018.  Modeling Relational Data with Graph Convolutional Networks.  In _Extended Semantic Web Conference (ESWC)_ , Lecture Notes in Computer Science, 593–607.
  * Seipp, Keller, and Helmert (2020) Seipp, J.; Keller, T.; and Helmert, M. 2020.  Saturated Cost Partitioning for Optimal Classical Planning.  _J. Artif. Intell. Res._ , 67: 129–167.
  * Sharma et al. (2022) Sharma, V.; Arora, D.; Geißer, F.; Mausam; and Singla, P. 2022.  SymNet 2.0: Effectively handling Non-Fluents and Actions in Generalized Neural Policies for RDDL Relational MDPs.  In Cussens, J.; and Zhang, K., eds., _Uncertainty in Artificial Intelligence, (UAI)_ , volume 180, 1771–1781.
  * 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 (ICAPS)_.
  * Shleyfman et al. (2015) Shleyfman, A.; Katz, M.; Helmert, M.; Sievers, S.; and Wehrle, M. 2015.  Heuristics and Symmetries in Classical Planning.  In _AAAI Conference on Artificial Intelligence (AAAI)_ , 3371–3377.
  * Sievers et al. (2019) Sievers, S.; Röger, G.; Wehrle, M.; and Katz, M. 2019.  Theoretical Foundations for Structural Symmetries of Lifted PDDL Tasks.  In _International Conference on Automated Planning and Scheduling (ICAPS)_ , volume 29, 446–454.
  * Ståhlberg, Bonet, and Geffner (2022a) Ståhlberg, S.; Bonet, B.; and Geffner, H. 2022a.  Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits.  In _International Conference on Automated Planning and Scheduling (ICAPS)_ , 629–637.
  * Ståhlberg, Bonet, and Geffner (2022b) Ståhlberg, S.; Bonet, B.; and Geffner, H. 2022b.  Learning Generalized Policies without Supervision Using GNNs.  In _International Conference on Principles of Knowledge Representation and Reasoning (KR)_.
  * Teichteil-Königsbuch et al. (2023) Teichteil-Königsbuch, F.; Povéda, G.; Guillermo Gonzalez de Garibay Barba, T. L.; and Thiébaux, S. 2023.  Fast and Robust Resource-Constrained Scheduling with Graph Neural Networks.  In _International Conference on Automated Planning and Scheduling (ICAPS)_.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, L.; and Polosukhin, I. 2017.  Attention is All you Need.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 5998–6008.
  * Wang et al. (2022) Wang, H.; Yin, H.; Zhang, M.; and Li, P. 2022.  Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks.  In _International Conference on Learning Representations (ICLR)_.
  * Xu et al. (2019) Xu, K.; Hu, W.; Leskovec, J.; and Jegelka, S. 2019.  How powerful are graph neural networks?  In _International Conference on Learning Representations (ICLR)_.

##  Appendix A Proofs of Theorems

This appendix includes the proofs of all theorems. For ease of reference,
theorem statements are also repeated here.

Data: Propositional STRIPS planning task $\Pi=\left<P,A,s_{0},G\right>$,
desired heuristic $h\in\left\\{h^{\operatorname*{add}},h^{\max}\right\\}$

Result: $h(s)\in{\mathbb{N}}$

1 if  _$h=h^{\operatorname*{add}}$_ then $\oplus\leftarrow\sum$;

2 else if  _$h=\max$_ then $\oplus\leftarrow\max$;

3 $h^{(0)}[p]\leftarrow 0,\quad\forall p\in s_{0}$

4 $h^{(0)}[p]\leftarrow\infty,\quad\forall p\in P\setminus s_{0}$

5 for  _$i=1,\ldots$_ do

6 for  _$a\in A$_ do

7 $h^{(i)}[a]\leftarrow\oplus_{p\in\operatorname*{pre}(a)}h^{(i-1)}[p]$

8

9 for  _$p\in P$_ do

10 $h^{(i)}[p]\leftarrow\min\bigl{(}h^{(i-1)}[p],\min_{a\in
A,p\in\operatorname*{add}(a)}h^{(i)}[a]+c(a)\bigr{)}$

11

12 if  _$h^{(i)}=h^{(i-1)}$_ then

13 return _$\oplus_{p\in g}h^{(i)}[p]$_

14

15

Algorithm 1 Naive dynamic programming for computing $h^{\operatorname*{add}}$
and $h^{\max}$

######  Theorem A.1 (MPNNs can learn $h^{\operatorname*{add}}$ and $h^{\max}$
on grounded graphs).

Let $L,B\in{\mathbb{N}}$, $\mathcal{G}\in\left\\{{SLG},{FLG}\right\\}$,
$\varepsilon>0$ and $h\in\\{h^{\operatorname*{add}},h^{\max}\\}$. Then there
exists a set of parameters ${\Theta}$ for an MPNN ${\mathcal{F}}_{{\Theta}}$
such that for all planning tasks $\Pi$, if naive dynamic programming for
computing $h$ (Alg. 1) converges within $L$ iterations for $\Pi$, and
$h(s_{0})\leq B$, then we have
$\left|h(s_{0})-{\mathcal{F}}_{{\Theta}}(\mathcal{G}(\Pi))\right|<\varepsilon$.

###### Proof.

The main idea of the proof is that we can encode Alg. 1 for computing $h$ into
an MPNN using a correct choice of continuous bounded functions and aggregation
operators and using the approximation theorem to find parameters in order to
achieve the desired function. We will assume unitary cost actions and note
that the below proof can be generalised to account for general cost actions.
We first deal with the case where $h=h^{\max}$ and $\mathcal{G}={DLG}{}$,
where DLG is the graph SLG but without delete edges. The proof generalises to
SLG as an MPNN can learn to ignore delete edges.

Let $x^{(u)}\in\mathbb{R}^{3}$ be the feature of node $u$. By definition of
DLG as the graph SLG (Def. 3.1) with no delete edges, it is defined by
$x^{(u)}_{0}=1$ if $u$ corresponds to a proposition node, else $x^{(u)}_{0}=0$
when $u$ corresponds to an action node $a$. Furthermore, $x^{(u)}_{1}=1$ if
$u$ is a proposition in the initial state and $x^{(u)}_{2}=1$ if $u$ is a goal
proposition. Note that it is possible that $x^{(u)}_{1}=x^{(u)}_{2}=1$ when a
proposition is both a goal condition and in the initial state. If not
mentioned, we have that $x^{(u)}_{i}=0$ everywhere else.

Then we will construct a MPNN with $2L+2$ layers. For the first layer we have
an embedding layer which ignores neighbourhood nodes with
$\operatorname*{agg}^{(0)}=\vec{0}$ and
$\varphi^{(0)}({\mathbf{h}}_{u},{\mathbf{h}}_{N})=f_{\text{emb}}({\mathbf{h}}_{u})$.
Let $K$ be the finite set of possible node features in a DLG representation of
a planning task. Then $f_{\text{emb}}:K\to\mathbb{R}^{3}$ is defined by

$\displaystyle f_{\text{emb}}([0,0,0]^{\top})$ $\displaystyle=[0,0,0]^{\top}$
(1) $\displaystyle f_{\text{emb}}([1,0,0]^{\top})$
$\displaystyle=[B,0,1]^{\top}$ (2) $\displaystyle
f_{\text{emb}}([1,0,1]^{\top})$ $\displaystyle=[B,1,1]^{\top}$ (3)
$\displaystyle f_{\text{emb}}([1,1,0]^{\top})$ $\displaystyle=[0,0,1]^{\top}$
(4) $\displaystyle f_{\text{emb}}([1,1,1]^{\top})$
$\displaystyle=[0,1,1]^{\top}.$ (5)

This first round of message passing updates corresponds to the initialisation
step of the heuristic algorithm with $B$ representing infinity values. We also
note that after applying $\operatorname*{agg}^{(0)}$ and $\varphi^{(0)}$ and
throughout the remaining forward pass of the MPNN, node embeddings will have
the form $[x_{0},x_{1},x_{2}]$ which encode information about their
corresponding proposition or action during the execution of the $h^{\max}$
algorithm where

  * •

$x_{0}$ corresponds to the intermediate $h$ values computed in the $h^{\max}$
algorithm,

  * •

$x_{1}$ signifies whether the node corresponds to a goal node, and

  * •

$x_{2}$ determines if the node is a proposition or action node.

The next $2L$ layers use the component wise max aggregation function
$\operatorname*{agg}=\max$ and alternates between setting
$\varphi^{(l)}({\mathbf{h}}_{u},{\mathbf{h}}_{N})=f_{a}([{\mathbf{h}}_{u}\operatorname*{\mathchoice{\Big{\|}}{\big{\|}}{\|}{\|}}{\mathbf{h}}_{N}])$
and
$\varphi^{(l+1)}({\mathbf{h}}_{u},{\mathbf{h}}_{N})=f_{p}([{\mathbf{h}}_{u}\operatorname*{\mathchoice{\Big{\|}}{\big{\|}}{\|}{\|}}{\mathbf{h}}_{N}])$
where $f_{a}:\mathbb{R}^{6}\to\mathbb{R}^{3}$ and
$f_{p}:\mathbb{R}^{6}\to\mathbb{R}^{3}$ are defined by

$\displaystyle f_{a}\left(\begin{bmatrix}x_{0}\\\ x_{1}\\\ x_{2}\\\ y_{0}\\\
y_{1}\\\ y_{2}\end{bmatrix}\right)$
$\displaystyle=\begin{bmatrix}x_{0}x_{2}-(1-x_{2})y_{0}\\\ x_{1}x_{2}\\\
x_{2}^{2}\end{bmatrix},$ (6) $\displaystyle f_{p}\left(\begin{bmatrix}x_{0}\\\
x_{1}\\\ x_{2}\\\ y_{0}\\\ y_{1}\\\ y_{2}\end{bmatrix}\right)$
$\displaystyle=\begin{bmatrix}\min(x_{0},-y_{0}+1)x_{2}\\\ x_{1}x_{2}\\\
x_{2}^{2}\end{bmatrix}.$ (7)

These functions correspond to the iterative updates of $h^{(l)}[a]$ and
$h^{(l)}[p]$ in Alg. 1, recalling that $L$ is the number of iterations it
takes for the algorithm converges. More specifically, suppose we have a node
$u$ with embedding ${\mathbf{h}}_{u}=[x_{0},x_{1},x_{2}]$ and aggregated
embedding from its neighbours ${\mathbf{h}}_{N}=[y_{0},y_{1},y_{2}]$. Then we
have two cases.

  * •

If $x_{2}=0$, indicating that the node $u$ corresponds to a n action, then we
get

$\displaystyle
f_{a}([{\mathbf{h}}_{u}\operatorname*{\mathchoice{\Big{\|}}{\big{\|}}{\|}{\|}}{\mathbf{h}}_{N}])$
$\displaystyle=[-y_{0},0,0]$ (8) $\displaystyle
f_{p}([{\mathbf{h}}_{u}\operatorname*{\mathchoice{\Big{\|}}{\big{\|}}{\|}{\|}}{\mathbf{h}}_{N}])$
$\displaystyle=[0,0,0].$ (9)

Eq. 8 corresponds to Line 1 in Alg. 1 where $-y_{0}$ contains the negative of
$h[a]$. We take the negative since we are restricted to using $\max$
aggregators only111As $\min$ aggregators conflict with ReLU activation
functions commonly seen in neural networks. which in turn means we require
taking maximums of negatives in order to mimic the minimum aggregator later in
Line 1 of the same algorithm. Eq. 9 corresponds to Line 1 but since this line
only affects propositions and $h[a]$ values do not need to be stored after
execution of this line, we set ${\mathbf{h}}_{u}$ to zero.

  * •

If $x_{2}=1$, indicating that the node $u$ corresponds to a proposition, then
we get

$\displaystyle
f_{a}([{\mathbf{h}}_{u}\operatorname*{\mathchoice{\Big{\|}}{\big{\|}}{\|}{\|}}{\mathbf{h}}_{N}])$
$\displaystyle=[x_{0},x_{1},x_{2}]$ (10) $\displaystyle
f_{p}([{\mathbf{h}}_{u}\operatorname*{\mathchoice{\Big{\|}}{\big{\|}}{\|}{\|}}{\mathbf{h}}_{N}])$
$\displaystyle=[\min(x_{0},-y_{0}+1),x_{1},x_{2}].$ (11)

We recall $f_{a}$ corresponds to Line 1 which only affects $h[a]$ values.
Given that we require storing $h[p]$ values throughout the whole algorithm,
$f_{a}$ acts as the identity function on ${\mathbf{h}}_{u}$ for proposition
nodes as seen in Eq. 10. This is in contrast to $f_{p}$ which acts as the zero
function on ${\mathbf{h}}_{u}$ for action nodes. Eq. 11 corresponds to Line 1
where $-y_{0}$ is equivalent to the $\min_{a\in
A,p\in\operatorname*{add}(a)}h[a]=\max_{a\in
A,p\in\operatorname*{add}(a)}-h[a]$ term by definition of DLG,
$\operatorname*{agg}$ and $f_{a}$ acting on action node embeddings.

We append a final layer to the network where we ignore neighbourhood nodes
with $\operatorname*{agg}^{(2L+1)}=\vec{0}$ and
$\varphi^{(2L+1)}([x_{0},x_{1},x_{2}]^{\top},{\mathbf{h}}_{N})=x_{0}x_{1}$. In
combination with a max readout function $\Phi$, this corresponds to computing
the final heuristic value. The above encoding of Alg. 1 has also been
experimentally verified to be correct.

In order to satisfy the neural network component of the MPNN, we replace the
$\varphi^{(i)}$ for $i=0,\ldots,2L+1$ with feedforward networks. Noting that
we have finitely many layers we can choose small enough fractions of
$\varepsilon$ for the universal approximation theorem for neural networks
(Hornik, Stinchcombe, and White 1989; Cybenko 1989) to approximate the
continuous functions $\varphi^{(i)}$ whose domain is bounded in the ball of
radius $B$ in order to achieve our result.

The encoding for $h^{\operatorname*{add}}$ is the same except we use a sum
aggregator $\operatorname*{agg}=\sum$ and readout.

For the case of the other FLG, we note that the $h^{\max}$ and
$h^{\operatorname*{add}}$ algorithm for FDR problems and hence FLG graph
representations work in the obvious way by compiling FDR planning tasks into
propositional STRIPS planning task by treating variable-value pairs in FDR
problems as propositional facts. ∎

######  Theorem A.2 (MPNNs on grounded graphs are strictly more expressive
than STRIPS-HGN).

Let $\mathcal{G}\in\left\\{{SLG},{FLG}\right\\}$. Given any set of parameters
$\Theta$ for a STRIPS-HGN model $\mathcal{S}_{\Theta}$, there is a set of
parameters $\Phi$ for an MPNN ${\mathcal{F}}_{\Phi}$ such that for any pair of
planning tasks $\Pi_{1}$ and $\Pi_{2}$ where
$\mathcal{S}_{\Theta}(\Pi_{1})\not=\mathcal{S}_{\Theta}(\Pi_{2})$, we have
${\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi_{1}))\not={\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi_{2}))$.
Furthermore, there exists a pair of planning problems $\Pi_{1}$ and $\Pi_{2}$
such that there exists $\Phi$ where
${\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi_{1}))\not={\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi_{2}))$
but $\mathcal{S}_{\Theta}(\Pi_{1})=\mathcal{S}_{\Theta}(\Pi_{2})$ for all
$\Theta$.

###### Proof sketch.

To show the first part of the theorem, we describe how to construct an MPNN
${\mathcal{F}}_{\Phi}$ acting on SLG and FLG corresponding to a given STRIPS-
HGN (Shen, Trevizan, and Thiébaux 2020) model $\mathcal{S}_{\Theta}$ such that
for any pair of planning tasks $\Pi_{1}$ and $\Pi_{2}$ where
$\mathcal{S}_{\Theta}(\Pi_{1})\not=\mathcal{S}_{\Theta}(\Pi_{2})$, we have
${\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi_{1}))\not={\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi_{2}))$.
First we note that each STRIPS-HGN hypergraph message passing layer can be
emulated by two MPNN message passing layers. We note that the STRIPS-HGN
aggregation function is not permutation invariant as it requires ordering the
messages it receives before concatenating them and updating the aggregated
feature. This can similarly be done for a MPNN. Another difference with
STRIPS-HGN and MPNNs is the usage of global features that are updated with
each message passing layers. The MPNN framework can also be extended to make
use of global features, for example by appending a virtual node to the whole
input graph, and using different weights for the message passing functions
associated with the virtual node. Lastly, STRIPS-HGN uses the same weights for
each message passing layer and this may also be done for an MPNN.

For the second part of the theorem, we note that for any planning problem
$\Pi$ by definition of STRIPS-HGN,
$\mathcal{S}_{\Theta}(\Pi)=\mathcal{S}_{\Theta}(\Pi^{+})$ for all parameters
$\Theta$ where $\Pi^{+}$ is the delete relaxation of $\Pi$. Now consider the
STRIPS problem $\Pi=\left<P,A,s_{0},G\right>$ with
$P=G=\left\\{p_{0},p_{1}\right\\}$, $s_{0}=\left\\{p_{0}\right\\}$, and
$A=\left\\{a_{0},a_{1}\right\\}$ where both $a_{0}$ and $a_{1}$ have empty
precondition and

$\displaystyle\operatorname*{add}(a_{0})$
$\displaystyle=\left\\{p_{1}\right\\},$
$\displaystyle\operatorname*{del}(a_{0})$
$\displaystyle=\left\\{a_{0}\right\\}$
$\displaystyle\operatorname*{add}(a_{1})$
$\displaystyle=\left\\{a_{1}\right\\},$
$\displaystyle\operatorname*{del}(a_{1})$ $\displaystyle=\emptyset.$

Then the optimal plan for $\Pi$ has cost 2, while the optimal plan cost of its
delete relaxation $\Pi^{+}$ is 1. There exists a set of parameters for an MPNN
${\mathcal{F}}_{\Phi}$ acting on $\mathcal{G}\in\left\\{{SLG},{FLG}\right\\}$
such that
${\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi))=2\not=1={\mathcal{F}}_{\Phi}(\mathcal{G}(\Pi^{+}))$.
∎

######  Theorem A.3 (MPNNs cannot learn $h^{\operatorname*{add}}$ and
$h^{\max}$ on lifted graphs).

Let $h\in\left\\{h^{\operatorname*{add}},h^{\max}\right\\}$. There exists a
pair of planning tasks $\Pi_{1}$ and $\Pi_{2}$ with
$h(\Pi_{1})\not=h(\Pi_{2})$ such that for any set of parameters $\Theta$ for
an MPNN we have
${\mathcal{F}}_{\Theta}({LLG}(\Pi_{1}))={\mathcal{F}}_{\Theta}({LLG}(\Pi_{2}))$.

$o_{1}$$o_{2}$$1$$2$$1$$2$$1$$2$$1$$2$$Q(o_{1},o_{2})$$Q(o_{2},o_{1})$$W(o_{1},o_{2})$$W(o_{2},o_{1})$$Q$$W$$\operatorname*{pre}$$\operatorname*{add}$$1$$2$$1$$2$$1$$2$$a$
(a) LLG of $P_{1}$.

$o_{1}$$o_{2}$$1$$2$$1$$2$$1$$2$$1$$2$$Q(o_{1},o_{2})$$Q(o_{2},o_{1})$$W(o_{1},o_{2})$$W(o_{2},o_{1})$$Q$$W$$\operatorname*{pre}$$\operatorname*{add}$$1$$2$$1$$2$$1$$2$$a$
(b) LLG of $P_{2}$.

Figure 8: LLG of problems used in Thm. A.3 (edges between objects and
predicates omitted). Only colours are known to the WL algorithm, not the node
descriptions in the figure. The only difference between the two graphs lies in
the different edges between the top two layers of the graph as highlighted by
the dashed regions. However, they are indistinguishable by the WL algorithm.

###### Proof.

Consider the two (delete free) lifted problems
$P_{1}=\langle\mathcal{P},\mathcal{O},\mathcal{A},s_{0}^{(1)},G\rangle$ and
$P_{2}=\langle\mathcal{P},\mathcal{O},\mathcal{A},s_{0}^{(2)},G\rangle$ with
$\mathcal{P}=\left\\{Q(x_{1},x_{2}),W(x_{1},x_{2})\right\\}$,
$\mathcal{O}=\left\\{o_{1},o_{2}\right\\}$,
$s_{0}^{(1)}=\left\\{Q(o_{1},o_{2}),Q(o_{2},o_{1})\right\\}$,
$s_{0}^{(2)}=\left\\{Q(o_{1},o_{1}),Q(o_{2},o_{2})\right\\}$,
$G=\left\\{{W(o_{1},o_{2}),W(o_{2},o_{1})}\right\\}$ and one action schema
$\mathcal{A}=\left\\{a\right\\}$ with
$\Delta(a)=\left\\{\delta_{1},\delta_{2}\right\\}$,
$\operatorname*{pre}(a)=\left\\{Q(\delta_{1},\delta_{2})\right\\}$,
$\operatorname*{add}(a)=\left\\{W(\delta_{1},\delta_{2})\right\\}$ and
$\operatorname*{del}(a)=\emptyset$.

By definition $P_{1}$ can be solved with a plan consisting of $a(o_{1},o_{2})$
and $a(o_{2},o_{1})$ in either order and the corresponding heuristic values
are $h^{\max}(s_{0}^{(1)})=h^{\operatorname*{add}}(s_{0}^{(1)})=1$. On the
other hand $P_{2}$ is unsolvable in which case we have
$h^{\max}(s_{0}^{(2)})=h^{\operatorname*{add}}(s_{0}^{(2)})=\infty$.

The graphs are indistinguishable by the WL algorithm where we colour nodes by
mapping their features to the set of natural numbers for the ${LLG}{}$ graphs,
given that the set of possible node features is countable. Note that it is
possible to extend the WL algorithm to deal with edge labelled graphs by
replacing each labelled edge with a coloured node connected to the edge’s
endpoints. Fig. 8 illustrates the graph representations for LLG. Then the
result follows by the contrapositive of (Xu et al. 2019, Lem. 2) as WL assigns
the same output for both graphs, and hence any MPNN also assigns the same
output. ∎

######  Theorem A.4 (MPNNs cannot learn $h^{+}$ or $h^{*}$ with our graphs).

Let $h\in\left\\{h^{+},h^{*}\right\\}$ and
$\mathcal{G}\in\left\\{{SLG},{FLG},{LLG}\right\\}$. There exists a pair of
planning tasks $\Pi_{1}$ and $\Pi_{2}$ with $h(\Pi_{1})\not=h(\Pi_{2})$ such
that for any set of parameters $\Theta$ for an MPNN we have
${\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{1}))={\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{2}))$.

$a_{1}^{(1)}$$a_{2}^{(1)}$$p_{1}$$p_{2}$$a_{3}^{(1)}$$a_{4}^{(1)}$$a_{5}^{(1)}$$a_{6}^{(1)}$$g_{3}$$g_{4}$
(a) SLG of $P_{1}$.

$a_{1}^{(2)}$$a_{2}^{(2)}$$p_{1}$$p_{2}$$a_{3}^{(2)}$$a_{4}^{(2)}$$a_{5}^{(2)}$$a_{6}^{(2)}$$g_{3}$$g_{4}$
(b) SLG of $P_{2}$.

Figure 9: SLG of problems used in the proof of Thm. A.4. Black edges indicate
preconditions and blue edges indicate add effects.

###### Proof.

Consider the two (delete free) planning problems
$P_{1}=\left<P,A_{1},s_{0},G\right>$ and $P_{2}=\left<P,A_{2},s_{0},G\right>$
with $P=\left\\{p_{1},p_{2},g_{3},g_{4}\right\\}$,
$G=\left\\{g_{3},g_{4}\right\\}$, $s_{0}=\emptyset$ and action sets
$A_{1}=\\{a_{i}^{(1)}\mid i=1,\ldots,6\\}$, $A_{2}=\\{a_{i}^{(2)}\mid
i=1,\ldots,6\\}$ where actions have no delete effects and are defined by

$\displaystyle\operatorname*{pre}(a_{1}^{(1)})$ $\displaystyle=\emptyset,$
$\displaystyle\operatorname*{add}(a_{1}^{(1)})$ $\displaystyle=\\{p_{1}\\},$
$\displaystyle\operatorname*{pre}(a_{1}^{(2)})$ $\displaystyle=\emptyset,$
$\displaystyle\operatorname*{add}(a_{1}^{(2)})$ $\displaystyle=\\{p_{1}\\},$
$\displaystyle\operatorname*{pre}(a_{2}^{(1)})$ $\displaystyle=\emptyset,$
$\displaystyle\operatorname*{add}(a_{2}^{(1)})$ $\displaystyle=\\{p_{2}\\},$
$\displaystyle\operatorname*{pre}(a_{2}^{(2)})$ $\displaystyle=\emptyset,$
$\displaystyle\operatorname*{add}(a_{2}^{(2)})$ $\displaystyle=\\{p_{2}\\},$
$\displaystyle\operatorname*{pre}(a_{3}^{(1)})$ $\displaystyle=\\{p_{1}\\},$
$\displaystyle\operatorname*{add}(a_{3}^{(1)})$ $\displaystyle=\\{g_{3}\\},$
$\displaystyle\operatorname*{pre}(a_{3}^{(2)})$ $\displaystyle=\\{p_{1}\\},$
$\displaystyle\operatorname*{add}(a_{3}^{(2)})$ $\displaystyle=\\{g_{3}\\},$
$\displaystyle\operatorname*{pre}(a_{4}^{(1)})$ $\displaystyle=\\{p_{1}\\},$
$\displaystyle\operatorname*{add}(a_{4}^{(1)})$ $\displaystyle=\\{g_{3}\\},$
$\displaystyle\operatorname*{pre}(a_{4}^{(2)})$ $\displaystyle=\\{p_{1}\\},$
$\displaystyle\operatorname*{add}(a_{4}^{(2)})$ $\displaystyle=\\{g_{4}\\},$
$\displaystyle\operatorname*{pre}(a_{5}^{(1)})$ $\displaystyle=\\{p_{2}\\},$
$\displaystyle\operatorname*{add}(a_{5}^{(1)})$ $\displaystyle=\\{g_{4}\\},$
$\displaystyle\operatorname*{pre}(a_{5}^{(2)})$ $\displaystyle=\\{p_{2}\\},$
$\displaystyle\operatorname*{add}(a_{5}^{(2)})$ $\displaystyle=\\{g_{3}\\},$
$\displaystyle\operatorname*{pre}(a_{6}^{(1)})$ $\displaystyle=\\{p_{2}\\},$
$\displaystyle\operatorname*{add}(a_{6}^{(1)})$ $\displaystyle=\\{g_{4}\\},$
$\displaystyle\operatorname*{pre}(a_{6}^{(2)})$ $\displaystyle=\\{p_{2}\\},$
$\displaystyle\operatorname*{add}(a_{6}^{(2)})$ $\displaystyle=\\{g_{4}\\}.$

We have that the minimum plan cost for $P_{1}$ is 4 by applying actions
$a_{1}^{(1)},a_{2}^{(1)},a_{3}^{(1)},a_{5}^{(1)}$ whereas the minimum plan
cost for $P_{2}$ is 3 with actions $a_{1}^{(1)},a_{3}^{(1)},a_{5}^{(1)}$, as
seen in Fig. 9. Both $h^{+}$ and $h^{*}$ return 4 for $P_{1}$ and 3 for
$P_{2}$.

Colour refinement assigns the same invariant to the graph representations of
$P_{1}$ and $P_{2}$ and thus by the contrapositive of (Xu et al. 2019, Lem.
2), any MPNN assigns the same embedding to both graphs. ∎

######  Theorem A.5 (MPNNs cannot learn any approximation of $h^{*}$).

Let $\mathcal{G}\in\left\\{{SLG},{FLG},{LLG}\right\\}$ and $c>0$. There exists
a pair of planning tasks $\Pi_{1}$ and $\Pi_{2}$ with
$h(\Pi_{1})\not=h(\Pi_{2})$ such that for any set of parameters $\Theta$ for
an MPNN we do not have
$\left|{\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{1}))-h(\Pi_{1})\right|\leq
c\wedge\left|{\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{2}))-h(\Pi_{2})\right|\leq
c$. Furthermore, for any set of parameters we do not have
$\left|1-\frac{{\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{1}))}{h(\Pi_{1})}\right|\leq
c\wedge\left|1-\frac{{\mathcal{F}}_{\Theta}(\mathcal{G}(\Pi_{2}))}{h(\Pi_{2})}\right|\leq
c$.

$a(1,\\!1)$$p(1,\\!1)$$a(2,\\!1)$$p(2,\\!1)$$a_{1}(1,\\!2)$$a_{1}(1,\\!1)$$a_{1}(1,\\!3)$$p(3,\\!1)$$a(1,\\!2)$$p(1,\\!2)$$a(2,\\!2)$$p(2,\\!2)$$a_{1}(2,\\!2)$$a_{1}(2,\\!1)$$a_{1}(2,\\!3)$$p(3,\\!2)$$a(1,\\!3)$$p(1,\\!3)$$a(2,\\!3)$$p(2,\\!3)$$a_{1}(3,\\!2)$$a_{1}(3,\\!1)$$a_{1}(3,\\!3)$$p(3,\\!3)$

(a) SLG of $P_{1}$ for $n=3$.

$a(1,\\!1)$$p(1,\\!1)$$a(2,\\!1)$$p(2,\\!1)$$a_{2}(1,\\!2)$$a_{2}(1,\\!1)$$a_{2}(1,\\!3)$$p(3,\\!1)$$a(1,\\!2)$$p(1,\\!2)$$a(2,\\!2)$$p(2,\\!2)$$a_{2}(2,\\!2)$$a_{2}(2,\\!1)$$a_{2}(2,\\!3)$$p(3,\\!2)$$a(1,\\!3)$$p(1,\\!3)$$a(2,\\!3)$$p(2,\\!3)$$a_{2}(3,\\!2)$$a_{2}(3,\\!1)$$a_{2}(3,\\!3)$$p(3,\\!3)$

(b) SLG of $P_{2}$ for $n=3$.

Figure 10: SLGs of problems used in the proof of Thm. A.5 where black edges
indicate preconditions and blue edges indicate add effects.

###### Proof.

Let us fix $n\in{\mathbb{N}}$ with $n>2$. Then we will construct a pair of
planning problems whose optimal plan costs are $2n-1$ and $n^{2}$ respectively
but are indistinguishable by MPNNs by any graph representations
$\mathcal{G}\in\left\\{{SLG},{FLG},{LLG}\right\\}$ of the problems. Thus, we
can make our absolute and relative errors, given by $n^{2}-2n+1$ and
$\frac{n^{2}}{2n-1}$ respectively, arbitrary large.

Consider the two (delete free) planning problems given by
$P_{1}=\left<P,A_{1},s_{0},G\right>$ and $P_{2}=\left<O,A_{2},s_{0},G\right>$
with $P=\left\\{p(x,y)\mid x,y\in[n]\right\\}$, $G=\left\\{p(n,y)\mid
y\in[n]\right\\}\subset P$, $s_{0}=\emptyset$ and actions
$A_{1}=\left\\{a_{1}(y,z)\mid y,z\in[n]\right\\}\cup A$ and
$A_{2}=\left\\{a_{2}(y,z)\mid y,z\in[n]\right\\}\cup A$ where
$A=\left\\{a(x,y)\mid x\in[n-1],y\in[n]\right\\}$. All actions have no delete
effects and their preconditions and add effects are given as follows

$\displaystyle\operatorname*{pre}(a(1,y))$ $\displaystyle=\emptyset,$
$\displaystyle\operatorname*{add}(a(1,y))$
$\displaystyle=\left\\{p(1,y)\right\\},$ $\forall y\in[n]$
$\displaystyle\operatorname*{pre}(a(x,y))$
$\displaystyle=\left\\{p(x-1,y)\right\\},$
$\displaystyle\operatorname*{add}(a(x,y))$
$\displaystyle=\left\\{p(x,y)\right\\},$ $\forall x\in[2..n-1],y\in[n]$
$\displaystyle\operatorname*{pre}(a_{1}(y,z))$
$\displaystyle=\left\\{p(n-1,y)\right\\},$
$\displaystyle\operatorname*{add}(a_{1}(y,z))$
$\displaystyle=\left\\{p(n,y)\right\\},$ $\forall y,z\in[n]$
$\displaystyle\operatorname*{pre}(a_{2}(y,z))$
$\displaystyle=\left\\{p(n-1,z)\right\\},$
$\displaystyle\operatorname*{add}(a_{2}(y,z))$
$\displaystyle=\left\\{p(n,y)\right\\},$ $\forall y,z\in[n]$

where we note that the case $n=2$ is given in the proof of Thm. A.4. We refer
to Fig. 10 for the case of $n=3$. An optimal plan for $P_{1}$ consists of
executing all actions $a\in A$ and $a_{1}(y,1)$ for $y\in[n]$. On the other
hand, an optimal plan for $P_{2}$ consists only of executing $a(x,1)$ for
$x\in[n-1]$ followed by $a_{2}(y,1)$ for all $y\in[n]$. Thus, the optimal plan
costs for $P_{1}$ and $P_{2}$ are $n^{2}$ and $2n-1$ respectively.

As in the previous proof, any graph representations of the pair of problems
for any $n$ are indistinguishable by colour refinement and hence by MPNNs (Xu
et al. 2019, Lem. 2). ∎