Abstract
In the literature, we find several formulations of the control problem for timed and hybrid systems.We argue that formulations where a controller can cause an action at any point in dense (rational or real) time are problematic, by presenting an example where the controller must act faster and faster, yet causes no Zeno effects (say, the control actions are at times 0, 1 2, 1, 11 4, 2, 21 8, 3, 31 16, ... ). Such a controller is, of course, not implementable in software. Such controllers are avoided by formulations where the controller can cause actions only at discrete (integer) points in time. While the resulting control problem is wellunderstood if the time unit, or “sampling rate” of the controller, is fixed a priori, we define a novel, stronger formulation: the discrete-time control problem with unknown sampling rate asks if a sampling controller exists for some sampling rate. We prove that this problem is undecidable even in the special case of timed automata.
Partially supported by the FNRS, Belgium, under grant 1.5.096.01.
Partially supported by the DARPA SEC grant F33615-C-98-3614, the AFOSR MURI grant F49620-00-1-0327, the NSF Theory grant CCR-9988172, and the MARCO GSRC grant 98-DT-660.
Partially supported by a “Crédit aux chercheurs” from the Belgian National Fund for Scientific Research.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Asarin, O. Bournier, T. Dang, O. Maler, and A. Pnueli. Effective synthesis of switching controllers for linear systems. In Proc. IEEE, 88:1011–1025, 2000.
R. Alur, C. Courcoubetis, N. Halbwachs, T.A. Henzinger, P.-H. Ho, X. Nicollin, A. Olivero, J. Sifakis, and S. Yovine. The algorithmic analysis of hybrid systems. Theoretical Computer Science, 138:3–34, 1995.
R. Alur and D.L. Dill. A theory of timed automata. Theoretical Computer Science, 126:183–235, 1994.
E. Asarin, O. Maler, and A. Pnueli. Symbolic controller synthesis for discrete and timed systems. In Hybrid Systems II, LNCS 999, pp. 1–20. Springer, 1995.
E. Asarin, O. Maler, A. Pnueli, and J. Sifakis. Controller synthesis for timed automata. In IFAC Symp. System Structure and Control, pp. 469–474. Elsevier, 1998.
L. de Alfaro, T.A. Henzinger, and R. Majumdar. Symbolic algorithms for infinite-state games. In CONCUR: Concurrency Theory, LNCS 2154, pp. 536–550. Springer, 2001.
T.A. Henzinger, B. Horowitz, and R. Majumdar. Rectangular hybrid games. In CONCUR: Concurrency Theory, LNCS 1664, pp. 320–335. Springer, 1999.
T.A. Henzinger and P.W. Kopke. Discrete-time control for rectangular hybrid automata. Theoretical Computer Science, 221:369–392, 1999.
T.A. Henzinger, P.W. Kopke, A. Puri, and P. Varaiya. What’s decidable about hybrid automata? J. Computer and System Sciences, 57:94–124, 1998.
T.A. Henzinger and J.-F. Raskin. Robust undecidability of real-time and hybrid systems. In Hybrid Systems: Computation and Control, LNCS 1790, pp. 145–159. Springer, 2000.
G. Hoffmann and H. Wong-Toi. The input-output control of real-time discreteevent systems. In RTSS: Real-time Systems Symp., pp. 256–265. IEEE, 1992.
O. Maler, A. Pnueli, and J. Sifakis. On the synthesis of discrete controllers for timed systems. In STACS: Theoretical Aspects of Computer Science, LNCS 900, pp. 229–242. Springer, 1995.
C. Tomlin, J. Lygeros, and S. Sastry. A game-theoretic approach to controller design for hybrid systems. In Proc. IEEE, 88:949–970, 2000.
H. Wong-Toi. The synthesis of controllers for linear hybrid automata. In CDC: Conf. Decision and Control, pp. 4607–4612. IEEE, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cassez, F., Henzinger, T.A., Raskin, JF. (2002). A Comparison of Control Problems for Timed and Hybrid Systems. In: Tomlin, C.J., Greenstreet, M.R. (eds) Hybrid Systems: Computation and Control. HSCC 2002. Lecture Notes in Computer Science, vol 2289. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45873-5_13
Download citation
DOI: https://doi.org/10.1007/3-540-45873-5_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43321-7
Online ISBN: 978-3-540-45873-9
eBook Packages: Springer Book Archive