Skip to content

Julia Package for computing [controlled] invariant sets of Hybrid Systems using Sum Of Squares Programming

License

Notifications You must be signed in to change notification settings

blegat/SwitchOnSafety.jl

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Switch On Safety (SOS)

Documentation Build Status Zenodo
Build Status DOI
Codecov branch

This packages implements methods for computing invariant sets using Sum Of Squares Programming. It supports:

It also includes utilities for approximation the Joint Spectral Radius.

Installation

The package currently requires Julia v1.0, you can download it here. Once Julia is installed, simply launch the REPL an type

] add SwitchOnSafety

Examples

Example notebooks are available in the examples folder. We link them below with the literature.

Reproducing

The linked notebooks reproduce the results of the following papers:

Exploring

The linked notebooks explores the examples of the following papers using this package:

  • [AJPR14] A. Ahmadi, R. Jungers, P. Parrilo and M. Roozbehani, Joint spectral radius and path-complete graph Lyapunov functions. SIAM J. CONTROL OPTIM 52(1), 687-717, 2014: Example 5.4.
  • [AP12] A. Ahmadi, and P. Parrilo Joint spectral radius of rank one matrices and the maximum cycle mean problem. CDC, 731-733, 2012: Example 2.1.
  • [AS98] Ando, T. and Shih, M.-h. Simultaneous Contractibility. SIAM Journal on Matrix Analysis & Applications, 1998, 19, 487: construction.
  • [BTV03] V. D. Blondel, J. Theys and A. A. Vladimirov. An elementary counterexample to the finiteness conjecture, SIAM Journal on Matrix Analysis and Applications, 2003. 24, 963-970: the counterexample.
  • [GZ05] N. Guglielmi and M. Zennaro. Polytope norms and related algorithms for the computation of the joint spectral radius. 44th IEEE Conference on Decision and Control, and European Control Conference, 2005, pp. 3007-3012: Section V.
  • [GZ08] N. Guglielmi and M. Zennaro. An algorithm for finding extremal polytope norms of matrix families. Linear Algebra and its Applications, 2008, 428(10), 2265-2282: Section 5.
  • [GP13] N. Guglielmi and V. Protasov. Exact computation of joint spectral characteristics of linear operators. Foundations of Computational Mathematics 13.1, 2013, 37-97. Example 1. Example 2.
  • [HMST11] K. G. Hare, I. D Morris, N. Sidorov and J. Theys, An explicit counterexample to the Lagarias–Wang finiteness conjecture. Advances in Mathematics, 2011, 226(6), 4667-4701: the counterexample.
  • [JCG14] R. Jungers, A. Cicone and N. Guglielmi, Lifted polytope methods for computing the joint spectral radius. SIAM Journal on Matrix Analysis and Applications, SIAM, 2014, 35, 391-410: Example 6.1, Example 6.3.
  • [PJ08] P. Parrilo and A. Jadbabaie. Approximation of the joint spectral radius using sum of squares. Linear Algebra and its Applications, Elsevier, 2008, 428, 2385-2402: Example 2.8, Example 5.4.
  • [P17] M. Philippe. Path-Complete Methods and Analysis of Constrained Switching Systems Doctoral dissertation, UCLouvain, 2017: Example 2.50, Example 2.52.
  • [PEDJ16] M. Philippe, R. Essick, G. E. Dullerud and R. M. Jungers. Stability of discrete-time switching systems with constrained switching sequences. Automatica, 72:242-250, 2016: Section 4,

How to cite

For the soslyapb and sosbuildsequence functions, cite:

@Article{legat2020certifying,
  author    = {Legat, Beno\^it and Parrilo, Pablo A. and Jungers, Rapha\"el M.},
  journal   = {{SIAM} Journal on Control and Optimization},
  title     = {Certifying Unstability of Switched Systems Using Sum of Squares Programming},
  year      = {2020},
  month     = jan,
  number    = {4},
  pages     = {2616--2638},
  volume    = {58},
  doi       = {10.1137/18M1173460},
  publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
}

and for the lower bound obtained by soslyapb, see:

@Article{legat2019entropy,
  author    = {Beno\^it Legat and Pablo A. Parrilo and Rapha\"el M. Jungers},
  title     = {An entropy-based bound for the computational complexity of a switched system},
  journal   = {IEEE Transactions on Automatic Control},
  year      = {2019},
  doi       = {10.1109/TAC.2019.2902625},
  publisher = {IEEE},
}

For the getis and fillis! functions with ellipsoids or polysets, cite:

@InProceedings{legat2018computing,
  author   = {Beno\^it Legat and Paulo Tabuada and Rapha\"el M. Jungers},
  title    = {Computing controlled invariant sets for hybrid systems with applications to model-predictive control},
  year     = {2018},
  volume   = {51},
  number   = {16},
  pages    = {193--198},
  note     = {6th IFAC Conference on Analysis and Design of Hybrid Systems ADHS 2018},
  doi      = {https://doi.org/10.1016/j.ifacol.2018.08.033},
  issn     = {2405-8963},
  journal  = {IFAC-PapersOnLine},
  keywords = {Controller Synthesis, Set Invariance, LMIs, Scalable Methods},
  url      = {http://www.sciencedirect.com/science/article/pii/S2405896318311480},
}

or with piecewise semi-ellipsoids, cite:

@Article{legat2020piecewise,
  author    = {Beno{\^\i}t Legat and Sa{\v{s}}a V. Rakovi{\'c} and Rapha{\"e}l M. Jungers},
  journal   = {{IEEE} Control Systems Letters},
  title     = {Piecewise Semi-Ellipsoidal Control Invariant Sets},
  year      = {2021},
  month     = jul,
  number    = {3},
  pages     = {755--760},
  volume    = {5},
  doi       = {10.1109/LCSYS.2020.3005326},
  publisher = {Institute of Electrical and Electronics Engineers ({IEEE})},
}

About

Julia Package for computing [controlled] invariant sets of Hybrid Systems using Sum Of Squares Programming

Topics

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages