Efficient representation and approximation of model predictive control laws via deep learning

Benjamin Karg; Sergio Lucia

Source-linked AI summary

Efficient representation and approximation of model predictive control laws via deep learning

Benjamin Karg, Sergio Lucia

arXiv:1806.10644v3Jun 27, 2018math.OC

TL;DR

MPC requires repeated optimization, while explicit MPC can become memory-intensive as its exact piecewise-affine representation grows. The paper uses ReLU deep networks to represent or approximate these laws, derives exact-representation size bounds, and evaluates compact controllers with verification and embedded deployment. Simulations report substantially lower memory use with near-exact average settling times.

Problem
MPC deployment on fast embedded systems is challenged by repeated optimization and the memory requirements of exact explicit MPC representations.
Method
The paper uses deep neural networks with ReLU activations to exactly represent or approximate explicit MPC laws, with size bounds and error-verification strategies.
Results
The proposed networks N6,6 and N10,6 use 0.23 % and 1.07 % of the memory of K7 and K10 while their average AST is 1.5 % and 3.8 % longer than the exact solution.
Takeaways & Limitations
The reduced memory footprint enabled deployment of the proposed deep neural network controllers on a low-power embedded device with constrained resources.

Abstract

from arXiv · show

We show that artificial neural networks with rectifier units as activation functions can exactly represent the piecewise affine function that results from the formulation of model predictive control of linear time-invariant systems. The choice of deep neural networks is particularly interesting as they can represent exponentially many more affine regions compared to networks with only one hidden layer. We provide theoretical bounds on the minimum number of hidden layers and neurons per layer that a neural network should have to exactly represent a given model predictive control law. The proposed approach has a strong potential as an approximation method of predictive control laws, leading to better approximation quality and significantly smaller memory requirements than previous approaches, as we illustrate via simulation examples. We also suggest different alternatives to correct or quantify the approximation error. Since the online evaluation of neural networks is extremely simple, the approximated controllers can be deployed on low-power embedded devices with small storage capacity, enabling the implementation of advanced decision-making strategies for complex cyber-physical systems with limited computing capabilities.

I. INTRODUCTION

MPC handles constrained predictive control but repeatedly solves optimization problems, motivating efficient explicit and approximate representations. This work proposes deep neural networks with exact-representation bounds, approximation strategies, verification, and embedded deployment.

MPC computes constrained control inputs by repeatedly solving a numerical optimization problem at each sampling time.
Explicit MPC precomputes a piecewise affine feedback law for linear time-invariant systems, reducing online control to region identification and law evaluation.
Deep networks can represent exponentially more linear regions than shallow networks, motivating their use for compact MPC-law approximation.
The paper derives explicit width and depth bounds for exactly representing an explicit MPC solution with a deep network.
The proposed approach targets better accuracy with less memory, statistical verification, and embedded implementation of approximate controllers.

C. Artificial Neural Networks

The paper models controllers with feed-forward neural networks composed of affine layers and activation functions. It distinguishes deep from shallow networks and uses ReLU activations.

A feed-forward neural network is a layered function mapping the system state x ∈ R^nx to the control output u ∈ R^nu.
Networks with L ≥ 2 hidden layers are called deep, whereas networks with one hidden layer are shallow.
Each hidden layer applies an affine transformation followed by a nonlinear activation function.
The paper uses rectified linear units exclusively as activation functions.
The network parameters comprise the weights and biases of all affine layers, with dimensions determined by input, hidden-layer, and output sizes.

D. Motivation

Exact explicit MPC controllers can require prohibitive storage because their piecewise-affine regions grow rapidly. Deep ReLU networks offer a memory-efficient representation by encoding exponentially many regions with depth.

Explicit MPC implementation may require storing exponentially many regions, hyperplanes, and affine feedback laws.
The paper seeks an efficient MPC-law representation that reduces memory requirements while preserving high-quality approximation.
ReLU networks represent piecewise-affine functions because they compose affine transformations with piecewise-affine activation functions.
The representable number of affine regions grows exponentially with depth when network width M is at least the input dimension n_x.
For fixed memory, deep ReLU networks can represent exponentially more linear regions than shallow networks because parameter growth is only linear in depth.

III. DEEP LEARNING-BASED EXPLICIT MPC

The paper constructs exact deep-ReLU representations of explicit MPC laws by decomposing each scalar piecewise-affine control component into differences of convex functions. The resulting networks have explicit width and depth bounds and avoid online region-location searches.

The construction represents only the first optimal control input, since MPC recomputes a new trajectory after each applied input.
Each scalar explicit MPC control component is written as the difference of two convex piecewise-affine functions.
A convex piecewise-affine function defined as the maximum of N affine functions can be exactly represented by a ReLU network with width M = n_x + 1 and depth N.
Any explicit MPC law on the unit hypercube can be exactly represented by 2n_u deep ReLU networks with width n_x + 1 and constructive depth bounds.
General explicit MPC laws can use invertible affine state and input transformations before applying the exact transformed-law representation.
Neural-network evaluation avoids explicit region identification and consists of affine functions and simple nonlinearities, supporting embedded implementation.
For the oscillator example, two width-3, depth-3 networks reproduce the five-region explicit MPC law, with maximal error below 0.001 treated as exact.

IV. APPROXIMATE EXPLICIT MPC BASED ON DEEP

The paper emphasizes deep networks as efficient approximators of explicit MPC laws rather than only exact representers. It proposes feasibility recovery and statistical verification to manage approximation error, while noting that deterministic stability guarantees are challenging.

Deep networks are presented as a promising way to obtain efficient approximations of explicit MPC laws.
The proposed approximation strategies include feasibility recovery using control invariant sets and statistical verification for computing safe sets.
Deterministic stability guarantees are challenging for neural-network approximations because the learning procedure is stochastic.

A. Training of the deep learning-based approach

The approximate controller is trained on MPC-generated state-input samples and then paired with feasibility-recovery or verification procedures. Projection onto a control-invariant set can enforce constraints and recursive feasibility when feasible.

Training data are generated by repeatedly solving the MPC problem in closed loop and recording each applied first-step input.
Exact explicit MPC laws can be decomposed into convex components and represented through transformed deep networks, as illustrated by the plotted controller decomposition.
A deep network with chosen width M ≥ n_x and depth L is trained by minimizing mean squared error over the generated samples.
The trained network is used within feasibility-recovery or verification strategies to control approximation error.
Projection onto a convex set is used to recover feasibility by satisfying input constraints and keeping the next state inside a control-invariant set.
When the projection problem is feasible, recursive feasibility and closed-loop input and state constraint satisfaction are ensured.
With only box input constraints, feasibility recovery reduces to saturation; state constraints require computing a control-invariant set.

C. Statistical verification

The verification procedure uses independent closed-loop trajectory data to construct and assess safe sets for approximate controllers. It evaluates trajectory requirements, separates valid and invalid data, and defines safe sets as initial conditions with controlled constraint-violation risk.

The feasibility-recovery approach can require an additional optimization problem in the control loop and extensive simulator testing when the plant model is inaccurate.The computed control invariant set may be invalid for the real system when the design model is only an approximation.
A data-driven procedure enables a-posteriori statistical verification of closed-loop performance from sampled trajectories.
The procedure comprises data generation, safe-set computation, and safe-set validation.
Verification datasets are independent of neural-network training data and include sets for safe-set computation, controller comparison, and validation.
Trajectory requirements classify datasets into valid and invalid subsets, with each subset retaining the corresponding trajectories’ initial conditions.

2) Safe sets:

Safe sets are estimated from closed-loop data containing valid and invalid initial conditions using either a conservative ellipsoid or a less restrictive SVM classifier. These methods trade safe-set size against the risk of false positives.

The ellipsoidal safe set is computed by convex optimization to inscribe a maximum-sized hypercube while excluding invalid initial conditions.Its boundary is parameterized by x^T E x = 1, with E symmetric.
ϵ ≥ 0 tunes robustness of the ellipsoidal construction against the finite number of invalid samples.
The ellipsoidal validation condition x^T E x > 1 for every invalid validation point is equivalent to having no false positives in that set.
The SVM approach derives a less restrictive safe set by weighting classification errors through a penalty parameter and slack variables.The resulting set is defined by decision functions associated with support vectors.
The ellipsoidal set is more conservative, whereas the larger SVM set trades safe-set size against susceptibility to misclassification.False positives are especially consequential because they may lead to actual closed-loop constraint violations.
Safe-set conservativeness is assessed by comparing the computed set’s volume with the exact controller’s safe-set volume using test initial conditions.

3) Validation:

Validation estimates false-positive rates and uses statistical learning theory to make confidence-based statements about closed-loop constraint satisfaction. The paper also compares neural-network approximations with polynomial and reduced-horizon explicit MPC alternatives.

3) Validation:: Approximation quality is assessed using false-positive rates and statistical learning theory applied to safe-set validation data.
3) Validation:: The validation strategy directly evaluates approximate closed-loop performance and remains applicable when the controller-design model is potentially incorrect.
3) Validation:: The resulting statement is that trajectories starting inside the safe set satisfy constraints with probability at least 1 − (remp − δ).The passage expresses this equivalently as a constraint-violation probability no greater than remp − δ.
D. Alternative approximation methods: The deep-learning approximation is compared with multivariate polynomials and optimized explicit MPC using a reduced horizon.

V. SIMULATION RESULTS

Simulation studies compare neural networks, polynomial approximations, and reduced-horizon explicit MPC against exact explicit MPC on control performance and memory footprint. The experiments include a spring-connected mass chain and an inverted pendulum.

The simulations steer both a spring-connected mass system and an inverted pendulum on a cart toward the origin.
Approximation methods are compared with exact explicit MPC using performance and memory-footprint measures.
Average settling time measures the time needed to bring all states to the origin, with |x_i| ≤ 1 × 10^-2 defining arrival.
Relative AST is measured against the exact explicit solution with the longest horizon N_max.
The study examines shallow networks with L = 1 and deep networks with L ≥ 2, while the deepest tested network has no more than L = 10 layers.The authors note that very deep networks can encounter vanishing gradients during training, although this was not necessary to mitigate in their experiments.

A. Case-studies

The case studies evaluate approximate controllers on oscillating masses and an inverted pendulum, comparing deep and shallow neural networks with exact explicit MPC and other approximations. Deep networks achieve near-exact closed-loop behavior with substantially lower memory requirements.

Case-study setup: The study evaluates oscillating masses and an inverted pendulum on a cart using trajectories from exact explicit MPC solutions to train approximation methods.Both tasks are simulated from multiple initial conditions, with input saturation used to enforce box constraints.
Oscillating masses: The oscillating-masses benchmark uses horizon Nmax = 7, 2317 regions, and 25952 training samples.
Inverted pendulum: The inverted-pendulum benchmark uses horizon Nmax = 10, 1638 polyhedral regions, and 88341 training samples.
Performance: 0.23 % and 1.07 % of the exact controllers’ memory yields average settling times only 1.5 % and 3.8 % longer for deep networks N6,6 and N10,6.The comparison covers the oscillating-masses and inverted-pendulum examples, respectively.
Performance: The proposed deep network performs slightly better than the finest optimized explicit-MPC partition for oscillating masses and clearly better for the inverted pendulum, with a much smaller memory footprint.
Performance: Deep networks N6,6 and N10,6 produce trajectories almost identical to exact controllers K7 and K10, while degree-3 polynomial approximations perform poorly.

C. Statistical verification

Statistical verification constructs safe sets for approximate controllers and evaluates their coverage, false-positive rates, and probabilistic constraint-satisfaction guarantees. The approach supports deployment on constrained embedded hardware, while future work remains for stronger stability and violation predictions.

Verification method: Safe sets are validated using generated data, safe-set computation, and validation, with the sets defined as initial conditions having controlled risk of state and input constraint violations.
Direct safe sets: 97.7 % for OM and 95.1 % for IP are the direct safe-set cardinality ratios relative to the corresponding reference sets.
Ellipsoidal safe sets: Ellipsoidal safe sets cover 70.5 % for OM and 53.3 % for IP, with no false positives and confidence above 99.9 % for constraint satisfaction probability at least 97.0 %.
SVM safe sets: SVM safe sets cover 98.3 % for OM and 83.1 % for IP while classifying less than 2 % of validation points as false positives.
SVM safe sets: The resulting safety is 96.9 % for OM and 95.1 % for IP with confidence above 99.9 % for the SVM safe sets.
Embedded deployment: Deep neural network controllers were deployed on a 32-bit SAMD21 microcontroller, and their reduced memory footprint enabled embedded deployment on constrained devices.For N6,6, evaluation took 1.6 ms and required 23.2 kB of code memory.