Safe and Efficient Model Predictive Control Using Neural Networks: An Interior Point Approach

Model predictive control (MPC) [1] is a powerful technique for controlling systems that are subject to state and input constraints, such as agricultural [2], automotive [3], and energy systems [4]. However, many applications require fast decision-making which may preclude the possibility of repeatedly solving an optimization problem online [5].

A popular approach for accelerating MPC is to move as much computation offline as possible [5, 6]. These techniques, known as explicit MPC, involve precomputing the solution to the MPC problem over a range of parameters or initial conditions. Most of the research effort has focused on problems with linear dynamics and constraints, and linear or quadratic cost functions. In this case, the explicit MPC solution is a piecewise affine (PWA) function defined over a polyhedral partition of the state constraints. However, many of the applications of interest have cost functions that are not necessarily linear or quadratic, or even convex. Further, the memory required to store the partition and affine functions can be prohibitive even for modestly-sized problems.

In order to reduce the complexity of explicit MPC, the optimal offline solution can be approximated. Approximations generally fall into two categories: partition-based solutions [7, 8, 9] that generate piecewise control laws over coarser state space partitions, and learning-based solutions [10, 11, 12, 13] that use function approximation to compactly represent the optimal MPC policy. In this paper, we focus on the latter with the key contribution of ensuring constraint satisfaction while exploring all feasible policies.

Constraint satisfaction is crucial in many engineering applications, and the ability of MPC to enforce constraints is a major factor in its popularity. However, it is not straightforward to guarantee that a learning-based solution will satisfy constraints. The main challenge arises from the fact that while neural networks can limit their outputs to be in simple regions, there is no obvious way of forcing complex constraint satisfaction at the output. In [10, 14], supervised and unsupervised learning were used to approximate the solution of MPCs, but did not provide any feasibility guarantees. By contrast, [11] trains an NN using a policy gradient approach, and guarantees feasibility by projecting the NN output into the feasible action set. However, this extra optimization step slows down the speed of online implementation, making it difficult to use in applications that require high-frequency solutions [15]. Supervised learning approaches that provide safety guarantees [13, 12] rely on a choice of MPC oracle that is not obvious when persistent disturbances are present.

In this paper, we propose an NN architecture for approximating explicit solutions to finite-horizon MPC problems with linear dynamics, linear constraints, and arbitrary differentiable cost functions. The proposed architecture guarantees constraint satisfaction without relying on projections or MPC oracles. By exploring the interior of the feasible set, we demonstrate faster training and evaluation, and comparable closed-loop performance relative to other NN architectures.

The proposed approach has parallels in interior point methods for convex optimization [16]. Interior point methods first solve a Phase I problem to find a strictly feasible starting point. This solution is used to initialize the Phase II algorithm for optimizing the original problem. Our approach accelerates both phases. The Phase I solution is given by a simple function (e.g., affine map) and the Phase II problem is solved using an NN architecture that can encode arbitrary polytopic constraints (Fig. 1).

The Phase II solution builds on a technique first proposed in [17], which uses a gauge map to establish equivalence between compact, convex sets. With respect to [17], the current work has three novel aspects. First, the reinforcement learning (RL) algorithm in [17] only uses information about the constraints, and does not use information about the cost function or dynamics. The resulting policy is safe, but can exhibit suboptimal performance. The MPC formulation in the current paper gives rise to a training algorithm that can exploit knowledge about the system, improving performance. Second, the MPC formulation permits explicit consideration for future time steps. The RL formulation cannot optimize entire trajectories due to the presence of constraints. This inability to “look ahead” again limits the performance of the RL algorithm. Finally, the previous work required a Phase I that used a linear feedback to find a strictly feasible point. A linear feedback, however, may not exist for some problems. The current work proposes a more general class of Phase I solutions (piecewise affine), while providing a way to manage the complexity of the Phase I solution.

We demonstrate the effectiveness of the proposed technique on a 3-state test system, and compare to standard projection- and penalty-based approaches for learning with constraints. The results show that the proposed technique achieves Pareto efficiency in terms of closed-loop performance and online computation effort. All code is available at github.com/dtabas/gauge_networks.

Notation: The $p$-norm ball for $p\geq 1$ is $\mathbb{B}_{p}=\{z\mid\|z\|_{p}\leq 1\}$. A polytope $\mathcal{P}\subset\mathbb{R}^{n}:=\{z\in\mathbb{R}^{n}\mid Fz\leq g\}$ is the (bounded) intersection of a finite number of halfspaces. Scaling of polytopes by a factor $\lambda>0$ is defined as $\lambda\mathcal{P}=\{\lambda z\in\mathbb{R}^{n}\mid Fz\leq g\}=\{z\in\mathbb{R}^{n}\mid Fz\leq\lambda g\}$. Given a matrix $F$ and a vector $g$, the $i$th row of $F$ is denoted $F^{(i)T}$ and the $i$th component of $g$ is $g^{(i)}$. The interior of any set $\mathcal{Q}$ is denoted $\textbf{int }\mathcal{Q}$. The value of a variable $y$ at a time interval $t$ is denoted $y_{t}$. A state or control trajectory of length $\tau$ is written as the vector $\textbf{x}=\begin{bmatrix}x_{1}^{T},\ldots,x_{\tau}^{T}\end{bmatrix}^{T}\in\mathbb{R}^{n\tau}$ or $\textbf{u}=\begin{bmatrix}u_{0}^{T},\ldots,u_{\tau-1}^{T}\end{bmatrix}^{T}\in\mathbb{R}^{m\tau}$. The column vector of all ones is 1. The symbol $\circ$ denotes function composition.

In this paper, we consider the problem of regulating discrete-time dynamical systems of the form

$\displaystyle x_{t+1}=Ax_{t}+Bu_{t}+d_{t}$

(1)

where $x_{t}\in\mathbb{R}^{n}$ is the system state at time $t$, $u_{t}\in\mathbb{R}^{m}$ is the control input, and $d_{t}\in\mathbb{R}^{n}$ is an uncertain input that captures exogenous disturbances and/or linearization error (if the true system dynamics are nonlinear) [18]. We assume the pair $(A,B)$ is stabilizable. The input constraints (actuation limits) are $\mathcal{U}=\{u\in\mathbb{R}^{m}\mid F_{u}u\leq g_{u}\}$ while the state constraints arising from safety-critical engineering considerations are $\mathcal{X}=\{x\in\mathbb{R}^{n}\mid F_{x}x\leq g_{x}\}$.

We consider the problem of operating the system (1) using finite-horizon model predictive control. The goal is to choose, given initial condition $x_{0}\in\mathcal{X}$, a sequence of inputs u of length $\tau$ that minimizes the cost of operating the system while respecting the operational constraints.

However, since the disturbances $d_{t}$ are unknown ahead of time, the designer must carefully consider how to achieve both optimality and constraint satisfaction. Robust MPC literature contains many ways to handle the presence of disturbances in both the cost and constraints [19]. For example, the certainty-equivalent approach [5] considers only the nominal system trajectory, while the min-max approach [9] considers the worst-case disturbance. Interpolating between these two extremes, the tube-based approach [20] considers the cost of a nominal trajectory while guaranteeing that the true trajectory satisfies constraints. A stochastic point of view in [21] considers the disturbance as a random variable and minimizes the expected cost while providing probabilistic guarantees for constraint satisfaction.

In most robust MPC formulations, the set of possible disturbances is modeled as either a finite set, a bounded set, or a probability distribution [22]. In this paper, we assume the disturbances lie in a closed and bounded set $\mathcal{D}:=\{d\in\mathbb{R}^{n}\mid F_{d}d\leq g_{d}\}$. In order to ensure constraint satisfaction, we operate the system within a robust control invariant set (RCI) $\mathcal{S}\subseteq\mathcal{X}$, defined as a set of initial conditions for which there exists a feedback policy in $\mathcal{U}$ keeping all system trajectories in $\mathcal{S}$, under any disturbance sequence in $\mathcal{D}$ [23]. In our simulations, we used approximately-maximal RCIs computed with the semidefinite program from [24].

With $\mathcal{S}:=\{x\in\mathbb{R}^{n}\mid F_{s}x\leq g_{s}\}$, we define the target set $\mathcal{T}$ as $\{x\in\mathbb{R}^{n}\mid x+d\in\mathcal{S},\ \forall\ d\in\mathcal{D}\}=\{x\in\mathbb{R}^{n}\mid F_{s}x\leq\tilde{g}_{s}\}$ where for each row $i$, $\tilde{g}_{s}^{(i)}=g_{s}^{(i)}-\max_{d\in\mathcal{D}}F_{s}^{(i)T}d$ [23]. Any policy that maps $\mathcal{S}$ to $\mathcal{T}$ under the nominal dynamics will map $\mathcal{S}$ to itself under the true dynamics, rendering $\mathcal{S}$ robustly invariant. By constraining the nominal state to the target set, robust constraint satisfaction is guaranteed for the first time step. Since $\mathcal{S}$ is RCI, this is sufficient for keeping closed-loop trajectories inside $\mathcal{S}$. Under this formulation, the MPC problem is posed as follows, given initial state $x_{0}$:

	$$\displaystyle\min_{\textbf{u}}\sum_{k=0}^{\tau-1}l(x_{k},u_{k})+l_{F}(x_{\tau})$$		(2a)
	$$\displaystyle\text{subject to $\forall\ k$: }x_{k+1}=Ax_{k}+Bu_{k}$$		(2b)
	$$\displaystyle x_{k+1}\in\mathcal{T}$$		(2c)
	$$\displaystyle u_{k}\in\mathcal{U}$$		(2d)

where $l$ and $l_{F}$ are stage and terminal costs that are differentiable but possibly nonlinear or even non-convex. Although (2) differs from the standard tube-based approach, the techniques introduced in this paper can be applied to a variety of MPC formulations.

In this paper, we seek to derive a safe feedback policy $\pi_{\theta}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ that approximates the explicit solution to (2) by first approximating the optimal control sequence with a function $\mu_{\theta}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m\tau}$ and then implementing the first action of the sequence in the closed loop. In practice, any MPC policy implemented in closed loop must be stabilizing and recursively feasible. Recursive feasibility is the property that closed-loop trajectories generated by the MPC controller will not lead to states in which the MPC problem is infeasible. This property is guaranteed when $\mathcal{S}$ is RCI [23]. If recursive feasibility is not guaranteed, then a backup controller must be developed or a control sequence that is feasible for the most immediate time steps can be used. There is suggestion in the literature that the latter approach performs quite well in practice [25], but the theoretical aspects remain open. In terms of stability, recursive feasibility guarantees that trajectories will remain within a bounded set. Since this work focuses on constraint satisfaction, we do not consider stricter notions of stability.

The feasible set of (2) is a polytope $\mathcal{F}(x_{0})\subseteq\mathbb{R}^{m\tau}$, defined by the following inequalities in u:

	$\displaystyle H_{s}(M_{0}x_{0}+M_{u}\textbf{u})$	$\displaystyle\leq\tilde{h}_{s},$		(3a)
	$\displaystyle H_{u}\textbf{u}$	$\displaystyle\leq h_{u}$		(3b)

where $H_{s},H_{u},M_{0},M_{u},\tilde{h}_{s},$ and $h_{u}$ are block matrices and vectors derived from the system dynamics and constraints. In this paper, we assume that $\mathcal{F}(x_{0})$ has nonempty interior for all $x_{0}\in\mathcal{S}$. Since the state constraints $\mathcal{S}$ form an RCI, $\mathcal{F}(x_{0})$ is already guaranteed to be nonempty, and the assumption of nonempty interior is only marginally more restrictive.

The gauge map technique introduced in [17] provides a way to constrain the outputs of a neural network $\mu_{\theta}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m\tau}$ to $\mathcal{F}(x_{0})$ without a projection or penalty function, but $\mathcal{F}(x_{0})$ must contain the origin in its interior. If this is not the case, then we must temporarily “shift” $\mathcal{F}(x_{0})$ by subtracting any one of its interior points. In this section, we discuss several ways to reduce the complexity of finding an interior point.

We begin by considering the feasibility problem for the one-step safe action set defined as $\mathcal{V}(x_{0})=\{u\in\mathbb{R}^{m}\mid u\in\mathcal{U},Ax_{0}+Bu\in\mathcal{T}\},$ which is guaranteed to have an interior point by the assumption on $\mathcal{F}(x_{0}).$ One way to find an interior point of $\mathcal{V}(x_{0})$ is to minimize the maximum constraint violation:

	$$\displaystyle\min_{u,s}s$$		(4a)
	$$\displaystyle\text{subject to: }F_{s}(Ax_{0}+Bu)\leq\tilde{g}_{s}+s\textbf{1}$$		(4b)
	$$\displaystyle F_{u}u\leq g_{u}+s\textbf{1}$$		(4c)

which has an optimal cost $s^{*}\leq 0$ if $\mathcal{V}(x_{0})$ is nonempty, and $s^{*}<0$ if $\mathcal{V}(x_{0})$ has nonempty interior [16]. To avoid solving a linear program online during closed-loop implementation, the solution to (4) can be stored as a piecewise affine (PWA) function $\pi_{0}(x_{0}):\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ [7]. Although solutions to multiparametric LPs can be demanding on computer memory, we take advantage of the fact that feasibility problems have low accuracy requirements: any suboptimal solution to (4) that achieves a cost $s<0$ for all $x_{0}\in\mathcal{S}$ is acceptable.

Existing techniques for approximate multiparametric linear programming [26], especially those that generate continuous solutions [27], can be used to reduce the memory requirements of offline solutions to (4).

To show just how far one can go with reducing complexity, we will construct an affine (rather than PWA) function that solves (4), for the system studied in Section V. Let $\pi_{0}(x_{0})=Wx_{0}+w$. If $W\in\mathbb{R}^{m\times n}$ and $w\in\mathbb{R}^{m}$ satisfy

	$\displaystyle F_{x}(Ax_{0}+B(Wx_{0}+w))$	$\displaystyle<\tilde{g}_{x}$		(5a)
	$\displaystyle F_{u}(Wx_{0}+w)$	$\displaystyle<g_{u}$		(5b)

for all $x_{0}\in\mathcal{S}$, then $\pi_{0}(x_{0})=Wx_{0}+w$ solves (4). The following optimization problem can be solved to find $W$ and $w$ or certify that none exists. Let $\mathcal{Y}(s)=\{x_{0}\in\mathbb{R}^{n}\mid F_{s}(Ax_{0}+B(Wx_{0}+w))\leq\tilde{g}_{s}+s\textbf{1},F_{u}(Wx_{0}+w)\leq g_{u}+s\textbf{1}\}.$ If the optimal cost of

$$\displaystyle\min_{W,w,s}s\text{ subject to }{\color[rgb]{0,0,0}\mathcal{S}}\subseteq\mathcal{Y}(s)$$

(6)

is negative, then (5) holds for all $x_{0}\in\mathcal{S}$, thus $\pi_{0}$ solves (4). This happens to be the case for the example in Section V, taken from [6]. The constraint in (6) is a polytope containment constraint in halfspace representation, thus (6) can be solved as a linear program [28].

Now consider the feasibility problem for $\mathcal{F}(x_{0})$, which is obtained by replacing (4b) and (4c) with (3a) and (3b), and changing the optimization variable from $u\in\mathbb{R}^{m}$ to $\textbf{u}\in\mathbb{R}^{m\tau}$. One would naturally expect the complexity of the PWA solution to this feasibility problem to increase rapidly with the time horizon $\tau$, as more decision variables and constraints are added. However, the next proposition shows that the cardinality of the stored partition can be made constant in $\tau$.

In our simulations on the example from [6], $\eqref{eqn:3-17-4}$ was feasible with negative optimal cost, meaning that a polyhedral partition of the state space was not needed (see Section V). This indicates that the minimum number of regions in a polyhedral state space partition associated with a PWA solution to (4) is in general very small relative to the number of regions in an explicit solution to (2).

In this section, we construct a class of policies from $x_{0}\in\mathcal{S}$ to $\mathcal{F}(x_{0})$, that can be trained using standard machine learning packages. Although it is difficult to constrain the output of a neural network to an arbitrary polytope such as $\mathcal{F}(x_{0})$, it is easy to constrain the output to the hypercube $\mathbb{B}_{\infty}$ by applying a clamping function elementwise in the output layer. We apply a mapping between polytopes that is closed-form, differentiable, and bijective. This mapping establishes an equivalence between $\mathbb{B}_{\infty}$ and $\mathcal{F}(x_{0})$, allowing one to constrain the outputs of the policy to $\mathcal{F}(x_{0})$. The mapping from $\mathbb{B}_{\infty}$ to $\mathcal{F}(x_{0})$ is called the gauge map. The concept is illustrated in Figure 2.

We begin constructing the gauge map by introducing some preliminary concepts. A C-set is a convex, compact set that contains the origin as an interior point. The gauge function with respect to C-set $\mathcal{P}\subset\mathbb{R}^{n}$, denoted $\gamma_{\mathcal{P}}:\mathbb{R}^{n}\rightarrow\mathbb{R}_{+}$, is the function whose sublevel sets are scaled versions of $\mathcal{P}$. Specifically, the gauge of a vector $v$ with respect to $\mathcal{P}$ is given by $\gamma_{\mathcal{P}}(v)=\inf\{\lambda\geq 0\mid v\in\lambda\mathcal{P}\}.$ If $\mathcal{P}$ is a polytopic C-set given by $\{v\in\mathbb{R}^{k}\mid Fv\leq g\}$, then $\gamma_{\mathcal{P}}$ is the pointwise maximum over a finite set of affine functions [17]:

$\displaystyle\gamma_{\mathcal{P}}(v)=\max_{i}\frac{F^{(i)T}v}{g^{(i)}}.$

(7)

Given two C-sets $\mathcal{P}$ and $\mathcal{Q}$, the gauge map $G:\mathcal{P}\rightarrow\mathcal{Q}$ is

$\displaystyle G(v\mid\mathcal{P},\mathcal{Q})=\frac{\gamma_{\mathcal{P}}(v)}{\gamma_{\mathcal{Q}}(v)}\cdot v.$

(8)

This function maps level sets of $\gamma_{\mathcal{P}}$ to level sets of $\gamma_{\mathcal{Q}}$.

We now use the gauge map in conjunction with the Phase I solution to construct a neural network whose output is confined to $\mathcal{F}(x_{0}).$ Let $\psi_{\theta}:\mathcal{S}\rightarrow\mathbb{B}_{\infty}$ be a neural network parameterized by $\theta$. A safe policy is constructed by composing the gauge map $G:\mathbb{B}_{\infty}\rightarrow\tilde{\mathcal{F}}(x_{0})$ with $\psi_{\theta}$, then adding $\mu_{0}(x_{0})$ to map the solution into $\mathcal{F}(x_{0})$:

$\displaystyle\mu_{\theta}(x_{0})=G(\cdot\mid\mathbb{B}_{\infty},\tilde{\mathcal{F}}(x_{0}))\circ\psi_{\theta}(x_{0})+\mu_{0}(x_{0}).$

(9)

Computing the gauge map online simply requires evaluating $H_{s}M_{0}x_{0}$ from (3a) as well as the operations in (7).

The function $\mu_{\theta}$ has several important properties for approximating the optimal solution to (2). First, it leverages the universal function approximation properties of neural networks [29] along with the bijectivity of the gauge map (Proposition 2) to explore all interior points of $\mathcal{F}(x_{0}).$ This is an advantage over projection-based methods [11] which may be biased towards the boundary of $\mathcal{F}(x_{0})$ when the optimal solution may lie on the interior. Second, $\mu_{\theta}$ is evaluated in closed form, and its outputs are constrained to $\mathcal{F}(x_{0})$ without the use of an optimization layer [14] that may have high computational overhead. Finally, the subdifferentiability of the gauge map (Proposition 2) enables selection of parameter $\theta$ using standard automatic differentiation techniques.

In this paper, we provided an efficient way of exploring the interior of the MPC feasible set for learning-based approximate explicit MPC, and demonstrated the performance and computational gains that can be achieved by approaching the problem from the interior. The paradigm relies on a Phase I solution that exploits the structure of the MPC problem and a Phase II solution that features a projection-free feasibility guarantee. The results compare favorably against common approaches that use unsupervised learning, as well as against the oracle itself used in supervised approaches. Future work includes applications to MPC problems with convex but non-polytopic constraint sets, and to distributed settings.