Optimal Control for Multi-Mode Systems

 In this talk I will survey the results for optimal
(time-bounded) control in multi-mode systems, which is a subclass of
linear hybrid systems with no guards on transitions and where all
invariants are global. This model is directly related to
continuous-time Petri Nets as well as Minkowski games. In our model,
each state has a continuous cost attached to it, which is linear in
the sojourn time, and a discrete cost may be attached to each
transition taken. We show that an optimal control problem with no
discrete costs can be solved in polynomial time. In the presence of
discrete costs, the same problem is shown to be NP-hard, but solvable
in NEXPTIME and the optimal cost can be approximated in PSPACE. We
also show that the one-dimensional case is simpler: although the
problem is NP-complete, we develop an FPTAS for finding an approximate
solution.

This talk is based on joint work with Rajeev Alur, Ashutosh Trivedi,
Mahmoud A. Mousa, and Sven Schewe.