Cited By
View all- Breeden JPanagou D(2023)Compositions of Multiple Control Barrier Functions Under Input Constraints2023 American Control Conference (ACC)10.23919/ACC55779.2023.10156625(3688-3695)Online publication date: 31-May-2023
Improving validated computation of Viability Kernels
Pages 227 - 236
Abstract
The study of viability kernels can be of critical importance for the verification of control systems. A viability kernel over a set of safe states is the set of initial states for which the trajectory can be controlled so as to stay within the safe set for an indefinite amount of time. This paper investigates improvements of the rigorous method from Monnet et al. [19, 20]. This method computes an inner-approximation of the viability kernel of a continuous time control system using methods based on interval analysis. It consists of two phases: first an initial inner-approximation of the viability kernel is computed via Lyapunov-like functions; second the initial inner-approximation is improved by finding other states that can reach the inner-approximation, without exiting the safe set, using validated numerical integration. Among the improvements, we discuss an approach inspired by an interval method using barrier functions for computing a good initial inner-approximation of the viability kernel, easing the improvement phase.
References
[1]
Julien Alexandre dit Sandretto and Alexandre Chapoutot. 2016. Validated Explicit and Implicit Runge-Kutta Methods. Reliable Computing 22 (2016), 79--103.
[2]
Julien Alexandre dit Sandretto and Alexandre Chapoutot. 2016. Validated simulation of differential algebraic equations with Runge-Kutta methods. Reliable Computing 22, pp. 56--77 (July 2016).
[3]
Jean-Pierre Aubin. 2009. Viability theory. Springer Science & Business Media.
[4]
Olivier Bouissou, Alexandre Chapoutot, and Adel Djoudi. 2013. Enclosing Temporal Evolution of Dynamical Systems Using Numerical Methods. In NASA Formal Methods (LNCS). Springer, 108--123.
[5]
Olivier Bouissou and Matthieu Martel. 2006. GRKLib: a Guaranteed Runge Kutta Library. In Scientific Computing, Computer Arithmetic and Validated Numerics.
[6]
Gilles Chabert and Luc Jaulin. 2009. Contractor programming. Artificial Intelligence 173, 11 (2009), 1079 - 1100.
[7]
Guillaume Deffuant, Laetitia Chapel, and Sophie Martin. 2007. Approximating Viability Kernels With Support Vector Machines. IEEE Trans. Automat. Control 52, 5 (May 2007), 933--937.
[8]
Adel Djaballah, Alexandre Chapoutot, Michel Kieffer, and Olivier Bouissou. 2017. Construction of parametric barrier functions for dynamical systems using interval analysis. Automatica 78 (2017), 287 - 296.
[9]
Karol Gajda, Andrzej Marciniak, and Barbara Szyszka. 2000. Three- and Four-Stage Implicit Interval Methods of Runge-Kutta Type. Computational Methods in Science and Technology 6, 1 (2000), 41--59.
[10]
Antoine Girard. 2012. Controller synthesis for safety and reachability via approximate bisimulation. Automatica 48, 5 (2012), 947--953.
[11]
Milan Hladík and Stefan Ratschan. 2014. Efficient Solution of a Class of Quantified Constraints with Quantifier Prefix Exists-Forall. Mathematics in Computer Science 8, 3 (2014), 329--340.
[12]
Daisuke Ishii, Alexandre Goldsztejn, and Christophe Jermann. 2012. Interval-based projection method for under-constrained numerical systems. Constraints 17, 4 (2012), 432--460.
[13]
Luc Jaulin, Michel Kieffer, Olivier Didrit, and Eric Walter. 2001. Applied Interval Analysis with Examples in Parameter and State Estimation, Robust Control and Robotics. Springer-Verlag.
[14]
Shahab Kaynama, John Maidens, Meeko Oishi, Ian M. Mitchell, and Guy A. Dumont. 2012. Computing the Viability Kernel Using Maximal Reachable Sets. In Proceedings of the 15th ACM International Conference on Hybrid Systems: Computation and Control (HSCC '12). ACM, New York, NY, USA, 55--64.
[15]
R. Baker Kearfott. 1996. Rigorous Global Search: Continuous Problems. Kluwer Academic Publishers.
[16]
Milan Korda, Didier Henrion, and Colin N. Jones. 2013. Convex computation of the maximum controlled invariant set for discrete-time polynomial control systems. In 52nd IEEE Conference on Decision and Control. 7107--7112.
[17]
Andrzej Marciniak. 2004. Implicit Interval Methods for Solving the Initial Value Problem. Numerical Algorithms 37, 1-4 (2004), 241--251.
[18]
Andrzej Marciniak and Barbara Szyszka. 2004. On Representations of Coefficients in Implicit Interval Methods of Runge-Kutta Type. Computational Methods in Science and Technology 10, 1 (2004), 57--71.
[19]
Dominique Monnet, Luc Jaulin, Jordan Ninin, Alexandre Chapoutot, and Julien Alexandre-dit Sandretto. 2015. Viability kernel computation based on interval methods. In SWIM (Summer Workshop on Interval Analysis).
[20]
D. Monnet, J. Ninin, and Luc Jaulin. 2016. Computing an Inner and an Outer Approximation of the Viability Kernel. Reliable Computing 22, 1 (Sep 2016), 138--148.
[21]
Ramon E. Moore. 1966. Interval Analysis. Prentice-Hall.
[22]
Bouguerra Muhammad, Thierry Fraichard, and Mohamed Fezari. 2015. Safe Motion using Viability Kernels. In ICRA 2015-IEEE Int. Conf. on Robotics and Automation. 3259--3264.
[23]
Nedialko S Nedialkov, Kenneth R Jackson, and George F Corliss. 1999. Validated solutions of initial value problems for ordinary differential equations. Appl. Math. Comput. 105, 1 (1999), 21--68.
[24]
Arnold Neumaier. 1991. Interval Methods for Systems of Equations. Cambridge University Press.
[25]
Bertrand Neveu, Gilles Trombettoni, and Ignacio Araya. 2016. Node selection strategies in interval Branch and Bound algorithms. Journal of Global Optimization 64, 2 (2016), 289--304.
[26]
Gunther Reissig, Alexander Weber, and Matthias Rungger. 2017. Feedback Refinement Relations for the Synthesis of Symbolic Controllers. IEEE Trans. Automat. Control 62, 4 (April 2017), 1781--1796.
[27]
Patrick Saint-Pierre. 1994. Approximation of the viability kernel. Applied Mathematics and Optimization 29, 2 (01 Mar 1994), 187--209.
[28]
Zhikun She and Bai Xue. 2013. Computing an invariance kernel with target by computing Lyapunov-like functions. IET Control Theory & Applications 7, 15 (2013), 1932--1940.
Recommendations
Approximation of the viability kernel
We study recursive inclusionsxn+1ź G(xn). For instance, such systems appear for discrete finite-difference inclusionsxn+1 źGź(xn) whereGź:=1+źF. The discrete viability kernel ofGź, i.e., the largest discrete viability domain, can be an internal ...
An anti-diffusive scheme for viability problems
Numerical methods for viscosity solutions and applicationsThis paper is concerned with the numerical approximation of viability kernels. The method described here provides an alternative approach to the usual viability algorithm. We first consider a characterization of the viability kernel as the value function ...
Intersection and Signed-Intersection Kernels for Intervals
Proceedings of the 2008 conference on Artificial Intelligence Research and Development: Proceedings of the 11th International Conference of the Catalan Association for Artificial IntelligenceIn this paper two kernels for interval data based on the intersection operation are introduced. On the one hand, it is demonstrated that the intersection length of two intervals is a positive definite (PD) kernel. On the other hand, a signed variant of ...
Comments
Information & Contributors
Information
Published In
April 2018
296 pages
ISBN:9781450356428
DOI:10.1145/3178126
Copyright © 2018 ACM.
Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 April 2018
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
HSCC '18
Sponsor:
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
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 104Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 02 Mar 2025
Other Metrics
Citations
Cited By
View all- Breeden JPanagou D(2023)Compositions of Multiple Control Barrier Functions Under Input Constraints2023 American Control Conference (ACC)10.23919/ACC55779.2023.10156625(3688-3695)Online publication date: 31-May-2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in