# Heuristic Search Planning with Deep Neural Networks using Imitation,
Attention and Curriculum Learning

Leah Chrestien, Tomáš Pevný, Antonín Komenda, Stefan Edelkamp

###### Abstract

Learning a well-informed heuristic function for hard task planning domains is
an elusive problem. Although there are known neural network architectures to
represent such heuristic knowledge, it is not obvious what concrete
information is learned and whether techniques aimed at understanding the
structure help in improving the quality of the heuristics.

This paper presents a network model to learn a heuristic capable of relating
distant parts of the state space via optimal plan imitation using the
attention mechanism, which drastically improves the learning of a good
heuristic function. To counter the limitation of the method in the creation of
problems of increasing difficulty, we demonstrate the use of curriculum
learning, where newly solved problem instances are added to the training set,
which, in turn, helps to solve problems of higher complexities and far exceeds
the performances of all existing baselines including classical planning
heuristics. We demonstrate its effectiveness for grid-type PDDL domains.

## Introduction

Classical Planning has always relied on strong heuristic functions to
approximate distances to the nearest goal (Bonet and Geffner 2001). Generally
speaking, the quality of heuristics is measured by how well it performs when
used inside a planner, i.e., it depends on the quality of the solution and the
time taken to generate it. A major drawback of classical planning is the need
to formulate problems by extensively capturing information from the
environment. Recent years observe a progress in using visual representations
to capture the specifics of a problem (Asai and Fukunaga 2017). Yet, there is
still a big gap between the length of optimal plans and the plans found by
planners using learnt heuristic functions.

A significant amount of importance is given to developing deep networks that
are able to learn strong heuristics (Ernandes and Gori 2004) and policies
(Torrey et al. 2006). This is particularly common in Reinforcement Learning
which uses positive and negative feedback to learn the correct sequence of
next actions. In learning for planning, there is no such provision; instead,
it relies heavily on either hand-coded logical problem representations (Yoon,
Fern, and Givan 2012) or deep convolution neural networks (Groshev et al.
2017) that imitate an expert. While there exists successful approaches in
training neural networks to learn heuristic estimates of various problem
domains (Arfaee, Zilles, and Holte 2011; Virseda, Borrajo, and Alcázar 2013;
Groshev et al. 2017), designing a meaningful neural network architecture to
extract the relevant information from the data set is still an open-ended
problem.

This work extends the work by Schaal (1999) and Groshev et al. (2017) by
addressing limitations of convolutional neural network and by using imitation
and curriculum learning to train from plans of more difficult problem
instances for hard planning domains. Specifically, we propose to use self-
attention and position encoding (Vaswani et al. 2017), as we believe a strong
heuristic function needs to relate ”distant” parts of the state space.

In our default experimental settings, neural networks (NNs) realizing
heuristic functions are trained on plans of small problem instances created by
classical planners. While this allows us to generalize across more difficult
instances (some of which are still solvable by classical planners) such that
we can measure distances to optimal plan lengths, they do not achieve the best
results for two reasons. First, even though the generalization of A*-NN is
surprisingly good as will be seen below, there is still a scope of large-scale
improvement on previously unseen, larger and more complex environments.
Second, classical domain independent planners can solve only small problem
instances anyway, which means that obtaining plans from large ones is
difficult. We demonstrate that this problem can be partially mitigated by
curriculum learning, where the NN is retrained / fine-tuned using plans from
problems it has previously solved.

The proposed approach is compared to state-of-the-art domain-independent
planners, namely SymBA*(Torralba et al. 2014), Lama (Richter and Westphal
2010), and Mercury (Katz and Hoffmann 2014) and to currently best combination
of A* and CNNs (Groshev et al. 2017) on three grid domains: (1) Sokoban where
each maze consists of walls, empty spaces, boxes, targets and an agent; the
goal is to push the boxes to target locations; the boxes can only be pushed
and not pulled in the game; (2) Maze-with-Teleports where the goal for an
agent is to reach the goal position via interconnected teleports; (3) Floor-
Tile where the tiles in a given maze are to be colored alternatively by agents
(in our case, two agents) that are assigned a particular color each. At no
stage can an agent step on a tile that has been colored. The approach is
domain-independent and only requires the selection of propositions in the PDDL
file for spanning the underlying grid and the objects moving on it. It uses
either policy or heuristic value heads.

We have chosen these domains because (1) all can be easily translated into an
image based representation on which we can apply the convolution
operation;111If the domain can be described by graph, we can replace image
convolution by graph-convolution, though we do expect the experimental results
on these domains to exhibit very different behavior. (2) Sokoban is PSPACE-
complete (Culberson 1999) and known to be a challenging problem in Deep
Learning for Planning (Fern, Khardon, and Tadepalli 2011); therefore, an
improvement in Sokoban’s policy and heuristic learning implies success in
other two dimensional planning domains; (3) Maze-with-Teleports have non-local
actions as the maze agent is being teleported to different parts of the maze
via teleports; (4) Floor-Tile is NP-Complete and allows easy generation of
mazes of increasing difficulty, which makes it a great choice of domain for
improving the learnt heuristics via curriculum learning (Bengio et al. 2009).

The paper is organised as follows. We first discussed existing relevant
research that has been carried out in deep learning for planning, especially
in image based games. Next, we explore the formal basics of classical
planning. Then, we highlight the shortcomings of a prior state of the art and
propose a solution that addresses some of these shortcomings. Here, we
introduce the basics of the attention mechanism from NLP and explain the role
of positional encoding in learning distances. Then, the proposed networks are
compared to other state of the art methods that attempt to solve Sokoban,
Floor-Tile and Maze-with-Teleports. Finally, we conclude with an overall
synopsis of our work and lay the ground for future work.

## Related Work

The implementation of neural networks (NN) in learning policies and heuristics
for deducing strategic positions or moves in various game domains has been
studied extensively in the past. In Chess (Thrun 1994), NNs have been used to
evaluate chess board functions from the outcome of various games. A
combination of supervised learning and reinforcement learning has been
implemented in games such as Go (Silver et al. 2017), which uses value
networks to evaluate board positions and policy networks that choose
successive actions. In Backgammon (Tesauro 2002), temporal difference learning
was employed to train networks from millions of gameplay. Even single agent
games such as Sokoban (Racanière et al. 2017) and Rubik’s cube (Agostinelli et
al. 2019) use NNs to solve the respective puzzles. The relative success of NNs
in reinforcement learning has led researchers to believe that a similar
success may be achieved in learning heuristic functions for various classical
planning domains.

Fern, Khardon, and Tadepalli (2011) presented the earliest known work that
combines planning and learning and concludes that the performance of NNs is
promising in learning heuristic functions. The work of (Virseda, Borrajo, and
Alcázar 2013) attempts to combine classical planning and deep learning by
modifying costs and learning an improved heuristic function that generates
good quality plans. Arfaee, Zilles, and Holte (2011) generated strong
heuristics by repeatedly training on a set of weak heuristics by the boot-
strapping procedure which are then used inside a classical planner. Neural
search policies (Gomoluch et al. 2020) rely on parameter learning to generate
heuristics during the actual search process. The learning procedure in
(Srivastava, Immerman, and Zilberstein 2011) leads to generalizations of
classical plans by identifying landmark actions that may be repeatedly applied
during learning. Delphi applies deep learning on performance profile graphs to
choose the cost-optimal planner in a portfolio (Sievers et al. 2019)

Asai and Fukunaga (2017) used classical planning to generate data and designs
in an architecture that returns a visualised plan execution. In (Groshev et
al. 2017)’s work, the training samples were generated by classical planning,
and imitation learning (Schaal 1999) was performed on this data set for policy
and heuristic learning. Unlike Fikes and Nilsson (1971) and Shavlik (1989)
that used hand-coded domains to represent problems, Asai and Fukunaga (2017)
and Groshev et al. (2017) learned useful information from the input data
through image-based state descriptions.

Our approach significantly differs from prior work in planning and learning:
(1) we do not require any pre-designed model of the problem domain or the
state transition system; instead our model learns primarily from optimal
plans; (2) our model uses attention mechanism with positional encoding
designed to learn distances in the heuristic network; this generates near
optimal solutions for complex problem instances where other techniques often
fail.

## Classical Planning

We construct our problem domains in a classical setting, i.e. fully observable
and deterministic.

In classical planning, a STRIPS (Fikes and Nilsson 1971) planning task is
defined by a tuple $\Pi=\langle F,A,I,G\rangle$. $F$ denotes a set of facts
which can hold in the environment (for instance, in Sokoban, a particular box
at a particular position is a fact). A state $s$ of the environment is defined
as a set of facts holding in that particular $s$, i.e. $s\subseteq F$. The set
of all states is, therefore, defined as all possible subsets of $F$ as
$S=2^{F}$. $I\in S$ is the initial state of the problem and $G\subseteq F$ is
a goal condition comprising facts which has to hold in a goal state. An action
$a$, if applicable and applied, transforms a state $s$ into a successor state
$s^{\prime}$ denoted as $a(s)=s^{\prime}$ (if the action is not applicable, we
assume it returns a distinct failure value $a(s)=\bot$). All actions of the
problem are contained in the action set $A$, i.e. $a\in A$. The sets $S$ and
$A$ define the state-action transition system.

Let $\pi=({a}_{1},{a}_{2},\ldots,{a}_{l})$, we call $\pi$ a plan of length $l$
solving a planning task $\Pi$ iff $a_{l}(\ldots
a_{2}(a_{1}(I))\ldots)\supseteq G$. We assume a unit cost for all actions,
therefore the plan length and plan cost are equal. Moreover, let $\pi_{s}$
denote a plan from a state $s$, not $I$. An optimal solution (plan) is defined
as a minimal length solution of a problem $\Pi$ and is denoted as $\pi^{*}$
together with its length $l^{*}=|\pi^{*}|$.

A heuristic function $h$ is defined as $h:S\rightarrow\mathbb{R}^{\geq 0}$ and
provides an approximation of the optimal plan length from a state $s$ to a
goal state $s_{g}\supseteq G$, formally $h(s)\approx l^{*}$, where
$l^{*}=|\pi^{*}_{s}|$.

In our experiments, we choose domains encoded in PDDL (Fox and Long 2003),
where a planning problem is compactly represented in a lifted form based on
predicates and operators. This representation is grounded into a STRIPS
planning task $\Pi$, which is subsequently solved by the planner using a
heuristic search navigating in the state-action transition system graph and
resulting in a solution plan $\pi$.

## Planner’s Architecture

To learn a heuristic function for a planning domain that estimates the cost-
to-go in a current state is one of the holy grails in AI (Edelkamp and Schrödl
2012; Mostow and Prieditis 1989).

In our approach we combine a domain-independent planner with a trained neural
networks heuristic for its improved guidance during the overall search. This
way we are bridging symbolic and sub-symbolic reasoning, given that neural
networks are data-driven, and task planning requires symbolic reasoning in
some form of logical calculus.

To bridge this gap, we highlight that any (deterministic) plan is a sequence
of actions, but also on states. Given the initial state $I$, each partial plan
$\pi=({a}_{1},{a}_{2},\ldots,{a}_{k})$, $k<l$ induces a sequence of states
$({s}_{0}=I,{s}_{1},{s}_{2},\ldots,{s}_{k})$ with $s_{k}=a_{k}(\ldots
a_{2}(a_{1}(I))$. Extracting the state sequence was not difficult to program,
on could also use off-the-shelf tools like VAL (Howey, Long, and Fox 2004).

That a state is propositional is not a limitation to the approach. We might
also uses finite-domain variables as in SAS+ (Bäckström and Nebel 1995), or
include real-valued variables for metric planning (Fox and Long 2003).

Any encoded state is an input for the network. In our setting we use a _one-
hot bitvector encoding_ of the propositions. The output of the network is the
heuristic value called _value head_ , in some cases, together with a
distribution of action to take, called _policy head_. We prefer optimal plans
for selecting training instances for the neural network, which might be
generated by any optimal planner. More precisely, given the plans in the
training set, with imitation learning we generate pairs
$(s_{i},\delta(s_{i}))$, where $\delta$ is cost of an optimal plan from
$s_{i}$ to the goal. For the sake of simplicity, $\delta(s_{i})$ is the
distance $l-i$ of the state $s_{i}$ to the goal $s_{l}$ in the optimal plan
$({s}_{0}=I,{s}_{1},{s}_{2},\ldots,s_{i},\ldots,{s}_{l})$. Evaluating the
network for a given state, directly serves as estimator in our heuristic
search planner. With curriculum learning we also include newly found close-to-
optimal plans to retran the NN learner.

In some cases we will also take pairs of $(s_{i-1},a_{i})$ to train the
network for its policy head. Since our aim is close-to-optimal plans, as the
search algorithm for exploring the planning state space, we employed A* (Hart,
Nilsson, and Raphael 1968). For training the network we run the known
backpropagation algorithm on input batches together with stochastic gradient
decent (Bottou and Bousquet 2007) to minimize the network error, that is
computed with a simple loss function applied to the predicted and real value.
Once trained, the heuristic estimate can be extracted very efficiently for
each state from the value head. In some cases action selection can be based on
the policy head.

As we use optimal plans, we train the perfect heuristic estimate, but even for
considerably good plans, a goal estimate can be defined on other plans that
have been generate. All options that have been suggested also work for
solutions of simplified planning task, such as abstraction, relaxation can be
used to generate a set of plans from which we can extract distances. While we
assume to be able to identify the propositions that generate an underlying
grid, we emphasize that the above architecture is general and could be applied
to any state/action pairs extracted from the selection of good or optimal
plans. We take a rather generic network model, but with key ingredients of
position attention convolution, trained with imitation and curriculum
learning.

## Learning the Heuristic

Figure 1: The structure of our neural network. A current state $s$ and a goal
state $s_{g}$ are fed into a variable number of pre-processing convolution
(pre-conv) layers, $P_{1}..P_{n}$. All convolution filters in the pre-conv
layers are of the same shape $3\times 3$ with 64 filters. Then the network
splits into two branches and each branch has four blocks, each block
containing a convolution layer (C) followed by a multi head attention
operation (A) and a positional encoding layer (E). There are 180 filters in
each of these convolution layers in the blocks. At all stages, the original
dimension of the input is preserved. The output from block 4 is flattened by
applying a 1 × 1 window around the agent’s location before being passed onto
the fully connected layers (FC1) and the action prediction output (FC2-A) with
8 actions (move: up, down, left, right and push: up, down, left, right) and a
single output for heuristic prediction (FC2-H). For the sake of picture
clarity, skip connections are not shown in the neural network.

This section describes the proposed neural network for planning in maze-like
PDDL domains. But before, we introduce the notation and briefly discuss the
state-of-the-art along with the proposed modification. In the end, we discuss
the concrete architecture we used for all the benchmark domains (Sokoban,
Floor-Tile and Maze-with-Teleports). We extract the grid layout automatically,
but for the time being, we assume to have the grid dimensions $h$ and $w$
available to define the network.

### Formal notations for the proposed neural networks

The input to the neural network is denoted as
$\vec{x}\in\mathbb{R}^{h,w,d_{0}},$ where $h$ and $w$ is the height and width
of the maze respectively, and $d_{0}$ varies with the number of channels as
explained above. Intermediate outputs are denoted by
$\vec{z}^{i}=L_{i}(\vec{z}^{i-1}),$ where $L$ is some neural network layer
(convolution $C$, attention $A$, or position encoding $E$) and for the sake of
convenience, we set $\vec{z}^{0}=\vec{x}.$ All $\vec{z}^{\cdot}$ are three
dimensional tensors, i.e. $\vec{z}^{i}\in\mathbb{R}^{h,w,d_{i}}.$ Notice that
all intermediate outputs $\vec{z}^{i}$ have the same width and height as the
maze (ensured by padding), while the third dimension which is the number of
output filter(s) differs. Value $\vec{z}^{i}_{u,v}$ denotes a vector created
from $\vec{z}^{i}$ as
$(\vec{z}^{i}_{u,v,1},\vec{z}^{i}_{u,v,2},\ldots,\vec{z}^{i}_{u,v,d_{i}}).$
Below, this vector will be called a hidden vector at position $(u,v)$ and can
be seen as some description of the properties of this position.

### The proposed neural network

The best published NN implementing a heuristic function for Sokoban was
proposed in (Groshev et al. 2017). The network’s shape resembled letter Y, as
it has two heads, and it contains only convolution layers. The first seven
convolution layers were shared (we call them pre-conv layer abbreviating
preprocessing-convolution). Then, the network splits to yield two sets of
outputs: (i) the estimate of the heuristic function and (ii) the policy. After
the split, each path to the output contained seven convolution layers followed
by two dense layers. Although the heuristic function should be sufficient for
planning purposes, (Groshev et al. 2017) states that training the network to
estimate the policy helps in computing a better heuristic function.

Our criticism of the architecture is that convolution is strictly a local
operator. This means that the hidden vector $z^{i+1}_{u,v,\cdot}$ is
calculated from hidden vectors
$\\{z^{i}_{u^{\prime},v^{\prime},\cdot}|u^{\prime}\in\\{u-1,u,u+1\\},v^{\prime}\in\\{v-1,v,v+1\\}\\},$
where we assume convolution to have dimension $3\times 3$ as in (Groshev et
al. 2017). This limits the neural network in synthesizing information from two
distant parts of the maze. Yet, we believe that any good heuristic requires
such features, since Sokoban, Floor-Tile and Maze-with-Teleports are non-local
problems.

## Convolution, Attention, and Position Encoding

Therefore, we turn our attention to self-attention mechanism, (Vaswani et al.
2017) first introduced in NLP, as it allows to relate distant parts of input
together. The output of self-attention from $z^{i}$ is calculated in the
following manner. At first, the output from previous layer $z^{i}$ is divided
into three tensors of the same height, width, and depth, i.e.

$\displaystyle\vec{k}$ $\displaystyle=z^{i}_{\cdot,\cdot,j}\quad
j\in\left\\{1,\ldots,\frac{d_{i}}{3}\right\\}$ $\displaystyle\vec{q}$
$\displaystyle=z^{i}_{\cdot,\cdot,j}\quad
j\in\left\\{\frac{d_{i}}{3}+1,\ldots,\frac{2d_{i}}{3}\right\\}$
$\displaystyle\vec{v}$ $\displaystyle=z^{i}_{\cdot,\cdot,j}\quad
j\in\left\\{\frac{2d_{i}}{3}+1,\ldots,d_{i}\right\\}$

then, the output $z^{i+1}$ at position $(u,v)$ is calculated as

$\vec{z}^{i+1}_{u,v}=\sum_{r=1,s=1}^{h,w}\frac{\exp(\vec{q}_{u,v}\cdot\vec{k}_{r,s})}{\sum_{r^{\prime}=1,s^{\prime}=1}^{h,w}\exp(\vec{q}_{u,v}\cdot\vec{k}_{r^{\prime},s^{\prime}})}\cdot
v_{r,s}$ (1)

Self attention, therefore, makes a hidden vector $z^{j+1}_{u,v}$ dependent on
all hidden vectors
$\\{z^{j}_{r,s}|r\in\\{1,\dots,h\\},s\in\\{1,\ldots,w\\}\\}$, which is aligned
with our intention. The self-attention also preserves the size of the maze. A
multi-head variant of self-attention means that $z^{i}$ is split along the
third dimension in multiple $\vec{k}$s, $\vec{q}$s, and $\vec{v}$s. The
weighted sum is performed independent of each triple $(k,q,z)$ and the
resulting tensors are concatenated along the third dimension. We refer the
reader for further details to (Vaswani et al. 2017).

While self-attention captures information from different parts of the maze, it
does not have a sense of a distance. This implies that it cannot distinguish
close and far neighborhoods. To address this issue, we add positional
encoding, which augments the tensor $z^{i}\in\mathbb{R}^{h,w,d_{i}}$ with
another tensor $\vec{e}\in\mathbb{R}^{w,h,d_{e}}$ containing outputs of
harmonic functions along the third dimension. Harmonic functions were chosen,
because of their linear composability properties (Vaswani et al. 2017). 222The
composability of harmonic functions is based on the following property
$\cos(\theta_{1}+\theta_{2})=\cos(\theta_{1})\cos(\theta_{2})-\sin(\theta_{1})\sin(\theta_{2})=(\cos(\theta_{1}),\sin(\theta_{1}))\cdot(\sin(\theta_{1}),\sin(\theta_{2})),$
where $\cdot$ denotes the inner product of two vectors, which appears in
Equation (1) in inner product of $\vec{q}_{uv}$ and $\vec{k}_{rs}$. Because
our mazes are two dimensional, the distances are split up into row and column
distances where $p,q\in[0,d_{i}/4)$ assigns positions with sine values at even
indexes and cosine values at odd indexes. The positional encoding tensor
$\vec{e}\in\mathbb{R}^{w,h,d_{e}}$ has elements equal to

$\displaystyle\vec{e}_{u,v,2p}$ $\displaystyle=\sin\left(\theta(p)u\right)$
$\displaystyle\vec{e}_{u,v,2p+1}$ $\displaystyle=\cos\left(\theta(p)u\right)$
$\displaystyle\vec{e}_{u,v,2q+\frac{d_{e}}{2}}$
$\displaystyle=\sin\left(\theta(q)v\right)\quad$
$\displaystyle\vec{e}_{u,v,2q+1+\frac{d_{e}}{2}}$
$\displaystyle=\cos\left(\theta(q)v\right),$

where $\theta(p)=\frac{1}{10000^{\frac{4p}{d_{e}}}}$. On appending this tensor
to the input $z^{i}$ along the third dimension, we get

$z^{i+1}_{u,v,\cdot}=[z^{i}_{u,v,\cdot},e_{u,v,\cdot}].$

With respect to the above, we propose using blocks combining Convolution,
Attention, and Position encoding, in this order (we call them CoAt blocks), as
a part of our NN architecture. The CoAt blocks can therefore relate hidden
vectors from a local neighborhood through convolution, from a distant part of
the maze through attention, and calculate distances between them through
position encoding, as has been explained in (Tsai et al. 2019). Since CoAt
blocks preserve the size of the maze,333Convolution layers are appropriately
padded to preserve sizes. they are ”scale-free” in the sense that they can be
used on a maze of any size. Yet, we need to provide an output of a fixed
dimension to estimate the heuristic function and the policy. The outputs of
the last CoAt blocks are flattened by a $1\times 1$ window, centered around
the agent’s location and fed to a fully-connected layer and an output head
(see Figure 1). For example, assuming $z^{L}$ to be the very last layer, and
agent is on position $u,v$, the vector $z_{u,v,\cdot}$ is of constant
dimension equal to the number of filters and is used as an input to the fully-
connected layers providing the desired outputs (heuristic values, policy).

Next, we describe the implementation of CoAt blocks in the network
architectures we used for all the domains. The network is shown in Figure 1
and its structure is similar to that of (Groshev et al. 2017). It uses
preprocessing convolution layers $P_{1},\ldots,P_{n},$ $n=7,$ (further called
pre-conv) containing 64 filters where each convolution filter is of the shape
$3\times 3$; after the network splits into two heads, it uses four CoAt blocks
in each head instead of seven convolution layers used in (Groshev et al.
2017). The convolution layers in the CoAt blocks contain 180 filters of size
$3\times 3$ each. The attention block uses two attention heads. Each head is
finished by two fully-connected layers with reduction to a fixed dimension as
described above.

The input to the network is the current state of the game and a goal state,
$s$ and $s_{g}$, respectively. Each state is represented by a tensor of
dimensions equal to width and height (fixed to $10\times 10$ for Sokoban, to
$15\times 15$ for Maze-with-Teleorts, and to $4\times 4$ for Floor-Tile) of
the maze $\times$ objects. The objects stands for one-hot encoding of the
object states on a grid position (e.g., for Sokoban, we have wall, empty, box,
agent and box target, for Maze-with-Teleport agent, wall, floor, goal and
teleports 1-4, and for Floor-Tile agent1, agent2, black and white), which we
could derive automatically from the grounded representation. An important
design detail is that all convolutions are padded, which means that the output
has the same dimension as the input, and they feature skip-connections444A
layer $c$ augmented by a skip connection calculates the output as $x+c(x)$
instead of the usual $x$. alleviating a possible vanishing gradient (He et al.
2016).

We have implemented two different versions of the network according to their
heads: dual-head with estimating policy and heuristic value and single-head
with just estimating heuristic value.. In Maze-with-Teleports and Sokoban the
dual-head representation performed best, while the best network for Floor-tile
uses just a single head estimating heuristic value (which means there is no
separate head estimating policy). The presence of two agents would make it
difficult to design a policy network in a domain-independent setting and would
result in a much larger network, which is inconvenient, time-consuming and
computationally expensive. The other implementation details of the Floor-Tile
network are the same as the heuristic networks of Sokoban and Maze-with-
Teleports (see Figure 1).

## Imitation and Curriculum Learning

Imitation learning (Pomerleau 1989) is a framework for learning a behavior
policy from demonstrations. We present demonstrations in the form of optimal
state-action plans, with each pair indicating the action to take at the state
being visited. Generally, imitation learning is useful when it is easier for
an expert to demonstrate the desired behaviour rather than to specify a reward
function which would generate the same behaviour or to directly learn the
policy

A curriculum refers to an interactive system of instruction and learning with
specific goals, contents, strategies, measurement, and resources. The desired
outcome of curriculum is a successful transfer and/or development of
knowledge, skills, and attitudes. In the context of AI, curriculum learning is
a way of training a machine learning model where more difficult aspects of a
problem are gradually introduced in such a way that the model is always
optimally challenged.

Curriculum learning (Elman 1993) describes a type of learning in which we
first start out with only easy examples of a task and then gradually increase
the task difficulty. Humans have been learning according to this principle
ever since, but in the common learning setting, we use neural networks and
instead let them train on the whole data set.

Curriculum learning strategies have been successfully employed in different
areas of machine learning, for a wider range of tasks (Bengio et al. 2009).
However, the necessity of finding a way to rank the samples from easy to hard,
as well as the right pacing function for introducing more difficult data can
limit the usage of the curriculum approaches.

In order to extend the training set without providing any additional plans
that the neural network would not be able to solve, we turn our attention to a
form of curriculum learning for neural networks. This approach that partially
circumvents this problem by re-training from unseen test samples of increasing
complexity.

In our case, curriculum learning is used to develop scale-free heuristic
values for a wider selection of AI planning problems. Specifically, in our
experiments we have quickly reached the capability of planners at larger
sizes. To further improve our heuristic function to scale to bigger problems,
we re-train our network by extending the training set to include harder
problem instances.

We first train the heuristic network on a training set containing easy problem
instances quickly solvable by an optimal, then use this NN as a heuristic
function inside A*, and then extend the training set by more difficult problem
instance the NN has solved and retrain the NN. Thus, we perform a bootstrap,
where the NN is gradually trained on more difficult problem instances.

This way, curriculum learning plays an important role in improving the
performance of the heuristic network on not just the trained dimensions but
also on higher dimensions by extrapolation. For curriculum learning, the
learning rate is reduced in successive training iterations.

## Experimental Results

This section briefly describes the details of training and presents the
experimental results on the compared PDDL benchmark domains: Sokoban, Maze-
with-Teleports, and Floor-Tile. A* algorithms with learnt heuristic functions
realized by the proposed convolution-attention-position networks (further
denoted as A*-CoAt) are compared to A* with learned heuristic function
realized by convolutional networks as proposed in (Groshev et al. 2017)
(denoted as A*-CNN), and to the state of the art planners LAMA (Richter and
Westphal 2010), SymBA* (Torralba et al. 2014), and Mercury (Katz and Hoffmann
2014). We emphasize that A*-CNN and A*-CoAt uses vanilla A* search algorithm
(Hart, Nilsson, and Raphael 1968) without any additional tweaks. In case of
Sokoban, we also compare our planner to a solution based on Reinforcement
Learning (Racanière et al. 2017).

On all the compared domains, we analyse the strength of our learnt heuristic
and generalization property by solving grid mazes of increasing complexities,
approximated by the number of boxes in Sokoban, grids of higher dimensions in
Floor-Tile and Maze-with-Teleports, and rotated mazes in Maze-with-Teleports.

### Training

#### Sokoban:

The policy-heuristic network we wish to learn accepts a state of a game, $s$
as an input and returns the next action, $a,$ and a heuristic value, $h(s),$
as an output. The training set
$\mathcal{X}_{\mathrm{trn}}=\\{(s_{i},a_{i},|\pi^{*}(s_{i})|)\\}_{i=1}^{n}.$
therefore consists of $n\approx 10^{6}$ of these triples, i.e.
$\mathcal{X}_{\mathrm{trn}}=\\{(s_{i},a_{i},|\pi^{*}(s_{i})|)\\}_{i=1}^{n}.$
The triples in the training set were created by randomly generating $40000$
Sokoban instances using gym-sokoban (Schrader 2018). Each instance has
dimension $10\times 10$ and it always contains only 3 boxes (and an agent).
SymBA* (Torralba et al. 2014), a planner that generates optimal solutions was
used to generate optimal plans $\pi^{*}$ for each of these n Sokoban
instances. In each plan trajectory, the distance from a current state to the
goal state is learned as the heuristic value, $h(s_{i}).$ Thus, the collection
of all state-action-heuristic triples form the training set
$\mathcal{X}_{\mathrm{trn}}$.

The Sokoban mazes in the _training set were created with only three boxes_.
This means that in the testing set, when we are solving instances with more
boxes, we are evaluating its _extrapolation_ to more complex unseen
environments, which cannot be solved by naive memorisation. However, our
limited training set (containing 3 boxes) hinders the full potential of the
neural network. With curriculum learning, we fine-tune the neural network
using a training set containing Sokoban mazes of dimensions $10\times 10$ with
3,4 5 6 and 7 boxes that have been already solved by the A*-NN with the
corresponding architecture. This, therefore improves the heuristic function
without the need to train the network from scratch and, more importantly,
without the need to use other planners to create new plans.

#### Maze-with-Teleports:

The policy and heuristic network returns an action $a$, and a heuristic value,
$h(s)$ as outputs. The training set $\mathcal{X}_{\mathrm{trn}}$consists of
$\approx$ 10000 maze problems of dimension $15\times 15$. The mazes in
$\mathcal{X}_{\mathrm{trn}}$were generated using a maze
creator555https://github.com/ravenkls/Maze-Generator-and-Solver with slight
modifications. Random walls were broken and a total of 4 pairs of teleports
that connect different parts of the maze were created inside each training
sample. As in the case of Sokoban, SymBA* (Torralba et al. 2014) was used to
generate optimal solutions for the problems in the training set. The mazes for
training were generated such that the initial position of the agent was in the
upper-left corner and the goal was in the lower-right corner. Later,in our
evaluations, we rotate each maze to investigate whether the heuristic function
is rotation independent.

#### Floor-Tile:

The Floor-Tile heuristic network accepts a state of a game, $s$ as an input
and returns a heuristic value, $h(s)$ as an output. The training set initially
consists of $\approx$ 10000 Floor-Tile instances of dimension $4\times 4$ with
2 agents. In our version of Floor-Tile, we assign _white_ to the first agent
and _black_ to the second agent. The colors assigned to the agents are fixed
and cannot be flipped at any stage of the game. SymBA* (Torralba et al. 2014)
was used to generate optimal solutions for the Floor-Tile domain.

Since it is easy to generate Floor-Tile instances of increasing complexity (by
increasing the size and varying the initial positions of the two agents), we
experiment again with curriculum learning (Bengio et al. 2009) to develop
scale-free heuristic values. Specifically, in our experiments we have quickly
reached the capability of planners at size $6\times 5$ (more on this below).
To further improve our heuristic function to scale to bigger problems, we re-
train our network by extending the training set to include harder problem
instances (of size $4\times 4$, $5\times 5$, $6\times 5$ and $6\times 6$) the
heuristic network has already solved.

All neural networks were trained by the Adam optimiser (Kingma and Ba 2014)
with a default learning rate of 0.001 for optimisation. In Sokoban and Maze-
with-Teleports, the categorical cross entropy loss function was used to
minimise the loss in the action prediction network and the mean absolute error
loss was the loss function in the heuristic network. In Floor-Tile, the mean
absolute loss was used in the heuristic network. For curriculum learning,
domain, the learning rate was reduced to $\approx 1\times 10^{-4}$ in
successive training iterations. Our experiments were conducted in Keras-2.4.3
framework with Tensorflow-2.3.1 as the backend. We used a NVIDIA Tesla GPU
model V100-SXM2-32GB for training the neural networks.

### Comparison to prior State-of-the-Art

#### Sokoban:

The evaluation set consists of 2000 mazes of dimensions $10\times 10$ with 3,
4, 5, 6 or 7 boxes (recall that the training set contain mazes with only 3
boxes). Unless said otherwise, the quality of heuristics is measured by the
relative number of solved mazes, which is also known as coverage. Table 1
shows the coverage of compared planners, where _all_ planners were given 10
minutes to solve each Sokoban instance. We see that the classical planners
solved all test mazes with three and four boxes but as the number of boxes
increase, the A*-NN starts to have an edge. On problem instances with six and
seven boxes, A*-CoAt achieved the best performance, even though it was trained
only on mazes with three boxes. The same table shows, that A*-CoAt offers
better coverage than A*-CNN, and we can also observe that curriculum learning
(see column captioned curr.) significantly improves the coverage.

We attribute SymBA*’s poor performance to its feature of always returning
optimal plans while we are content with sub-optimal plans. LAMA had even lower
success in solving more complicated mazes than SymBA*, despite having the
option to output sub-optimal plans. To conclude, with an increase in the
complexity of the mazes, the neural networks outshine the classical planners
which makes them a useful alternative in the Sokoban domain.

The average plan length, shown in Table 2, reveals that the heuristic learnt
by the CoAt network is strong, as the average length of the plans is close to
that of SymBA* which always returns optimal solutions. We conclude that the
proposed CoAt network delivers a strong heuristic outside its training, much
better than that of the CNN (Groshev et al. 2017) network and the planners
(for mazes with more than 6 boxes).

|  |  |  |  | normal |  | curr.
---|---|---|---|---|---|---|---
#b |  SBA* |  Mrcy |  LAMA |  |  CNN |  CoAt |  |  CoAt
3 |  1 |  1 |  1 |  |  0.92 |  0.94 |  |  0.95
4 |  1 |  1 |  1 |  |  0.87 |  0.91 |  |  0.93
5 |  0.95 |  0.75 |  0.89 |  |  0.83 |  0.89 |  |  0.91
6 |  0.69 |  0.60 |  0.65 |  |  0.69 |  0.76 |  |  0.85
7 |  0.45 |  0.24 |  0.32 |  |  0.58 |  0.63 |  |  0.80
Table 1: Fraction of solved Sokoban mazes (coverage, higher is better) of SymBA* (SBA*), Mercury (Mrcy), LAMA, A*-CNN (caption CNN) and the proposed A*-CoAt (caption CoAt). A*-CNN and A*-CoAt (with caption normal) use networks trained on mazes with three bozes; A*-CoAt (with caption curr.) used curriculum learning. #b | SBA* | Mrcy | CNN | CoAt
---|---|---|---|---
3 | 21.40 | 21.70 | 24.20 | 22.20
4 | 34.00 | 34.33 | 40.53 | 36.00
5 | 38.82 | 42.83 | 45.52 | 39.11
6 | 41.11 | - | 51.00 | 42.11
7 | - | - | 54.33 | 44.17
Table 2: Average plan length of SymBA*, Mercury, A* -CNN (Groshev et al. 2017)
(denoted as CNN) and that with the A*-CoAt. For clarity, we do not show
results of LAMA, as it is performs exactly like SymBA* for 3 and 4 boxes.
Column captioned #b indicates the number of boxes in different categories.

CoAt network is also on par with Deep Mind’s implementation of Reinforcement
Learning (DM-RL) in solving Sokoban (Racanière et al. 2017). Instead of re-
implementing DM-RL by ourselves, we report the results on their test
set666Available at https://github.com/deepmind/boxoban-levels. containing
$10\times 10$ Sokoban mazes with 4 boxes. While DM-RL had a coverage of 90%,
our A*-CoAt (trained on mazes with three boxes) has a coverage 87%, and our
A*-CoAt with curriculum learning has a coverage of 98.29%
777https://github.com/deepmind/boxoban-
levels/blob/master/unfiltered/test/000.txt. Taking into account that DM-RL’s
training set contained $10^{10}$ state-action pairs from mazes with 4 boxes,
A*-CoAt achieves higher coverage using several orders of magnitude smaller
training set.

#### Maze-with-Teleports:

The evaluation set contains a total of 2100 training samples of dimensions
$15\times 15$, $20\times 20$, $30\times 30$, $40\times 40$, $50\times 50$,
$55\times 55$ and $60\times 60$. Each maze in the evaluation set contains 4
pairs of teleports that connects different parts of the maze. From Table 3, we
see that the performance of A*-CNN and A*-CoAt (initially trained on $15\times
15$ mazes) is the same as SymBA*888The planners and NNs were given 10 minutes
to solve each maze instance. for dimensions up to $40\times 40$ and is
consistently better for problem instances of size $50\times 50$, $55\times 55$
and $60\times 60$.

All ”No Rotation” mazes were created such that the agents start in the top
left corner and the goal is in the bottom right corner. This allows us to
study to which extent the learnt heuristic is rotation-independent (domain
independent planners are rotation invariant by default). The same Table
therefore reports fraction of solved mazes that have been rotated by 90∘, 180∘
and 270${}^{\circ}.$ The results clearly show that the proposed heuristic
function featuring CoAt blocks generalizes better than the one utilizing only
convolutions, as the solved rotated instances of A*-CoAt network are
comparable to the non-rotated case. Rotating mazes have no effect on SymBA*
(the complexity is solely dependent on the grid size) and the coverage rate
stays unaffected.

From the results in Table 3, it can be concluded that the CoAt blocks (1)
improve detection of non-local actions (teleports) compared to state-of-the-
art planners such as SymBA*; (2) learn ‘useful’ information from the mazes
which makes the network robust to rotations; (3) learn to approximate
distances inside the mazes which results in a scale-free heuristic function.

|  | No Rotation |  |  $90^{\circ}$ rotation |  |  $180^{\circ}$ rotation |  |  $270^{\circ}$ rotation
---|---|---|---|---|---|---|---|---
size | SBA* | CNN | CoAt |  | CNN | CoAt |  | CNN | CoAt |  | CNN | CoAt
$15\times 15$ | 1 | 1 | 1 |  | 1 | 1 |  | 1 | 1 |  | 1 | 1
$20\times 20$ | 1 | 1 | 1 |  | 1 | 1 |  | 1 | 1 |  | 1 | 1
$30\times 30$ | 1 | 1 | 1 |  | 1 | 1 |  | 1 | 1 |  | 1 | 1
$40\times 40$ | 1 | 1 | 1 |  | 1 | 1 |  | 1 | 1 |  | 1 | 1
$50\times 50$ | 0.92 | 0.94 | 1 |  | 0.91 | 1 |  | 0.92 | 1 |  | 0.91 | 1
$55\times 55$ | 0.55 | 0.78 | 0.89 |  | 0.71 | 0.85 |  | 0.70 | 0.87 |  | 0.69 | 0.87
$60\times 60$ | - | 0.73 | 0.76 |  | 0.68 | 0.75 |  | 0.66 | 0.74 |  | 0.68 | 0.75
Table 3: Fraction of solved mazes with teleports (coverage) of SymBA*, A*
algorithm with convolution network (Groshev et al. 2017) (denoted as CNN) and
that with the proposed Convolution-Position-Attention (CoAt) network. Only
non-rotated mazes (No Rotation) of size $15\times 15$ were used to train the
heuristic function. On mazes rotated by $90^{\circ},$ $189^{\circ},$
$270^{\circ}$, the heuristic function has to extrapolate outside its training
set.

#### Floor-Tile:

The evaluation set consists of 400 problem instances of sizes $5\times 5$,
$6\times 5$, $6\times 6$ and $7\times 7$. Similarly to Sokoban, we first
trained the CNN and CoAt NNs on small problem instances of size $4\times 4$
(see columns denoted as ”normal”) and extrapolated it to instances of higher
dimensions outside of the training set. Table 4 shows the coverage of SymBA*
and the heuristics learnt by the NNs inside A* for different problem
instances. The results are similar to those we have observed in Sokoban. On
smaller problem instances, the classical planner SymBA* is better; on larger
problem instances, the NNs are better. The test set deliberately includes
problem instances of size $6\times 5$ to demonstrate the exact break point up
to which SymBA* is able to generate solutions. Beyond grid size $6\times 5$,
_all_ state of the art planners fail and the solutions are generated only by
the NNs. The heuristics generated by the A*-CoAt network can be extrapolated
to solve 71% of the tiling problems of size $6\times 6$. On further increasing
the grid dimension, the coverage of the A*-CoAt decreases to 29% and even
lower while A*-CNN is unable to generate solutions. The rightmost column (see
column captioned “curr”) in Table 4 shows an improvement in coverage for
dimensions $6\times 6$ and $7\times 7$ on implementing curriculum learning.

|  | normal |  | curr.
---|---|---|---|---
size | SBA* | CNN | CoAt |  | CoAt
$4\times 4$ | 1 | 0.92 | 0.96 |  | 0.96
$5\times 5$ | 1 | 0.89 | 0.93 |  | 0.93
$6\times 5$ | 1 | 0.78 | 0.88 |  | 0.91
$6\times 6$ | - | 0.54 | 0.71 |  | 0.89
$7\times 7$ | - | - | 0.29 |  | 0.76
Table 4: Fraction of solved Floor-Tile problem instances (coverage) of SymBA*,
A*-CNN, and the proposed A*-CoAt. Fractions in columns captioned “normal” /
“curr.” are of A* with heuristic functions trained on problem instances of
size $4\times 4$ / by curriculum training respectively (see details in the
text).

## Conclusion and Future Work

We showed that learning a strong heuristic function for PDDL domains with
underlying grid structure is possible without the need for any specific domain
knowledge. In fact, the architecture of the learning approach is general to
any PDDL-type planning problem, and the learning can be executed on any vector
of propositions, or finite-domain variables as states forming the input to the
neural network. Identifying some structure in advance is advantageous.

While the heuristic function can generate sub-optimal plans, our experiments
suggest that the plan quality is not far from the optimum. Moreover, while we
have generated training data from a classical planner on small problem sizes,
the proposed architecture is able to generalize and successfully solve more
difficult problem instances, where it surpasses classical domain-independent
planners, while improving on previously known state-of-the-art.

Our experiments further suggest that the learnt heuristic can further improve,
if it is retrained / fine-tuned on problem instances it has previously solved.
This form of curriculum learning aids the heuristic function in solving mainly
large and more complex problem instances that are otherwise not solvable by
domain independent planners within 10 minutes.

As future work, our next goal would be to better understand if the learnt
heuristic function is similar to something that is already known, or something
so novel that it can further enrich the field; i.e., what kind of underlying
problem structure we can learn by which network type best, possibly in form of
studying generic types (Long and Fox 2000).

Our experiments with curriculum learning suggest that the neural network might
boot-strap itself by first learning on simple trivial examples and gradually
solving more difficult ones by adding them to the training set. This raises
two questions, mainly regarding the limit of this process and if the gains
obtained by using larger networks will vanish.

We believe that an improvement in the heuristic function is tied to the
generation of problem instances that inherently possess the right level of
difficulty, by which we mean that they have to be just on the edge of
solvability, such that the plan can be created and added to the training set.
We are fully aware that the problem instance generation itself is a hard
problem, but we cannot imagine the above solution to be better than
specialized domain-dependent Sokoban solvers without such a generator (unless
the collection of all Sokoban mazes posses this property). We also question
the average estimation error minimized during learning of the heuristic
function. It might put too much emphasis on simple problem instances that are
already abundant in the training set while neglecting the difficult ones. We
wish to answer some of the above question in the future in an endeavour to
generate strong, scale-free heuristics.

## References

  * Agostinelli et al. (2019) Agostinelli, F.; McAleer, S.; Shmakov, A.; and Baldi, P. 2019.  Solving the Rubik’s cube with deep reinforcement learning and search.  _Nature Machine Intelligence_ , 1(8): 356–363.
  * 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.
  * Asai and Fukunaga (2017) Asai, M.; and Fukunaga, A. 2017.  Classical planning in deep latent space: Bridging the subsymbolic-symbolic boundary.  _arXiv preprint arXiv:1705.00154_.
  * Bäckström and Nebel (1995) Bäckström, C.; and Nebel, B. 1995.  Complexity Results for SAS+ Planning.  _Comput. Intell._ , 11: 625–656.
  * Bengio et al. (2009) Bengio, Y.; Louradour, J.; Collobert, R.; and Weston, J. 2009.  Curriculum learning.  In _Proceedings of the 26th annual international conference on machine learning_ , 41–48.
  * Bonet and Geffner (2001) Bonet, B.; and Geffner, H. 2001.  Planning as heuristic search.  _Artificial Intelligence. 2001 Jun; 129 (1-2): 5-33._
  * Bottou and Bousquet (2007) Bottou, L.; and Bousquet, O. 2007.  The Tradeoffs of Large Scale Learning.  In Platt, J. C.; Koller, D.; Singer, Y.; and Roweis, S. T., eds., _NIPS_ , 161–168.
  * Culberson (1999) Culberson, J. 1999.  Sokoban is PSPACE-complete.  _Proceedings of the International Conference on Fun with Algorithms_ , 65–76.
  * Edelkamp and Schrödl (2012) Edelkamp, S.; and Schrödl, S. 2012.  _Heuristic Search - Theory and Applications_.  Academic Press.
  * Elman (1993) Elman, J. L. 1993.  Learning and development in neural networks: the importance of starting small.  _Cognition_ , 48(1): 71–99.
  * Ernandes and Gori (2004) Ernandes, M.; and Gori, M. 2004.  Likely-admissible and sub-symbolic heuristics.  In _Proceedings of the 16th European Conference on Artificial Intelligence_ , 613–617. Citeseer.
  * Fern, Khardon, and Tadepalli (2011) Fern, A.; Khardon, R.; and Tadepalli, P. 2011.  The first learning track of the international planning competition.  _Machine Learning_ , 84: 81–107.
  * 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.
  * Fox and Long (2003) Fox, M.; and Long, D. 2003.  PDDL2. 1: An extension to PDDL for expressing temporal planning domains.  _Journal of artificial intelligence research_ , 20: 61–124.
  * Gomoluch et al. (2020) Gomoluch, P.; Alrajeh, D.; Russo, A.; and Bucchiarone, A. 2020.  Learning Neural Search Policies for Classical Planning.  In _Proceedings of the International Conference on Automated Planning and Scheduling_ , volume 30, 522–530.
  * Groshev et al. (2017) Groshev, E.; Goldstein, M.; Tamar, A.; Srivastava, S.; and Abbeel, P. 2017.  Learning generalized reactive policies using deep neural networks.  _arXiv preprint arXiv:1708.07280_.
  * Hart, Nilsson, and Raphael (1968) Hart, P. E.; Nilsson, N. J.; and Raphael, B. 1968.  A formal basis for the heuristic determination of minimum cost paths.  _IEEE transactions on Systems Science and Cybernetics_ , 4(2): 100–107.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 770–778.
  * Howey, Long, and Fox (2004) Howey, R.; Long, D.; and Fox, M. 2004.  VAL: Automatic Plan Validation, Continuous Effects and Mixed Initiative Planning Using PDDL.  In _ICTAI_ , 294–301. IEEE Computer Society.
  * Katz and Hoffmann (2014) Katz, M.; and Hoffmann, J. 2014.  Mercury planner: Pushing the limits of partial delete relaxation.  _IPC 2014 planner abstracts_ , 43–47.
  * Kingma and Ba (2014) Kingma, D. P.; and Ba, J. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Long and Fox (2000) Long, D.; and Fox, M. 2000.  Automatic Synthesis and Use of Generic Types in Planning.  In _AAAI_ , 196–205. AAAI Press.
  * Mostow and Prieditis (1989) Mostow, J.; and Prieditis, A. 1989.  Discovering Admissible Heuristics by Abstracting and Optimizing: A Transformational Approach.  In _IJCAI_.
  * Pomerleau (1989) Pomerleau, D. A. 1989.  Alvinn: An autonomous land vehicle in a neural network.  In _Advances in neural information processing systems_ , 305–313.
  * Racanière et al. (2017) Racanière, S.; Weber, T.; Reichert, D.; Buesing, L.; Guez, A.; Jimenez Rezende, D.; Puigdomènech Badia, A.; Vinyals, O.; Heess, N.; Li, Y.; et al. 2017.  Imagination-augmented agents for deep reinforcement learning.  _Advances in neural information processing systems_ , 30: 5690–5701.
  * 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.
  * Schaal (1999) Schaal, S. 1999.  Is imitation learning the route to humanoid robots?  _Trends in cognitive sciences_ , 3(6): 233–242.
  * Schrader (2018) Schrader, M.-P. B. 2018.  gym-sokoban.  https://github.com/mpSchrader/gym-sokoban.
  * Shavlik (1989) Shavlik, J. W. 1989.  Acquiring Recursive Concepts with Explanation-Based Learning.  In _IJCAI_ , 688–693. Citeseer.
  * Sievers et al. (2019) Sievers, S.; Katz, M.; Sohrabi, S.; Samulowitz, H.; and Ferber, P. 2019.  Deep Learning for Cost-Optimal Planning: Task-Dependent Planner Selection.  In _AAAI_ , 7715–7723. AAAI Press.
  * Silver et al. (2017) Silver, D.; Schrittwieser, J.; Simonyan, K.; Antonoglou, I.; Huang, A.; Guez, A.; Hubert, T.; Baker, L.; Lai, M.; Bolton, A.; et al. 2017.  Mastering the game of go without human knowledge.  _nature_ , 550(7676): 354–359.
  * Srivastava, Immerman, and Zilberstein (2011) Srivastava, S.; Immerman, N.; and Zilberstein, S. 2011.  A new representation and associated algorithms for generalized planning.  _Artificial Intelligence_ , 175(2): 615–647.
  * Tesauro (2002) Tesauro, G. 2002.  Programming backgammon using self-teaching neural nets.  _Artificial Intelligence_ , 134(1-2): 181–199.
  * Thrun (1994) Thrun, S. 1994.  Learning to play the game of chess.  _Advances in neural information processing systems_ , 7: 1069–1076.
  * Torralba et al. (2014) Torralba, A.; Alcázar, V.; Borrajo, D.; Kissmann, P.; and Edelkamp, S. 2014\.  SymBA*: A symbolic bidirectional A* planner.  In _International Planning Competition_ , 105–108.
  * Torrey et al. (2006) Torrey, L.; Shavlik, J.; Walker, T.; and Maclin, R. 2006.  Skill acquisition via transfer learning and advice taking.  In _European Conference on Machine Learning_ , 425–436. Springer.
  * Tsai et al. (2019) Tsai, Y.-H. H.; Bai, S.; Yamada, M.; Morency, L.-P.; and Salakhutdinov, R. 2019\.  Transformer Dissection: An Unified Understanding for Transformer’s Attention via the Lens of Kernel.  _arXiv preprint arXiv:1908.11775_.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30: 5998–6008.
  * Virseda, Borrajo, and Alcázar (2013) Virseda, J.; Borrajo, D.; and Alcázar, V. 2013.  Learning heuristic functions for cost-based planning.  _Planning and Learning_ , 6.
  * Yoon, Fern, and Givan (2012) Yoon, S. W.; Fern, A.; and Givan, R. 2012.  Inductive policy selection for first-order MDPs.  _arXiv preprint arXiv:1301.0614_.


Efficient Calculation the Number of Partitions of the Set
$\\{1,2,\ldots,3n\\}$ into Subsets $\\{x,y,z\\}$ Satisfying $x+y=z$
Christian Hercher
Institut für Mathematik
Europa-Universität Flensburg
Auf dem Campus 1b
24944 Flensburg
Germany
<EMAIL_ADDRESS>

Frank Niedermeyer
Bonn
Germany
<EMAIL_ADDRESS>

###### Abstract

Consider the set $\\{1,2,\ldots,3n\\}$. We are interested in the number of
partitions of this set into subsets of three elements each, where the sum of
two of them equals the third.

We give some criteria such a partition has to fulfill, which can be used for
efficient pruning in the search for these partitions. In particular, we
enumerate all such partitions for $n=16$ and $n=17$ adding new terms to the
series A108235 in the Online Encyclopedia of Integer Sequences.

##  1 Introduction

The enumeration of set partitions with different constraints as pattern
avoiding is a long-studied field of problems; see Mansour [2] for an overview.

We are interested in partitions of the set $\\{1,\ldots,3n\\}$ for a positive
integer $n$ into subsets of size 3 each with the additional property that in
every such subset the sum of the two smaller elements gives the third one.

This problem has wide connections to cyclic Steiner triple systems, modified
Nim games or arranging colored blocks; see Nowakowski [4] for an overview.

E.g., Nickerson asks in [3] for an arrangement of two copies of all integers
$i\in\\{1,\ldots,2n\\}$ such that the two copies of $i$ are separated by
exactly $i-1$ other terms. Thus, $11423243$ is a Nickerson sequence for $n=4$.
If $a_{1},a_{2},\ldots,a_{2n}$ is such a Nickerson sequence, then let
$p_{1}(i)$ be the index of the first occurrence of the number $i$ and
$p_{2}(i)$ the index of the second one. Then the sets
$\\{p_{1}(i),p_{2}(i)\\}$ are partitioning the set $\\{1,\ldots,2n\\}$, and
each difference $p_{2}(i)-p_{1}(i)=i$ occurs exactly once. Thus, the sets
$\\{i,p_{1}(i)+n,p_{2}(i)+n\\}$ are a partition of $\\{1,\ldots,3n\\}$. Hence,
every solution to Nickerson’s problem leads to such a partition. (Note that
the revers is not true.)

But the task of finding the number of such partitions is also a good riddle;
see e.g. [6]. That was the context in which the authors of this paper had
first contact with this problem.

It is well-known that such a partition can only exist if $n\equiv 0\
\mbox{\rm(mod}\ 4\mbox{\rm)}$ or $n\equiv 1\ \mbox{\rm(mod}\ 4\mbox{\rm)}$.
The proof of this statement is straightforward: Suppose we have a partition of
$\\{1,\ldots,3n\\}$ into such subsets $\\{x_{i},y_{i},z_{i}\\}$ with
$x_{i}+y_{i}=z_{i}$. Then, clearly, we have

$\sum_{i}(x_{i}+y_{i})=\sum_{i}z_{i}=\frac{1}{2}\sum_{k=1}^{3n}k=\frac{3n(3n+1)}{4}.$

So $4\mid 3n(3n+1)$. Since $3n$ and $3n-1$ are relatively prime it follows
$4\mid 3n$ or $4\mid 3n+1$, and hence, we get $n\equiv 0\ \mbox{\rm(mod}\
4\mbox{\rm)}$ or $n\equiv 1\ \mbox{\rm(mod}\ 4\mbox{\rm)}$, $\Box$.

If a positive integer $n$ is of the necessary form, then such partitions of
$\\{1,\ldots,3n\\}$ always exist. Examples of general constructions are given
by Nowakowski [4].

The question of how many such partitions for a given $n$ exist is not so easy
to answer. In the next sections, we give tools for an efficient computation of
these numbers.

##  2 Key Ideas

In the following, we want to use a recursive approach to search for such
partitions: Find one subset $\\{x,y,z\\}$ with $x+y=z$, eliminate those
numbers and search for the next one in the remaining set until all numbers are
partitioned. This can be done as in the naive recursive Algorithm 1.

Input: A nonempty set
$S=\\{b_{1},b_{2},\ldots,b_{3m}\\}\subseteq\\{1,\ldots,3n\\}$ with
$b_{1}<b_{2}<\cdots<b_{3m}$

Output: The number of partitions
$P=\\{\\{x_{1},y_{1},z_{1}\\},\ldots,\\{x_{m},y_{m},z_{m}\\}\\}$ of $S$ into
pairwise disjoint subsets $\\{x_{i},y_{i},z_{i}\\}$ satisfying
$x_{i}+y_{i}=z_{i}$ for all $1\leq i\leq m$

1 Function  _Counting_Partitions( $S$)_:

2 if  _$m=1$_ then // End of Recursion

3 if  _$b_{1}+b_{2}=b_{3}$_ then

4 return _1_

5 else

6 return _0_

7

8 $number\\_of\\_partitions\leftarrow 0$;

9 for  _$i=2$ to $3m-1$_ do

10 if  _there is a $i<k\leq 3m$ with $b_{1}+b_{i}=b_{k}$_ then // found a
triple $(x,y,z)=(b_{1},b_{i},b_{k})$

11 $S^{\prime}\leftarrow S\setminus\\{b_{1},b_{i},b_{k}\\}$;

12 $number\\_of\\_partitions+=Counting\\_Partitions(S^{\prime})$;

13

14

15 end for

16 return _$number\\_of\\_partitions$_ ;

17

18 end

Algorithm 1 Naive Recursive Algorithm.

For a much faster calculation, we want to know as early as possible if a
complete such partition is not possible anymore. The first and most used
constraint is given in the next theorem.

######  Theorem 1.

Let $m$ be a positive integer, and $S:=\\{b_{1},b_{2},\ldots,b_{3m}\\}$ a set
of positive integers with $b_{1}<b_{2}<\cdots<b_{3m}$ which can be partitioned
into subsets $\\{x_{i},y_{i},z_{i}\\}$, $i=1,\ldots,m$ with
$x_{i}+y_{i}=z_{i}$. Furthermore, let $S_{1}:=\sum_{k=1}^{2m}b_{k}$ and
$S_{2}:=\sum_{k=2m+1}^{3m}b_{k}$. Then

$S_{1}\leq S_{2}.$

###### Proof.

For a given set $S=\\{b_{1},b_{2},\ldots,b_{3m}\\}$ with
$b_{1}<b_{2}<\cdots<b_{3m}$ let $\bigcup_{i=1}^{m}\\{x_{i},y_{i},z_{i}\\}=S$
and $x_{i}+y_{i}=z_{i}$ for all $i=1,\ldots,m$. Then we have

$S_{1}=\sum_{k=1}^{2m}b_{k}\leq\sum_{i=1}^{m}(x_{i}+y_{i})=\sum_{i=1}^{m}z_{i}\leq\sum_{k=2m+1}^{3m}b_{k}=S_{2}.$

∎

This leads to the following basic Algorithm 2 for enumerating all such
partitions of subsets of $\\{1,\ldots,3n\\}$.

Input: A nonempty set
$S=\\{b_{1},b_{2},\ldots,b_{3m}\\}\subseteq\\{1,\ldots,3n\\}$ with
$b_{1}<b_{2}<\cdots<b_{3m}$, the sums $S_{1}:=\sum_{i=1}^{2m}b_{i}$ and
$S_{2}:=\sum_{i=2m+1}^{3m}b_{i}$

Output: The number of partitions
$P=\\{\\{x_{1},y_{1},z_{1}\\},\ldots,\\{x_{m},y_{m},z_{m}\\}\\}$ of $S$ into
pairwise disjoint subsets $\\{x_{i},y_{i},z_{i}\\}$ satisfying
$x_{i}+y_{i}=z_{i}$ for all $1\leq i\leq m$

1 Function  _Counting_Partitions( $S$, $S_{1}$, $S_{2}$)_:

2 if  _$m=1$_ then // End of Recursion

3 if  _$S_{1}=S_{2}$_ then

4 return _1_

5 else

6 return _0_

7

8 if  _$S_{1} >S_{2}$_ then // Condition of Theorem 1 does not hold

9 return _0_

10 $number\\_of\\_partitions\leftarrow 0$;

11 for  _$i=2$ to $3m-1$_ do

12 if  _there is a $i<k\leq 3m$ with $b_{1}+b_{i}=b_{k}$_ then // found a
triple $(x,y,z)=(b_{1},b_{i},b_{k})$

13 $S^{\prime}\leftarrow S\setminus\\{b_{1},b_{i},b_{k}\\}$;

14 if  _$i\geq 2m+1$_ then

15 $S_{1}^{\prime}\leftarrow S_{1}-b_{1}-b_{2m}$;

16 $S_{2}^{\prime}\leftarrow S_{2}-b_{i}-b_{k}+b_{2m}$;

17

18 else if  _$k\geq 2m+1$_ then

19 $S_{1}^{\prime}\leftarrow S_{1}-b_{1}-b_{i}$;

20 $S_{2}^{\prime}\leftarrow S_{2}-b_{k}$;

21

22 else

23 $S_{1}^{\prime}\leftarrow S_{1}-b_{1}-b_{i}-b_{k}+b_{2m+1}$;

24 $S_{2}^{\prime}\leftarrow S_{2}-b_{2m+1}$;

25

26

27
$number\\_of\\_partitions+=Counting\\_Partitions(S^{\prime},S_{1}^{\prime},S_{2}^{\prime})$;

28

29

30 end for

31 return _$number\\_of\\_partitions$_ ;

32

33 end

Algorithm 2 Basic Algorithm.

Furthermore, we have some extra conditions such a partition must have:

######  Theorem 2.

In the same setting as in Theorem 1 the following conditions hold:

  1. 1.

If and only if $S_{1}=S_{2}$, then $\\{x_{i}\mid 1\leq i\leq
n\\}\cup\\{y_{i}\mid 1\leq i\leq n\\}=\\{b_{1},b_{2},\ldots,b_{2n}\\}$ and
$\\{z_{i}\mid 1\leq i\leq n\\}=\\{b_{2n+1},b_{2n+2},\ldots,b_{3n}\\}$.

  2. 2.

It is $b_{1}+b_{2n}\leq b_{3n}$.

  3. 3.

If equality holds in 2, then
$\\{x_{i},y_{i},z_{i}\\}=\\{b_{1},b_{2n},b_{3n}\\}$ for some $i$ and
$S_{1}=S_{2}$.

  4. 4.

If $b_{1}+b_{2n+1}>b_{3n}$, then $S_{1}=S_{2}$.

###### Proof.

We use the same notation as in the proof of Theorem 1.

  1. 1.

If equality holds in Theorem 1, then it must hold on all places in the chain
of inequalities given in the last item. If
$S_{1}=\sum_{i=1}^{n}(x_{i}+y_{i})$, then $\\{x_{i},y_{i}\mid 1\leq i\leq
n\\}=\\{b_{1},b_{2},\ldots,b_{2n}\\}$. And if $\sum_{i=1}^{n}z_{i}=S_{2}$, we
have $\\{z_{i}\mid 1\leq i\leq n\\}=\\{b_{2n+1},b_{2n+2},\ldots,b_{3n}\\}$.
And if the sets are as described, equality holds in Theorem 1.

  2. 2.

Clearly, we have $x_{i}\geq b_{2n}$ or $y_{i}\geq b_{2n}$ for some $i$.
W.l.o.g. let the second case be true. Then we have $b_{1}+b_{2n}\leq
x_{i}+y_{i}=z_{i}\leq b_{3n}$.

  3. 3.

If equality holds in Theorem 1, then from the chain of inequalities in the
previous item we get $x_{i}=b_{1}$, $y_{i}=b_{2n}$, and $z_{i}=b_{3n}$, which
proves the first part of this claim. Furthermore, if there were an index $j$
with $x_{j}<y_{j}$ and $y_{j}>b_{2n}$, we would have
$b_{1}+b_{2n}<x_{j}+y_{j}=z_{j}\leq b_{3n}$, contradicting the assumed
equality in Theorem 1. Therefore, all $x_{i}$ and $y_{i}$ are smaller than or
equal to $b_{2n}$, which proves the second part of this claim.

  4. 4.

Let $j\in\\{1,2,\ldots,n\\}$, and w.l.o.g. let $x_{j}<y_{j}$. If
$b_{1}+b_{2n+1}>b_{3n}$, we have $b_{3n}\geq z_{j}=x_{j}+y_{j}\geq
b_{1}+y_{j}>b_{3n}-b_{2n+1}+y_{j}$. Thus, it is $b_{2n+1}>y_{j}>x_{j}$, and we
get equality in Theorem 1 with the second direction of the equivalence given
in Condition 1.

∎

This leads to some significant improvements of Algorithm 2:

  * •

If at some point in the recursive search the equality $S_{1}=S_{2}$ holds,
then any triple has to consist of two elements of $\\{b_{1},\ldots,b_{2m}\\}$
and one of $\\{b_{2m+1},\ldots,b_{3m}\\}$. Thus, we have $2\leq i\leq 2m$ and
$2m+1\leq k\leq 3m$, which narrows the search space for triples. Also, if this
equality is reached at one point, it has to hold in all subsequent recursion
steps. Therefore, in this case, the sums $S_{1}$ and $S_{2}$ need not be
computed anymore. This will be done in a reduced version of the given
function.

  * •

If $b_{1}+b_{i}\geq b_{k}$, then $b_{1}+b_{i+1}>b_{k}$. Therefore, after the
search for triples with $b_{1}$ and $b_{i}$ up to $b_{k}$, the search for
triples with $b_{1}$ and $b_{i+1}$ can start with the next value after
$b_{k}$.

  * •

If for some $i$ one has $b_{1}+b_{i}>b_{3m}$, then one can end the search not
only for this $i$ but also for all higher values of $i$ in the for loop.

  * •

If $b_{1}+b_{i}>b_{3m}$ for some $i\geq 2m+1$, then by Condition 4 of Theorem
2, we can use the reduced function for further calculating, since we have
$S_{1}=S_{2}$.

  * •

If $b_{1}+b_{2m}=b_{3m}$, we have found one triple
$\\{b_{1},b_{2m},b_{3m}\\}$, and the next step of the recursion can be done
with the reduced function, since we have $S_{1}=S_{2}$ in this case as well.

With this we improved the program by a fair bit; see Tables 1 and 2 for
comparison. Its source code is given in an additional document.

With this we calculated the up to then unknown values for $n=16$ and $n=17$
listed in the series A108235 of the Online Encyclopedia of Integer Sequences.
We get

$\displaystyle a_{16}$ $\displaystyle=142664107305\text{ and}$ $\displaystyle
a_{17}$ $\displaystyle=1836652173363.$

##  3 Further Ideas

Theorems 1 and 2 as well as the algorithms we provided do not make use of the
fact that the set $S$ to be partitioned is a subset of $\\{1,\ldots,3n\\}$. It
could be any set of positive reals. Thus, we can use them to answer some
slight variation of the given problem, too:

Sedláček [5] asks if, for every $n\not\equiv 6\ \mbox{\rm(mod}\ 12\mbox{\rm)}$
and $n\not\equiv 9\ \mbox{\rm(mod}\ 12\mbox{\rm)}$ in the set
$\\{1,\ldots,n\\}$, there are $\lfloor\tfrac{n}{3}\rfloor$ pairwise disjoint
subset $\\{x,y,z\\}$ with $x+y=z$. (For $n\equiv 6\ \mbox{\rm(mod}\
12\mbox{\rm)}$ or $n\equiv 9\ \mbox{\rm(mod}\ 12\mbox{\rm)}$ the parity
argument made in the introduction proves that there cannot be $\tfrac{n}{3}$
such triples.) Guy [1] gives a general proof of existence for all remaining
$n$ and asks how many different such maximal collections of disjoint subsets
with the desired property exist. The sequence A002849 in OEIS gives these
numbers. (For $n\equiv 6\ \mbox{\rm(mod}\ 12\mbox{\rm)}$ or $n\equiv 9\
\mbox{\rm(mod}\ 12\mbox{\rm)}$ the maximal number of disjoint subsets only is
$\tfrac{n}{3}-1$.)

By excluding the right quantity of numbers from $\\{1,\ldots,n\\}$ such that
the remaining set has a multiple of 3 elements and their sum is divisible by
4, we construct subproblems which can be solved with our methods. In this way,
we calculated the next hitherto unknown elements in this series:

$\displaystyle a_{43}$ $\displaystyle=16852166906\text{ and}$ $\displaystyle
a_{44}$ $\displaystyle=270947059160.$

But, if we constrain our search to the task of partitioning the set
$\\{1,\ldots,3n\\}$ (with $n\equiv 0\ \mbox{\rm(mod}\ 4\mbox{\rm)}$ or
$n\equiv 1\ \mbox{\rm(mod}\ 4\mbox{\rm)}$ as given in the introduction), then
we can use this as a meta information. Thus, we know that all elements
$b_{1},\ldots,b_{3m}$ of the considered set are positive integers and at most
$3n$. Additionally, by our strategy of always putting the smallest available
element in the next triple, we know $b_{1}\geq n-m+1$, since, previously, at
least the smallest $n-m$ elements have already been chosen for the first $n-m$
triples.

######  Theorem 3.

In the recursive search for partitions of $\\{1,\ldots,3n\\}$ into subsets
$\\{x,y,z\\}$ satisfying $x+y=z$, where in every step the smallest available
number is chosen, suppose that only be six elements remain. Thus, we have
$m=2$. Let $S=\\{b_{1},\ldots,b_{6}\\}$ with $b_{1}<\cdots<b_{6}$,
$S_{1}=b_{1}+\cdots+b_{4}$, and $S_{2}=b_{5}+b_{6}$. If there is such a
partition, then $S_{1}=S_{2}$.

###### Proof.

Since $m=2$, we look at the second to last step in the recursion: Only six
elements $b_{1}<\cdots<b_{6}$ are remaining; and we know
$b_{1}+b_{2}+b_{3}+b_{4}\leq b_{5}+b_{6}$. From the previous paragraph, we
additionally have $n-1\leq b_{1}$, $n\leq b_{2}$, $\ldots$ and $b_{6}\leq 3n$.

Now we can make an analysis by case which partitions are still possible. In
the following, we distinguish the cases by naming the “partners” of $b_{1}$ in
its triple. The other triple is then well-defined:

  * •

$b_{1}+b_{2}=b_{3}$: Then $b_{3}\geq(n-1)+n=2n-1$ and $b_{4}\geq 2n$. But this
leads to the contradiction $3n\geq b_{6}=b_{5}+b_{4}>2n+2n=4n$.

  * •

$b_{1}+b_{2}=b_{4}$: Then $b_{4}\geq 2n-1$, and $b_{5}\geq 2n$. This yields
the contradiction $n+1\leq b_{3}\leq b_{6}-b_{5}\leq 3n-2n=n$.

  * •

$b_{1}+b_{2}=b_{5}$: A possible solution.

  * •

$b_{1}+b_{2}=b_{6}$: This cannot be the case, since
$b_{1}+b_{2}<b_{3}+b_{4}=b_{5}<b_{6}$.

  * •

$b_{1}+b_{3}=b_{4}$: Then $b_{4}\geq(n-1)+(n+1)=2n$ and $b_{5}\geq 2n+1$.
Because of $n+1\leq b_{2}=b_{6}-b_{5}\leq 3n-(2n+1)=n-1$, this leads to a
contradiction, too.

  * •

$b_{1}+b_{3}=b_{5}$: A possible solution.

  * •

$b_{1}+b_{3}=b_{6}$: This cannot be the case, since
$b_{1}+b_{3}<b_{2}+b_{4}=b_{5}<b_{6}$.

  * •

$b_{1}+b_{4}=b_{5}$: A possible solution.

  * •

$b_{1}+b_{4}=b_{6}$: A possible solution.

  * •

$b_{1}+b_{5}=b_{6}$: Then we have $b_{4}=b_{2}+b_{3}\geq n+(n+1)=2n+1$ and,
therefore, $b_{5}\geq 2n+2$. This gives the contradiction $3n\geq
b_{6}=b_{1}+b_{5}\geq(n-1)+(2n+2)=3n+1$.

In all four remaining cases, we have $b_{1}+b_{2}+b_{3}+b_{4}=b_{5}+b_{6}$,
hence $S_{1}=S_{2}$. ∎

If this equality does not hold, we can discard the set directly. Otherwise, we
only need to check the four possible solutions from above. This speeds up the
process, a little bit further.

A comparison of running times and number of recursive function calls of the
different algorithms was done on a i9 processor of the 11th generation. The
algorithms were not parallelized. So only one core was used. The different
running times are given in Table 1 and the number of recursive function calls
in Table 2.

| Running Time for
---|---
| $n=8$ | $n=9$ | $n=12$ | $n=13$ | $n=16$
Number of Solutions | 3040 | 20505 | 10567748 | $103372655$ | $\approx 1.43\cdot 10^{11}$
Naive Algorithm 1 | 16 ms | 146 ms | 308 s |  $>$24 h | —
Basic Algorithm 2 | 2 ms | 18 ms | 19 s | 219 s | —
Algorithm with Theorem 2 | 1 ms | 11 ms | 10 s | 110 s | 211658 s
Algorithm with Theorems 2 & 3 | 1 ms | 11 ms | 10 s | 107 s | 199610 s
Table 1: Running Times of the different Algorithms. | Number of recursive function calls for
---|---
| $n=8$ | $n=9$ | $n=12$ | $n=13$ | $n=16$
Naive Algorithm 1 | 435083 | 4567652 | $88.00\cdot 10^{8}$ | — | —
Basic Algorithm 2 | 49059 | 401092 | $3.77\cdot 10^{8}$ | $4.36\cdot 10^{9}$ | —
Algorithm with Theorem 2 | 39793 | 307826 | $2.49\cdot 10^{8}$ | $2.73\cdot 10^{9}$ | $5.432\cdot 10^{12}$
Algorithm with Theorems 2 & 3 | 36103 | 287085 | $2.43\cdot 10^{8}$ | $2.69\cdot 10^{9}$ | $5.405\cdot 10^{12}$
Table 2: Number of recursive function calls of the different Algorithms.

## References

  * [1] R. K. Guy, Sedlacek’s Conjecture on disjoint solutions of $x+y=z$, Dept. Math., Univ. Calgary, Research Paper No. 129, 1971. avaibale at https://oeis.org/A002848/a002848.pdf.
  * [2] T. Mansour, Combinatorics of set partitions, CRC Press, 2012.
  * [3] R. S. Nickerson, Problem E1845, Amer. Math. Monthly, 73 (1966), 81.
  * [4] R. J. Nowakowski, Generalizations of the Langford-Skolem problem, M.S. Thesis, Dept. Math., Univ. Calgary, 1975. available at https://oeis.org/A104429/a104429.pdf.
  * [5] J. Sedláček, On a set system, Int. Conf. Comb. Math. 1970, Ann Acad. Sci. 175 (1970), 329–330.
  * [6] D. Viertel, F. Niedermeyer, C. Hercher, et al., Das kaputte Osterei, https://matheplanet.de/matheplanet/nuke/html/viewtopic.php?topic=246540&start=0, 2023.

2020 _Mathematics Subject Classification_ : Primary 05A18

_Keywords_ : set partitions with arithmetic property