Abstract
A problem of great interest in the control of hybrid systems is the design of least restrictive controllers for reachability specifications. Controller design typically uses game theoretic methods which compute the region of the state space for which there exists a control such that for all disturbances, an unsafe set is not reached. In general, the computation of the controllers requires the steady state solution of a Hamilton-Jacobi-Isaacs partial differential equation which is very difficult to compute, if it exists. In this paper, we show that for classes of linear systems, the controller synthesis problem is decidable: There exists a computational algorithm which, after a finite number of steps, will exactly compute the least restrictive controller. This result is achieved by a very interesting interaction of results from mathematical logic and optimal control.
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. Maler, and A. Pnueli. Symbolic controller synthesis for discrete and timed systems. In P. Antsaklis, W. Kohn, A. Nerode, and S. Sastry, editors, Hybrid Systems II, volume 999 of Lecture Notes in Computer Science. Springer-Verlag, 1995.
T. Başar and G.J. Olsder. Dynamic Noncooperative Game Theory. Academic Press, 2nd edition, 1995.
A. Church. Logic, arithmetic, and automata. In Proceedings of the International Congress of Mathematics, pages 23–35, 1962.
G.E. Collins and H. Hong. Partial cylindrical algebraic decomposition for quantifier elimination. Journal of Symbolic Computation, 12:299–328, September 1991.
A. Dolzman and T. Sturm. REDLOG: Computer algebra meets computer logic. ACM SIGSAM Bulletin, 31(2):2–9, June 1997.
D.E. Kirk. Optimal Control Theory, An Introduction. Prentice Hall, 1970.
G. Lafferriere, G. J. Pappas, and S. Sastry. O-minimal hybrid systems. Mathematics of Control, Signals, and Systems. To appear.
G. Lafferriere, G. J. Pappas, and S. Yovine. A new class of decidable hybrid systems. In Hybrid Systems: Computation and Control, volume 1569 of Lecture Notes in Computer Science, pages 137–151. Springer Verlag, 1999.
G. Lafferriere, G. J. Pappas, and Sergio Yovine. Reachability computation for linear hybrid systems. In Proceedings of the 14th IFAC World Congress, volume E, pages 7–12, Beijing, P.R. China, July 1999.
J. Lewin. Differential Games. Springer Verlag, 1994.
J. Lygeros, D.N. Godbole, and S. Sastry. Verified hybrid controllers for automated vehicles. IEEE Transactions on Automatic Control, 43(4):522–539, April 1998.
J. Lygeros, C. Tomlin, and S.S. Sastry. Controllers for reachability specifications for hybrid systems. Automatica, 35(3):349–370, March 1999.
L.S. Pontryagin, V. Boltyanskii, R. Gamkrelidze, and E. Mischenko. The Mathematical Theory of Optimal Processes. John Wiley & Sons, 1962.
A. Tarski. A decision method for elementary algebra and geometry. University of California Press, second edition, 1951.
W. Thomas. On the synthesis of strategies in infinite games. In Ernst W. Mayr and Claude Puech, editors, Proceedings of STACS 95, Volume 900 of LNCS, pages 1–13. Springer Verlag, Munich, 1995.
C. Tomlin, G. J. Pappas, and S. Sastry. Conflict resolution for air traffic management: A study in muti-agent hybrid systems. IEEE Transactions on Automatic Control, 43(4):509–521, April 1998.
L. van den Dries. Tame Topology and o-minimal structures. Cambridge University Press, 1998.
H. Wong-Toi. The synthesis of controllers for linear hybrid automata. In Proceedings of the 36th IEEE Conference on Decision and Control, San Diego, CA, December 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shakernia, O., Pappas, G.J., Sastry, S. (2000). Decidable Controller Synthesis for Classes of Linear Systems. In: Lynch, N., Krogh, B.H. (eds) Hybrid Systems: Computation and Control. HSCC 2000. Lecture Notes in Computer Science, vol 1790. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46430-1_34
Download citation
DOI: https://doi.org/10.1007/3-540-46430-1_34
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67259-3
Online ISBN: 978-3-540-46430-3
eBook Packages: Springer Book Archive