Ellipsoidal partitions for improved multi-stage robust model predictive control

Moritz Heinlein, Florian Messerer, Moritz Diehl, Sergio Lucia · 2025

Read Ellipsoidal partitions for improved multi-stage robust model predictive control by Moritz Heinlein, Florian Messerer, Moritz Diehl, Sergio Lucia (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-12792.txt.

Introduction

Moritz Heinlein and 3 co-authors improve robust model predictive control in a 2025 paper. Model predictive control plans actions over a horizon while respecting limits, and tube-based methods track how uncertainty in the reachable set propagates. Those methods typically use linear feedback policies, while scenario-based approaches offer more flexible feedback through a tree of possible futures but struggle to give rigorous guarantees.

The authors join both strengths by adding a scenario tree formulation to ellipsoidal tube-based control. Uncertainty ellipsoids are partitioned by halfspaces so each partitioned set can be controlled independently. The new ellipsoidal multi-stage approach is showed in a human-robot system. It aims to handle uncertainty while maintaining computational tractability, keeping the method usable in real time.

Catalog record

CREATORMoritz Heinlein, Florian Messerer, Moritz Diehl, Sergio Lucia
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-12792

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ellipsoidal partitions for improved multi-stage robust model predictive control Moritz Heinlein, Florian Messerer, Moritz Diehl, Sergio Lucia Abstract Ellipsoidal tube-based model predictive control methods effectively account for the propagation of the reachable set, typically employing linear feedback policies. In contrast, scenario-based approaches offer more flexibility in the feedback structure by considering different control actions for different branches of a scenario tree. However, they face challenges in ensuring rigorous guarantees. This work aims to integrate the strengths of both methodologies by enhancing ellipsoidal tube-based MPC with a scenario tree formulation. The uncertainty ellipsoids are partitioned by halfspaces such that each partitioned set can be controlled independently. The proposed ellipsoidal multi-stage approach is demonstrated in a human-robot system, highlighting its advantages in handling uncertainty while maintaining computational tractability. ©2025 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. I Introduction Model predictive control (MPC) is widely applied to multi-input, multi-output nonlinear systems with constraints, optimizing a given performance metric over a prediction horizon [ 1 ] . However, guaranteeing constraint satisfaction, recursive feasibility, and stability requires an accurate system model and reliable disturbance predictions. Consequently, numerous methods have been proposed to ensure robust performance under uncertainty. Unlike nominal MPC, which computes a single input trajectory while ignoring uncertainties, robust MPC considers uncertainty explicitly. Open-loop robust methods optimize one input trajectory to cover all uncertainties by focusing on worst-case performance [ 2 ] . In contrast, closed-loop robust approaches optimize over families of feedback policies, often limiting themselves to linear policies for tractability [ 3 ] , as exemplified by tube-based methods [ 1 ] . This concept, known as recourse , decreases the conservatism, as it considers that future measurements will become available. A key challenge in robust MPC is ensuring that constraints hold for every possible uncertainty realization. This is typically addressed by computing or approximating the reachable set of the uncertain dynamics with a fixed parameterization. In tube-based MPC, the reachable sets (or tubes) can be computed offline or online as intervals [ 4 , 5 ] , polytopes [ 6 , 7 ] or ellipsoids [ 8 , 9 , 10 , 11 ] , see [ 12 , 13 ] for overviews. Intervals are computationally cheap, but can be conservative, as they cannot rotate. Polytopes can represent more complex shapes but may drastically increase complexity in higher dimensions [ 10 , 12 ] . Ellipsoids can perform rotation and scaling and the number of parameters to describe them scales only quadratically with the state dimension. In contrast to tube-based formulations, where the constraints are tightened based on a reachability tube around a nominal trajectory, scenario-based approaches [ 14 , 15 , 16 ] describe the influence of the uncertainty by propagating different realizations in a tree-based structure. For discrete uncertainty sets, scenario-tree (also called multi-stage) approaches can rigorously ensure robust constraint satisfaction even for nonlinear systems. While the tree-structure can be less conservative than a single reachability tube, as decisions can be made independently in different branches of the tree, the number of branches increases exponentially with the prediction horizon and the dimension of the uncertainties. In the general nonlinear case or when the branching is stopped after a few time steps [ 16 ] , theoretical guarantees are lost. In [ 17 ] , it was proposed to combine a multi-stage formulation with polytopic tubes for linear systems to stop the complexity growth after some time steps without losing guarantees. In this paper, we introduce a robust MPC approach that combines efficient uncertainty propagation using ellipsoidal tubes with a state-based partition strategy to independently consider different scenarios in a tree-like structure, depicted in Figure 1 . Because, the partitioning can be stopped at any time step ( n_{r} in Fig 1 ) we avoid the exploding number of scenarios necessary for multi-stage MPC [ 14 ] . By intersecting the ellipsoidal tubes with halfspaces and propagating each partition individually, our method accommodates multiple, potentially disconnected reachable sets, a feature that no standard tube-based approaches can achieve, while maintaining rigorous guarantees and a controllable computational complexity. We expect this aspect to be especially relevant for nonconvex control tasks that may require disjoint reachable sets, which are not possible to obtain with standard tube-based methods. Object avoidance in robotics or autonomous driving is one of these applications. In contrast to [ 17 ] , which proposes a combination of scenario trees and polytopic reachable sets for linear systems, we consider ellipsoidal reachable sets because of their good scaling properties and because they can be robustified against linearization errors to consider nonlinear systems. For the proposed approach, we prove recursive feasibility for the nonlinear case, provided that suitable nonlinearity bounds exist. To show the benefit of considering multiple reachable sets via the scenario formulation, we present the method in a collision avoidance case study, as different paths around an object can be considered. In Section II the nominal MPC problem is presented, as well as the ellipsoidal tube-based problem. Section III describes the ellipsoidal partitioning. Section IV presents the ellipsoidal multi-stage MPC and Section V applies it in a human-robot collision avoidance system. I-A Notation We denote the sequence of vectors \left[{x}_{k}^{\intercal},...,{x}_{k+n}^{\intercal}\right]^{\intercal} as {x}_{\left[k:k+n\right]} . The square root of a vector \sqrt{{x}} is to be understood elementwise. The set of positive semidefinite matrices of a given size n is denoted as {\mathcal{S}}^{n}_{+} . Each matrix {Q}\in{\mathcal{S}}_{+}^{n} defines an ellipsoid around the center {c} , {\mathcal{E}}({Q},{c})=\{{x}\in{\mathbb{R}}^{n}|({x}-{c})^{\intercal}{Q}^{-1}({x}-{c})\leq 1\} . An ellipsoid around the origin is denoted as {\mathcal{E}}({Q}) . The set of integers from m to n is denoted as {\mathbb{I}}_{\left[m:n\right]} . The identity matrix is denoted as {I} , where its dimension can be inferred from context or is given as index. II Ellipsoidal tube-based optimal control We consider discrete-time nonlinear dynamical systems {x}_{k+1}={f}({x}_{k},{u}_{k},{w}_{k}), (1) with the states {x}_{k}\in{\mathbb{R}}^{n_{x}} , inputs {u}_{k}\in{\mathbb{R}}^{n_{u}} and disturbances {w}_{k}\in{\mathbb{R}}^{n_{w}} . We assume that the disturbances {w}=({w}_{0},...,{w}_{N-1}) are drawn collectively from an ellipsoidal uncertainty set {\mathbb{W}}={\mathcal{E}}(\sigma^{2}{I}_{n_{w}N}) without loss of generality. Instead of a robust perspective, as taken in this paper, this approach can be used in a stochastic setting, for which the uncertainty ellipsoid can be understood as the covariance of a Gaussian disturbance [ 11 ] . The nominal optimal control problem for the initial state {x}_{\text{init}} , considering no uncertainty ( w_{k}=0 ), can be stated as \displaystyle\min_{\overline{{x}}_{\left[0:N\right]},\overline{{u}}_{\left[0:N-1\right]}} \displaystyle\sum_{k=0}^{N-1}\ell_{k}(\overline{{x}}_{k},\overline{{u}}_{k})+V(\overline{{x}}_{N}) (2a) s.t.: \displaystyle\overline{{x}}_{0}={x}_{\text{init}}, (2b) \displaystyle\overline{{x}}_{k+1}={f}(\overline{{x}}_{k},\overline{{u}}_{k},0),\ 0\leq k<N, (2c) \displaystyle 0\geq h_{k}(\overline{{x}}_{k},\overline{{u}}_{k}),\ 0\leq k<N, (2d) \displaystyle 0\geq h_{N}(\overline{{x}}_{N}), (2e) where the stage and terminal cost are denoted as \ell_{k}:{\mathbb{R}}^{n_{x}}\times{\mathbb{R}}^{n_{u}}\rightarrow{\mathbb{R}} and V:{\mathbb{R}}^{n_{x}}\rightarrow{\mathbb{R}} and the stage and and terminal constraints are given by h_{k}:{\mathbb{R}}^{n_{x}}\times{\mathbb{R}}^{n_{u}}\rightarrow{\mathbb{R}}^{n_{h_{k}}} \forall k=0,...,N-1 and h_{N}:{\mathbb{R}}^{n_{x}}\rightarrow{\mathbb{R}}^{n_{h_{N}}} respectively. To robustify problem ( 2 ) against uncertainties, we use ellipsoidal uncertainty tubes of the form {\mathcal{E}}({P}_{k},\overline{{x}}_{k}) around the nominal trajectory \overline{{x}}_{k} . To keep the real trajectory close to the nominal one, a linear ancillary controller can be used, {u}_{k}=\overline{{u}}_{k}+{K}_{k}({x}_{k}-\overline{{x}}_{k}), with {K}_{0}=0 . In [ 11 ] , an iterative

Read the complete text