\section{Introduction}
Model predictive control (MPC) is a popular control strategy that computes control inputs by solving a numerical optimization problem. A mathematical model is used to predict the future behavior of the system and an optimal sequence of  control inputs is computed by solving an optimization problem that minimizes a given objective function subject to constraints. The main reasons for its success are the possibility of handling systematically multiple-input multiple-output systems, nonlinearities as well as constraints.
The main challenge of MPC is that it requires the solution of an optimization problem at each sampling time of the controller. For this reason, traditional applications included those related to slow systems such as chemical processes~\cite{qin2003}, \cite{rawlings2009}. 

During the past two decades, a large research effort has been devoted to broaden the range of MPC applications, leading to various specific MPC algorithms reaching from event-triggered robust control~\cite{liu2018aperiodic} to hierarchical distributed systems ~\cite{hans2019hierarchical}.
To enable the the application of MPC strategies to complex cyber-physical systems \cite{raman2014}, extending the application of MPC to fast embedded systems with limited computing capabilities is an important challenge.
Two different approaches have been followed to achieve this goal.
The first approach included the development of fast solvers and tailored implementations  \cite{mattingley2012cvxgen} that can solve the required optimization problems in real time for fast systems. Different variations of the Nesterov's fast gradient method (see e.g. \cite{richter2012} \cite{giselsson2013}, \cite{koegel2011}) and of the alternating directions method of multipliers (ADMM)  \cite{boyd2011distributed} have been very successful for embedded optimization and model predictive control.  Different versions of these algorithms have been used to obtain MPC implementations on low-cost microcontrollers  \cite{zometa2013}, \cite{lucia2016_ARC} or high-performance FPGAs \cite{jerez2014}, \cite{lucia2018_TII}.

The second approach to extend the application of MPC to fast and embedded systems is usually called explicit MPC. The MPC problem for linear time invariant systems is a parametric quadratic program whose solution is a piecewise affine function defined on polytopes and only depends on the current state of the system \cite{bemporad2002}. Explicit MPC exploits this idea by precomputing and storing the piecewise affine function that completely defines the MPC feedback law. The online evaluation of the explicit MPC law reduces to finding the polytopic region in which the system is currently located and applying the corresponding affine law.
The main drawback of explicit MPC is that the number of regions on which the control law is defined grows exponentially with the prediction horizon and the number of constraints.
The inherent growth of the memory footprint and of the complexity of the point location problem limits the application to small systems and small prediction horizons, especially in the case of embedded systems with limited storage capabilities and computational power.

To counteract the massive memory requirements, some approaches try to simplify the representation of the control law by eliminating redundant regions \cite{geyer2008} or by using different number representations \cite{ingole2017}. Other approaches try to approximate the exact explicit MPC solution to further reduce the memory requirements of the approach (see a review in \cite{alessio2009}). Approximate explicit MPC schemes include the use of simplicial partitions \cite{Bemporad2011}, neural networks \cite{parisini1995}, radial basis functions \cite{cseko2015}, lattice representation \cite{wen2009analytical} or using a smaller number of regions to describe the MPC law \cite{holaza2013}.

To reduce the complexity of the point location problem, binary search trees (BST) \cite{tondel2003evaluation} introduce a tree structure where the nodes represent unique hyperplanes. At each node it is checked on which side of the hyperplane the state is until a leaf node is reached. At the leaf node, a unique feedback law is identified and evaluated.
This method renders the online computation time logarithmic in the number of regions, but precomputation times can be prohibitive or intractable for larger problems \cite{bayat2012flexible}.
Modifications of BST include approximations of the exact solution via hypercubic regions \cite{johansen2003approximate}, truncated BSTs combined with direct search  to restrict the depth of BSTs \cite{bayat2011combining}, computation of arbitrary hyperplanes which balance the tree and minimize its depth \cite{fuchs2010optimized} and merging a BST with the lattice representation \cite{bayat2012flexible}.


Motivated by new advances on the theoretical description of the representation capabilities of deep neural networks \cite{silver2016}, \cite{safran2017}, the goal of this work is to provide a scheme for an approximated explicit MPC controller with significantly lower memory and computational requirements compared to existing approaches.
Deep neural networks (with several hidden layers) can represent exponentially many more linear regions than shallow networks (with only one hidden layer).
This attribute has been exploited in recent works for complex control tasks such as mixed-integer MPC \cite{karg2018} and robust nonlinear MPC \cite{lucia2018deep}.
While many control approaches have used neural networks to capture unknown or nonlinear dynamics of the model~\cite{liu2018neural}, \cite{ding2018neural}, in this work neural networks are used to directly approximate the optimal control law.
This work differs from \cite{chen2018approximating}, which is based on similar ideas, by presenting bounds on the necessary size of a deep network to represent an explicit MPC law exactly, as well as by presenting a comprehensive comparison with other approximate explicit MPC methods and statistical verification techniques.
The main contributions of the paper are:
\begin{itemize}
	\item the derivation of explicit bounds for the required size (width and depth) that a deep network should have to exactly represent a given explicit MPC solution.
	\item the presentation of an approach to approximate explicit MPC based on deep learning which achieves better accuracy with less memory requirements when compared to other approximation techniques.
	\item statistical verification techniques to assess the validity of the obtained approximate controllers.
	\item an embedded implementation of the resulting controllers.
\end{itemize}

The remainder of the paper is organized as follows. Section \ref{sec:background} introduces background information about model predictive control and neural networks. Section \ref{sec:deep} presents explicit bounds for a deep network to be able to represent exactly an MPC law and serves as a motivation for the approximation of explicit MPC laws presented in Section \ref{sec:approximate}, where different techniques to deal with the approximation error are also presented. Section \ref{sec:results} illustrates the potential of the approach with two simulation examples and the paper is concluded in Section \ref{sec:conclusions}.
{"config": "arxiv", "file": "1806.10644/chapters/thueringer_bockwuerste.tex"}