Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Euler’s Method Applied to the Control of Switched Systems Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Optimal Control for Multi-mode Systems with Discrete Costs

Authors : Mahmoud A. A. Mousa, Sven Schewe, Dominik Wojtczak

Published in: Formal Modeling and Analysis of Timed Systems

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper studies optimal time-bounded control in multi-mode systems with discrete costs. Multi-mode systems are an important subclass of linear hybrid systems, in which there are no guards on transitions and all invariants are global. Each state has a continuous cost attached to it, which is linear in the sojourn time, while a discrete cost is attached to each transition taken. We show that an optimal control for this model can be computed in NExpTime and approximated in PSpace. We also show that the one-dimensional case is simpler: although the problem is NP-complete (and in LogSpace for an infinite time horizon), we develop an FPTAS for finding an approximate solution.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Optimal Reachability in Cost Time Petri Nets
next chapter Augmented Complex Zonotopes for Computing Invariants of Affine Hybrid Systems
Literature
1.
2.
3.
4.
Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T.A., Ho, P.-H., Nicollin, X., Olivero, A., Sifakis, J., Yovine, S.: The algorithmic analysis of hybrid systems. Theor. Comput. Sci. 138(1), 3–34 (1995)MathSciNetCrossRefMATH
5.
Alur, R., Courcoubetis, C., Henzinger, T.A., Ho, P.-H.: Hybrid automata: An algorithmic approach to the specification and verification of hybrid systems. In: Grossman, R.L., Nerode, A., Ravn, A.P., Rischel, H. (eds.) HS 1991-1992. LNCS, vol. 736, pp. 209–229. Springer, Heidelberg (1993). doi:10.​1007/​3-540-57318-6_​30 CrossRef
6.
7.
Alur, R., Forejt, V., Moarref, S., Trivedi, A.: Safe schedulability of bounded-rate multi-mode systems. In: HSCC, pp. 243–252. ACM (2013)
8.
Alur, R., Trivedi, A., Wojtczak, D.: Optimal scheduling for constant-rate multi-mode systems. computation and control. In: Proceedings of Hybrid Systems (2012)
9.
Asarin, E., Mysore, V.P., Pnueli, A., Schneider, G.: Low dimensional hybrid systems – decidable, undecidable, don’t know. Inf. Comput. 211, 138–159 (2012)MathSciNetCrossRefMATH
10.
Bouyer, P.: Weighted timed automata: model-checking and games. Electron. Notes Theor. Comput. Sci. 158, 3–17 (2006)CrossRefMATH
11.
Bouyer, P., Brihaye, T., Jurdziński, M., Lazić, R., Rutkowski, M.: Average-price and reachability-price games on hybrid automata with strong resets. In: Cassez, F., Jard, C. (eds.) FORMATS 2008. LNCS, vol. 5215, pp. 63–77. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-85778-5_​6 CrossRef
12.
13.
Chiu, A., Davida, G.I., Litow, B.E.: Division in logspace-uniform \({NC}^{\text{1 }}\). ITA 35(3), 259–275 (2001)MathSciNetMATH
14.
David, A., Du, D., Guldstrand Larsen, K., Legay, A., Mikučionis, M.: Optimizing control strategy using statistical model checking. In: Brat, G., Rungta, N., Venet, A. (eds.) NFM 2013. LNCS, vol. 7871, pp. 352–367. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38088-4_​24 CrossRef
15.
David, A., Jensen, P.G., Larsen, K.G., Mikučionis, M., Taankvist, J.H.: Uppaal Stratego. In: Baier, C., Tinelli, C. (eds.) TACAS 2015. LNCS, vol. 9035, pp. 206–211. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-46681-0_​16
16.
David, A., Larsen, K.G., Legay, A., Mikučionis, M., Wang, Z.: Time for statistical model checking of real-time systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 349–355. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-22110-1_​27 CrossRef
17.
Henzinger, T.A.: The theory of hybrid automata. In: Proceedings of the 11th IEEE LICS 1996 Symposium, Washington, DC (1996)
18.
19.
Laroussinie, F., Markey, N., Schnoebelen, P.: Model checking timed automata with one or two clocks. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 387–401. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-28644-8_​25 CrossRef
20.
Larsen, K.G., Mikučionis, M., Muñiz, M., Srba, J., Taankvist, J.H.: Online and compositional learning of controllers with application to floor heating. In: Chechik, M., Raskin, J.-F. (eds.) TACAS 2016. LNCS, vol. 9636, pp. 244–259. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49674-9_​14 CrossRef
21.
Li, B., Alleyne, A.G.: Optimal on-off control of an air conditioning and refrigeration system. In: American Control Conference (ACC), pp. 5892–5897. IEEE (2010)
22.
Mousa, M.A.A., Schewe, S., Wojtczak, D.: Optimal control for simple linear hybrid systems. In: 23rd International Symposium on Temporal Representation and Reasoning (TIME), pp. 12–20. IEEE (2016)
23.
24.
Nghiem, T.X., Behl, M., Mangharam, R., Pappas, G.J.: Green scheduling of control systems for peak demand reduction. In: 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), pp. 5131–5136. IEEE (2011)
25.
Nghiem, T.X., Pappas, G.J., Mangharam, R.: Event-based green scheduling of radiant systems in buildings. In: American Control Conference (ACC), pp. 455–460. IEEE (2013)
26.
Oldewurtel, F., Ulbig, A., Parisio, A., Andersson, G., Morari, M.: Reducing peak electricity demand in building climate control using real-time pricing and model predictive control. In: 2010 49th IEEE Conference on Decision and Control (CDC), pp. 1927–1932. IEEE (2010)
27.
Pérez-Lombard, L., Ortiz, J., Pout, C.: A review on buildings energy consumption information. Energy Build. 40(3), 394–398 (2008)CrossRef
28.
Metadata
Title
Optimal Control for Multi-mode Systems with Discrete Costs
Authors
Mahmoud A. A. Mousa
Sven Schewe
Dominik Wojtczak
Copyright Year
2017
Book
Formal Modeling and Analysis of Timed Systems

Print ISBN: 978-3-319-65764-6

Electronic ISBN: 978-3-319-65765-3

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-65765-3_5

Premium Partner

    Image Credits