(250e) Improved Set-Based State Estimation for Nonlinear Discrete-Time Systems Using Constrained Zonotopes

Set-based methods have gained attention in the last decades in a wide range of applications [1]. Examples of studied problems are robust economic model predictive control [2], robust state estimation [3,4], joint state and parameter estimation [5], and estimation of the state of charge and parameters in battery cells [6].

The set-based state estimation problem has been extensively studied for linear discrete-time systems. The pioneering methods make use of ellipsoids to bound the trajectories of the system [7]. Other classical methods propose recursive state estimation algorithms based on parallelotopes, and also zonotopes [8]. However, since these sets are not closed in every set operation that arises in the state estimation problem, recently, in [3], a generalization of zonotopes, called constrained zonotopes (CZs), is used to overcome most of the difficulties encountered by the former linear algorithms. While solutions for the state estimation problem of linear systems are well consolidated, nonlinear state estimation is still an open field. The exact characterization of sets containing the evolution of the system states is very difficult in the nonlinear case, if not intractable. Therefore, the usual objective is to enclose such sets as tightly as possible by guaranteed outer bounds on the possible trajectories of the system states. Severe conservatism can occur when these enclosures are represented by simple sets such as intervals, ellipsoids, parallelotopes, and zonotopes.

Outer-approximation methods based on zonotopes and CZs found in the literature often require linear approximations of the nonlinear function, with conservative bounds on the linearization error, which are obtained by using either the Mean Value Theorem or the first-order Taylor expansion [4]. These linear approximations may result in reasonable enclosures for small uncertainties, but can also generate severe conservatism for larger sets, even if the previous bounds correspond to the exact reachable set, rendering the obtained enclosures impractical. Improved bounds on the linearization error can be obtained using DC programming [9]. However, these error bounds ignore the resulting dependencies between state variables, and the required algorithm has exponential computational complexity.

In this presentation, we propose a new algorithm for reachability analysis and state estimation of nonlinear discrete-time systems using lifted polyhedral relaxations to propagate constrained zonotopes through nonlinear functions. Constrained zonotopes [3] are an extension of zonotopes capable of describing convex polytopes with arbitrary complexity, while carrying-on most of the computational advantages of zonotopes. In the new propagation method, the nonlinear function is decomposed into an equivalent sequence of elementary operations, known as a factorable representation, for the generation of a polyhedral enclosure in an augmented space. Such methodology is commonly used in the global optimization community for the computation of linear programming relaxations of nonlinear optimization problems [10]. Properties of CZs are then employed in the projection of the enclosure into the function's image space, while additionally enabling the domain to be a CZ, thus allowing the recursive computation of CZ enclosures for reachability analysis. The propagation method is extended to include an update step with measurements, leading to a new state estimation method for nonlinear discrete-time systems. The proposed methodology results in a linear complexity increase of the obtained enclosures, which can be reduced by using well-known complexity reduction algorithms for CZs [3]. The result is a significant improvement in comparison to other CZ methods from the literature based on linearization procedures.

References Cited

[1] Jaulin, L., Kieffer, M., Didrit, O., and Éric Walter (2001). Applied Interval Analysis. Springer.

[2] Wang, Y., de la Peña, D. M., Puig, V., and Cembrano, G. (2019). Robust economic model predictive control based on a periodicity constraint. International Journal of Robust Nonlinear Control, 29(11), 3296–3310.

[3] Scott, J. K., Raimondo, D. M., Marseglia, G. R., and Braatz, R. D. (2016). Constrained zonotopes: a new tool for set-based estimation and fault detection. Automatica, 69, 126–136.

[4] Rego, B. S., Scott, J. K., Raimondo, D. M., and Raffo, G. V. (2021). Set-valued state estimation of nonlinear discrete-time systems with nonlinear invariants based on constrained zonotopes. Automatica, 129, 109628.

[5] Rego, B. S., Locatelli, D., Raimondo, D. M., and Raffo, G. V. (2022). Joint state and parameter estimation based on constrained zonotopes. Automatica, 142, 110425.

[6] Locatelli, D., Saccani, G., Rego, B. S., Raffo, G. V., and Raimondo, D. M. (2022). Set-based joint state and parameter estimation of a Li-ion cell using constrained zonotopes. In Proc. of the 2022 IEEE Vehicle Power and Propulsion Conference (pp. 1–6).

[7] Schweppe, F. (1968). Recursive state estimation: Unknown but bounded errors and system inputs. IEEE Transactions on Automatic Control, 13(1), 22–28.

[8] Alamo, T., Bravo, J., and Camacho, E. (2005). Guaranteed state estimation by zonotopes. Automatica, 41(6), 1035–1043.

[9] T. Alamo, J. M. Bravo, M. J. Redondo, and E. F. Camacho (2008). A set-membership state estimation algorithm based on DC programming, Automatica, 44(1), 216–224.

[10] M. Tawarmalani and N. V. Sahinidis (2002). Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming, ser. Nonconvex Optimization and Its Applications, P. Pardalos, Ed. Boston, MA: Springer US, 2002, vol. 65.