Sum-of-squares methods for controlled invariant sets with applications to model-predictive control. (English) Zbl 1441.93075
Summary: We develop a method for computing controlled invariant sets of discrete-time affine systems using sum-of-squares programming. We apply our method to the controller design problem for switching affine systems with polytopic safe sets but our work also improves the state of the art for the particular case of LTI systems. The task is reduced to a semidefinite programming problem by enforcing an invariance relation in the dual space of the geometric problem. The paper ends with an application to safety critical model predictive control.
MSC:
| 93B45 | Model predictive control |
| 93B50 | Synthesis problems |
| 93C55 | Discrete-time control/observation systems |
| 93C30 | Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) |
| 90C90 | Applications of mathematical programming |
References:
| [1] | Tomlin, Claire; Pappas, George J.; Sastry, Shankar, Conflict resolution for air traffic management: A study in multiagent hybrid systems, IEEE Trans. Autom. Control, 43, 4, 509-521 (1998) · Zbl 0904.90113 |
| [2] | Blanchini, Franco, Set invariance in control, Automatica, 35, 11, 1747-1767 (1999) · Zbl 0935.93005 |
| [3] | Blanchini, Franco; Miani, Stefano, Set-Theoretic Methods in Control (2015), Springer · Zbl 1417.93008 |
| [4] | Pólik, Imre; Terlaky, Tamás, A survey of the S-lemma, SIAM Rev., 49, 3, 371-418 (2007) · Zbl 1128.90046 |
| [5] | Boyd, Stephen P.; El Ghaoui, Laurent; Feron, Eric; Balakrishnan, Venkataramanan, Linear Matrix Inequalities in System and Control Theory, Vol. 15 (1994), SIAM · Zbl 0816.93004 |
| [6] | Rungger, Matthias; Mazo, Manuel; Tabuada, Paulo, Specification-guided controller synthesis for linear systems and safe linear-time temporal logic, (Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control (2013), ACM), 333-342 · Zbl 1362.93059 |
| [7] | Smith, Stanley W.; Nilsson, Petter; Ozay, Necmiye, Interdependence quantification for compositional control synthesis with an application in vehicle safety systems, (Decision and Control (CDC), 2016 IEEE 55th Conference on (2016), IEEE), 5700-5707 |
| [8] | Rungger, Matthias; Tabuada, Paulo, Computing robust controlled invariant sets of linear systems, IEEE Trans. Automat. Control (2017) · Zbl 1370.93165 |
| [9] | Avis, David; Bremner, David; Seidel, Raimund, How good are convex hull algorithms?, (Proceedings of the Eleventh Annual Symposium on Computational Geometry (1995), ACM), 20-28 · Zbl 0877.68119 |
| [10] | Rakovic, Saša V.; Baric, Miroslav, Parameterized robust control invariant sets for linear systems: Theoretical advances and computational remarks, IEEE Trans. Automat. Control, 55, 7, 1599-1614 (2010) · Zbl 1368.93205 |
| [11] | Athanasopoulos, Nikolaos; Jungers, Raphaël M., Computing the domain of attraction of switching systems subject to non-convex constraints, (Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control. Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control, HSCC ’16 (2016), ACM: ACM New York, NY, USA), 41-50 · Zbl 1364.93377 |
| [12] | Kurzhanski, Alexander B.; Varaiya, Pravin, On verification of controlled hybrid dynamics through ellipsoidal techniques, (Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC’05. 44th IEEE Conference on (2005), IEEE), 4682-4687 |
| [13] | Henrion, Didier; Korda, Milan, Convex computation of the region of attraction of polynomial control systems, IEEE Trans. Automat. Control, 59, 2, 297-312 (2014) · Zbl 1360.93601 |
| [14] | Korda, Milan; Henrion, Didier; Jones, Colin N., Convex computation of the maximum controlled invariant set for polynomial control systems, SIAM J. Control Optim., 52, 5, 2944-2969 (2014) · Zbl 1311.49073 |
| [15] | Korda, Milan; Henrion, Didier; Jones, Colin N., Inner approximations of the region of attraction for polynomial dynamical systems, IFAC Proc. Vol., 46, 23, 534-539 (2013) |
| [16] | Toker, Onur; Ozbay, Hitay, On the NP-hardness of solving bilinear matrix inequalities and simultaneous stabilization with static output feedback, (American Control Conference, Proceedings of the 1995, Vol. 4 (1995), IEEE), 2525-2526 · Zbl 0839.93030 |
| [17] | Blekherman, Grigoriy; Parrilo, Pablo A.; Thomas, Rekha R., Semidefinite Optimization and Convex Algebraic Geometry (2012), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 1260.90006 |
| [18] | Ando, Tsuyoshi; Shih, Mau-hsiang, Simultaneous contractibility, SIAM J. Matrix Anal. Appl., 19, 2, 487 (1998) · Zbl 0912.15033 |
| [19] | Parrilo, Pablo A.; Jadbabaie, Ali, Approximation of the joint spectral radius using sum of squares, Linear Algebra Appl., 428, 10, 2385-2402 (2008) · Zbl 1151.65032 |
| [20] | Ahmadi, Amir Ali; Jungers, Raphaël M.; Parrilo, Pablo A.; Roozbehani, Mardavij, Joint spectral radius and path-complete graph Lyapunov functions, SIAM J. Control Optim., 52, 1, 687-717 (2014) · Zbl 1292.93093 |
| [21] | Legat, Benoît; Tabuada, Paulo; Jungers, Raphaël M., Computing controlled invariant sets for hybrid systems with applications to model-predictive control, 6th IFAC Conference on Analysis and Design of Hybrid Systems ADHS 2018. 6th IFAC Conference on Analysis and Design of Hybrid Systems ADHS 2018, IFAC-PapersOnLine, 51, 16, 193-198 (2018) |
| [22] | Ahmadi, Amir Ali; Günlük, Oktay, Robust-to-dynamics linear programming, (IEEE 54th Annual Conference on Decision and Control. IEEE 54th Annual Conference on Decision and Control, CDC (2015), IEEE), 5915-5919 · Zbl 1034.78008 |
| [23] | Bezanson, Jeff; Edelman, Alan; Karpinski, Stefan; Shah, Viral B., Julia: A fresh approach to numerical computing, SIAM Rev., 59, 1, 65-98 (2017) · Zbl 1356.68030 |
| [24] | Benoît Legat, Cláudio Gomes, blegat/SwitchOnSafety.jl: v0.0.1, May 2019. |
| [25] | Benoît Legat, Marcelo Forets, Christian Schilling, blegat/HybridSystems.jl: v0.3.0, May 2019. |
| [26] | MOSEK ApS, MOSEK optimization suite release 8.1.0.43 (2017), URL: http://docs.mosek.com/8.1/intro.pdf |
| [27] | Benoît Legat, Chris Coey, Robin Deits, Joey Huchette, Amelia Perry, Sum-of-squares optimization in Julia, in: The First Annual JuMP-Dev Workshop, 2017. |
| [28] | Benoît Legat, Raphaël M. Jungers, Pablo A. Parrilo, Paulo Tabuada, Set programming with JuMP, in: The Third Annual JuMP-Dev Workshop, 2019. |
| [29] | Dunning, Iain; Huchette, Joey; Lubin, Miles, JuMP: A modeling language for mathematical optimization, SIAM Rev., 59, 2, 295-320 (2017) · Zbl 1368.90002 |
| [30] | Fukuda, Komei, CDD-A C-Implementation of the Double Description Method (2003), Institut fur Operations Research, ETH Zurich, available via anonymous ftp:ifor13.ethz.ch, directory pub/fukuda/cdd |
| [31] | Benoît Legat, Robin Deits, Oliver Evans, Gustavo Goretkin, Twan Koolen, Joey Huchette, Daisuke Oyama, Marcelo Forets, Guberger, Robert Schwarz, Elliot Saba, Chase Coleman, JuliaPolyhedra/Polyhedra.jl: v0.5.1, May 2019. |
| [32] | Alur, Rajeev; Courcoubetis, Costas; Halbwachs, Nicolas; Henzinger, Thomas A.; Ho, P-H; Nicollin, Xavier; Olivero, Alfredo; Sifakis, Joseph; Yovine, Sergio, The algorithmic analysis of hybrid systems, Theoret. Comput. Sci., 138, 1, 3-34 (1995) · Zbl 0874.68206 |
| [33] | Liberzon, Daniel, Switching in Systems and Control (2012), Springer Science & Business Media · Zbl 1239.49001 |
| [34] | Liberzon, Daniel; Trenn, Stephan, Switched nonlinear differential algebraic equations: Solution theory, Lyapunov functions, and stability, Automatica, 48, 5, 954-963 (2012) · Zbl 1246.93064 |
| [35] | Owens, David H.; Debeljkovic, Dragutin Lj, Consistency and Liapunov stability of linear descriptor systems: A geometric analysis, IMA J. Math. Control Inform., 2, 2, 139-151 (1985) · Zbl 0637.93051 |
| [36] | Lasserre, Jean Bernard, Moments, Positive Polynomials and Their Applications (2009), World Scientific · Zbl 1211.90007 |
| [37] | Rockafellar, Ralph Tyrell, Convex Analysis (2015), Princeton University Press |
| [38] | Ziegler, Günter M., Lectures on Polytopes, Vol. 152 (1995), Springer Science & Business Media · Zbl 0823.52002 |
| [39] | Durieu, Cécile; Polyak, Boris T.; Walter, Eric, Trace versus determinant in ellipsoidal outer-bounding, with application to state estimation, IFAC Proc. Vol., 29, 1, 3975-3980 (1996) |
| [40] | Golub, Gene H.; Van Loan, Charles F., Matrix Computations, Vol. 3 (2012), JHU Press · Zbl 1268.65037 |
| [41] | Dabbene, Fabrizio; Henrion, Didier; Lagoa, Constantino M., Simple approximations of semialgebraic sets and their applications to control, Automatica, 78, 110-118 (2017) · Zbl 1357.93058 |
| [42] | Fukuda, Komei, cdd/cdd+ Reference Manual (1999), Institute for Operations Research, ETH-Zentrum |
| [43] | Ahmadi, Amir Ali; Olshevsky, Alex; Parrilo, Pablo A.; Tsitsiklis, John N., NP-hardness of deciding convexity of quartic polynomials and related problems, Math. Program., 137, 1-2, 453-476 (2013) · Zbl 1274.90516 |
| [44] | Magnani, Alessandro; Lall, Sanjay; Boyd, Stephen, Tractable fitting with convex polynomials via sum-of-squares, (Proceedings of the 44th IEEE Conference on Decision and Control, and European Control Conference 2005 (2005), IEEE), 1672-1677 |
| [45] | Nesterov, Yurii, Introductory Lectures on Convex Optimization, Vol. 87 (2004), Springer Science & Business Media · Zbl 1086.90045 |
| [46] | Ben-Tal, Aharon; Nemirovski, Arkadi, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications (2001), SIAM · Zbl 0986.90032 |
| [47] | Helton, J. William; Nie, Jiawang, Semidefinite representation of convex sets, Math. Program., 122, 1, 21-64 (2010) · Zbl 1192.90143 |
| [48] | Willems, Jan C.; Polderman, Jan W., Introduction to Mathematical Systems Theory: A Behavioral Approach, Vol. 26 (2013), Springer Science & Business Media |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
