Switch On Safety (SOS)

Documentation	Build Status	Zenodo

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

• Systems defined in MathematicalSystems.jl.
• Hybrid Systems defined in HybridSystems.jl.

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:

• [LTJ18] B. Legat, P. Tabuada, R. M. Jungers. Computing controlled invariant sets for hybrid systems with applications to model-predictive control, IFAC-PapersOnLine, Volume 51, Issue 16, 2018, Pages 193-198, ISSN 2405-8963, https://doi.org/10.1016/j.ifacol.2018.08.033: Figure 4 and 5, Figure 6.
• [LJP17] B. Legat, R. M. Jungers, and P. A. Parrilo. Certifying unstability of Switched Systems using Sum of Squares Programming, arXiv preprint arXiv:1710.01814, 2017: running example, Example 4.3.

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})},
}