Abstract
Approximate simulation relations have recently been introduced as a powerful tool for the approximation of discrete and continuous systems. In this paper, we extend this abstraction framework to hybrid systems. Using the notion of simulation functions, we develop a characterization of approximate simulation relations which can be used for hybrid systems approximation. For several classes of hybrid systems, this characterization leads to effective algorithms for the computation of approximate simulation relations. An application in the context of reachability analysis is shown.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
de Alfaro L, Faella M, Stoelinga M (2004) Linear and branching metrics for quantitative transition systems, ICALP’04, LNCS, vol 3142. Springer, pp 1150–1162
Alur R, Courcoubetis C, Halbwachs N, Henzinger TA, Ho P-H, Nicollin X, Olivero A, Sifakis J, Yovine S (1995) The algorithmic analysis of hybrid systems. Theor Comput Sci 138(1):3–34
Alur R, Henzinger TA, Lafferriere G, Pappas GJ (2000) Discrete abstractions of hybrid systems. In: Proceedings of the IEEE, vol 88(7), pp 971–984
Belta C, Isler V, Pappas GJ (2005) Discrete abstractions for robot planning and control in polygonal environments. IEEE Trans on Robotics 21(5):864–874
Clarke EM, Grumberg O, Peled DA (2000) Model checking. MIT Press
Desharnais J, Gupta V, Jagadeesan R, Panangaden P (2004) Metrics for labelled Markov processes. Theor Comput Sci 318(3):323–354
Fainekos GE, Girard A, Pappas GJ (2007) Hierarchical synthesis of hybrid controllers from temporal logic specifications. Hybrid systems: computation and control, LNCS, vol 4416. Springer, pp 203–216
Freeman RA, Kokotovic PV (1996) Inverse optimality in robust stabilization. SIAM J Control Optim 34(4):1365–1391
Frehse G (2005) PHAVer: algorithmic verification of hybrid systems past hyTech. Hybrid systems: computation and control, LNCS, vol 3414. Springer, pp 258–273
Girard A, Pappas GJ (2007a) Approximation metrics for discrete and continuous systems. IEEE Trans Autom Control 52(5):782–798
Girard A, Pappas GJ (2007b) Approximation bisimulation relations for constrained linear systems. Automatica 43(8):1307–1317
Girard A, Pappas GJ (2005) Approximate bisimulations for nonlinear dynamical systems. In: Proc. IEEE Conference on Decision and Control and European Control Conference. IEEE, pp 684–689, December
Haghverdi E, Tabuada P, Pappas GJ (2005) Bisimulation relations for dynamical, control, and hybrid systems. Theor Comput Sci 342(2–3):229–262
Julius AA (2006) Approximate abstraction of stochastic hybrid automata. Hybrid systems: computation and control, LNCS, vol 3927. Springer, pp 318–332
Julius AA, Girard A, Pappas GJ (2006) Approximate bisimulation for a class of stochastic hybrid systems. In: Proc American Control Conference
Liberzon D, Sontag ED, Wang Y (2002) Universal construction of feedback laws achieving ISS and integral-ISS disturbance attenuation. Syst Control Lett 46:111–127
Milner R (1989) Communication and concurrency. Prentice-Hall
Pappas GJ (2003) Bisimilar linear systems. Automatica 39(12):2035–2047
Pola G, van der Schaft AJ, Di Benedetto MD (2004) Bisimulation theory for switching linear systems. In: Proc of the 43rd IEEE Conference on Decision and Control
Prajna S, Papachristodoulou A, Seiler P, Parrilo PA (2005) SOSTOOLS and its control applications. Positive Polynomials in Control. Springer
Tabuada P (2007) Symbolic models for control systems. Acta Informatica 43(7):477–500
van der Schaft A (2004) Equivalence of dynamical systems by bisimulation. IEEE Trans Autom Control 49(12):2160–2172
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is partially supported by the NSF Presidential Early CAREER (PECASE) Grant 0132716.
Rights and permissions
About this article
Cite this article
Girard, A., Julius, A.A. & Pappas, G.J. Approximate Simulation Relations for Hybrid Systems. Discrete Event Dyn Syst 18, 163–179 (2008). https://doi.org/10.1007/s10626-007-0029-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10626-007-0029-9