# Physics-Informed Convolutional Neural Networks for Corruption Removal on
Dynamical Systems

Daniel Kelshaw
Department of Aeronautics
Imperial College London
<EMAIL_ADDRESS>
&Luca Magri
Department of Aeronautics
Imperial College London,
Alan Turing Institute
<EMAIL_ADDRESS>

###### Abstract

Measurements on dynamical systems, experimental or otherwise, are often
subjected to inaccuracies capable of introducing corruption; removal of which
is a problem of fundamental importance in the physical sciences. In this work
we propose physics-informed convolutional neural networks for stationary
corruption removal, providing the means to extract physical solutions from
data, given access to partial ground-truth observations at collocation points.
We showcase the methodology for 2D incompressible Navier-Stokes equations in
the chaotic-turbulent flow regime, demonstrating robustness to modality and
magnitude of corruption.

Figure 1: Diagrammatic overview of the corruption removal task.

##  1 Introduction

In the physical sciences, corrupted data can arise for a number of reasons:
faulty experimental sensors, or low-fidelity numerical results to name a few.
The detection and removal of this corruption would allow for the extraction of
the underlying true-state, ensuring that the governing equations are
satisfied. In practice, verifying that given observations are characteristic
of a dynamical system is more straightforward than determining the solution
itself. For observations on dynamical systems we evaluate the residual, giving
an indication of the fidelity of the observations.

Corruption removal typically considers noise-removal, and flow-reconstruction
[1]. Noise-removal constitutes methods which remove small, stochastic
variations from the true-state, with examples including: filtering methods
[2], proper orthogonal decomposition [3, 4], and autoencoders [5]. Flow-
reconstruction considers inference of a solution over the domain, given only
partial information; a popular example being that of super-resolution.
Convolutional neural networks (CNNs) are prominent in the domain of flow
reconstruction due to their ability to exploit spatial correlations [6, 7].

In the absence of ground-truth labels, it is possible to impose prior
knowledge by regularising predictions with respect to known governing
equations [8]. Physics-informed CNNs have been used for solving PDEs [9, 10],
basic super-resolution [11], and surrogate modelling without access to
labelled data [12]. This regularisation method differs from the standard
physics-informed neural network (PINN) approach which strives to exploit the
automatic-differentiation capabilities of neural networks to constrain
gradients of the network [13].

Our work considers a form of physics-informed CNNs for flow reconstruction. We
provide a method for removing arbitrary, stationary corruption from
observations on dynamical systems, given access to only partial ground-truth
information at select collocation points. We showcase corruption removal for
the 2D incompressible Navier-Stokes equations in the chaotic-turbulent regime,
highlighting the ability to accurately recover the true-state, independent of
modality or magnitude of corruption.

##  2 Methodology

We consider corruption removal from observations on dynamical systems of the
form

$\partial_{t}\bm{u}-\mathcal{N}(\bm{u};\lambda)=0\qquad\text{with}\quad\bm{u}=u(\bm{x},t),\quad\bm{x}\in\Omega\subset\mathbb{R}^{n},\quad
t\in[0,T]\subset\mathbb{R}^{+},$ (1)

where $u:\Omega\times[0,T]\rightarrow\mathbb{R}^{n}$, $\mathcal{N}$ is a
sufficiently smooth differential operator, and $\lambda$ are the physical
parameters of the system. We define the residual of the system as the left-
hand side of equation (1)

$\mathcal{R}(\bm{u};\lambda)\triangleq\partial_{t}\bm{u}-\mathcal{N}(\bm{u};\lambda),$
(2)

such that $\mathcal{R}(\bm{u};\lambda)=0$ when $u(\bm{x},t)$ is a solution to
the partial differential equation (PDE). We consider corrupted observations
such that $\mathcal{R}(\zeta(\bm{x},t);\lambda)>0$, where $\zeta(\bm{x},t)$ is
the linear combination of the true state $u(\bm{x},t)$ and the stationary
corruption $\phi(\bm{x})$, precisely
$\zeta(\bm{x},t)=u(\bm{x},t)+\phi(\bm{x}).$

Given the corrupted state, we aim to recover the underlying, physical solution
to the governing equations: the true-state. Mathematically, we denote this
process by the mapping

$\eta_{\theta}:\zeta(\bm{\Omega_{g}},t)\rightarrow u(\bm{\Omega_{g}},t),$ (3)

where the domain $\Omega$ is discretised on a uniform, structured grid
$\bm{\Omega_{g}}\subset\mathbb{R}^{N^{n}}$. We further discretise the time
domain, providing $\mathcal{T}=\\{t_{i}\in[0,T]\\}_{i=0}^{N_{t}}$ for $N_{t}$
samples in time. Approximating the mapping $\eta_{\theta}$ as a CNN, we
optimise weights of the network to minimise the loss

$\mathcal{L}_{\theta}=\alpha\left(\mathcal{L}_{\partial\Omega}+\mathcal{L}_{\phi}\right)+\mathcal{L}_{\mathcal{R}},$
(4)

where $\alpha$ is a fixed, empirical weighting factor. We define each of the
loss terms as

$\displaystyle\mathcal{L}_{\mathcal{R}}$
$\displaystyle=\frac{1}{\lvert\mathcal{T}\rvert}\sum_{t\in\mathcal{T}}\big{\lVert}\mathcal{R}\big{(}\eta_{\theta}(\zeta(\bm{\Omega_{g}},t));\lambda\big{)}\big{\rVert}_{\bm{\Omega_{g}}}^{2},$
(5) $\displaystyle\mathcal{L}_{\partial\Omega}$
$\displaystyle=\frac{1}{\lvert\mathcal{T}\rvert}\sum_{t\in\mathcal{T}}\big{\lVert}\eta_{\theta}(\zeta(\partial\bm{\Omega_{g}},t))-u(\partial\bm{\Omega_{g}},t)\big{\rVert}_{\partial\bm{\Omega_{g}}}^{2},$
(6) $\displaystyle\mathcal{L}_{\phi}$
$\displaystyle=\frac{1}{\lvert\mathcal{T}\rvert}\sum_{t\in\mathcal{T}}\big{\lVert}\partial_{t}\big{[}\zeta(\bm{\Omega_{g}},t)-\eta_{\theta}(\zeta(\bm{\Omega_{g}},t))\big{]}\big{\rVert}_{\bm{\Omega_{g}}}^{2},$
(7)

where $\partial\bm{\Omega_{g}}$ denotes boundary points of the grid, and
$\lVert\mathrel{\;\cdot\;}\rVert_{\Omega}$ is the $\ell^{2}$-norm over the
given domain. We regularise network predictions with the residual-based loss
$\mathcal{L}_{\mathcal{R}}$, imposing prior-knowledge of the system to promote
network realisations which conform to the governing equations. The data-driven
boundary loss $\mathcal{L}_{\partial\Omega}$ serves to minimise the error
between predictions and known measurements; when used in conjunction with the
residual-loss, this effectively allows us to condition the underlying physics
on the observations. For this case, we consider access to ground-truth
measurements on the boundary $\partial\Omega$. Inclusion of the corruption-
based loss $\mathcal{L}_{\phi}$ embeds our assumption of stationary
corruption, driving predictions away from the trivial solution,
$u(\bm{\Omega_{g}},t)=0$.222All code is available on GitHub:
https://github.com/magriLab/PICR

##  3 Results

We consider the corruption removal for measurements on the Kolmogorov flow, an
instance of the 2D incompressible Navier-Stokes equations. The flow is defined
on the domain $\Omega\in[0,2\pi)\subset\mathbb{R}^{2}$, imposing periodic
boundary conditions on $\partial\Omega$, and subjected to stationary,
sinusoidal forcing $g(\bm{x})$. The chaotic-turbulent nature of the Kolmogorov
flow provides a challenging case study, introducing complex non-linear
dynamics and turbulent structures across a range of spatial frequencies [14].
The standard continuity and momentum equations are given as

$\displaystyle\begin{split}\nabla\cdot\bm{u}&=0\\\
\partial_{t}\bm{u}+\bm{u}\cdot\nabla\bm{u}&=-\nabla
p+\nu\Delta\bm{u}+g(\bm{x}),\end{split}$ (8)

where $p,\nu$ denote the scalar pressure field and kinematic viscosity
respectively. We take $\nu=\nicefrac{{1}}{{34}}$ to ensure chaotic-turbulent
dynamics, and prescribe the forcing model
$g(\bm{x})=[\sin(4\bm{x}_{2}),0]^{\top}$.

###  3.1 Pseudospectral Discretisation

We provide a differentiable pseudospectral discretisation for the differential
operator, defining operations on the spectral grid
$\bm{\hat{\Omega}_{k}}\in\mathbb{Z}^{61\times 61}$, enabling backpropagation
for the residual-based loss $\mathcal{L}_{\mathcal{R}}$. By eliminating the
pressure term, our discretisation handles the continuity constraint
implicitly, affording us the ability to neglect the constraint in the loss
[15]. We produce a solution by time-integration of the dynamical system with
the forward-Euler method, taking a time-step $\Delta t=0.005$ to ensure
numerical stability according to the Courant-Friedrichs-Levy condition.

Due to the spectral discretisation, we evaluate the residual-based loss
$\mathcal{L}_{\mathcal{R}}$ in the Fourier domain on the grid
$\bm{\hat{\Omega}_{k}}$, offering two distinct advantages over the standard
finite-difference approach: spectral accuracy, and implicit handling of
periodic boundary conditions. We employ a form of time-windowed batching,
considering the evaluation of the residual-based loss over $\tau\geq 2$
consecutive time-steps.

###  3.2 Parameterised Corruption

We conduct experiments varying the frequency $f$, and relative magnitude
$\mathcal{M}$ of the corruption. For a scaling magnitude
$M=\mathcal{M}\cdot\max{\left(u(\bm{\Omega_{g}},\mathrel{\;\cdot\;})\right)}$,
we define the corruption field as

$\phi(\bm{x};f,M)=\Gamma\left(20+\sum_{i=1}^{2}\left[(\bm{x}_{i}-\pi)^{2}-10\cos(f\cdot(\bm{x}_{i}-\pi))\right];M\right),$
(9)

where $\Gamma(\;\bm{\cdot}\;;M)$ is a linear operator that re-scales the
vector in the range $[0,M]$, [16].

Figure 2: Corruption removal results for the Kolmogorov flow
$[f=7,\mathcal{M}=0.5]$.

###  3.3 Numerical Experiments

The Kolmogorov flow is solved in the Fourier domain, as per §3.1, before
generating data on the grid $\bm{\Omega_{g}}\in\mathbb{R}^{64\times 64}$. A
total of $1024$ time-windows are used for training, with a further $256$ for
validation, taking $\tau=2$ in each instance. We employ a standard U-Net [17]
architecture and train with the Adam optimizer, taking a learning rate of
$3\times 10^{-4}$ for $5000$ epochs, fixing computational resource for each
experiment. We impose a fixed weighting of $\alpha=1\times 10^{3}$ for the
empirical weighting term.333All experiments were run on a single NVIDIA Quadro
RTX 8000.

In Figure 2 we demonstrate results for $f=7,\mathcal{M}=0.5$, showcasing the
ability to separate the true-state from corruption. We note that the residual
of the corruption is not equal to the sum of the residuals of it’s
constituents, highlighting the challenge of non-linearity. We further assess
the robustness of the methodology to both modality and magnitude of corruption
by running two studies:

$\begin{aligned} &\mathit{(i)}\\\
&\mathit{(ii)}\end{aligned}\quad\begin{aligned} &\mathcal{M}=0.5,\\\
&f=3,\end{aligned}\quad\begin{aligned} f&\in\\{1,3,5,7,9\\};\\\
\mathcal{M}&\in\\{0.01,0.1,0.25,0.5,1.0\\}.\end{aligned}$

Results can be seen in Figure 3, where performance for all experiments is
measured by the relative $\ell^{2}$-error between the predicted-state
$\eta_{\theta}(\zeta(\bm{\Omega}_{g},t))$, and the true-state
$u(\bm{\Omega_{g}},t)$. Results denote the mean over five repeats with random
seeds, the standard deviation not exceeding $8.169\times 10^{-4}$.

Figure 3:  Comparison of relative $\ell^{2}$-error for parameterised
corruption frequency and magnitude.

We find that performance is largely agnostic to both multi-modality and
magnitude of corruption, with error decreasing slightly with increasing
$f,\mathcal{M}$, as demonstrated in Figure 3. Quantitatively, we observe
excellent robustness of the methodology, with relative $\ell^{2}$-error not
exceeding $2.284\times 10^{-2}$.

##  4 Conclusion

In this work we introduce a methodology for physics-informed removal of
arbitrary, stationary corruption from observations on dynamical systems, given
access to only partial ground-truth information. We demonstrate results for
corrupted observations on the Kolmogorov flow, using ground-truth observations
on the boundaries to condition the physics. Experiments indicate that
performance is agnostic to both magnitude and modality of corruption, with
relative $\ell^{2}$-error remaining consistently low, as demonstrated in
Figure 3. Our results in Figure 2 qualitatively showcase the performance of
the model, clearly separating the corrupted field into its component parts:
true-state, and corruption. This work opens opportunities for accurate flow
reconstruction from corrupted state measurements with access to partial
ground-truth information, potentially allowing for correcting sensor
measurements and low-fidelity simulation results - problems of fundamental
importance in the physical sciences.

We note the limitations of our work: the assumption of stationary corruption,
and the requirement of ground-truth observations to condition the physics;
providing considerations for future work.

## Acknowledgments and Disclosure of Funding

D. Kelshaw. and L. Magri. acknowledge support from the UK EPSRC. L. Magri
gratefully acknowledges financial support from the ERC Starting Grant PhyCo
949388.

## References

  * Brunton et al. [2020] S. Brunton, B. Noack, and P. Koumoutsakos, “Machine learning for fluid mechanics,” _Annual Review of Fluid Mechanics_ , vol. 52, pp. 477–508, 1 2020.
  * Kumar and Nachamai [2017] N. Kumar and M. Nachamai, “Noise removal and filtering techniques used in medical images,” _Oriental journal of computer science and technology_ , vol. 10, pp. 103–113, 3 2017.
  * Raiola et al. [2015] M. Raiola, S. Discetti, and A. Ianiro, “On piv random error minimization with optimal pod-based low-order reconstruction,” _Experiments in Fluids_ , vol. 56, 4 2015.
  * Mendez et al. [2017] M. A. Mendez, M. Raiola, A. Masullo, S. Discetti, A. Ianiro, R. Theunissen, and J. M. Buchlin, “Pod-based background removal for particle image velocimetry,” _Experimental Thermal and Fluid Science_ , vol. 80, pp. 181–192, 1 2017.
  * Vincent et al. [2008] P. Vincent, H. Larochelle, Y. Bengio, and P.-A. Manzagol, “Extracting and composing robust features with denoising autoencoders,” in _Proceedings of the 25th International Conference on Machine Learning_ , 2008, pp. 1096–1103.
  * Dong et al. [2014] C. Dong, C. C. Loy, K. He, and X. Tang, “Learning a deep convolutional network for image super-resolution,” in _European Conference on Computer Vision_ , 2014, pp. 184–199.
  * Shi et al. [2016] W. Shi, J. Caballero, F. Huszár, J. Totz, A. P. Aitken, R. Bishop, D. Rueckert, and Z. Wang, “Real-time single image and video super-resolution using an efficient sub-pixel convolutional neural network,” _Computer Vision and Pattern Recognition_ , 9 2016.
  * Lagaris et al. [1998] I. E. Lagaris, A. Likas, and D. I. Fotiadis, “Artificial neural networks for solving ordinary and partial differential equations,” _IEEE Transactions on Neural Networks_ , vol. 9, pp. 987–1000, 1998.
  * Gao et al. [2021a] H. Gao, L. Sun, and J. X. Wang, “Phygeonet: Physics-informed geometry-adaptive convolutional neural networks for solving parameterized steady-state pdes on irregular domain,” _Journal of Computational Physics_ , vol. 428, 3 2021\.
  * Ren et al. [2022] P. Ren, C. Rao, Y. Liu, J. X. Wang, and H. Sun, “Phycrnet: Physics-informed convolutional-recurrent network for solving spatiotemporal pdes,” _Computer Methods in Applied Mechanics and Engineering_ , vol. 389, 2 2022\.
  * Gao et al. [2021b] H. Gao, L. Sun, and J.-X. Wang, “Super-resolution and denoising of fluid flow using physics-informed convolutional neural networks without high-resolution labels,” _Physics of Fluids_ , vol. 33, p. 073603, 7 2021.
  * Zhao et al. [2021] X. Zhao, Z. Gong, Y. Zhang, W. Yao, and X. Chen, “Physics-informed convolutional neural networks for temperature field prediction of heat source layout without labeled data,” _Preprint_ , 9 2021. [Online]. Available: http://arxiv.org/abs/2109.12482
  * Raissi et al. [2019] M. Raissi, P. Perdikaris, and G. E. Karniadakis, “Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations,” _Journal of Computational Physics_ , vol. 378, pp. 686–707, 2 2019.
  * Fylladitakis [2018] E. D. Fylladitakis, “Kolmogorov flow: Seven decades of history,” _Journal of Applied Mathematics and Physics_ , vol. 06, pp. 2227–2263, 2018\.
  * Canuto et al. [1988] C. Canuto, M. Y. Hussaini, A. Quarteroni, and T. A. Zang, _Spectral Methods in Fluid Dynamics_. Springer Berlin Heidelberg, 1988.
  * Rastrigin [1974] L. A. Rastrigin, “Systems of extremal control,” _Nauka_ , 1974.
  * Ronneberger et al. [2015] O. Ronneberger, P. Fischer, and T. Brox, “U-net: Convolutional networks for biomedical image segmentation,” in _Medical Image Computing and Computer-Assisted Intervention_ , 2015, pp. 234–241.


# Model-free, Model-based, and General Intelligence

Hector Geffner1,2
1 Universitat Pompeu Fabra, Roc Boronat 138, 08032 Barcelona, Spain
2 ICREA, Pg. Lluís Companys 23, 08010 Barcelona, Spain
<EMAIL_ADDRESS>
###### Abstract

During the 60s and 70s, AI researchers explored intuitions about intelligence
by writing programs that displayed intelligent behavior. Many good ideas came
out from this work but programs written by hand were not robust or general.
After the 80s, research increasingly shifted to the development of _learners_
capable of inferring behavior and functions from experience and data, and
_solvers_ capable of tackling well-defined but intractable models like SAT,
classical planning, Bayesian networks, and POMDPs. The learning approach has
achieved considerable success but results in black boxes that do not have the
flexibility, transparency, and generality of their model-based counterparts.
Model-based approaches, on the other hand, require models and scalable
algorithms. Model-free learners and model-based solvers have close parallels
with _Systems 1 and 2_ in current theories of the human mind: the first, a
fast, opaque, and inflexible intuitive mind; the second, a slow, transparent,
and flexible analytical mind. In this paper, I review developments in AI and
draw on these theories to discuss the gap between model-free learners and
model-based solvers, a gap that needs to be bridged in order to have
intelligent systems that are robust and general.

##  1 Introduction

The current excitement about AI is the result of a number of breakthroughs in
machine learning. Some of these developments are true AI milestones, like the
programs that achieve top world performance in games such as Chess and Go by
learning from self-play only Silver et al. (2017a, b). These are no small
accomplishments and most of them have to do with deep learning LeCun et al.
(2015) and deep reinforcement learning Mnih et al. (2015). The goal of this
paper is to place these developments in perspective, in particular by
comparing _model-free learners_ with _model-based solvers_. Solvers are
programs that accept instances of different types of models, like SAT,
classical planning, Bayesian networks, and POMDPs, and automatically compute
their solutions. Learners and solvers have interesting similarities and
differences. Both are concerned with the derivation of functions $f$ for
mapping inputs $x$ into outputs, but while learners derive the function $f$
from data or experience, solvers compute the output $f(x)$ for each given
input $x$ from a model. Interestingly the scope and characteristics of model-
free learners and model-based solvers have close parallels with those of the
two systems or processes that are currently assumed to make up the human mind
Kahneman (2011); Evans and Stanovich (2013): one, a fast, opaque, and
inflexible intuitive mind (System 1); the other, a slow, transparent, and
general analytical mind (System 2). A number of works have analyzed the
limitations of deep learning, often placing the emphasis on the need to
construct and use _models_ Lake et al. (2017); Darwiche (2017); Pearl (2018);
Marcus (2018b). In this paper, I place the emphasis on _solvers_ , and in
particular _planners_ , which require both models and general, scalable
algorithms. The Systems 1 and 2 perspective will be useful for understanding
the scope of learners and solvers, and the need for a tight integration.

The paper is organized as follows. I trace some history, look at learners,
solvers, and planners, which are a particular type of solvers, and address the
similarities and differences between learners and solvers, and the challenge
of integrating them.

##  2 Programming, AI, and AI Programming

Artificial Intelligence is a brain child of Alan Turing and his universal
computer Turing (1936). Turing was not only a logician and the father of the
modern computer but also the first modern programmer. Programming played a key
role in the early days of AI and in the selection of papers for the seminal
_Computers and Thought_ book where each chapter described “a working computer
program” Feigenbaum and Feldman (1963). The emphasis on working programs,
however, was not shared by everyone. John McCarthy, who was both the father of
the most popular AI programming language at the time (Lisp) and the person
that gave AI its name, was putting the basis for the logical approach to AI
where the emphasis was not in the use of representations but in their
expressiveness and semantics McCarthy (1958). Yet such dissenting views were
not common and are not to be found in the CT book. Several of the key AI
contributions in 60s, 70s, and 80s had to do indeed with _programming_ and the
_representation of knowledge in programs_ , and this includes Lisp and
functional programming, Prolog and logic programming, rule-based programming,
expert systems shells, frames, scripts, and semantic networks Charniak et al.
(1980); Norvig (1992).

##  3 The Problem of Generality

Many great ideas came out of this work but there was a problem: the programs
were not sufficiently robust or general, and they tended to fail on examples
or scenarios not anticipated by the programmer. It was natural to put the
blame on the knowledge that the programs were missing but it was not clear
then how to proceed. Some programmers narrowed down the domain and scope of
the programs so that all the relevant knowledge could be made explicit. This
was the ’expert systems’ approach. Some took the programs as illustrations or
demonstrations of potential capabilities which were not actually delivered.
Some decided to sit down and write down all the relevant commonsense
knowledge. This was the motivation underlying projects like CYC Lenat et al.
(1990). McCarthy discussed related issues in his 1971 ACM Turing lecture
entitled “Generality in Artificial Intelligence”, published in revised form
many years later McCarthy (1987).

The limitations of AI programs for exhibiting general intelligence not tied to
toy worlds or narrow domains led to an impasse in the 80s, one of whose
effects was a _methodological shift_ in which research increasingly moved away
from _writing programs for ill-defined problems_ to _designing algorithms for
well-defined mathematical tasks_. The algorithms are general in the sense that
they are not tied to particular examples but to certain classes of models and
tasks expressed in mathematical form. The new programs, _learners_ and
_solvers_ , have a crisp functionality and both can be seen as computing
_functions_ that map inputs into outputs (Figure 1).

##  4 Learners

The current excitement about AI in academia and in industry is the result of a
number of breakthroughs that have pushed the state-of-the-art in tasks such as
image understanding, speech recognition, and challenging games Krizhevsky et
al. (2012); Graves et al. (2013); Mnih et al. (2015), in certain cases
delivering superhuman performance while starting with basic knowledge of the
rules of the game only Silver et al. (2017b). These developments have to do
with two classes of learners: _deep learners_ and _deep reinforcement
learners._ While these are not the only approaches pursued in machine
learning, they are the ones behind these milestones and the ones on which I
focus.

In both deep learning (DL) and deep reinforcement learning (DRL), training
results in a function $f_{\theta}$ that has a fixed structure, given by a deep
neural network LeCun et al. (2015), and a number of adjustable parameters
$\theta$. In DL, the input vector $x$ may represent an image and the output
$f_{\theta}(x)$, a classification label, a probability distribution over the
possible labels, or object labels with suitable bounding boxes. In DRL, the
input $x$ may represent the state of a dynamic system or game, and the output
$f_{\theta}(x)$, the value of the state, the action to be done in the state,
or a probability distribution over such actions. The key difference between DL
and DRL is in the way in which the functions $f_{\theta}$ are learned during
training. Deep learning is a supervised method where the parameters $\theta$
are learned by minimizing an error function that depends on the inputs and
target outputs in a training set. Deep reinforcement learning, on the other
hand, is a non-supervised method that learns from experience, where the error
function depends on the value of states and their successors. In both DL and
DRL, the most common algorithm for minimizing the error function is stochastic
gradient descent where the parameter vector $\theta$ is modified incrementally
by taking steps in the direction of the gradient. Similar optimization
algorithms are used in policy-based DRL where the function $f_{\theta}$
represents a policy.

The basic ideas underlying DL and DRL methods are not new and can be traced
back to the neural network and reinforcement learning algorithms of the 80s
and 90s Rumelhart and McClelland (1986); LeCun et al. (1989); Sutton and Barto
(1998). The recent successes have to do with the gains in computational power
and the ability to use deeper nets on more data. The use of these methods on
problems that have attracted and spurred commercial interest has helped as
well. A common question that arises is what are the limits of these methods.
One important restriction is that _the inputs $x$ and outputs $y$ of neural
nets have a bounded, fixed size._ This limitation is not relevant for learning
to play chess or Go whose boards have a fixed size, but is relevant for
tackling, for example, arbitrary instances of the much simpler Blocks world.
Attention mechanisms have been proposed as a way to deal with arbitrarily
large inputs Graves et al. (2014), but such mechanisms introduce partial
observability, which is another challenge in learning. Indeed, as one moves
away from the basic setting of DL and DRL, the methods, the results, and the
evaluation standards, all look somehow weaker.

Input $x$ $\Longrightarrow$ Function $f$ $\Longrightarrow$ Output $f(x)$

Figure 1: Learners and solvers map inputs into outputs. Learners derive the
function $f$ from data or experience. _Solvers_ derive the value of the
function $f(x)$ for each given input $x$ from a model.

##  5 Solvers

The second type of programs that we consider are _solvers_. Solvers take a
convenient description of a particular model instance (a classical planning
problem, a constraint satisfaction problem, and so on) and automatically
compute its solution. Solvers can also be thought as computing a function $f$
mapping inputs $x$ into outputs, the difference is that they work out of the
box without training by computing the output $f(x)$ lazily for each given
input $x$. The target $f(x)$ is given implicitly by the model. For a SAT
solver, the inputs $x$ are formulas in conjunctive normal form, and the output
$f(x)$ tells whether the formula $x$ is satisfiable or not. For a classical
planner, the inputs are classical planning problems $x$ and the output is a
plan that solves the problem. Solvers have been developed for a variety of
models that include constraint satisfaction problems (CSPs), SAT, Bayesian
networks, classical planning, fully and partially observable non-deterministic
and stochastic planning problems (FONDPs, PONDPs, MDPs, and POMDPs), general
game playing, and answer set programming among others Dechter (2003); Biere et
al. (2009); Pearl (1988); Geffner and Bonet (2013); Bertsekas (1995);
Kaelbling et al. (1998); Genesereth et al. (2005); Gebser et al. (2012).
Solvers are _general_ as they must deal with _any_ problem that fits the
model: any classical planning problem, any CSP, etc. This presents a crisp
_computational challenge_ , as all models are computationally intractable,
with complete algorithms running in time that is exponential in the number of
problem variables or worse. The challenge is to push this exponential
explosion as far as possible, as solvers should not break down on a problem
merely because it has many variables. To achieve this, domain-independent
solvers must be able to exploit the structure of the given problems so that
their performance over a given domain can approach the performance of a
domain-specific solver. The computational value of solving techniques is
assessed experimentally and in most cases by means of competitions.
Competitions have helped to generate hundreds of problems used as benchmarks,
have set standards for the encodings of problems, and have facilitated the
empirical evaluation of algorithms. The focus on models and solvers that can
scale up has acted as _a powerful filter on ideas and techniques_ , setting up
a clear distinction between the ideas that look well from those that actually
work well. We illustrate some of these ideas in the context of planning to
make the comparison between learners and solvers more concrete.

##  6 Planners

Planners are solvers for models that involve goal-directed behavior. Planners
and planning models come in many forms depending on a number of dimensions
including: 1) uncertainty about the initial situation and action transitions,
2) type of sensing, 3) representation of uncertainty, and 4) objectives. The
simplest type of planning, classical planning, involves no uncertainty about
the initial situation or action effects, hence no uncertainty or sensing, and
the objective is to reach some condition. MDPs have stochastic actions and
full state observability and the objectives are described in two different
ways: as goals to be reached with probability 1 by applying actions with
positive costs (goal MDPs), or as discounted rewards to be collected
(discounted reward MDPs). Other types of objectives considered in planning are
temporally extended goals, like “visit rooms 5 and 7 forever”, that are
conditions on possibly infinite state trajectories Camacho et al. (2017).
Three other relevant dimensions in planning are whether 5) models are
expressed in compact or flat form, 6) solutions are sought off-line or on-
line, and in the latter case, 7) which off-line solution form is sought. About
the last point, partially observable problems can be solved optimally with
policies that map belief states into actions but can also be approached
effectively with simpler solution forms such as finite-state controllers. Many
of these dimensions affect the complexity of planning. Focusing on the
decision problems, classical planning is PSPACE-complete, while classical
planning with a fixed horizon is NP-complete Kautz and Selman (1996).
Similarly, PONDPs expressed in compact form are 2-EXP complete Rintanen
(2004), while computing memoryless policies for PONDPs expressed in flat form
is NP-complete Chatterjee et al. (2016).

We look next at three powerful computational ideas in planning, relaxations,
transformations, and width, drawing in each case contrasts between planners
and learners.

###  6.1 Relaxations

The derivation of heuristics in classical planning for guiding the search for
plans follows an old idea: if you do not know how to solve a problem, solve a
simpler problem and use its solution as guidance for solving the original
problem Pearl (1983). In planning, the most useful simplification $P^{\prime}$
of a planning problem $P$ is the _monotonic relaxation_ where the effects of
the actions on the variables are made monotonic McDermott (1999); Bonet and
Geffner (2001). For this, the states $\bar{s}$ of the relaxation $P^{\prime}$
are defined not as assignment of values $x$ to variables $X$ but as collection
of atoms $X\\!=\\!x$. In the original problem $P$, if an action $a$ makes an
atom $X\\!=\\!x^{\prime}$ true, it makes the atoms $X\\!=\\!x^{\prime}$ for
$x\not\\!=\\!x^{\prime}$ false. In the monotonic relaxation, on the other
hand, the new atom $X\\!=\\!x^{\prime}$ does not make the other atoms false. A
result of this is that the monotonic relaxation $P^{\prime}$ becomes
_decomposable_ : a plan that achieves two atoms $X\\!=\\!x$ and $Y\\!=\\!y$
jointly in $P^{\prime}$ can be obtained by concatenating a plan for
$X\\!=\\!x$ and a plan for $Y\\!=\\!y$. This idea can be used to compute plans
for all atoms and hence for the conjunction of atoms in the goal of
$P^{\prime}$ in low polynomial time. The heuristic $h(s)$ can be set then to
the size of the plan in the relaxation obtained from the state $\bar{s}$ where
the only true atoms are those which are true in $s$ Hoffmann and Nebel
(2001).111 When variables are boolean and actions are represented in STRIPS as
precondition, add, and delete lists, the monotonic relaxation is known as the
_delete-relaxation_ , as the monotonic relaxation is obtained by making all
delete lists empty. Planners compute the heuristic value $h(s)$ for any state
$s$ _over any problem_ $P$ following variations of this procedure. This is why
they are called _domain-independent_ planners. Learners can infer the
heuristic function $h$ over all the states $s$ of a _single_ problem $P$ in a
straightforward way, but they can’t infer an heuristic function $h$ that is
valid for _all problems_. This is natural: learners can deal with new problems
only if they have acquired experience on related problems.

###  6.2 Transformations

Planners tend to work well even in large classical instances yet many problems
do not have this form. Transformations are used to leverage on classical
planners.

Goal recognition. Goal recognition is a _classification problem_ where the
hidden goal of an agent has to be uncovered from his observed behavior and a
pool of possible goals. For example, an agent is observed to move up twice
from the middle of the grid in Figure 2, and we want to determine to which of
the marked targets he may be heading to. A goal recognition problem $P({\cal
G},O)$ can be represented as a classical problem $P$ but with the goal
replaced by a pool $\cal G$ of possible goals $G$ and a sequence of observed
actions $O$. In the example, the reason that the observed agent is likely to
be moving to one of targets in the top row is that it is _not_ reasonable
(cost-efficient) to reach the other targets by moving up. This can be
formalized in terms of _two cost measures_ (plan lengths) for each possible
goal $G$: the cost of reaching $G$ with a plan that complies with the
observations, denoted $c^{+}(G)$, and the cost of reaching $G$ with a plan
that does not comply with the observations, denoted $c^{-}(G)$. Bayes’ rule
says that the goal posterior is $P(G|O)=P(O|G)\,P(G)/P(O)$ where the priors
$P(G)$ can be assumed to be given. The posterior $P(G|O)$ is then determined
by the likelihoods $P(O|G)$ that express how well each of the possible goals
$G$ predicts $O$. In Ramírez and Geffner (2010), the likelihood $P(O|G)$ is
set to a monotonic function $f$ of the cost difference
$\Delta(G)=c^{-}(G)-c^{+}(G)$ that expresses that the costlier that it is to
reach $G$ with a plan that complies with $O$ in relation to one that does not,
the less likely that it is the observation $O$ given $G$. The costs are
computed by running a planner on problems obtained from the goal recognition
problem $P({\cal G},O)$. The posterior distribution $P(G|O)$ for all goals
$G\in{\cal G}$ is computed using Bayes’ rule by calling a classical planner
$2|{\cal G}|$ times. Once again, even if _goal recognition is a classification
problem_ , it is not possible to obtain a _general, domain-independent_
account of goal recognition using learners instead of planners.

|  |
---|---|---
Figure 2: _Left._ Goal recognition: where is the agent heading to? _Right._
Partial observability: get the gold without knowing where the gold, pits, and
wumpus are, using the sensors (see text).

Partial observability. Figure 2 shows an instance of the Wumpus problem
Russell and Norvig (2009) where an agent has to get the gold while avoiding
the monster and the pits. The positions of the gold, the monster, and the
pits, however, are not known to the agent that can sense stench if at distance
one from the wumpus, a breeze, if at distance one from a pit, and a shiny
object if in the same cell as the gold. The problem can be modeled as a POMDP
or as a contingent planning problem but few planners scale up when the size of
the grid is increased. Even if we focus on _on-line planning_ methods, two
challenges need to be addressed: tracking the beliefs about the true hidden
state, and selecting the actions that take the agent to the goal or provide
relevant information. The two challenges have been addressed jointly through a
“planning under optimism” scheme where the partially observable problem $P$ is
relaxed into a classical problem $K(P)$ inside a _plan-execute-observe-and-
replan_ loop Bonet and Geffner (2014). The transformation $K(P)$ removes the
uncertainty in $P$ in two steps. First, literals $L$ that represent that $L$
is true are replaced by two literals $KL$ and $K\neg L$, the first meaning $L$
is known to be true, the second meaning that $L$ is known to be false. Second,
sensing the truth value of a positive literal $L$ that is currently unknown is
mapped into two actions: one that predicts $KL$, and another that predicts
$K\neg L$. The _plan-execute-observe-and-replan_ loop then executes the prefix
of the plan obtained from $K(P)$ using a classical planner until a discrepancy
is found between what has been predicted and what has been observed. In such a
case, the observed literals are added, a new plan is computed, and the loop
continues until the goal is reached. For problems with no dead ends and
_belief width_ 1, the executions are guaranteed to reach the goal in a bounded
number of steps Bonet and Geffner (2014). Problems like Wumpus over 15x15
grids are solved consistently very fast. On the other hand, coverage over
instances of problems like Minesweeper is not 100%, which is natural as belief
tracking in Minesweeper is NP-hard Kaye (2000) while incomplete and polynomial
in the planner Palacios and Geffner (2009). Learning approaches face two
challenges in these types of problems: dealing with partial observability over
instances of the same domain, and more critically, transferring useful
knowledge from instances of one domain to instances of another.

Finite-state controllers and generalized planning. Finite-state controllers
represent an action selection mechanism widely used in video-games and
robotics. A finite-state controller for a partially observable problem $P$
with actions $a$ and observations $o$ can be characterized by a set of tuples
$(q,o,a,q^{\prime})$ with no pair of tuples sharing the first two components
$q$ and $o$. Each such tuple prescribes the action $a$ to be done when the
controller state is $q$ and the observation is $o$, switching then to the
controller state $q^{\prime}$ (which may be equal to $q$ or not). A controller
solves $P$ if starting in the distinguished controller state $q_{0}$, all the
executions that are compatible with the controller reach a goal state. In the
approach by Bonet et al. [2009], the problem $P$ is transformed into a
classical planning problem $P^{\prime}$ whose actions are associated with each
one of the possible tuples $(q,o,a,q^{\prime})$, and where extra fluents
$p_{q}$ and $p_{o}$ track the controller states and observations. The action
$t=(q,o,a,q^{\prime})$ behaves like the action $a$ but conditional on $p_{q}$
and $p_{o}$ being true, and setting $p_{q^{\prime}}$ to true. Figure 3 shows a
problem where a visual-marker or eye (circle on the lower left) must be placed
on top of a green block by moving it one cell at a time. The location of the
green block is not known, and the observations are whether the cell currently
marked contains a green block (G), a non-green block (B), or neither (C), and
whether this cell is at the level of the table (T) or not (–). The finite-
state controller shown on the right has been computed by running a classical
planner over the transformed problem. The controller moves the eye from left
to right at the level of the table, and when it finds a block that is not
green, it moves the eye up the tower and then down. Interestingly, this
controller not only solves the problem shown on the left, but _any
modification of the problem resulting from changes in the number or
configuration of blocks_. This is an instance of what has been called _one-
shot learning_ : the controller obtained by the classical planner for one
instance solves all instances of the problem. The task of computing solutions
to families of planning problems, for example, all instances of Blocks world
featuring blocks $A$ and $B$ where the goal is $A$ on $B$, is called
_generalized planning_ Srivastava et al. (2011); Hu and De Giacomo (2011);
Bonet et al. (2017). Generalized planning provides an interesting bridge to
work in DRL Groshev et al. (2017) as a generalized plan is not just the output
$f(x)$ for a particular planning instance $x$ (Figure 1), but the function $f$
itself. This is indeed a case where _planners and learners aim at the same
type of plans_ , ones using models, the others, experience.

Figure 3: Left: Problem where a visual-marker (mark on the lower left cell)
must be placed on top of a green block whose location is not known, by moving
the mark one cell at a time, and by observing what’s in the marked cell.
Right: Two-state controller obtained with a classical planner. The controller
solves the problem and any variation resulting from changes in the number or
configuration of blocks. Edge $q\rightarrow q^{\prime}$ labeled $o/a$
represents tuple $(q,o,a,q^{\prime})$.

###  6.3 Width

The third and last idea that we consider in planning is related to a very
simple search algorithm called IW($k$) that has some remarkable properties
Lipovetzky and Geffner (2012). The algorithm assumes that the states $s$
assign values to a number of boolean features $F$ that are given. In classical
planning, the boolean features are the atoms of the problem but the algorithm
applies to other settings as well. For $k=1$, IW(1) is a standard _breadth-
first search_ with just one change: if upon generation of a state $s$, there
is no feature $f_{i}$ in $F$ such that $f_{i}$ is true in $s$ and false in all
the states generated before $s$, the state $s$ is pruned. In other words, the
only states that are not pruned are those that make _some_ feature true for
the first time. Such states are said to have novelty $1$. The number of states
expanded by IW(1) is thus _linear_ in $|F|$ and not exponential in $|F|$ as in
breadth-first search. The algorithm IW($k$) is IW(1) but applied to the larger
feature set $F^{k}$ made up of the conjunctions of $k$ features from $F$. A
basic property of IW($k$) is that most classical planning benchmark domains
can be formally shown to have a bounded and small _width_ $w$ no greater than
2 when goals are _single atoms_ , meaning that any such instances can be
solved optimally (shortest plans) by running IW($w$) in low polynomial time.
For example, the goal $on(x,y)$ for any two blocks $x$ and $y$ in Blocks world
can be shown to have width no greater than $2$, no matter the number of blocks
or initial configuration. This means that IW(2) finds a shortest plan to
achieve $on(x,y)$ in polynomial time in the number of atoms and blocks even
though the state space for the problem is exponential. The majority of the
benchmarks, however, do not feature a single atomic goal but a conjunction of
them, and a number of extensions of IW($k$) have been developed aimed at them,
some of which represent the current state of the art Lipovetzky and Geffner
(2017). Moreover, unlike all the classical planning algorithms developed so
far, including those that rely on heuristics obtained from relaxations or
reductions into SAT, some of these extensions scale up equally well without
taking into account the structure of actions (preconditions and effects),
meaning that they can plan with _simulators_ Francès et al. (2017). In
particular, IW(1) has been used effectively as an on-line planner in the Atari
video games in two modes: with the memory states of the emulator Lipovetzky et
al. (2015) and with the screen states Bandres et al. (2018). In the first
case, the features $f_{i}$ are associated with each of the 256 values of the
128 memory bytes; in the second case, the features are the B-PROST pixel
features Liang et al. (2016) defined and motivated by the neural net
architecture underlying DQN Mnih et al. (2015).

##  7 Learners and Solvers: Contrasts

The IW(1) planner and the DQN learner perform comparably well in the Atari
games while working in ways that illustrate _key differences between learners
and solvers:_ DQN requires lots of training data and time, and then plays very
fast, reactively; IW(1) plays out of the box with no training but needs to
think a bit before each move.2220.5 seconds per move in the rollout version of
IW(1). This is a general characteristic: learners require training, which is
often slow, but then are fast; solvers can deal with new problems with no
training but after some deliberation. Solvers are thus general, domain
independent as they are called, in a way that learners can’t be: solvers can
deal with new problems from scratch, provided a suitable representation of the
problems; learners need experience on related problems.

The differences between _model-free learners_ and _model-based solvers_ are
reminiscent of current accounts in psychology that describe the human mind as
made of two interacting systems or processes: a System 1 associated with the
“intuitive mind”, and a System 2 associated with the “analytical mind” Evans
and Stanovich (2013). Kahneman [2011] refers to the two processes as fast and
slow thinking. Common characteristics associated with these systems are:

System 1 |  | System 2
---|---|---
fast |  | slow
associative |  | deliberative
unconscious |  | conscious
effortless |  | effortful
parallel |  | serial
automatic |  | controlled
heuristic |  | systematic
specialized |  | general
… |  | …

It is hard not to see the parallels between the characteristics associated
with Systems 1 and 2 on the one hand, and those of learners and solvers on the
other. The processes underlying Systems 1 and 2 in the human mind, however,
are not independent: System 2 is assumed to have evolved more recently than
System 1 and to be based on it. For activities like solving a Sudoku, writing
a proof, or understanding a long text, it is assumed that the analytical
System 2 is in command, integrating the suggestions of System 1 that are
triggered by clues issued by System 2 or picked up from context. Our account
of classical planning as heuristic search has this flavor: the deliberate
search for the goal is informed by an heuristic which must be opaque to the
“analytical mind”, as it is computed from a relaxed model that has no
resemblance to the real world Geffner (2010). More generally, there cannot be
a System 2 without a System 1, as reasoning is computationally hard and for
inference methods to be effective they have to be “biased” to exploit the
structure of common tasks. At the same time, human cognition cannot be a
System 1 process only, as there are situations and new problems where
accumulated experience and built-in mechanisms are not adequate.

##  8 Learners and Solvers: Challenges

The learning algorithm AlphaZero at the heart of the systems that learn to
play chess and Go at world-class level by pure self-play Silver et al. (2017a,
b) is an _effective integration of a learner and a solver._ AlphaZero is a
modified, pointwise version of policy iteration, a basic planning algorithm
for MDPs and adversarial games where a policy is evaluated and improved
iteratively Bertsekas (2018). In AlphaZero, a neural network is used to
represent the value and policy functions, and in each iteration both functions
are improved incrementally at one state (and at others by generalization) by
carrying out a Monte Carlo tree search Coulom (2006); Kocsis and Szepesvári
(2006) from such state guided by the current value and policy functions.
Interestingly, AlphaZero is similar to an algorithm developed independently at
the same time, Expert Iteration (ExIt), that is explicitly cast as an
integration of System 1 and System 2 inference Anthony et al. (2017). Both
AlphaZero and ExIt can also be understood as systems that learn by imitation
but with a planner as teacher, and with the ability to iteratively improve the
teacher.

Two key questions are what are the inherent limitations of these algorithms,
and what else would be needed in order to get a more _general integration of
System 1 and System 2 inference_ in AI systems. As mentioned before, a key
restriction of learners relying on neural networks is that the _size of their
inputs $x$ is fixed._ This implies that learners cannot emulate solvers even
over specific domains. That is, deep learners cannot emulate a classical
planner or a domain-specific Blocks world planner unless arbitrary instances
can be expressed in finite size. Attention mechanisms have been proposed for
this but attention may be more relevant for executing policies than for
computing them. Regarding the second question, some key dimensions for a more
_general and synergistic integration of learners and solvers_ are:

Model learning. Solvers provide flexibility and generality, but solvers need
models. Explanation and accountability also require models: we build
explanations and make predictions using models Darwiche (2017); Lake et al.
(2017); Pearl (2018). Model-based reinforcement learning is model-learning but
the standard algorithms assume that the state variables are given. Learning
models from streams of actions and partial observations remains challenging.

Learning the relevant variables. In deep learning, representation learning is
learning functions (features) of the inputs that are somehow reusable.
Features that are particularly reusable are the _variables of a problem_. For
example, many of the Atari games involve 2D objects that move, and things that
happen as a result of collisions. How to learn such variables from the screen?
Should the moving objects emerge from a general learning scheme, from prior
knowledge, or from a combination of both Mugan and Kuipers (2012); Thomas et
al. (2017); Marcus (2018a)?

Learning finite-size abstract representations. The input size restriction
makes it challenging for DRL methods to learn general policies for achieving a
goal like $on(A,B)$ over all instances with blocks $A$ and $B$. An alternative
to the use of attention mechanisms is to learn problem abstractions of bounded
size that depend on the goal. For example, for achieving the goal $on(x,y)$
the only features that matter are the number of blocks above $x$ and above
$y$, along with some booleans, and a convenient, fixed-size abstraction of
this family of problems can be obtained by projecting the actions over such
features Bonet and Geffner (2018). The challenge is to learn such features and
projections automatically.

Most work in DRL has not been aimed at an integration of learners and solvers
but at expanding the range of problems handled by DRL. Something similar can
be said about work in planners and solvers. Yet, the solutions to some of the
bottlenecks faced by each approach, that often have to do with
representational issues, may lie in the integration that is required to
resemble the integration of Systems 1 and 2 in the human mind. One area where
research on solvers and learners meet, as mentioned above, is in the
computation of generalized plans capable of solving many problems at the same
time. Other types of challenges are dealing with other agents, virtual or
human, in what constitutes the social dimension of intelligence, and dealing
with a physical and social world that is not segmented into problems or tasks
Dietterich (2018).

##  9 AI: Dreams and Nightmares

AI is not close to a general, human level-intelligence but this does not mean
that current and future AI capabilities can’t be used for good or ill. The
Asilomar AI Principles enumerate ways in which harms can be avoided and
benefits realized333https://futureoflife.org/ai-principles. but the principles
are not easy to enforce. It would be great to align the values of AI systems
with human values, but the same applies to technology in general, politics,
and economics. Clearly, there are other forces at play: forces like a powerful
market and a weak political system, both increasingly aimed at our System 1. I
have argued why flexible and transparent AI systems need a System 2 that
cannot be provided by learners alone. The same applies to our collective lives
where learning from mistakes, when it is possible at all, can be very costly.
For living together in modern societies, we need a well-functioning System 2
informed by facts and the common good.444Stanovich (2005); Heath (2014). If we
want good AI, we can’t look away from culture and politics.

## Acknowledgments

I thank Jérôme Lang for the invitation to speak at IJCAI, Guillem Francès and
Blai Bonet for many useful comments, and my current and former students for
the opportunity to learn with them. The work is partially funded by grant
TIN2015-67959-P, MINECO, Spain.

## References

  * Anthony et al. [2017] T. Anthony, Z. Tian, and D. Barber.  Thinking fast and slow with deep learning and tree search.  In NIPS, 2017.
  * Bandres et al. [2018] W. Bandres, B. Bonet, and H. Geffner.  Planning with pixels in (almost) real time.  In AAAI, 2018.
  * Bertsekas [1995] D. Bertsekas.  Dynamic Programming and Optimal Control, Vols 1 and 2. Athena Scientific, 1995.
  * Bertsekas [2018] D. Bertsekas.  Feature-based aggregation and deep reinforcement learning: A survey and some new implementations.  arXiv preprint arXiv:1804.04577, 2018.
  * Biere et al. [2009] A. Biere, M. Heule, H. van Maaren, and T. Walsh, editors.  Handbook of Satisfiability: Volume 185 Frontiers in Artificial Intelligence and Applications.  IOS Press, 2009.
  * Bonet and Geffner [2001] B. Bonet and H. Geffner.  Planning as heuristic search.  Artificial Intelligence, 129(1–2):5–33, 2001.
  * Bonet and Geffner [2014] B. Bonet and H. Geffner.  Flexible and scalable partially observable planning with linear translations.  In Proc. AAAI, 2014.
  * Bonet and Geffner [2018] B. Bonet and H. Geffner.  Features, projections, and representation change for generalized planning.  arXiv preprint arXiv:1801.10055, 2018.
  * Bonet et al. [2009] B. Bonet, H. Palacios, and H. Geffner.  Automatic derivation of memoryless policies and finite-state controllers using classical planners.  In Proc. ICAPS-09, pages 34–41, 2009.
  * Bonet et al. [2017] B. Bonet, G. De Giacomo, H. Geffner, and S. Rubin.  Generalized planning: non-deterministic abstractions and trajectory constraints.  In Proc. IJCAI, 2017.
  * Camacho et al. [2017] A. Camacho, E. Triantafillou, C. Muise, J. Baier, and S. McIlraith.  Non-deterministic planning with temporally extended goals: LTL over finite and infinite traces.  In Proc. AAAI, 2017.
  * Charniak et al. [1980] E. Charniak, C. Riesbeck, and D. McDermott.  Artificial intelligence programming.  L. Erlbaum Associates, 1980.
  * Chatterjee et al. [2016] K. Chatterjee, M. Chmelik, and J. Davies.  A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs.  In Proc AAAI, 2016.
  * Coulom [2006] R. Coulom.  Efficient selectivity and backup operators in Monte-Carlo tree search.  In Proc. Int. Conference on Computers and Games, pages 72–83. Springer, 2006.
  * Darwiche [2017] A Darwiche.  Human-level intelligence or animal-like abilities?  arXiv preprint, 2017.
  * Dechter [2003] R. Dechter.  Constraint Processing.  Morgan Kaufmann, 2003.
  * Dietterich [2018] T. Dietterich.  Reflections on innateness in machine learning.  https://medium.com/@tdietterich, 2018.
  * Evans and Stanovich [2013] J. Evans and K. Stanovich.  Dual-process theories of higher cognition: Advancing the debate.  Perspectives on psychological science, 8(3), 2013.
  * Feigenbaum and Feldman [1963] E.A. Feigenbaum and J. Feldman.  Computers and thought.  McGraw-Hill, 1963.
  * Francès et al. [2017] G. Francès, M. Ramírez, N. Lipovetzky, and H. Geffner.  Purely declarative action representations are overrated: Classical planning with simulators.  In Proc. IJCAI, 2017.
  * Gebser et al. [2012] M. Gebser, R. Kaminski, B. Kaufmann, and T. Schaub.  Answer set solving in practice.  Morgan & Claypool, 2012.
  * Geffner and Bonet [2013] H. Geffner and B. Bonet.  A concise introduction to models and methods for automated planning.  Morgan & Claypool, 2013.
  * Geffner [2010] H. Geffner.  Heuristics, planning and cognition.  In J. Halpern R. Dechter, H. Geffner, editor, Heuristics, Probability and Causality. A Tribute to Judea Pearl. College Publications, 2010\.
  * Genesereth et al. [2005] M. Genesereth, N. Love, and B. Pell.  General game playing: Overview of the AAAI competition.  AI magazine, 26(2):62, 2005.
  * Graves et al. [2013] A. Graves, A. Mohamed, and G. Hinton.  Speech recognition with deep recurrent neural networks.  In Proc. ICASSP, pages 6645–6649, 2013.
  * Graves et al. [2014] A. Graves, G. Wayne, and I. Danihelka.  Neural Turing machines.  arXiv preprint arXiv:1410.5401, 2014.
  * Groshev et al. [2017] E. Groshev, A. Tamar, S. Srivastava, and P. Abbeel.  Learning generalized reactive policies using deep neural networks.  arXiv preprint arXiv:1708.07280, 2017.
  * Heath [2014] J. Heath.  Enlightenment 2.0.  Harper Collins, 2014.
  * Hoffmann and Nebel [2001] J. Hoffmann and B. Nebel.  The FF planning system: Fast plan generation through heuristic search.  JAIR, 14:253–302, 2001.
  * Hu and De Giacomo [2011] Y. Hu and G. De Giacomo.  Generalized planning: Synthesizing plans that work for multiple environments.  In Proc. IJCAI, 2011.
  * Kaelbling et al. [1998] L. Kaelbling, M. Littman, and T. Cassandra.  Planning and acting in partially observable stochastic domains.  AI, 101(1–2):99–134, 1998.
  * Kahneman [2011] D. Kahneman.  Thinking, fast and slow.  Farrar, Straus and Giroux, 2011.
  * Kautz and Selman [1996] H. Kautz and B. Selman.  Pushing the envelope: Planning, propositional logic, and stochastic search.  In Proc. AAAI, pages 1194–1201, 1996.
  * Kaye [2000] R. Kaye.  Minesweeper is NP-Complete.  Mathematical Intelligencer, 22(2):9–15, 2000.
  * Kocsis and Szepesvári [2006] L. Kocsis and C. Szepesvári.  Bandit based Monte-Carlo planning.  In Proc. ECML-2006, pages 282–293, 2006.
  * Krizhevsky et al. [2012] A. Krizhevsky, I. Sutskever, and G. Hinton.  Imagenet classification with deep convolutional neural networks.  In NIPS, 2012.
  * Lake et al. [2017] B. Lake, T. Ullman, J. Tenenbaum, and S. Gershman.  Building machines that learn and think like people.  Behavioral and Brain Sciences, 40, 2017.
  * LeCun et al. [1989] Y. LeCun, B. Boser, J. Denker, D. Henderson, R. Howard, W. Hubbard, and L. Jackel.  Backpropagation applied to handwritten zip code recognition.  Neural computation, 1(4):541–551, 1989.
  * LeCun et al. [2015] Y. LeCun, Y. Bengio, and G. Hinton.  Deep learning.  Nature, 521(7553):436, 2015.
  * Lenat et al. [1990] D. Lenat, R. Guha, K. Pittman, D. Pratt, and M. Shepherd.  CYC: toward programs with common sense.  Communications of the ACM, 33(8):30–49, 1990.
  * Liang et al. [2016] Y. Liang, M. Machado, E. Talvitie, and M. Bowling.  State of the art control of Atari games using shallow reinforcement learning.  In Proc. AAMAS, 2016.
  * Lipovetzky and Geffner [2012] N. Lipovetzky and H. Geffner.  Width and serialization of classical planning problems.  In Proc. ECAI, 2012.
  * Lipovetzky and Geffner [2017] N. Lipovetzky and H. Geffner.  Best-first width search: Exploration and exploitation in classical planning.  In Proc. AAAI, 2017.
  * Lipovetzky et al. [2015] N. Lipovetzky, M. Ramirez, and H. Geffner.  Classical planning with simulators: Results on the atari video games.  In Proc. IJCAI, 2015.
  * Marcus [2018a] G. Marcus.  Innateness, AlphaZero, and artificial intelligence.  arXiv preprint, 2018.
  * Marcus [2018b] Gary Marcus.  Deep learning: A critical appraisal.  arXiv preprint arXiv:1801.00631, 2018.
  * McCarthy [1958] J. McCarthy.  Programs with common sense.  In Proc. Symp. on Mechanization of Thought Processes, 1958.
  * McCarthy [1987] J. McCarthy.  Generality in artificial intelligence.  Communications of the ACM, 30(12), 1987.
  * McDermott [1999] D. McDermott.  Using regression-match graphs to control search in planning.  Artificial Intelligence, 109(1-2):111–159, 1999.
  * Mnih et al. [2015] V. Mnih, K. Kavukcuoglu, D. Silver, A. A Rusu, J. Veness, M. G Bellemare, A. Graves, M. Riedmiller, A. K Fidjeland, G. Ostrovski, et al.  Human-level control through deep reinforcement learning.  Nature, 518(7540):529, 2015.
  * Mugan and Kuipers [2012] J. Mugan and B. Kuipers.  Autonomous learning of high-level states and actions in continuous environments.  IEEE Transactions on Autonomous Mental Development, 4(1):70–86, 2012.
  * Norvig [1992] P. Norvig.  Paradigms of artificial intelligence programming: case studies in Common LISP.  Morgan Kaufmann, 1992.
  * Palacios and Geffner [2009] H. Palacios and H. Geffner.  Compiling uncertainty away in conformant planning problems with bounded width.  JAIR, 35:623–675, 2009.
  * Pearl [1983] J. Pearl.  Heuristics.  Addison Wesley, 1983.
  * Pearl [1988] J. Pearl.  Probabilistic Reasoning in Intelligent Systems.  Morgan Kaufmann, 1988.
  * Pearl [2018] J. Pearl.  Theoretical impediments to machine learning with seven sparks from the causal revolution.  arXiv preprint arXiv:1801.04016, 2018.
  * Ramírez and Geffner [2010] M. Ramírez and H. Geffner.  Probabilistic plan recognition using off-the-shelf classical planners.  In Proc. AAAI, 2010.
  * Rintanen [2004] J. Rintanen.  Complexity of planning with partial observability.  In ICAPS, pages 345–354, 2004.
  * Rumelhart and McClelland [1986] D. Rumelhart and J. McClelland, editors.  Parallel distributed processing: explorations in the microstructure of cognition. Vol. 1.  MIT Press, 1986.
  * Russell and Norvig [2009] S. Russell and P. Norvig.  Artificial Intelligence: A Modern Approach.  Prentice Hall, 2009.  3rd Edition.
  * Silver et al. [2017a] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, et al.  Mastering chess and shogi by self-play with a general reinforcement learning algorithm.  arXiv preprint arXiv:1712.01815, 2017.
  * Silver et al. [2017b] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al.  Mastering the game of go without human knowledge.  Nature, 550(7676):354, 2017.
  * Srivastava et al. [2011] S. Srivastava, N. Immerman, and S. Zilberstein.  A new representation and associated algorithms for generalized planning.  AI, 175(2):615–647, 2011.
  * Stanovich [2005] K. Stanovich.  The robot’s rebellion: Finding meaning in the age of Darwin.  Univ. of Chicago Press, 2005.
  * Sutton and Barto [1998] R. Sutton and A. Barto.  Introduction to Reinforcement Learning.  MIT Press, 1998.
  * Thomas et al. [2017] V. Thomas, J. Pondard, E. Bengio, M. Sarfati, P. Beaudoin, M. Meurs, J. Pineau, D. Precup, and Y. Bengio.  Independently controllable features.  arXiv preprint, 2017.
  * Turing [1936] A. Turing.  On computable numbers, with an application to the Entscheidungsproblem.  In Proc. of the London Mathematical Society, volume 42, 1936.


# Semilinear Home-space is Decidable for Petri Nets

Petr Jančar  Dept of Comp. Sci., Faculty of Science, Palacký Univ. Olomouc,
<EMAIL_ADDRESS>Jérôme Leroux  LaBRI, CNRS, Univ. Bordeaux,
<EMAIL_ADDRESS>
###### Abstract

A set of configurations $\mathbf{H}$ is an home-space for a set of
configurations $\mathbf{X}$ of a Petri net if every configuration reachable
from $\mathbf{X}$ can reach $\mathbf{H}$. The semilinear home-space problem
for Petri nets asks, given a Petri net $A$, and semilinear sets of
configurations $\mathbf{X},\mathbf{H}$ if $\mathbf{H}$ is an home-space for
$\mathbf{X}$. In 1989, Davide de Frutos Escrig and Colette Johnen proved that
the problem is decidable when $\mathbf{X}$ is a singleton and $\mathbf{H}$ is
a finite union of linear sets using the same periods. In this paper, we show
that the general problem is decidable. This result is obtained by proving a
duality between the reachability problem and the non-home-space problem. More
formally, we prove that for any Petri net $A$ and for any linear set of
configurations $\mathbf{L}$, we can effectively compute a semilinear set
$\mathbf{W}$ of configurations such that for every set $\mathbf{X}$, the set
$\mathbf{L}$ is not an home-space for $\mathbf{X}$ if, and only if
$\mathbf{W}$ is reachable from $\mathbf{X}$.

##  1 Introduction

Petri nets are one of the most popular formal methods for the representation
and the analysis of parallel processes [4].

The central algorithmic problem for Petri net is reachability: given a Petri
net $A$ and two configurations $\mathbf{x}$ and $\mathbf{y}$, decide whether
there exists an execution of $A$ from $\mathbf{x}$ to $\mathbf{y}$. In fact
many important computational problems in logic and complexity reduce or are
even equivalent to this problem [11, 6]. Recently, the complexity of the Petri
net reachability problem was proved to be “Ackermannian-complete” (see [8] for
the upper-bound and [9, 2] for the lower-bound),

The reachability problem for Petri nets can be easily generalized to
semilinear sets, a class of geometrical sets that coincides with the sets
definable in the Presburger arithmetic [5]. The semilinear reachability
problem for Petri nets asks, given a Petri net $A$, and (presentations of)
semilinear sets of configurations $\mathbf{X}$,$\mathbf{Y}$ if there exists an
execution from a configuration in $\mathbf{X}$ to a configuration in
$\mathbf{Y}$. Denoting by $\textsc{post}^{*}_{A}(\mathbf{X})$ the
configurations reachable from $\mathbf{X}$ and by
$\textsc{pre}^{*}_{A}(\mathbf{Y})$ the configurations that can reach a
configuration in $\mathbf{Y}$, the semilinear reachability problem is
equivalent to decide if the intersection
$\textsc{post}^{*}_{A}(\mathbf{X})\cap\textsc{pre}^{*}_{A}(\mathbf{Y})$ is
empty. This problem can be easily reduced to classical (instances when
$\mathbf{X}$ and $\mathbf{Y}$ are singleton) reachability problems for Petri
nets.

The semilinear home-space problem is a problem that seems to be similar to the
semilinear reachability problem at a first sight. This problem asks, given a
Petri net $A$, and two semilinear sets $\mathbf{X},\mathbf{H}$, if every
configuration reachable from $\mathbf{X}$ can reach $\mathbf{H}$. This problem
is equivalent to prove the inclusion
$\textsc{post}^{*}_{A}(\mathbf{X})\subseteq\textsc{pre}^{*}_{A}(\mathbf{H})$.
In 1989, Davide de Frutos Escrig and Colette Johnen proved that the semilinear
home-space problem is decidable for instances where $\mathbf{X}$ is a
singleton set and $\mathbf{H}$ is a finite union of linear sets using the same
periods and let open the general case. The decidability status of the home-
space problem stays open for several years. In fact, it was unclear if the
general problem should be decidable since the inclusion (in fact also the
equality) problem
$\textsc{post}^{*}_{A}(\mathbf{X})\subseteq\textsc{pre}^{*}_{B}(\mathbf{H})$
is undecidable even when $\mathbf{X}$ and $\mathbf{H}$ are singleton sets and
the dimensions of the Petri nets $A,B$ are fixed to some small values [7].

Our contribution. In this paper, we show that the general semilinear home-
space problem is decidable. This result is obtained by proving a duality
between the reachability problem and the non-home-space problem. More
formally, we prove that for any Petri net $A$ and for any linear set of
configurations $\mathbf{L}$, we can effectively compute a semilinear set
$\mathbf{W}$ of configurations such that for every set $\mathbf{X}$, the set
$\mathbf{L}$ is not an home-space for $\mathbf{X}$ if, and only if
$\mathbf{W}$ is reachable from $\mathbf{X}$.

By $\mathbb{N}$ we denote the set $\\{0,1,2,\dots\\}$ of nonnegative integers.
For (a dimension) $d\in\mathbb{N}$, the elements of $\mathbb{N}^{d}$ are
called ($d$-dimensional) vectors; they are denoted in bold face, and for
$\mathbf{x}\in\mathbb{N}^{d}$ we put
$\mathbf{x}=(\mathbf{x}(1),\mathbf{x}(2),\ldots,\mathbf{x}(d))$ so that we can
refer to the vector components. We use the component-wise sum
$\mathbf{x}+\mathbf{y}$ of vectors, and their component-wise order
$\mathbf{x}\leq\mathbf{y}$. For $c\in\mathbb{N}$, we put
$c\cdot\mathbf{x}=(c\cdot\mathbf{x}(1),c\cdot\mathbf{x}(2),\ldots,c\cdot\mathbf{x}(d))$.
By $\|\mathbf{x}\|$ we denote the sum of components, i.e.,
$\|\mathbf{x}\|=\sum_{i=1}^{d}\mathbf{x}(i)$.

##  2 Semilinear Petri Net Reachability Problem

In this section, we briefly recall related notions about semilinear sets and
Petri nets.

A set $\mathbf{L}\subseteq\mathbb{N}^{d}$ is _linear_ , if there are
$d$-dimensional vectors $\mathbf{b}$ (the _basis_) and
$\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{k}$ (the _periods_ ,
$k\in\mathbb{N}$) such that

$\mathbf{L}=\\{\mathbf{x}\in\mathbb{N}^{d}\mid\mathbf{x}=\mathbf{b}+\mathbf{u}(1)\cdot\mathbf{p}_{1}\cdots+\mathbf{u}(k)\cdot\mathbf{p}_{k}$
for some $\mathbf{u}\in\mathbb{N}^{k}\\}$.

In this case $\mathbf{L}$ is said to be _presented_ by the tuple
$(\mathbf{b},\mathbf{p}_{1},\ldots,\mathbf{p}_{k})$. A set
$\mathbf{S}\subseteq\mathbb{N}^{d}$ is _semilinear_ if it is a finite union of
linear sets, i.e. $\mathbf{S}=\mathbf{L}_{1}\cdots\cup\mathbf{L}_{m}$ where
all $\mathbf{L}_{i}$ are linear. In that case, we present $\mathbf{S}$ as a
sequence of presentations of $\mathbf{L}_{1},\ldots,\mathbf{L}_{m}$. When such
a presentation is effectively computable, the semilinear set $\mathbf{S}$ is
said to be _effectively constructible_.

Given a set $\mathbf{S}\subseteq\mathbb{N}^{d}$, by $\overline{\mathbf{S}}$ we
denote its complement, i.e.,
$\overline{\mathbf{S}}=\mathbb{N}^{d}\smallsetminus\mathbf{S}$. If
$\mathbf{S}$ is semilinear, then also $\overline{\mathbf{S}}$ is semilinear.
Moreover, $\overline{\mathbf{S}}$ is effectively constructible from a
presentation of $\mathbf{S}$; this follows from the well-known fact that a set
is semilinear iff it is expressible in Presburger arithmetic [5].

We use a concise definition of (unmarked place/transition) Petri nets. By a
_$d$ -dimensional Petri-net action_ we mean a pair
$a=(\mathbf{a}_{-},\mathbf{a}_{+})\in\mathbb{N}^{d}\times\mathbb{N}^{d}$. With
$a=(\mathbf{a}_{-},\mathbf{a}_{+})$ we associate the binary relation
$\xrightarrow{a}$ on the set $\mathbb{N}^{d}$ by putting
$(\mathbf{x}+\mathbf{a}_{-})\xrightarrow{a}(\mathbf{x}+\mathbf{a}_{+})$ for
all $\mathbf{x}\in\mathbb{N}^{d}$. The relations $\xrightarrow{a}$ are
naturally extended to the relations $\xrightarrow{\sigma}$ for finite
sequences $\sigma$ of ($d$-dimensional Petri net) actions.

A _Petri net_ $A$ _of dimension_ $d$ (with $d$ places in more traditional
definitions) is a finite set of $d$-dimensional Petri-net actions
(transitions). Here the vectors $\mathbf{x}\in\mathbb{N}^{d}$ are also called
_configurations_ (markings). On the set $\mathbb{N}^{d}$ of configurations we
define the _reachability relation_ $\xrightarrow{A^{*}}$: we put
$\mathbf{x}\xrightarrow{A^{*}}\mathbf{y}$ if there is $\sigma\in A^{*}$ such
that $\mathbf{x}\xrightarrow{\sigma}\mathbf{y}$. Given two sets
$\mathbf{X},\mathbf{Y}\subseteq\mathbb{N}^{d}$, we write
$\mathbf{X}\xrightarrow{A^{*}}\mathbf{Y}$ if there exist
$\mathbf{x}\in\mathbf{X}$ and $\mathbf{y}\in\mathbf{Y}$ such that
$\mathbf{x}\xrightarrow{A^{*}}\mathbf{y}$.

We recall that the _reachability problem_ (given $A$, $\mathbf{x}$,
$\mathbf{y}$, is $\mathbf{x}\xrightarrow{A^{*}}\mathbf{y}$ ?) is decidable
[10]; it has been recently shown to be “Ackermannian-complete” [9, 2].
Moreover, if two sets $\mathbf{X},\mathbf{Y}\subseteq\mathbb{N}^{d}$ are
linear, the problem $\mathbf{X}\xrightarrow{A^{*}}\mathbf{Y}$ is decidable
since it is logspace reducible to the reachability problem (by adding to $A$
one Petri net action for each period of $\mathbf{X}$ and $\mathbf{Y}$).
Furthermore, by decomposing semilinear sets into finite union of linear sets,
it follows that the problem $\mathbf{X}\xrightarrow{A^{*}}\mathbf{Y}$ is also
decidable when $\mathbf{X}$ and $\mathbf{Y}$ are (effectively) semilinear.

##  3 Home Space Problem

We first define a few useful notions and then specify some variants of the
home-space problem that we consider. We implicitly assume a fixed Petri net
$A$ of dimension $d$ if not said otherwise.

For $\mathbf{X}\subseteq\mathbb{N}^{d}$ we put
$\textsc{post}^{*}_{A}(\mathbf{X})=\bigcup_{\mathbf{x}\in\mathbf{X}}\textsc{post}^{*}_{A}(\mathbf{x})$
where
$\textsc{post}^{*}_{A}(\mathbf{x})=\\{\mathbf{y}\in\mathbb{N}^{d}\mid\mathbf{x}\xrightarrow{A^{*}}\mathbf{y}\\}$.
Symmetrically, for $\mathbf{Y}\subseteq\mathbb{N}^{d}$ we put
$\textsc{pre}^{*}_{A}(\mathbf{Y})=\bigcup_{\mathbf{y}\in\mathbf{Y}}\textsc{pre}^{*}_{A}(\mathbf{y})$
where
$\textsc{pre}^{*}_{A}(\mathbf{y})=\\{\mathbf{x}\in\mathbb{N}^{d}\mid\mathbf{x}\xrightarrow{A^{*}}\mathbf{y}\\}$.
A set $\mathbf{X}\subseteq\mathbb{N}^{d}$ is an _inductive invariant_ if
$\textsc{post}^{*}_{A}(\mathbf{X})\subseteq\mathbf{X}$ (hence
$\textsc{post}^{*}_{A}(\mathbf{X})=\mathbf{X}$). We note that
$\textsc{post}^{*}_{A}(\mathbf{X})$ is an inductive invariant for each
$\mathbf{X}\subseteq\mathbb{N}^{d}$. Also
$\overline{\textsc{pre}^{*}_{A}(\mathbf{Y})}$ is an inductive invariant for
any $\mathbf{Y}\subseteq\mathbb{N}^{d}$.

Given two sets $\mathbf{X},\mathbf{H}\subseteq\mathbb{N}^{d}$, we say that
$\mathbf{H}$ is a  _home-space for_ $\mathbf{X}$, if
$\textsc{post}^{*}_{A}(\mathbf{X})\subseteq\textsc{pre}^{*}_{A}(\mathbf{H})$.
We are interested in the decidability of the _home-space problem_ asking,
given a Petri net $A$ of dimension $d$ and two effective semilinear sets
$\mathbf{X},\mathbf{H}\subseteq\mathbb{N}^{d}$, if $\mathbf{H}$ is a home-
space for $\mathbf{X}$.

######  Remark 1.

One might also consider “existential” problems that asks given a petri net $A$
of dimension $d$ and (a finite presentation of) a semilinear set
$\mathbf{X}\subseteq\mathbb{N}^{d}$, if there exists a home space $\mathbf{H}$
for $\mathbf{X}$ such that $\mathbf{H}$ is a singleton, or such that
$\mathbf{H}$ is a semilinear set included in
$\textsc{post}^{*}_{A}(\mathbf{X})$. The former case was proved to be
decidable in [1], and the last one is still open.

By [3] we know that the home-space problem is decidable for the instances $A$,
$\mathbf{X}$, $\mathbf{H}$ where $\mathbf{X}$ is a singleton set, and
$\mathbf{H}$ is a finite union of linear sets with the same period-sets. The
decidability is established by a Turing reduction to the reachability problem.

In [3] it was left open if the problem is decidable also for the instances
$A$, $\mathbf{X}$, $\mathbf{H}$ where $\mathbf{X}$ is a singleton, and
$\mathbf{H}$ is a general effective semilinear set (a finite union of linear
sets with possibly different period-sets). Here we give the positive answer by
proving the following theorem.

######  Theorem 1.

There is an algorithm that, given a Petri net $A$ of dimension $d$, and two
presentations of semilinear sets $\mathbf{X}$ and $\mathbf{H}$ decides if
$\mathbf{H}$ is a home-space for $\mathbf{X}$.

##  4 Non-Home-Space Witnesses

Now we start to think about a proof of Theorem 1. Given a Petri net $A$ of
dimension $d$, two semilinear sets
$\mathbf{X},\mathbf{H}\subseteq\mathbb{N}^{d}$, it is clear that we have:

$\mathbf{H}$ is not a home-space for $\mathbf{X}$ iff there exists
$\mathbf{c}$ such that
$\mathbf{X}\xrightarrow{A^{*}}\mathbf{c}\not\xrightarrow{A^{*}}\mathbf{H}$

If we have no means to directly verify this property, we can look for a
suitable (e.g. semilinear) set $\mathbf{W}$ which has the property for every
$\mathbf{x}\in\mathbb{N}^{d}$, we have
$\mathbf{x}\xrightarrow{A^{*}}\mathbf{W}$ iff there exists
$\mathbf{c}\in\mathbb{N}^{d}$ such that
$\mathbf{x}\xrightarrow{A^{*}}\mathbf{c}\not\xrightarrow{A^{*}}\mathbf{H}$. In
that case, we say that $\mathbf{W}\subseteq\mathbb{N}^{d}$ is a  _non-home-
space witness_ , or just a _witness_ , _for_
$\mathbf{H}\subseteq\mathbb{N}^{d}$.

So we would be done (with a proof of Theorem 1) if we could construct a
semilinear witness of $\mathbf{H}$. This does not seem straightforward, so we
will use still other general observations to simplify the problem (so that it
will suffice when a semilinear witness is effectively constructible for a
linear set).

######  Proposition 2.

If $\mathbf{H}=\mathbf{H}_{1}\cup\mathbf{H}_{2}\cdots\cup\mathbf{H}_{m}$, and
if $\mathbf{W}_{1},\ldots,\mathbf{W}_{k}$ are such that $\mathbf{W}_{i}$ is a
witness for $\mathbf{H}_{i}$ for each $i$, then $\mathbf{H}$ is not an home-
space for a set $\mathbf{X}\subseteq\mathbb{N}^{d}$ if, and only if, there is
an execution

$\mathbf{x}\xrightarrow{A^{*}}\mathbf{x}_{1}\cdots\xrightarrow{A^{*}}\mathbf{x}_{m}$
(1)

where $\mathbf{x}\in\mathbf{X}$, and $\mathbf{x}_{i}\in\mathbf{W}_{i}$ for
each $i$. (In fact, the order of $\mathbf{W}_{i}$ is irrelevant.)

###### Proof.

Given an execution (1), we have for each $i$ that
$\mathbf{x}_{i}\in\mathbf{W}_{i}$, and thus
$\mathbf{x}_{i}\not\xrightarrow{A^{*}}\mathbf{H}_{i}$. It follows that
$\mathbf{x}_{j}\not\xrightarrow{A^{*}}\mathbf{H}_{i}$ for all
$j\in\\{i,\ldots,m\\}$. Hence
$\mathbf{x}_{m}\not\xrightarrow{A^{*}}\mathbf{H}$. Thus $\mathbf{H}$ is not an
home-space for $\mathbf{X}$. Conversely, assume that $\mathbf{H}$ is not an
home-space for a set $\mathbf{X}\subseteq\mathbb{N}^{d}$. Then, there exist
configurations $\mathbf{x},\mathbf{x}_{0}$ such that
$\mathbf{x}\in\mathbf{X}$, and
$\mathbf{x}\xrightarrow{A^{*}}\mathbf{x}_{0}\not\xrightarrow{A^{*}}\mathbf{H}$.
Since $\mathbf{x}_{0}\not\xrightarrow{A^{*}}\mathbf{H}$ then
$\mathbf{x}_{0}\not\xrightarrow{A^{*}}\mathbf{H}_{1}$. It follows that
$\mathbf{x}_{0}\xrightarrow{A^{*}}\mathbf{x}_{1}$ for some configuration
$\mathbf{x}_{1}\in\mathbf{W}_{1}$. Now, observe that
$\mathbf{x}_{1}\not\xrightarrow{A^{*}}\mathbf{H}$ and now we deduce that
$\mathbf{x}_{1}\xrightarrow{A^{*}}\mathbf{x}_{2}\in\mathbf{W}_{2}$; etc. ∎

######  Proposition 3.

If $\mathbf{X}$ and the witnesses
$\mathbf{W}_{1},\mathbf{W}_{2}\dots,\mathbf{W}_{m}$ in Proposition 2 are
effectively constructible semilinear sets, then the existence of an execution
(1) is decidable (by a reduction to reachability).

###### Proof.

We can construct a bigger Petri net that stepwise freezes $m$ configurations
of an original execution from $\mathbf{x}\in\mathbf{X}$ and checks (by the
correspondingly defined gadgets and the end-configuration) that these
configurations belong to $\mathbf{W}_{1},\mathbf{W}_{2}\ldots,\mathbf{W}_{m}$,
respectively. ∎

Hence a proof of Theorem 1 will be finished once we show:

######  Lemma 4.

Given a Petri net $A$ of dimension $d$, and a linear set
$\mathbf{L}\subseteq\mathbb{N}^{d}$, we can effectively construct a semilinear
witness for $\mathbf{L}$.

Before proving the lemma, we verify that it indeed entails Theorem 1: We have
$\mathbf{H}=\mathbf{H}_{1}\cup\mathbf{H}_{2}\ldots\cup\mathbf{H}_{m}$ where
$\mathbf{H}_{i}$ are linear sets, and by the lemma we can construct a
semilinear witness $\mathbf{W}_{i}$ for $\mathbf{H}_{i}$, for each $i$. Then
we ask if there is an execution (1). Proposition 3 thus finishes a proof of
the decidability claimed in Theorem 1.

##  5 Witness of Non-Home-Space For Linear Sets

It thus remains to prove Lemma 4.

As a gentle introduction, we first prove the lemma for the case when
$\mathbf{L}$ is a singleton, hence $\mathbf{L}=\\{\mathbf{b}\\}$ (there is a
basis $\mathbf{b}$ but no periods).

Referring to the assumed Petri net $A$ of dimension $d$, we say that
$\mathbf{x}\in\mathbb{N}^{d}$ _can decrease the token-count_ if
$\|\mathbf{x}^{\prime}\|<\|\mathbf{x}\|$ for some
$\mathbf{x}^{\prime}\in\textsc{post}^{*}_{A}(\mathbf{x})$. We note that the
set

$\textsc{DC}=\\{\mathbf{x}\in\mathbb{N}^{d}\mid\mathbf{x}$ can decrease the
token-count$\\}$

is upward closed and the set $\textsc{MIN}(\textsc{DC})$ of its minimal
elements (w.r.t. the component-wise partial order) is effectively
constructible. (We can use a general framework by Valk-Jantzen [12]. A crucial
fact is that if we are given a “partial configuration” $\mathbf{\bar{x}}$, in
which some components are unspecified, then the question if there is a
configuration $\mathbf{x}\in\textsc{DC}$ that is an instance of
$\mathbf{\bar{x}}$ can be easily reduced to the reachability problem.)

We observe that $\mathbf{x}\in\textsc{DC}$ entails that
$\mathbf{x}\xrightarrow{A^{*}}\mathbf{x}^{\prime}$ for some
$\mathbf{x}^{\prime}\in\textsc{NDC}$ where we put
$\textsc{NDC}=\overline{\textsc{DC}}$. In other words, NDC is a home-space for
any $\mathbf{X}\subseteq\mathbb{N}^{d}$.

Recalling that $\mathbf{L}=\\{\mathbf{b}\\}$, we now verify that

$\mathbf{W}=\textsc{NDC}\cap\big{(}\\{\mathbf{x};\|\mathbf{x}\|>\|\mathbf{b}\|\\}\cup\\{\mathbf{x};\|\mathbf{x}\|\leq\|\mathbf{b}\|$
and $\mathbf{x}\not\xrightarrow{A^{*}}\mathbf{b}\\}\big{)}$

is a witness for $\mathbf{L}$;

  * •

$\mathbf{x}\xrightarrow{A^{*}}\mathbf{c}\in\mathbf{W}$ clearly entails
$\mathbf{c}\not\xrightarrow{A^{*}}\mathbf{b}$;

  * •

$\mathbf{x}\xrightarrow{A^{*}}\mathbf{c}\not\xrightarrow{A^{*}}\mathbf{L}$,
entails that $\mathbf{c}\xrightarrow{A^{*}}\mathbf{c}^{\prime}$ where
$\mathbf{c}^{\prime}\not\xrightarrow{A^{*}}\mathbf{b}$ and
$\mathbf{c}^{\prime}\in\textsc{NDC}$; hence $\mathbf{c}^{\prime}\in\mathbf{W}$
(and thus $\mathbf{x}\xrightarrow{A^{*}}\mathbf{W}$).

We easily note that $\mathbf{W}$ is an effectively constructible semilinear
set.

Now we prove Lemma 4 in general. We have a Petri net $A$ of dimension $d$, and
a linear set $\mathbf{L}$ presented with a basis $\mathbf{b}\in\mathbb{N}^{d}$
and periods
$\mathbf{p}_{1},\mathbf{p}_{2}\dots,\mathbf{p}_{k}\in\mathbb{N}^{d}$. For
$\mathbf{y}\in\mathbb{N}^{d}$ and $\mathbf{u}\in\mathbb{N}^{k}$ we put

$\textsc{conf}(\mathbf{y},\mathbf{u})=\mathbf{y}+\mathbf{u}(1)\cdot\mathbf{p}_{1}+\mathbf{u}(2)\cdot\mathbf{p}_{2}\cdots+\mathbf{u}(k)\cdot\mathbf{p}_{k}$.

Hence

$\mathbf{L}=\\{\textsc{conf}(\mathbf{b},\mathbf{u})\mid\mathbf{u}\in\mathbb{N}^{k}\\}$.

######  Remark 2.

We note that each configuration $\mathbf{x}\in\mathbb{N}^{d}$ is equal to
$\textsc{conf}(\mathbf{y},\mathbf{u})$ for one or more presentation pairs
$(\mathbf{y},\mathbf{u})\in\mathbb{N}^{d}\times\mathbb{N}^{k}$.

Let dcb-pr (determined by the Petri net $A$ and the sequence of periods) be
the set of presentation pairs that present configurations that _can decrease
the token-count in the presentation basis_ :

$\textsc{dcb-
pr}=\\{(\mathbf{y},\mathbf{u})\in\mathbb{N}^{d}\times\mathbb{N}^{k}\mid\exists(\mathbf{y}^{\prime},\mathbf{u}^{\prime}):\|\mathbf{y}\|>\|\mathbf{y}^{\prime}\|,\textsc{conf}(\mathbf{y},\mathbf{u})\xrightarrow{A^{*}}\textsc{conf}(\mathbf{y}^{\prime},\mathbf{u}^{\prime})\\}$.

We note that if $\mathbf{y}\geq\mathbf{p}_{i}$, for some $i$, then we
trivially have $(\mathbf{y},\mathbf{u})\in\textsc{dcb-pr}$ since
$\textsc{conf}(\mathbf{y},\mathbf{u})=\textsc{conf}(\mathbf{y}-\mathbf{p}_{i},\mathbf{u}^{\prime})$
where $\mathbf{u}^{\prime}$ arises from $\mathbf{u}$ by adding $1$ to
$\mathbf{u}(i)$.

_Claim._ dcb-pr is upward closed and the set $\textsc{MIN}(\textsc{dcb-pr})$
is effectively constructible.

(We compare $(\mathbf{y},\mathbf{u})$ and
$(\mathbf{y}^{\prime},\mathbf{u}^{\prime})$ component-wise. It is easy to
verify that dcb-pr is upward-closed. The effective constructibility is again
based on the fact that we can decide, by a reduction to reachability, if a
partial presentation pair $(\mathbf{\bar{y}},\mathbf{\bar{u}})$ has an
instance in dcb-pr.)

We now define the set of configurations that can be presented so that the
presentation basis cannot be decreased:

$\textsc{NDCB}=\\{\mathbf{x}\in\mathbb{N}^{d}\mid\mathbf{x}=\textsc{conf}(\mathbf{y},\mathbf{u})$
for some $(\mathbf{y},\mathbf{u})\not\in\textsc{dcb-pr}\\}$.

_Claim._ NDCB is an effectively constructible semilinear set.

(We recall that dcb-pr is an effectively constructible semilinear set, and
that semilinear sets coincide with the sets definable in Presburger
arithmetic. Then the claim is clear.)

Similarly as NDC, the set NDCB can be easily verified to be a home-space for
any set $\mathbf{X}\subseteq\mathbb{N}^{d}$.

Now we recall the basis $\mathbf{b}$ of $\mathbf{L}$, and consider the
following subset of NDCB:

$\mathbf{W}=\\{\mathbf{x}\in\mathbb{N}^{d}\mid\mathbf{x}=\textsc{conf}(\mathbf{y},\mathbf{u})$
where $(\mathbf{y},\mathbf{u})\not\in\textsc{dcb-pr}$ and

either $\|\mathbf{y}\|>\|\mathbf{b}\|$, or $\|\mathbf{y}\|\leq\|\mathbf{b}\|$
and
$\textsc{conf}(\mathbf{y},\mathbf{u})\not\xrightarrow{A^{*}}\mathbf{L}\\}$.

(We do not claim the effective semilinearity of $\mathbf{W}$ at the moment.)
We recall that $\mathbf{x}\in\mathbf{L}$ iff
$\mathbf{x}=\textsc{conf}(\mathbf{b},\mathbf{u})$ for some
$\mathbf{u}\in\mathbb{N}^{k}$, and we verify that $\mathbf{W}$ is a witness
for $\mathbf{L}$:

  * •

$\mathbf{x}\xrightarrow{A^{*}}\mathbf{c}\in\mathbf{W}$ clearly entails
$\mathbf{c}\not\xrightarrow{A^{*}}\mathbf{L}$;

  * •

$\mathbf{x}\xrightarrow{A^{*}}\mathbf{c}\not\xrightarrow{A^{*}}\mathbf{L}$,
entails that $\mathbf{c}\xrightarrow{A^{*}}\mathbf{c}^{\prime}$ where
$\mathbf{c}^{\prime}\not\xrightarrow{A^{*}}\mathbf{L}$ and
$\mathbf{c}^{\prime}\in\textsc{NDCB}$; hence there is
$(\mathbf{y},\mathbf{u})\not\in\textsc{dcb-pr}$ such that
$\mathbf{c}^{\prime}=\textsc{conf}(\mathbf{y},\mathbf{u})$; hence
$\mathbf{c}^{\prime}\in\mathbf{W}$ (and thus
$\mathbf{x}\xrightarrow{A^{*}}\mathbf{W}$).

We still need to show that $\mathbf{W}$ is an effectively constructible
semilinear set. Though for any concrete $\mathbf{y}$ and $\mathbf{u}$ we can
decide if $\textsc{conf}(\mathbf{y},\mathbf{u})\xrightarrow{A^{*}}\mathbf{L}$,
and there are only finitely many $\mathbf{y}$ to consider (those satisfying
$\|\mathbf{y}\|\leq\|\mathbf{b}\|$), we are not done: it is not immediately
obvious how to express
$\textsc{conf}(\mathbf{y},\mathbf{u})\not\xrightarrow{A^{*}}\mathbf{L}$ in
Presburger arithmetic, even when $\mathbf{y}$ is fixed. To this aim, for any
fixed $\mathbf{y}$ we define the set

$\mathbf{U}_{\mathbf{y}}=\\{\mathbf{u}\in\mathbb{N}^{k}\mid\textsc{conf}(\mathbf{y},\mathbf{u})\xrightarrow{A^{*}}\mathbf{L}\\}=\\{\mathbf{u}\in\mathbb{N}^{k}\mid\exists\mathbf{v}\in\mathbb{N}^{k}:\textsc{conf}(\mathbf{y},\mathbf{u})\xrightarrow{A^{*}}\textsc{conf}(\mathbf{b},\mathbf{v})\\}$.

_Claim._ For each fixed $\mathbf{y}\in\mathbb{N}^{d}$, the set
$\mathbf{U}_{\mathbf{y}}$ is upward closed and the set
$\textsc{MIN}(\mathbf{U}_{\mathbf{y}})$ is effectively constructible. (It is
obvious that $\mathbf{U}_{\mathbf{y}}$ is upward-closed; the effective
constructibility is again based on the fact that we can decide if
$\textsc{conf}(\mathbf{y},\mathbf{\bar{u}})\xrightarrow{A^{*}}\mathbf{L}$
where some components in $\mathbf{\bar{u}}$ might be unspecified; we thus ask
if there is an instance $\mathbf{u}\in\mathbb{N}^{k}$ of $\mathbf{\bar{u}}$
such that
$\textsc{conf}(\mathbf{y},\mathbf{u})\xrightarrow{A^{*}}\mathbf{L}$.)

Hence now it is clear that we can effectively construct a Presburger formula
expressing that $\|\mathbf{y}\|\leq\|\mathbf{b}\|$ and
$\textsc{conf}(\mathbf{y},\mathbf{u})\not\xrightarrow{A^{*}}\mathbf{L}$. Hence
the above $\mathbf{W}$ is an effectively constructible semilinear set. This
finishes a proof of Lemma 4, and thus also of Theorem 1.

## References

  * [1] Eike Best and Javier Esparza.  Existence of home states in petri nets is decidable.  Inf. Process. Lett., 116(6):423–427, 2016.  doi:10.1016/j.ipl.2016.01.011.
  * [2] Wojciech Czerwinski and Lukasz Orlikowski.  Reachability in vector addition systems is ackermann-complete.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1229–1240. IEEE, 2021.  doi:10.1109/FOCS52979.2021.00120.
  * [3] Davide de Frutos Escrig and Colette Johnen.  Decidability of home space property.  Univ. de Paris-Sud, Centre d’Orsay, Laboratoire de Recherche en Informatique LRI-503, July 1989.
  * [4] J. Esparza and M. Nielsen.  Decidability issues for petri nets - a survey.  Bulletin of the European Association for Theoretical Computer Science, 52:245–262, 1994.
  * [5] S. Ginsburg and E. H. Spanier.  Semigroups, Presburger formulas and languages.  Pacific Journal of Mathematics, 16(2):285–296, 1966.  doi:10.2140/pjm.1966.16.285.
  * [6] M. H. T. Hack.  Decidability questions for Petri nets.  PhD thesis, MIT, 1975.  URL: http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-161.pdf.
  * [7] Petr Jancar.  Undecidability of bisimilarity for petri nets and some related problems.  Theor. Comput. Sci., 148(2):281–301, 1995.  doi:10.1016/0304-3975(95)00037-W.
  * [8] J. Leroux and S. Schmitz.  Reachability in vector addition systems is primitive-recursive in fixed dimension.  In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019, pages 1–13. IEEE, 2019.  doi:10.1109/LICS.2019.8785796.
  * [9] Jérôme Leroux.  The reachability problem for petri nets is not primitive recursive.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1241–1252. IEEE, 2021.  doi:10.1109/FOCS52979.2021.00121.
  * [10] E. W. Mayr.  An algorithm for the general petri net reachability problem.  In Proceedings of the 13th Annual ACM Symposium on Theory of Computing, May 11-13, 1981, Milwaukee, Wisconsin, USA, pages 238–246. ACM, 1981.  doi:10.1145/800076.802477.
  * [11] S. Schmitz.  The complexity of reachability in vector addition systems.  SIGLOG News, 3(1):4–21, 2016.  URL: https://dl.acm.org/citation.cfm?id=2893585.
  * [12] Rüdiger Valk and Matthias Jantzen.  The residue of vector sets with applications to decidability problems in petri nets.  In Grzegorz Rozenberg, Hartmann J. Genrich, and Gérard Roucairol, editors, Advances in Petri Nets 1984, European Workshop on Applications and Theory in Petri Nets, covers the last two years which include the workshop 1983 in Toulouse and the workshop 1984 in Aarhus, selected papers, volume 188 of Lecture Notes in Computer Science, pages 234–258. Springer, 1984.  doi:10.1007/3-540-15204-0\\_14.