TY - GEN
T1 - Optimal control for multi-mode systems with discrete costs
AU - Mousa, M. A. A.
AU - Schewe, Sven
AU - Wojtczak, Dominik
PY - 2017/8/3
Y1 - 2017/8/3
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-85029542655&partnerID=MN8TOARS
U2 - 10.1007/978-3-319-65765-3_5
DO - 10.1007/978-3-319-65765-3_5
M3 - Conference contribution
SN - 9783319657646
T3 - Lecture Notes in Computer Science
SP - 77
EP - 96
BT - Formal Modeling and Analysis of Timed Systems. FORMATS 2017
PB - Springer
ER -