A computationally inexpensive algorithm for determining outer and inner enclosures of nonlinear mappings of ellipsoidal domains

Rauh, Andreas ; Jaulin, Luc

International Journal of Applied Mathematics and Computer Science, Tome 31 (2021) no. 3, pp. 399-415.

Résumé

A wide variety of approaches for set-valued simulation, parameter identification, state estimation as well as reachability, observability and stability analysis for nonlinear discrete-time systems involve the propagation of ellipsoids via nonlinear functions. It is well known that the corresponding image sets usually possess a complex shape and may even be nonconvex despite the convexity of the input data. For that reason, domain splitting procedures are often employed which help to reduce the phenomenon of overestimation that can be traced back to the well-known dependency and wrapping effects of interval analysis. In this paper, we propose a simple, yet efficient scheme for simultaneously determining outer and inner ellipsoidal range enclosures of the solution for the evaluation of multi-dimensional functions if the input domains are themselves described by ellipsoids. The Hausdorff distance between the computed enclosure and the exact solution set reduces at least linearly when decreasing the size of the input domains. In addition to algebraic function evaluations, the proposed technique is-for the first time, to our knowledge-employed for quantifying worst-case errors when extended Kalman filter-like, linearization-based techniques are used for forecasting confidence ellipsoids in a stochastic setting.

Détail

Keywords: bounded uncertainty, guaranteed enclosures, ellipsoidal enclosures, inner approximations, outer approximations, nonlinear system, confidence interval
Mots-clés : niepewność ograniczona, układ nieliniowy, przedział ufności

Bibliographie

[1] [1] Becis-Aubry, Y. (2020). Ellipsoidal constrained state estimation in presence of bounded disturbances, Preprint, arxiv.org/pdf/2012.03267v1.pdf.

[2] [2] Bünger, F. (2020). A Taylor model toolbox for solving ODEs implemented in MATLAB/INTLAB, Journal of Computational and Applied Mathematics 368: 112511.

[3] [3] Bouissou, O., Chapoutot, A. and Djoudi, A. (2013). Enclosing temporal evolution of dynamical systems using numerical methods, in G. Brat et al. (Eds), NASA Formal Methods, Springer-Verlag, Berlin/Heidelberg, pp. 108–123.

[4] [4] Bourgois, A. and Jaulin, L. (2021). Interval centred form for proving stability of non-linear discrete-time systems, in T. Dang and S. Ratschan (Eds), Symbolic-Numeric Methods for Reasoning About CPS and IoT, Open Publishing Association, Den Haag, pp. 1–17.

[5] [5] Chapoutot, A. (2010). Interval slopes as a numerical abstract domain for floating-point variables, in R. Cousot and M. Martel (Eds), Static Analysis. SAS 2010, Lecture Notes in Computer Science, Vol. 6337, Springer, Berlin/Heidelberg, pp. 184–200.

[6] [6] Chen, M. and Rincon-Mora, G. (2006). Accurate electrical battery model capable of predicting runtime and I-V performance, IEEE Transactions on Energy Conversion 21(2): 504–511.

[7] [7] Cornelius, H. and Lohner, R. (1984). Computing the range of values of real functions with accuracy higher than second order, Computing 33(3–4): 331–347.

[8] [8] de Berg, M., Cheong, O., van Kreveld, M. and Overmars, M. (2008). Computational Geometry: Algorithms and Applications, 3rd Edn, Springer, Berlin/Heidelberg.

[9] [9] Erdinc, O., Vural, B. and Uzunoglu, M. (2009). A dynamic Lithium-ion battery model considering the effects of temperature and capacity fading, International Conference on Clean Electrical Power, Capri, Italy, pp. 383–386.

[10] [10] Černý, M. (2012). Goffin’s algorithm for zonotopes, Kybernetika 48(5): 890–906.

[11] [11] Farrera, B., López-Estrada, F.-R., Chadli, M., Valencia-Palomo, G. and Gómez-Peñate, S. (2020). Distributed fault estimation of multi-agent systems using a proportional-integral observer: A leader-following application, International Journal of Applied Mathematics and Computer Science 30(3): 551–560, DOI: 10.34768/amcs-2020-0040.

[12] [12] Goubault, E., Mullier, O., Putot, S. and Kieffer, M. (2014). Inner approximated reachability analysis, 17th International Conference on Hybrid Systems: Computation and Control, Berlin, Germany, pp. 163–172.

[13] [13] Griewank, A. (2000). Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, SIAM, Philadelphia.

[14] [14] Hairer, E., Lubich, C. and Wanner, G. (2002). Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations, Springer, Berlin/Heidelberg.

[15] [15] Halder, A. (2018). On the parameterized computation of minimum volume outer ellipsoid of Minkowski sum of ellipsoids, IEEE Conference on Decision and Control (CDC), Miami Beach, USA, pp. 4040–4045.

[16] [16] Hanebeck, U.D., Briechle, K. and Rauh, A. (2003). Progressive Bayes: A new framework for nonlinear state estimation, in B.V. Dasarathy (Ed.), Multisensor, Multisource Information Fusion: Architectures, Algorithms, and Applications 2003, International Society for Optics and Photonics, Bellingham, pp. 256–267.

[17] [17] Hoefkens, J. (2001). Rigorous Numerical Analysis with High-Order Taylor Models, PhD thesis, Michigan State University, East Lansing, https://groups.nscl.msu.edu/nscl_library/Thesis/Hoefkens,%20Jens.pdf.

[18] [18] Houska, B., Villanueva, M. and Chachuat, B. (2015). Stable set-valued integration of nonlinear dynamic systems using affine set-parameterizations, SIAM Journal on Numerical Analysis 53(5): 2307–2328.

[19] [19] Jambawalikar, S. and Kumar, P. (2008). A note on approximate minimum volume enclosing ellipsoid of ellipsoids, International Conference on Computational Sciences and Its Applications, Perugia, Italy, pp. 478–487.

[20] [20] Jaulin, L., Kieffer, M., Didrit, O. and Walter, É. (2001). Applied Interval Analysis, Springer-Verlag, London.

[21] [21] John, F. (1948). Extremum problems with inequalities as subsidiary conditions, Studies and Essays Presented to R. Courant on his 60th Birthday, Interscience Publishers, New York, pp. 187–204.

[22] [22] Julier, S., Uhlmann, J. and Durrant-Whyte, H. (2000). A new approach for the nonlinear transformation of means and covariances in filters and estimators, IEEE Transactions on Automatic Control 45(3): 477–482.

[23] [23] Kalman, R. (1960). A new approach to linear filtering and prediction problems, Transaction of the ASME: Journal of Basic Engineering 82(Series D): 35–45.

[24] [24] Krasnochtanova, I., Rauh, A., Kletting, M., Aschemann, H., Hofer, E.P. and Schoop, K.-M. (2010). Interval methods as a simulation tool for the dynamics of biological wastewater treatment processes with parameter uncertainties, Applied Mathematical Modeling 34(3): 744–762.

[25] [25] Krishnaswami, G. and Senapati, H. (2019). An introduction to the classical three-body problem: From periodic solutions to instabilities and chaos, Reson 24: 87–114, DOI: 10.1007/s12045-019-0760-1.

[26] [26] Kühn, W. (1999). Rigorous error bounds for the initial value problem based on defect estimation, Technical report, http://www.decatur.de/personal/papers/defect.zip.

[27] [27] Kurzhanskii, A.B. and Vályi, I. (1997). Ellipsoidal Calculus for Estimation and Control, Birkhäuser, Boston.

[28] [28] Kurzhanskiy, A. and Varaiya, P. (2006). Ellipsoidal Toolbox (ET), Proceedings of the 45th IEEE Conference on Decision and Control, San Diego, USA, pp. 1498–1503.

[29] [29] Makino, K. and Berz, M. (2004). Suppression of the wrapping effect by Taylor model-based validated integrators, Technical Report MSU HEP 40910, Michigan State University, East Lansing.

[30] [30] Mayer, G. (2017). Interval Analysis and Automatic Result Verification, De Gruyter, Berlin/Boston.

[31] [31] Mejdi, S., Messaoud, A. and Ben Abdennour, R. (2020). Fault tolerant multicontrollers for nonlinear systems: A real validation on a chemical process, International Journal of Applied Mathematics and Computer Science 30(1): 61–74, DOI: 10.34768/amcs-2020-0005.

[32] [32] Moore, R. (1966). Interval Arithmetic, Prentice-Hall, Englewood Cliffs.

[33] [33] Moore, R., Kearfott, R. and Cloud, M. (2009). Introduction to Interval Analysis, SIAM, Philadelphia.

[34] [34] Musielak, Z.E. and Quarles, B. (2014). The three-body problem, Reports on Progress in Physics 77(6): 065901.

[35] [35] Neumaier, A., Fuchs, M., Dolejsi, E., Csendes, T., Dombi, J. and Banhelyi, B. (2007). Application of clouds for modeling uncertainties in robust space system design, Technical Report 05-5201, European Space Agency, Paris, http://www.esa.int/gsp/ACT/doc/ARI/ARI%20Study%20Report/ACT-RPT-INF-ARI-055201-Clouds.pdf.

[36] [36] Papoulis, A. (1965). Probability, Random Variables, and Stochastic Processes, McGraw-Hill, Tokyo.

[37] [37] Rauh, A., Bourgois, A. and Jaulin, L. (2021a). Ellipsoidal enclosure techniques for a verified simulation of initial value problems for ordinary differential equations, 5th International Conference on Control, Automation and Diagnosis (ICCAD’21), Grenoble, France, (accepted for publication).

[38] [38] Rauh, A., Bourgois, A. and Jaulin, L. (2021b). Union and intersection operators for thick ellipsoid state enclosures: Application to bounded-error discrete-time state observer design, Algorithms 14(3): 88.

[39] [39] Rauh, A., Briechle, K. and Hanebeck, U.D. (2009). Nonlinear measurement update and prediction: Prior density splitting mixture estimator, IEEE International Conference on Control Applications CCA 2009, St. Petersburg, Russia, pp. 1421–1426.

[40] [40] Rauh, A., Butt, S.S. and Aschemann, H. (2013). Nonlinear state observers and extended Kalman filters for battery systems, International Journal of Applied Mathematics and Computer Science 23(3): 539–556, DOI: 10.2478/amcs-2013-0041.

[41] [41] Rauh, A. and Jaulin, L. (2021). A novel thick ellipsoid approach for verified outer and inner state enclosures of discrete-time dynamic systems, 19th IFAC Symposium on System Identification: Learning Models for Decision and Control, online.

[42] [42] Rauh, A., Kletting, M., Aschemann, H. and Hofer, E.P. (2007). Reduction of overestimation in interval arithmetic simulation of biological wastewater treatment processes, Journal of Computational and Applied Mathematics 199(2): 207–212.

[43] [43] Rauh, A., Weitschat, R. and Aschemann, H. (2010). Modellgestützter Beobachterentwurf zur Betriebszustands- und Alterungserkennung für Lithium-Ionen-Batterien, VDI-Berichte 2105: Innovative Fahrzeugantriebe 2010 Die Vielfalt der Mobilität: Vom Verbrenner bis zum E-Motor: 7. VDI-Tagung Innovative Fahrzeugantriebe, Dresden, Germany, pp. 377–382.

[44] [44] Reuter, J., Mank, E., Aschemann, H. and Rauh, A. (2016). Battery state observation and condition monitoring using online minimization, 21st Internatioanl Conference on Methods and Models in Automation and Robotics, Miedzyzdroje, Poland, pp. 1223–1228.

[45] [45] Romig, S., Jaulin, L. and Rauh, A. (2019). Using interval analysis to compute the invariant set of a nonlinear closed-loop control system, Algorithms 12(12): 262.

[46] [46] Stengel, R. (1994). Optimal Control and Estimation, Dover Publications, New York.

[47] [47] Tarbouriech, S., Garcia, G., Gomes da Silva, J. and Queinnec, I. (2011). Stability and Stabilization of Linear Systems With Saturating Actuators, Springer-Verlag, London.

[48] [48] Tóth, B. and Csendes, T. (2005). Empirical investigation of the convergence speed of inclusion functions in a global optimization context, Reliable Computing 11: 253–273.

[49] [49] Villanueva, M., Houska, B. and Chachuat, B. (2015). Unified framework for the propagation of continuous-time enclosures for parametric nonlinear ODEs, Journal of Global Optimization 62(3): 575–613.

[50] [50] Wang, B., Shi, W. and Miao, Z. (2015). Confidence analysis of standard deviational ellipse and its extension into higher dimensional Euclidean space, PLOS ONE 10(3): 1–17.

[51] [51] Yildirim, E.A. (2006). On the minimum volume covering ellipsoid of ellipsoids, SIAM Journal on Optimization 17(3): 621–641.