Abstract
Computing reachable sets is an essential step in most analysis and synthesis techniques for hybrid systems. The representation of these sets has a deciding impact on the computational complexity and thus the applicability of these techniques. This paper presents a new approach for approximating reachable sets using oriented rectangular hulls (ORHs), the orientations of which are determined by singular value decompositions of sample covariance matrices for sets of reachable states. The orientations keep the over-approximation of the reachable sets small in most cases with a complexity of low polynomial order with respect to the dimension of the continuous state space. We show how the use of ORHs can improve the efficiency of reachable set computation significantly for hybrid systems with nonlinear continuous dynamics.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T.A., Ho, P.H., Nicollin, X., Olivero, A., Sifakis, J., Yovine, S.: The algorithmic analysis of hybrid systems. Theoretical Computer Science 138 (1995) 3–34
Bemporad, A., Morari, M.: Verification of hybrid systems via mathematical programming. In: Hybrid Systems: Computation and Control. Volume 1569 of LNCS., Springer (1999) 31–45
Greenstreet, M.R., Mitchell, I.: Reachability analysis using polygonal projections. In: Hybrid Systems: Computation and Control. Volume 1569 of LNCS., Springer (1999) 103–116
Asarin, E., Bournez, O., Dang, T., Maler, O.: Approximate reachability analysis of piecewise-linear dynamical systems. In: Hybrid Systems — Computation and Control. Volume 1790 of LNCS., Springer (2000) 20–31
Wong-Toi, H.: The synthesis of conbtrollers for linear hybrid automata. In: Proc. 36th IEEE Conf. Decision and Control. (1997) 4607–4612
Cury, J., Krogh, B., Niinomi, T.: Synthesis of supervisory controller for hybrid systems based on approximating automata. IEEE Transaction on Automatic Control 43 (1998) 564–569
Asarin, E., Bournez, O., Dang, T., Maler, O., Pnueli, A.: Effective synthesis of switching controllers for linear systems. Proc. of the IEEE 88 (2000) 1011–1025
Tomlin, C., Lygeros, J., Sastry, S.: A game theoretic approach to controller design for hybrid systems. Proc. of the IEEE 88 (2000) 949–970
Xia, H., Pang, Y., Trontis, A., Spathopoulos, M.: Eventuality synthesis for controlled linear automata. In: Proc. American Control Conf. (2002) 160–165
Mitchell, I., Bayen, A., Tomlin, C.: Computing reachable sets for continuous dynamic games using level set methods. IEEE Trans. on Automatic Control (2003) to appear
Bournez, K., Maler, O., Pnueli, A.: Orthogonal polyhedra: Representation and computation. In: Hybrid Systems: Computation and Control. Volume 1569 of LNCS., Springer (1999) 46–60
Puri, A., Borkar, V., Varaiya, P.: ∈-approximations of differential inclusions. In: Hybrid Systems III. Volume 1066 of LNCS., Springer (1996) 363–376
Stursberg, O.: Analysis of switched continuous systems based on discrete approximation. In: Proc. 4th Int. Conf. on Automation of Mixed Processes. (2000) 73–78
Chutinan, A., Krogh, B.: Verification of infinite-state dynamic systems using approximate quotient transition systems. IEEE Trans. on Automatic Control 46 (2001) 1401–1410
Botchkarev, O., Tripakis, S.: Verification of hybrid systems with linear differential inclusions using ellipsoidal approximations. In: Hybrid Systems: Computation and Control. Volume 1790 of LNCS., Springer (2000) 73–88
Kurzhanski, A., Varaiya, P.: Ellipsiodal techniques for reachability analysis. In: Hybrid Systems: Computation and Control. Volume 1790 of LNCS., Springer (2000) 202–214
Chazelle, B.: An optimal convex hull algorithm in any fixed dimension. Discrete Comput. Geom. 10 (1993) 377–409
Avis, D., Bremner, D., Seidel, R.: How good are convex hull algorithms? Comput. Geom.: Theory and Appl. 7 (1997) 265–301
Henzinger, T.A., Kopke, P.W., Puri, A., Varaiya, P.: What’s decidable about hybrid automata? Journ. Computer and System Sciences 57 (1998) 94–124
Lafferriere, G., Pappas, G.J., Yovine, S.: A new class of decidable hybrid systems. In: Hybrid Systems: Computation and Control. Volume 1569 of LNCS., Springer (1999) 137–151
Pearson, K.: On lines and panes of closest fit to systems of points in space. Phil. Mag. 6 (1901)
Hotelling, H.: Analysis of a complex of statistical variables into principal components. J. Educ. Psychol. 24 (1933) 417–441
Jolliffe, I., ed.: Principal Component Analysis. Series in Statistics. Springer (1986)
Barequet, G., Har-Peled, S.: Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. of Algorithms 38 (2001) 99–109
Klema, V.C., Laub, A.J.: The singular value decomposition: its computation and some applications. IEEE Trans. on Automatic Control 25 (1980) 164–176
Barber, C., Dobkin, D., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Trans. on Mathematical Software 22 (1996) 469–483
Vandenberghe, L., Boyd, S., Wu, S.: Determinant maximization with linear matrix inequalities. SIAM Journ. Matrix Analysis and Applications 19 (1998) 499–533
Chutinan, A., Krogh, B.H.: Computational techniques for hybrid system verification. IEEE Trans. on Automatic Control 48 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stursberg, O., Krogh, B.H. (2003). Efficient Representation and Computation of Reachable Sets for Hybrid Systems. In: Maler, O., Pnueli, A. (eds) Hybrid Systems: Computation and Control. HSCC 2003. Lecture Notes in Computer Science, vol 2623. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36580-X_35
Download citation
DOI: https://doi.org/10.1007/3-540-36580-X_35
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00913-9
Online ISBN: 978-3-540-36580-8
eBook Packages: Springer Book Archive