Zusammenfassung
Die optimale Steuerung und Regelung hybrider Systeme ist herausfordernd, da sie sprunghafte Änderungen von Zustandsgrößen und die Kombinatorik ereignisdiskreten Verhaltens in die Optimierung von kontinuierlicher Dynamik einbringt. Dieser Beitrag gibt zunächst einen Überblick über die wichtigsten Lösungsverfahren für verschiedene Problemausprägungen. Anschließend wird für den Fall zeitdiskreter hybrider Systeme mit kontinuierlichen und diskreten Stelleingriffen eine neue Lösungsmethode vorgestellt, worin die optimale Lösung durch Verwendung von approximierten Kostenschranken und Nachbarschaftsbeziehungen explorierter Zustände mit relativ geringem Rechenaufwand angenähert wird.
Abstract
The optimal control of hybrid systems is challenging as it adds resets of state variables as well as the combinatorics of discrete-event behavior to the optimization of continuous dynamics. This contribution first provides an overview of the most important methods for different variants of the hybrid optimal control problem. For a problem instance of discrete-time hybrid systems with continuous and discrete controls, the paper then proposes a new technique. In there, the optimal solution is approximated with relatively low computational effort by use of approximated cost bounds and an adjacancy criterion for explored states.
Funding source: European Commission
Award Identifier / Grant number: 643921
Funding statement: Diese Untersuchung wurde zum Teil durch die Europäische Kommission im Rahmen des Projekts UnCoVerCPS (Bewilligung Nr. 643921) gefördert.
About the authors
M. Sc. Zonglin Liu ist wissenschaftlicher Mitarbeiter im Fachgebiet für Regelungs- und Systemtheorie am Fachbereich Elektrotechnik / Informatik an der Universität Kassel. Im Rahmen seiner Forschungstätigkeiten untersucht er Verfahren zur optimalen und prädiktiven Regelung von cyberphysischen Systemen mit Unsicherheiten.
Prof. Dr.-Ing. Olaf Stursberg ist Professor und Fachgebietsleiter für Regelungs- und Systemtheorie im Fachbereich Elektrotechnik / Informatik an der Universität Kassel. Seine Hauptarbeitsgebiete schließen Methoden zur Regelung und Analyse hybrider Systeme, zur optimalen und prädiktiven Regelung vernetzter und hierarchischer Systeme sowie Verfahren zur Regelung stochastischer und unsicherer Systeme ein.
Literatur
1. J. Acevedo and E. Pistikopoulos. An algorithm for multiparametric mixed-integer linear programming problems. Operations Research Letters, 24(3):139–148, 1999.10.1016/S0167-6377(99)00017-6Search in Google Scholar
2. A. Bemporad, F. Borrelli and M. Morari. On the optimal control law for linear discrete time hybrid systems. In Hybrid systems: computation and control, Springer LNCS, pages 105–119, 2002.10.1007/3-540-45873-5_11Search in Google Scholar
3. A. Bemporad and M. Morari. Control of systems integrating logic, dynamics, and constraints. Automatica, 35(3):407–427, 1999.10.1016/S0005-1098(98)00178-2Search in Google Scholar
4. S. Bengea and R. DeCarlo. Optimal control of switching systems. Automatica, 41(1):11–27, 2005.10.1016/S0005-1098(04)00223-7Search in Google Scholar
5. F. Borrelli, M. Baotić, A. Bemporad and M. Morari. Dynamic programming for constrained optimal control of discrete-time linear hybrid systems. Automatica, 41(10):1709–1721, 2005.10.1016/j.automatica.2005.04.017Search in Google Scholar
6. S. Branicky, S. Borkar, and S. Mitter. A unified framework for hybrid control: Model and optimal control theory. IEEE Trans. on Automatic Control, 43(1):31–45, 1998.10.1109/9.654885Search in Google Scholar
7. M. Buss, O. von Stryk, R. Bulirsch and G. Schmidt. Towards hybrid optimal control. at–Automatisierungstechnik, 48(9/2000):448, 2000.10.1524/auto.2000.48.9.448Search in Google Scholar
8. G. Cassandras, L. Pepyne and Y. Wardi. Optimal control of a class of hybrid systems. IEEE Trans. on Automatic Control, 46(3):398–415, 2001.10.1109/9.911417Search in Google Scholar
9. A. Del Pia, S. Dey and M. Molinaro. Mixed-integer quadratic programming is in NP. Mathematical Programming, 162(1–2):225–240, 2017.10.1007/s10107-016-1036-0Search in Google Scholar
10. R. Goebel, R. Sanfelice and A. Teel. Hybrid dynamical systems. IEEE Control Systems Magazine, 29(2):28–93, 2009.10.1109/MCS.2008.931718Search in Google Scholar
11. D. Goerges, M. Izák and S. Liu. Optimal control and scheduling of switched systems. IEEE Trans. on Automatic Control, 56(1):135–140, 2011.10.1109/TAC.2010.2085573Search in Google Scholar
12. H. Gonzalez, R. Vasudevan, M. Kamgarpour, S. S. Sastry, R. Bajcsy and C. J. Tomlin. A descent algorithm for the optimal control of constrained nonlinear switched dynamical systems. In 13th ACM Int. Conf. on Hybrid Systems: Computation and Control, pages 51–60, 2010.10.1145/1755952.1755961Search in Google Scholar
13. D. Groß and O. Stursberg. Distributed predictive control for a class of hybrid systems with event-based communication. IFAC Proceedings, 46(27):383–388, 2013.10.3182/20130925-2-DE-4044.00048Search in Google Scholar
14. S. Hedlund and A. Rantzer. Optimal control of hybrid systems. In 38th IEEE Conf. on Decision and Control, volume 4, pages 3972–3977, 1999.Search in Google Scholar
15. T. A. Henzinger. The Theory of Hybrid Automata. In Proc. 11thIEEE Symp. on Logic in Comp. Science, pages 278–292, 1996.Search in Google Scholar
16. S. Karaman, R. Sanfelice and E. Frazzoli. Optimal control of mixed logical dynamical systems with linear temporal logic specifications. In 47th IEEE Conference on Decision and Control, pages 2117–2122, 2008.10.1109/CDC.2008.4739370Search in Google Scholar
17. C. Kirches, H. G. Bock and S. Leyffer. Modeling mixed-integer constrained optimal control problems in AMPL. IFAC Proceedings, 45(2):1124–1129, 2012.10.3182/20120215-3-AT-3016.00199Search in Google Scholar
18. X. Koutsoukos. Optimal control of stochastic hybrid systems based on locally consistent markov decision processes. In IEEE Mediterrean Conf. on Control and Automation, pages 435–440, 2005.Search in Google Scholar
19. Z. Liu and O. Stursberg. Optimizing online control of constrained systems with switched dynamics. In IEEE European Control Conference, pages 788–794, 2018.10.23919/ECC.2018.8550446Search in Google Scholar
20. N. Lynch, R. Segala and F. Vaandrager. Hybrid I/O Automata. Information and Computation, 185:105–157, 2003.10.1016/S0890-5401(03)00067-1Search in Google Scholar
21. R. T. Meyer, M. Zefran and R. DeCarlo. A comparison of the embedding method with multiparametric programming, mixed-integer programming, gradient-descent and hybrid minimum principle-based methods. IEEE Trans. on Control Systems Technology, 22(5):1784–1800, 2014.10.1109/TCST.2013.2296211Search in Google Scholar
22. B. Passenberg, P. Caines, M. Sobotka, O. Stursberg and M. Buss. The minimum principle for hybrid systems with partitioned state space and unspecified discrete state sequence. In 49th IEEE Conf. on Decision and Control, pages 6666–6673, 2010.10.1109/CDC.2010.5717263Search in Google Scholar
23. B. Passenberg, M. Sobotka, O. Stursberg, M. Buss and P. Caines. An algorithm for discrete state sequence and trajectory optimization for hybrid systems with partitioned state space. In 49th IEEE Conf. on Decision and Control, pages 4223–4229, 2010.10.1109/CDC.2010.5717264Search in Google Scholar
24. L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze and E. F. Mishchenko. The mathematical theory of optimal processes. Interscience Pub., 1962.Search in Google Scholar
25. A. Rantzer. Relaxed dynamic programming in switching systems. IEE Proc. Control Theory and Applications, 153(5):567–574, 2006.10.1049/ip-cta:20050094Search in Google Scholar
26. M. Rungger and O. Stursberg. Optimal control for deterministic hybrid systems using dynamic programming. IFAC Proceedings, 42(17):316–321, 2009.10.3182/20090916-3-ES-3003.00055Search in Google Scholar
27. M. Rungger and O. Stursberg. A numerical method for hybrid optimal control based on dynamic programming. Nonlinear Analysis: Hybrid Systems, 5(2):254–274, 2011.10.1016/j.nahs.2010.09.002Search in Google Scholar
28. M. Shaikh and P. Caines. On the hybrid optimal control problem: theory and algorithms. IEEE Trans. on Automatic Control, 52(9):1587–1603, 2007.10.1109/TAC.2007.904451Search in Google Scholar
29. O. Stursberg. A graph search algorithm for optimal control of hybrid systems. In 43rd IEEE Conference on Decision and Control, volume 2, pages 1412–1417, 2004.10.1109/CDC.2004.1430241Search in Google Scholar
30. O. Stursberg and S. Engell. Optimal control of switched continuous systems using mixed-integer programming. IFAC Proceedings, 35(1):433–438, 2002.10.3182/20020721-6-ES-1901.00560Search in Google Scholar
31. O. Stursberg and S. Panek. Control of switched hybrid systems based on disjunctive formulations. In Hybrid Systems: Computation and Control, volume 2289 of Springer LNCS, pages 421–435, 2002.10.1007/3-540-45873-5_33Search in Google Scholar
32. H. Sussmann. A maximum principle for hybrid optimal control problems. In 38th IEEE Conf. on Decision and Control, volume 1, pages 425–430, 1999.Search in Google Scholar
33. J. Till, S. Engell, S. Panek and O. Stursberg. Empirical complexity analysis of an MILP-approach for optimization of hybrid systems. IFAC Proceedings, 36(6):129–134, 2003.10.1016/S1474-6670(17)36419-4Search in Google Scholar
34. E. Wolff and R. Murray. Optimal control of nonlinear systems with temporal logic specifications. In Robotics Research, volume 114 of Springer Tracts in Advanced Robotics, pages 21–37. Springer, 2016.10.1007/978-3-319-28872-7_2Search in Google Scholar
35. P. Xu, X.and Antsaklis. A dynamic programming approach for optimal control of switched systems. In 39th IEEE Conf. on Decision and Control, volume 2, pages 1822–1827, 2000.Search in Google Scholar
36. W. Zhang and J. Hu. On optimal quadratic regulation for discrete-time switched linear systems. In Hybrid Systems: Computation and Control, Springer LNCS, pages 584–597, 2008.10.1007/978-3-540-78929-1_42Search in Google Scholar
© 2018 Walter de Gruyter GmbH, Berlin/Boston