research-article

Accurate reachability analysis of uncertain nonlinear systems

Authors:

Matthias Rungger,

Majid ZamaniAuthors Info & Claims

HSCC '18: Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (part of CPS Week)

Pages 61 - 70

https://doi.org/10.1145/3178126.3178127

Published: 11 April 2018 Publication History

Abstract

We propose an algorithm to over-approximate the reachable set of nonlinear systems with bounded, time-varying parameters and uncertain initial conditions. The algorithm is based on the conservative representation of the nonlinear dynamics by a differential inclusion consisting of a linear term and the Minkowsky sum of two convex sets. The linear term and one of the two sets are obtained by a conservative first-order over-approximation of the nonlinear dynamics with respect to the system state. The second set accounts for the effect of the time-varying parameters. A distinctive feature of the novel algorithm is the possibility to over-approximate the reachable set to any desired accuracy by appropriately choosing the parameters in the computation. We provide an example that illustrates the effectiveness of our approach.

References

[1]

M. Althoff. 2013. Reachability analysis of nonlinear systems using conservative polynomialization and non-convex sets. In Proc. of the 16th Int. Conf. on Hybrid Systems: Computation and Control. ACM, 173--182.

Digital Library

[2]

M. Althoff. 2015. An Introduction to CORA 2015. In Proc. of the Workshop on Applied Verification for Continuous and Hybrid Systems. EasyChair, 120--151.

[3]

M. Althoff and B. H. Krogh. 2014. Reachability analysis of nonlinear differential-algebraic systems. IEEE Trans. Automat. Control 59, 2 (2014), 371--383.

[4]

M. Althoff, O. Stursberg, and M. Buss. 2008. Reachability analysis of nonlinear systems with uncertain parameters using conservative linearization. In Proc. of the 47th IEEE Conf. on Decision and Control. IEEE, 4042--4048.

[5]

E. Asarin, T. Dang, and A. Girard. 2003. Reachability analysis of nonlinear systems using conservative approximation. In Proc. of the 6th Int. Conf. on Hybrid Systems: Computation and Control. Springer, 20--35.

Digital Library

[6]

E. Asarin, T. Dang, and A. Girard. 2007. Hybridization methods for the analysis of nonlinear systems. Acta Informatica 43, 7 (2007), 451--476.

Digital Library

[7]

J.-P. Aubin and A. Cellina. 1984. Differential inclusions: set-valued maps and viability theory. Grundlehren der mathematischen Wisschenschaften, Vol. 264. Springer.

Digital Library

[8]

R. Baier, M. Gerdts, and I. Xausa. 2013. Approximation of reachable sets using optimal control algorithms. Numerical Algebra, Control and Optimization 3, 3 (2013), 519--548.

[9]

S. Bak, S. Bogomolov, T. A. Henzinger, T. Johnson, and P. Prakash. 2016. Scalable static hybridization methods for analysis of nonlinear systems. In Proc. of the 19th Int. Conf. on Hybrid Systems: Computation and Control. ACM, 155--164.

Digital Library

[10]

R. G. Bartle. 1976. The elements of real analysis. Vol. 2. Wiley New York.

[11]

A. G. Beccuti, G. Papafotiou, and M. Morari. 2005. Optimal control of the boost dc-dc converter. In Proc. of the 44th IEEE Conf. on Decision and Control and European Control Conference. IEEE, 4457--4462.

[12]

M. Berz and K. Makino. 1998. Verified integration of ODEs and flows using differential algebraic methods on high-order Taylor models. Reliable Computing 4, 4 (1998), 361--369.

[13]

W-J Beyn and J. Rieger. 2007. Numerical fixed grid methods for differential inclusions. Computing 81, 1 (2007), 91--106.

Digital Library

[14]

O. Bokanowski, N. Forcadel, and H. Zidani. 2010. Reachability and minimal times for state constrained nonlinear problems without any controllability assumption. SIAM Journal on Control and Optimization 48, 7 (2010), 4292--4316.

Digital Library

[15]

CAPD. 2017. Computer Assisted Proofs in Dynamics group, a C++ package for rigorous numerics. (2017). Retrieved Sep, 2017 from http://capd.ii.uj.edu.pl.

[16]

P. Cardaliaguet, M. Quincampoix, and P. Saint-Pierre. 1999. Set-valued numerical analysis for optimal control and differential games. In Stochastic and differential games. Springer, 177--247.

[17]

X. Chen, E. Ábrahám, and S. Sankaranarayanan. 2013. Flow: An analyzer for non-linear hybrid systems. In Proc. of the Int. Conf. on Computer Aided Verification. Springer, 258--263.

[18]

P. Collins and L. Geretti. 2017. Ariadne: A C++ library for formal verification of cyber-physical systems, using reachability analysis for nonlinear hybrid automata. (2017). Retrieved Sep, 2017 from http://www.ariadne-cps.org/

[19]

T. Dang, C. Le Guernic, and O. Maler. 2011. Computing reachable states for nonlinear biological models. Theoretical Computer Science 412, 21 (2011), 2095--2107.

Digital Library

[20]

T. Dang, O. Maler, and R. Testylier. 2010. Accurate hybridization of nonlinear systems. In Proc. of the 13th Int. Conf. on Hybrid Systems: Computation and Control. ACM, 11--20.

Digital Library

[21]

A. L. Dontchev and E. M. Farkhi. 1989. Error estimates for discretized differential inclusions. Computing 41, 4 (1989), 349--358.

Digital Library

[22]

R. Freeman and P. V. Kokotovic. 1996. Robust nonlinear control design: state-space and Lyapunov techniques. Birkhäuser.

Digital Library

[23]

G. Frehse and et al. 2011. SpaceEx: Scalable verification of hybrid systems. In Proc. of the Int. Conf. on Computer Aided Verification. Springer, 379--395.

Digital Library

[24]

A. Girard, G. Pola, and P. Tabuada. 2010. Approximately bisimilar symbolic models for incrementally stable switched systems. IEEE Trans. Automat. Control 55 (2010), 116--126.

[25]

Z. Han and B. H. Krogh. 2006. Reachability analysis of nonlinear systems using trajectory piecewise linearized models. In American Control Conference. IEEE, 1505--1510.

[26]

S. M. Harwood and P. I. Barton. 2016. Efficient polyhedral enclosures for the reachable set of nonlinear control systems. Mathematics of Control, Signals, and Systems 28, 1 (2016), 1--33.

[27]

T. A. Henzinger, B. Horowitz, R. Majumdar, and H. Wong-Toi. 2000. Beyond HYTECH: Hybrid systems analysis using interval numerical methods. In Proc. of the 3rd Int. Conf. on Hybrid Systems: Computation and Control, Vol. 1790. Springer, 130--144.

Digital Library

[28]

T. A. Henzinger, P. W. Kopke, A. Puri, and P. Varaiya. 1995. What's decidable about hybrid automata?. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing. ACM, 373--382.

Digital Library

[29]

B. Houska, F. Logist, J. Van Impe, and M. Diehl. 2012. Robust optimization of nonlinear dynamic systems with application to a jacketed tubular reactor. Journal of Process Control 22, 6 (2012), 1152--1160.

[30]

T. Kapela and P. Zgliczyński. 2009. A Lohner-type algorithm for control systems and ordinary differential inclusions. Discrete and Continuous Dynamical Systems. Series B. A Journal Bridging Mathematics and Sciences 11, 2 (2009), 365--385.

[31]

V. A. Komarov and K. E. Pevchikh. 1991. A method of approximating attainability sets for differential inclusions with a specified accuracy. U. S. S. R. Comput. Math. and Math. Phys. 31, 1 (1991), 153--157.

Digital Library

[32]

C. Le Guernic and A. Girard. 2010. Reachability analysis of linear systems using support functions. Nonlinear Analysis: Hybrid Systems 4, 2 (2010), 250--262.

[33]

D. Li. 2007. Morse decompositions for general dynamical systems and differential inclusions with applications to control systems. SIAM Journal on Control and Optimization 46, 1 (2007), 35--60.

Digital Library

[34]

D. Limon, J. M. Bravo, T. Alamo, and E. F. Camacho. 2005. Robust MPC of constrained nonlinear systems based on interval arithmetic. IEE Proceedings-Control Theory and Applications 152, 3 (2005), 325--332.

[35]

Y. Lin and M. A. Stadtherr. 2007. Deterministic global optimization of nonlinear dynamic systems. AIChE Journal 53, 4 (2007), 866--875.

[36]

I. M. Mitchell, A. M. Bayen, and C. J. Tomlin. 2005. A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games. IEEE Transactions on Automatic control 50, 7 (2005), 947--957.

[37]

N. S. Nedialkov. 2011. Implementing a rigorous ODE solver through literate programming. In Modeling, Design, and Simulation of Systems with Uncertainties. Springer, 3--19.

[38]

N. S. Nedialkov, K. R. Jackson, and G. F. Corliss. 1999. Validated solutions of initial value problems for ordinary differential equations. Appl. Math. Comput. 105, 1 (1999), 21--68.

Digital Library

[39]

M. S. Nikol'skii. 1988. A method of approximating an attainable set for a differential inclusion. U. S. S. R. Comput. Math. and Math. Phys. 28, 4 (1988), 192--194.

Digital Library

[40]

D. Nira, F. Elza, and M. Alona. 2014. Approximation of Set-Valued Functions: Adaptation of Classical Approximation Operators. World Scientific Publishing Company.

[41]

A. Puri, V. Borkar, and P. Varaiya. 1996. ϵ-approximation of differential inclusions. In Hybrid Systems III: Verification and Control. Springer, 362--376.

Digital Library

[42]

G. Reissig. 2011. Computing abstractions of nonlinear systems. IEEE Trans. Automat. Control 56, 11 (2011), 2583--2598.

[43]

J. Rieger. 2009. Shadowing and the viability kernel algorithm. Applied Mathematics & Optimization 60, 3 (2009), 429--441.

[44]

R. T. Rockafellar and R. J-B Wets. 2009. Variational analysis. Vol. 317. Springer.

[45]

M. Rungger and G. Reißig. 2017. Arbitrarily Precise Abstractions for Optimal Controller Synthesis. In Proc. of the 56th IEEE Conf. on Decision and Control. IEEE, 1761--1768.

[46]

M. Sandberg. 2008. Convergence of the forward Euler method for nonconvex differential inclusions. SIAM J. Numer. Anal. 47, 1 (2008), 308--320.

Digital Library

[47]

J. K. Scott and P. I. Barton. 2013. Bounds on the reachable sets of nonlinear control systems. Automatica 49, 1 (2013), 93--100.

Digital Library

[48]

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

Digital Library

[49]

A. B. Singer and P. I. Barton. 2006. Global optimization with nonlinear ordinary differential equations. Journal of Global Optimization 34, 2 (2006), 159--190.

Digital Library

[50]

E. D. Sontag. 1998. Mathematical control theory: deterministic finite dimensional systems (2 ed.). Textbooks in Applied Mathematics, Vol. 6. Springer.

Digital Library

[51]

K. Taubert. 1981. Converging multistep methods for initial value problems involving multivalued maps. Computing 27, 2 (1981), 123--136.

[52]

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

Digital Library

[53]

W. Walter. 1964. Differential and integral inequalities. Vol. 55. Springer. Translated from German in 1970 by L. Rosenblatt and L. Shampine.

[54]

M. Zamani, G. Pola, M. Mazo, and P. Tabuada. 2012. Symbolic models for nonlinear control systems without stability assumptions. IEEE Trans. Automat. Control 57, 7 (2012), 1804--1809.

[55]

S. G. Živanović and P. Collins. 2010. Numerical solutions to noisy systems. In Proc. of the 49th IEEE Conf. on Decision and Control. IEEE, 798--803.

Cited By

Massa NPaulson J(2024)Optimal input design for guaranteed fault diagnosis of nonlinear systems: An active deep learning approachControl Engineering Practice10.1016/j.conengprac.2024.106118153(106118)Online publication date: Dec-2024
https://doi.org/10.1016/j.conengprac.2024.106118
Rieger JWawryk K(2023)Towards optimal space-time discretization for reachable sets of nonlinear control systemsJournal of Computational Dynamics10.3934/jcd.2023013(0-0)Online publication date: 2023
https://doi.org/10.3934/jcd.2023013
Shafa TOrnik M(2023)Reachability of Nonlinear Systems With Unknown DynamicsIEEE Transactions on Automatic Control10.1109/TAC.2022.317085568:4(2407-2414)Online publication date: Apr-2023
https://doi.org/10.1109/TAC.2022.3170855
Show More Cited By

Accurate reachability analysis of uncertain nonlinear systems
1. Computing methodologies
  1. Artificial intelligence

Recommendations

Synthetic adaptive fuzzy tracking control for MIMO uncertain nonlinear systems with disturbance observer

In this paper, a synthetic adaptive fuzzy tracking control method is studied for a class of multi-input multi-output (MIMO) uncertain nonlinear systems with time-varying disturbances. The unknown nonlinear functions are approximated by employing ...
Observer design for uncertain nonlinear systems with unmodeled dynamics

This paper is concerned with the observer design problem for a class of multi-input-multi-output nonlinear systems with the unmodeled dynamics, unknown parameters and external disturbance. A dynamic signal, which can dominate the unmodeled dynamics, is ...
Brief Global robust disturbance attenuation and almost disturbance decoupling for uncertain cascaded nonlinear systems

This paper studies the problem of global robust H"~ disturbance attenuation for a class of non-minimum-phase nonlinear systems subject to parameter uncertainty. The problem addressed is the design of a state feedback controller such that the closed-loop ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

HSCC '18: Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (part of CPS Week)

April 2018

296 pages

ISBN:9781450356428

DOI:10.1145/3178126

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 April 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

HSCC '18

Sponsor:

SIGBED

HSCC '18: 21st International Conference on Hybrid Systems: Computation and Control

April 11 - 13, 2018

Porto, Portugal

Acceptance Rates

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
389
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)4

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Massa NPaulson J(2024)Optimal input design for guaranteed fault diagnosis of nonlinear systems: An active deep learning approachControl Engineering Practice10.1016/j.conengprac.2024.106118153(106118)Online publication date: Dec-2024
https://doi.org/10.1016/j.conengprac.2024.106118
Rieger JWawryk K(2023)Towards optimal space-time discretization for reachable sets of nonlinear control systemsJournal of Computational Dynamics10.3934/jcd.2023013(0-0)Online publication date: 2023
https://doi.org/10.3934/jcd.2023013
Shafa TOrnik M(2023)Reachability of Nonlinear Systems With Unknown DynamicsIEEE Transactions on Automatic Control10.1109/TAC.2022.317085568:4(2407-2414)Online publication date: Apr-2023
https://doi.org/10.1109/TAC.2022.3170855
Hu RLiu KShe Z(2022)Reach-Avoid Verification for Time-varying Systems with Uncertain Disturbances2022 20th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE)10.1109/MEMOCODE57689.2022.9954600(1-12)Online publication date: 13-Oct-2022
https://doi.org/10.1109/MEMOCODE57689.2022.9954600
Bidet FGoubault EPutot S(2022)Reachability Analysis of Generalized Input-Affine Systems With Bounded Measurable Time-Varying UncertaintiesIEEE Control Systems Letters10.1109/LCSYS.2021.30845306(638-643)Online publication date: 2022
https://doi.org/10.1109/LCSYS.2021.3084530
Shafa TOrnik M(2022)Maximal Ellipsoid Method for Guaranteed Reachability of Unknown Fully Actuated Systems2022 IEEE 61st Conference on Decision and Control (CDC)10.1109/CDC51059.2022.9992407(5002-5007)Online publication date: 6-Dec-2022
https://doi.org/10.1109/CDC51059.2022.9992407
Schurmann BAlthoff M(2021)Optimizing Sets of Solutions for Controlling Constrained Nonlinear SystemsIEEE Transactions on Automatic Control10.1109/TAC.2020.298976266:3(981-994)Online publication date: Mar-2021
https://doi.org/10.1109/TAC.2020.2989762
Tajvar PMeyer PTumova J(2021)Closed-loop incremental stability for efficient symbolic control of non-linear systemsIFAC-PapersOnLine10.1016/j.ifacol.2021.08.48554:5(121-126)Online publication date: 2021
https://doi.org/10.1016/j.ifacol.2021.08.485
Geretti LŽivanović Gonzalez SCollins PBresolin DVilla T(2019)Rigorous Continuous Evolution of Uncertain SystemsNumerical Software Verification10.1007/978-3-030-28423-7_4(60-75)Online publication date: 3-Aug-2019
https://doi.org/10.1007/978-3-030-28423-7_4
Serry MReissig G(2018)Hyper-Rectangular Over-Approximations of Reachable Sets for Linear Uncertain Systems2018 IEEE Conference on Decision and Control (CDC)10.1109/CDC.2018.8619276(6275-6282)Online publication date: Dec-2018
https://doi.org/10.1109/CDC.2018.8619276

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten