On the well-posedness, equivalency, and low-complexity translation techniques of discrete-time hybrid automaton and piecewise affine systems

Document Type : Article

Authors

1 Department of Electrical Engineering, Sahand University of Technology, Sahand New Town, Tabriz, P.O. Box 51335-1996, Iran

2 Department of Electrical Engineering, Sharif University of Technology, Tehran, P.O. Box 11365-9363, Iran

Abstract

The main contribution of this paper is to present the systematic and low-complexity translation techniques between
a class of hybrid systems referred to as automaton-based DHA and piecewise affine (PWA) systems. As an starting
point the general modeling framework of the automaton-based DHA is represented which models the controlled and
uncontrolled switching phenomena between linear continuous dynamics including discrete and continuous states,
inputs and outputs. The basic theoretical definitions on the state trajectories of the proposed DHA with forward
and backward evolutions which yield forward and backward piecewise affine (FPWA and BPWA) systems are given.
Next, the well-posedness and equivalency properties are proposed and the sufficient conditions under which the wellposedness property is achieved with the automaton-based DHA and PWA systems are given. It is shown that the
graphical structure of the proposed automaton-based DHA makes it possible to obtain analytically the equivalent PWA
system with a polynomial complexity in contrast to the existing numerical translation techniques via decomposed
structure of the DHA with an exponential complexity. Examples are presented to confirm the effectiveness of the
proposed translation techniques.

Keywords

References

References:
[1] Cassandras, C.G. and Lafortune, S. ”Introduction to discrete event systems”, 2nd edition, Springer Berlin Heidelberg (2008).
[2] Pcolka M., Zacekova, E., Celikovsky, S. and Sebek, M. ”Toward a smart car: hybrid nonlinear predictive controller with adaptive horizon”, IEEE Trans. Control Syst. Technol., 26(6), pp. 1970-1981 (2017).
[3] Tantawy A., Koutsoukos, X. and Biswas, G. ”Aircraft power generators: hybrid modeling and simulation for fault detection”, IEEE Trans. Aerosp. Electron. Syst., 48(1), pp. 552–571 (2012).
[4] Soler, M., Kamgarpour, M., Lloret, J. and Lygeros, J. ”A hybrid optimal control approach to fuel-efficient aircraft conflict avoidance”, IEEE Trans. Intell. Transp. Syst., 17(7), pp. 1826–1838 (2016).
[5] Manon, P., Valentin-Roubinet, C. and Gilles, G. ”Optimal control of hybrid dynamical systems: application in process engineering”, Control Eng. Pract., 10(2), pp. 133-149 (2002).
[6] Lee, J., Bohacek, S., Hespanha, J.P. and Obraczka, K. ”Modeling communication networks with hybrid systems”, IEEE/ACM Trans. Netw., 15(3), pp. 630-643 (2007).
[7] Ding, J., and Gillula, J.H., Huang, H., Vitus, M.P., Zhang, W. and Tomlin, C.J. ”Hybrid systems in robotics”, IEEE Robot. Autom. Mag., 18(3), pp. 33-43 (2011).
[8] Bortolussi, L. and Policriti, A. ”Hybrid systems and biology” In Formal Methods for Computational Systems Biology: 8th International School on Formal Methods for the Design of Computer, Communication, and Software Systems, Advanced Lectures, Springer Berlin Heidel- berg, pp. 424-448 (2008).
[9] Theunisse, T.A.F., Chai, J., Sanfelice, R.G., and Heemels, W.P.M.H. ”Robust global stabilization of the DC-DC boost converter via hybrid control”, IEEE Trans. Circuits Syst. I, 62(4), pp. 1052-1061 (2015).
[10] Moarref M. and Rodrigues, L. ”Piecewise affine networked control systems” IEEE Trans. Control Netw. Syst., 3(2), pp. 173-181 (2016).
[11] Fourlas, G.K., Kyriakopoulos, K.J., and Vournas, C.D. ”Hybrid systems modeling for power systems”, IEEE Circuits Syst. Mag., 4(3), pp. 16-23 (2004).
[12] Kowalewski, S. ”Introduction to the analysis and verification of hybrid systems”, In Modelling, Analysis, and Design of Hybrid Systems, S. Engell, G. Frehse and E. Schnieder, Eds., pp. 153–171, Springer Berlin Heidelberg (2002).
[13] Belta, C., Yordanov, B. and Gol, E.A. ”Formal methods for discrete-time dynamical systems”, J. Kacprzyk, Ed., Springer International Publishing (2017).
[14] Borrelli, F., Baoti´c, M. and Bemporad, A. and Morari, M. ”Dynamic programming for constrained optimal control of discrete-time linear hybrid systems”, Automatica, 41(10), pp. 1709–1721 (2005).
[15] Karer, G. and ˇ Skrjanc, I. ”Introduction to predictive control of complex systems”, In Predictive approaches to control of complex systems, Springer Berlin Heidelberg, pp. 147–156 (2013).
[16] Johansson, K.H., Egerstedt, M., Lygeros, J. and Sastry, S. ”On the regularization of zeno hybrid automata”, Syst. Control Lett., 38, pp. 141–150 (1999).
[17] Floudas, C.A. and Lin, X. ”Continuous-time versus discrete-time approaches for scheduling of chemical processes: a review”, Comput. Chem. Eng., 28(11), pp. 2109 - 2129 (2004).
[18] Imura, J.-ichi ”Optimal control of sampled-data piecewise affine systems”, Automatica, 40(4), pp. 661-669 (2004).
[19] Stauner, T. ”Discrete-Time Refinement of Hybrid Automata”, Hybrid Systems: Computation and Control, C.J. Tomlin and M.R. Greenstreet, Eds., pp. 407–420, Springer Berlin Heidelberg (2002).
[20] Zaytoon, J. ”Hybrid Dynamic Systems: overview and discussion on verification methods”, Informatics in Control, Automation and Robotics II, J. Filipe, J.-L. Ferrier, J. A. Cetto and M. Carvalho, Eds., pp. 17–26, Springer Netherlands (2007).
[21] Heemels,W.P.H.M., De Schutter, B. and Bemporad, A. ”Equivalence of hybrid dynamical models”, Automatica, 37(7), pp. 1085-1091 (2001).
[22] Bemporad, A. and Morari, M. ”Control of systems integrating logic, dynamic and constraints”, Automatica, 35(3), pp. 407-427 (1999).
[23] Hejri, M., Giua, A., and Mokhtari, H. ”On the complexity and dynamical properties of mixed logical dynamical systems via an automaton- based realization of discrete-time hybrid automaton”, Int. J. of Robust Nonlin., 28(16), pp. 4713–4746 (2018).
[24] Heemels, W.P.M.H., Schumacher, J.M. and Weiland, S. ”Linear complementarity systems”, SIAM J. Appl. Math., 60(4), pp. 1234-1269 (2000).
[25] De Schutter, B. and DeMoor, B. ”The extended linear complementarity problem and the modeling and analysis of hybrid systems”, Lecture Notes in Computer Science, P. Antsaklis, W. Kohn, M. Lemmon, A. Nerode and S. Sastry, Eds., pp. 70–85 (1999).
[26] De Schutter, B. and van den Boom, T. ”Model predictive control for max-plus-linear systems”, American Control Conference, pp. 4046-4050 (2000).
[27] Sontag, E.D. ”Nonlinear regulation: the piecewise linear approach”, IEEE Trans. Autom. Control, 26(2), pp. 346-358 (1981).
[28] Ferrari-Trecate, G., Cuzzola, F.A., Mignone, D. and Morari M. ”Analysis of discrete-time piecewise affine and hybrid systems”, Automatica, 38(12), pp. 2139–2146 (2002).
[29] Johansson, M. and Rantzer, A. ”Computation of piecewise quadratic Lyapunov functions for hybrid systems”, IEEE Trans. Autom. Control, 43(4), pp. 555-559 (1998).
[30] Cuzzola, F.A. and Morari, M. ”A generalized approach for analysis and control of discrete-time piecewise affine and hybrid systems”, M.D. Di Benedetto and A. Sangiovanni-Vincentelli, Eds., Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001, Rome, Italy, Springer Berlin Heidelberg, pp. 189–203 (2001).
[31] Hajiahmadi, M., De Schutter, B. and Hellendoorn, H., ”Design of Stabilizing Switching Laws for Mixed Switched Affine Systems”, IEEE Trans. Autom. Control, 61(6), pp. 1676-1681 (2016).
[32] van der Schaft, A.J. and Schumacher, J.M. ”Complementarity modeling of hybrid systems”, IEEE Trans. Autom. Control, 43(4), pp. 483-490 (1998).
[33] Lygeros, J., Johansson, K.H., Simic, S.N., Zhang, J. and Sastry, S.S. ”Dynamical properties of hybrid automata”, IEEE Trans. Autom. Control, 48(1), pp. 2-17 (2003).
[34] Camacho, E.F., Ramirez, D.R., Limon D., Monuz de la Pena, D. and Alamo T. ”Model predictive control techniques for hybrid systems”, Annu. Rev. Control, 34, pp. 21–31 (2010).
[35] Torrisi, F.D. and Bemporad, A. ”HYSDEL-a tool for generating computational hybrid models for analysis and synthesis problems”, IEEE Trans. Control Syst. Technol., 12(2), pp. 235-249 (2004).
[36] Borrelli, F., Bemprad, A. and Morari, M. ”Predictive control for linear and hybrid systems”, Cambridge University Press (2017).
[37] Bemporad, A., Ferrari-Trecate, G. and Morari, M. ”Observability and controllability of piecewise affine and hybrid systems”, IEEE Trans. Autom. Control, 45(10), pp. 1864-1876 (2000).
[38] Geyer, T., Torrisi, F.D. and Morari, M. ”Efficient Mode Enumeration of Compositional Hybrid Systems”, Hybrid Systems: Computation and Control, O. Maler and A. Pnueli, Eds., Springer Berlin Heidelberg, pp. 216–232 (2003).
[39] Potocnik, B., Music, G. and Zupancic B., ”A new technique for translating discrete hybrid automata into piecewise affine systems”, Math. Comp. Model. Dyn., 10(1), pp. 41–57 (2004).
[40] Bemporad, A. ”Efficient conversion of mixed logical dynamical systems into an equivalent piecewise affine form”, IEEE Trans. Autom. Control, 49(5), pp. 832–838 (2004).
[41] Geyer, T., Torrisi, F.D. and Morari, M. ”Efficient mode enumeration of compositional hybrid systems”, Int. J. Control, 83(2), pp. 313–329 (2010).
[42] Groot, N., De Schutter, B. and Hellendoorn, H. ”Integrated model predictive traffic and emission control using a piecewise-affine approach”, IEEE Trans. Intell. Transp. Syst., 14(2), pp. 587–598 (2013).
[43] Ferrari-Trecate, G., Cuzzola, F.A. and Morari M. ”Lagrange stability and performance analysis of discrete-time piecewise affine systems with logic states”, Int. J. Control, 76(16), pp. 1585–1598 (2003).
[44] Ferrari-Trecate, G., Cuzzola, F.A. and Morari, M. ”An LMI approach for H-infinity analysis and control of discrete-time piecewise affine systems”, Int. J. Control, 75(16-17), pp. 1293–1301 (2002).
[45] Mignone, D., Ferrari-Trecate, G. and Morari, M. ”Stability and stabilization of piecewise affine and hybrid systems: an LMI approach”, Proceedings of the 39th IEEE Conference on Decision and Control, 1, pp. 504-509 (2000).
[46] Johansson, M. ”Piecewise linear control systems: a computational approach”, Springer (2003).
[47] Xu, J. and Xie, L. ”Control and estimation of piecewise affine systems”, Woodhead publishing (2013).
[48] Christophersen, F. ”Optimal control of constrained piecewise affine systems”, M. Thoma and M. Morari, Eds., Springer Berlin Heidelberg (2007).
[49] Sontag, E.D. ”Interconnected automata and linear systems: a theoretical framework in discrete-time”, Proceedings of the DIMACS/SYCON workshop on Hybrid systems III: verification and control, Springer-Verlag New York, pp. 436–448 (1996).
[50] Cairano, S. and Bemporad, A. ”Equivalent piecewise affine models of linear hybrid automata”, IEEE Trans. Autom. Control, 55(2), pp. 498–502 (2010).
[51] Henzinger, T.A. ”The theory of hybrid automata”, Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science (LICS ’96), New Brunswick, pp. 278–292 (1996).
[52] Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T.A., Ho, P.-H.,Nicollin, X., Olivero, A., Sifakis, J. and Yovine, S. ”The algorithmic analysis of hybrid systems”, Theor. Comput. Sci., 138(1), pp. 3–34 (1995).
[53] Alur, R., Courcoubetis, C., Henzinger, T.A. and Ho, P.-H. ”Hybrid automata: An algorithmic approach to the specification and verification of hybrid systems”, Hybrid Systems, pp. 209–229, Springer Berlin Heidelberg (1993).
[54] Nicollin, X., Olivero, A., Sifakis, J., and Yovine, S. ”An approach to the description and analysis of hybrid systems”, In Hybrid Systems, R.L. Grossman, A. Nerode, A. P. Ravn and H. Rischel, Eds., pp. 149–178, Springer Berlin Heidelberg (1993).
[55] Lygeros, J., Godbole, D.N. and Sastry, S.S. ”Verified hybrid controllers for automated vehicles”, IEEE Trans. Autom. Control, 43(4), pp. 522-539 (1998).
[56] Stursberg, O., Panek, S., Till, J. and Engell, S., ”Generation of optimal control policies for systems with switched hybrid dynamics”, Mod- elling, Analysis, and Design of Hybrid Systems, S. Engell, G. Frehse and E. Schnieder, Eds., pp. 337–352, Springer Berlin Heidelberg (2002).
[57] Stursberg, O. and Engell, S. ”Optimal control of switched continuous systems using mixed-integer programmings”, IFAC Proceedings Vol- umes, 35(1), pp. 433-438 (2002).
[58] Stursberg, O. and Panek, S. ”Control of switched hybrid systems based on disjunctive formulations”, Hybrid Systems: Computation and Control, C.J. Tomlin and M. R. Greenstreet, Eds., Springer Berlin Heidelberg, pp. 421–435 (2002).
[59] Pang, Y. and Spathopoulos, M.P. ”Time-optimal control for discrete-time hybrid automata”, Int. J. Control, 78(11), pp. 847-863 (2005).
[60] Zoncu M., Balluchi, A., Sangiovanni-Vicentelli, A.L., and Bicchi, A. ”On the stabilization of linear discrete-time hybrid automata”, 42nd IEEE International Conference on Decision and Control, pp. 1147-1152 (2003).
[61] Seatzu, C., Gromov, D., Raisch, J., Corona, D. and Giua, A. ”Optimal control of discrete-time hybrid automata under safety and liveness constraints”, Nonlinear Anal.-Theor., 65(6), pp. 1188-1210 (2006).
[62] Hejri, M. ”Hybrid modeling and control of power electrinic converters”, Ph.D Thesis, Sharif University of Technology Cotutorship with University of Cagliari, Iran and Italy (2010).
[63] Hejri, M. and Giua, A. ”Hybrid modeling and control of switching DC-DC converters via MLD systems”, IEEE 7th International Conference on Automation Science and Engineering, Trieste, Italy (2011).
[64] Hejri, M. and Mokhtari, H. ”Hybrid modeling and control of a DC-DC boost converter via Extended Mixed Logical Dynamical systems (EMLDs)”, Power Electronics, Drive Systems and Technologies Conference (PEDSTC), Tehran, Iran, pp. 373–378 (2014).
[65] Bemporad, A. ”An efficient technique for translating mixed logical dynamical systems into piecewise affine systems”, 41th IEEE Conf. on Decision and Control, pp. 1970-1975 (2002).
[66] Xia, X. ”Well posedness of piecewise-linear systems with multiple modes and multiple criteria”, IEEE Trans. Autom. Control, 47(10), pp. 1716–1720 (2002).
[67] Sahan, G. and Eldem, V. ”Well posedness conditions for Bimodal Piecewise Affine Systems”, Syst. Control Lett., 83, pp. 9–18 (2015).
[68] Ferrari-Trecate, G., Cuzzola, F.A. and Morari, M. ”Analysis of Discrete-Time PWA Systems with Logic States”, Hybrid Systems: Computa- tion and Control, C.J. Tomlin, and M.R. Greenstreet, Eds., pp. 194–208, Springer Berlin Heidelberg (2002).
[69] Bemporad, A. and Fukuda, K. and Torrisi, F.D. ”Convexity recognition of the union of polyhedra”, Computational Geometry, 18(3), pp. 141-154 (2001).
[70] Branicky, M.S., Borkar, V.S. and Mitter, S.K., ”A unified framework for hybrid control: model and optimal control theory”, IEEE Trans. Autom. Control, 43(1), pp. 31–45 (1998).
[71] Imura, J.-ichi and van der Schaft, A. ”Characterization of well-posedness of piecewise-linear systems”, IEEE Trans. Autom. Control, 45(9), 34 pp. 1600–1619 (2000).
[72] Lazar M., Heemels, W.P.M.H., Weiland, S. and Bemporad, A. ”Stabilizing model predictive control of hybrid systems”, IEEE Trans. Autom. Control, 51(11), pp. 1813–1818 (2006).
[73] Lin, H. and Antsaklis, P.J. ”Stability and stabilizability of switched linear systems: a survay of recent results”, IEEE Trans. Autom. Control, 54(2), pp. 308–322 (2009).
[74] Sindareh, Esfahani P. and Kurt, Pieper J. ”H∞ model predictive control for constrained discrete-time piecewise affine systems”, Int. J. of Robust Nonlin., 28(6), pp. 1973–1995 (2017).
Scientia Iranica
Volume 29, Issue 2
Transactions on Computer Science & Engineering and Electrical Engineering (D)
March and April 2022
Pages 693-726

Files

History

  • Receive Date: 20 April 2019
  • Revise Date: 26 August 2019
  • Accept Date: 07 October 2019

Share

How to cite

Statistics