Robust adaptive NMPC using ellipsoidal tubes

This paper proposes a computationally efficient, robust adaptive nonlinear model predictive control algorithm that utilizes ellipsoidal tubes to guarantee constraint satisfaction and stability for learning-based systems with unknown parameters and set-bounded disturbances.

The Gist

Imagine you are driving a car on a foggy, winding road. You want to get to your destination as fast as possible, but you have two major problems:

1. You don't know the car perfectly: The engine might be slightly weaker than you thought, or the tires might be wearing down faster than expected.
2. The road is slippery: Sometimes a gust of wind or a patch of ice (disturbances) pushes you off course.

If you just drive based on your best guess, you might hit a tree or slide off the road. Model Predictive Control (MPC) is like a super-smart co-pilot who constantly looks ahead, simulates the next few seconds of driving, and adjusts the steering wheel to keep you safe.

This paper introduces a new, super-efficient version of this co-pilot called Robust Adaptive NMPC with Ellipsoidal Tubes. Here is how it works, broken down into simple concepts:

1. The "Guessing Game" (Adaptive Learning)

Usually, a co-pilot assumes the car's manual is 100% correct. But in the real world, manuals are often wrong.

• The Old Way: The co-pilot guesses the car's behavior, drives, and if it gets close to a wall, it panics and slows down way too much (being overly conservative).
• The New Way: This algorithm is a learning student. As you drive, it watches how the car actually reacts. If the car turns slightly slower than expected, the co-pilot updates its mental map of the car in real-time. It narrows down the list of "what the car might be" until it knows the car very well.

2. The "Safety Bubble" (Ellipsoidal Tubes)

Even with a learning student, you can't be 100% sure of the future. You need a safety buffer.

• The Polytope Problem: Imagine drawing a safety box around your car. If the box is a square or a complex shape with many corners (a polytope), it's very hard for a computer to calculate if you will hit a wall inside that box, especially if the road is curvy. It's like trying to fit a square peg in a round hole; the math gets messy and slow.
• The Ellipsoidal Solution: Instead of a box, imagine a smooth, stretchy balloon (an ellipsoid) surrounding your car's possible path.
  • Why it's better: Mathematically, balloons are much easier to handle than boxes. They stretch and shrink smoothly. This allows the computer to calculate the safest path much faster, even as the car gets more complex (more wheels, more sensors, more unknowns).

3. The "Stretchy Tube" (The Tube Concept)

The algorithm doesn't just plan one single line for the car to follow. It plans a tube of possible paths.

• Think of the car driving through a tunnel. The center of the tunnel is the "nominal path" (the best guess). The walls of the tunnel are the "tube."
• The "Ellipsoidal Tube" ensures that no matter how the wind blows or how the engine sputters, the car will always stay inside the tunnel.
• The magic here is that the tunnel is made of these smooth, stretchy balloons stacked together. This makes the math "convex" (smooth and bowl-shaped), meaning the computer can find the best solution quickly without getting stuck in local traps.

4. The "Backtracking" Safety Net

Sometimes, the computer tries to calculate a new path and realizes, "Wait, this path is impossible! I can't solve this equation right now."

• In older systems, this might cause the car to freeze or crash.
• In this new system, there is a Backtracking Line Search. Imagine you are walking up a hill and realize the path ahead is blocked. Instead of stopping, you take a step back, try a slightly different angle, and keep moving. The algorithm does this instantly: if a perfect solution isn't found, it takes a "safe step" based on the previous good solution, ensuring the car never stops or crashes, even if the computer is having a bad day.

5. Why This Matters (The "So What?")

The authors tested this on computers with different sizes of "cars" (systems with many variables).

• The Result: As the car gets more complex (more wheels, more sensors), the old "box" methods (polytopic tubes) get incredibly slow, like trying to solve a Rubik's cube with a million pieces.
• The Winner: The "balloon" method (ellipsoidal tubes) scales beautifully. It stays fast and efficient even when the problem gets huge.

Summary Analogy

Think of driving a self-driving car through a storm:

• The Car: Has a slightly broken engine (unknown parameters).
• The Storm: Pushes the car around (disturbances).
• The Old Co-pilot: Draws a rigid, square safety box. It's safe, but the computer spends all its time calculating the corners of the box, so the car drives slowly and hesitantly.
• The New Co-pilot (This Paper): Draws a smooth, stretchy balloon around the car. It learns the engine's quirks as it drives. If the math gets too hard, it takes a safe step back and tries again. It keeps the car moving fast and safely, even as the car gets more complicated and the storm gets worse.

In short: This paper gives us a smarter, faster, and safer way for robots and cars to learn on the fly while guaranteeing they never hit a wall, using "smooth balloons" instead of "rigid boxes" to do the math.

Technical Summary

Here is a detailed technical summary of the paper "Robust adaptive NMPC using ellipsoidal tubes" by Johannes Buerger and Mark Cannon.

1. Problem Statement

The paper addresses the challenge of controlling nonlinear systems subject to:

• Parametric Uncertainty: Unknown parameters $\theta$ in the system model.
• Additive Disturbances: Bounded external disturbances $w$.
• Constraints: Hard constraints on states ($x$) and control inputs ($u$).

The goal is to design a Robust Adaptive Nonlinear Model Predictive Control (NMPC) algorithm that:

1. Ensures recursive feasibility (the optimization problem remains solvable at every time step).
2. Guarantees robust constraint satisfaction despite uncertainties.
3. Provides Input-to-State Practical Stability (ISpS).
4. Is computationally efficient and scales favorably with system dimensions, avoiding the exponential complexity often found in polytopic tube methods.

The system model is assumed to be an affine combination of known basis functions with unknown parameters:
$$x_{t+1} = f_0(x_t, u_t) + \sum_{i=1}^{n_\theta} \theta_i f_i(x_t, u_t) + w_t$$

2. Methodology

The proposed approach combines Sequential Convex Programming (SCP), Ellipsoidal Tube MPC, and Set Membership Estimation (SME).

A. Linearization and Error Bounding

The algorithm linearizes the nonlinear dynamics around a nominal trajectory $(x^0, v^0)$. It decomposes the state perturbation $s_k$ into a nominal component $z_k$ and an uncertain error component $e_k$.

• Linearization Errors: The paper derives rigorous bounds for two types of errors:
  • $\delta^0_k$: Error due to parameter uncertainty (polytopic bound).
  • $\delta^1_k$: Error due to linearization (Taylor expansion remainder).
• Ellipsoidal Tubes: Instead of using polytopic sets (which can grow exponentially in complexity with dimension), the uncertain error $e_k$ is bounded by an ellipsoidal set $E(V, \beta_k^2) = \{e : e^\top V e \leq \beta_k^2\}$.
• Tube Propagation: The evolution of the ellipsoidal scaling factor $\beta_k$ is governed by a recursive inequality involving the system Jacobians and the bounds of the disturbances and linearization errors.

B. Online Optimization (SOCP)

The control problem is formulated as a Second-Order Cone Program (SOCP).

• Objective: Minimize an upper bound on the quadratic cost over the ellipsoidal tube.
• Constraints:
  • Nominal dynamics evolution.
  • Ellipsoidal tube propagation constraints (ensuring the tube contains all possible trajectories).
  • State and input constraints (ensuring the tube remains within feasible sets).
  • Backtracking Line Search: To guarantee recursive feasibility even if the solver fails to converge or the linearization is poor, the algorithm employs a backtracking line search. If the optimization is infeasible, it scales the previous solution and re-attempts, ensuring a feasible solution always exists.

C. Terminal Conditions and Stability

To guarantee stability, the authors derive specific terminal sets and costs:

• Linear Difference Inclusion (LDI): A local linear approximation of the system dynamics is used to define a terminal region where a linear feedback law $u = Kx$ is stabilizing.
• LMI Design: A Linear Matrix Inequality (LMI) is solved offline (or online) to compute the feedback gain $K$, the ellipsoidal shape matrix $V$, and the disturbance bound $\sigma$.
• ISpS: The terminal cost is designed to ensure the closed-loop system is Input-to-State Practically Stable, meaning the state converges to a bounded neighborhood of the origin.

D. Online Learning

The algorithm integrates Set Membership Estimation (SME). At each step, the set of possible parameters $\Theta_t$ is updated by intersecting the previous set with the set of parameters consistent with the latest measurement. This shrinks the uncertainty set over time, reducing the conservatism of the tube.

3. Key Contributions

1. Ellipsoidal Tube Formulation for Nonlinear Systems: Extends the theory of ellipsoidal tubes (previously used for linear or specific nonlinear cases) to general nonlinear systems with both parametric and additive uncertainties.
2. Computational Scalability: Demonstrates that ellipsoidal tubes scale polynomially with system dimensions ($O(n_x n_\theta^2 N)$), whereas polytopic tube methods (specifically hyperrectangular ones) scale exponentially ($O(2^{n_x} n_\theta^2 N)$).
3. Recursive Feasibility Guarantee: Introduces a robust backtracking line search mechanism within the online optimization loop, ensuring that a feasible control input is always found, even with limited solver iterations.
4. Stability Proofs: Provides rigorous proofs for recursive feasibility and Input-to-State Practical Stability (ISpS) for the closed-loop system.
5. Comparison with Polytopic Tubes: Offers a comprehensive numerical comparison showing that while polytopic tubes (simplex) may require fewer iterations, the ellipsoidal approach offers a superior trade-off between computation time and performance for higher-dimensional systems.

4. Numerical Results

The authors tested the algorithm on random nonlinear systems with quadratic non-linearities.

• Scaling: Computation time per iteration for the ellipsoidal method increased polynomially with state dimension ($n_x$) and parameter dimension ($n_\theta$).
• Comparison:
  • Hyperrectangular Polytopic Tubes: Computation time exploded exponentially as $n_x$ increased, becoming intractable for $n_x > 6$.
  • Simplex Polytopic Tubes: Scaled linearly with $n_x$ but resulted in higher suboptimality (more conservative control) compared to ellipsoidal tubes.
  • Ellipsoidal Tubes: Required slightly more iterations per time step than polytopic methods but resulted in significantly lower total computation time for systems with $n_x > 3$ and $n_\theta > 3$, while maintaining comparable or better performance (lower cost).
• Performance: The closed-loop trajectories satisfied all constraints, and the cost converged to a small neighborhood of the optimal cost.

5. Significance

This paper presents a significant advancement in safe learning-based control.

• Practicality: It bridges the gap between theoretical robustness and computational feasibility for high-dimensional nonlinear systems. Many existing robust NMPC methods become computationally intractable as the number of states or unknown parameters grows; this method remains tractable.
• Safety: By using ellipsoidal tubes, it provides rigorous guarantees that constraints will not be violated despite model errors and disturbances, which is critical for applications like autonomous driving or robotics (where the authors are based).
• Adaptability: The integration of set membership estimation allows the controller to "learn" the system parameters online, reducing conservatism over time without sacrificing safety guarantees.

In summary, the proposed Ellipsoidal Tube NMPC offers a computationally efficient, robust, and adaptive control strategy that outperforms traditional polytopic tube approaches in higher-dimensional scenarios, making it a viable candidate for real-time implementation in complex engineering systems.