The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
Computational techniques for the verification of hybrid systems
Abstract
Hybrid system theory lies at the intersection of the fields of engineering control theory and computer science verification. It is defined as the modeling, analysis, and control of systems that involve the interaction of both discrete state systems, represented by finite automata, and continuous state dynamics, represented by differential equations. The embedded autopilot of a modern commercial jet is a prime example of a hybrid system: the autopilot modes correspond to the application of different control laws, and the logic of mode switching is determined by the continuous state dynamics of the aircraft, as well as through interaction with the pilot. To understand the behavior of hybrid systems, to simulate, and to control these systems, theoretical advances, analyses, and numerical tools are needed. In this paper, we first present a general model for a hybrid system along with an overview of methods for verifying continuous and hybrid systems. We describe a particular verification technique for hybrid systems, based on two-person zero-sum game theory for automata and continuous dynamical systems. We then outline a numerical implementation of this technique using level set methods, and we demonstrate its use in the design and analysis of aircraft collision avoidance protocols and in verification of autopilot logic.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Theory of games and economic behavior
(2019) · 100 Years of Math Milestones · doi:10.1090/mbk/121/32 · Cited by 16,632
Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations
Osher, S., & Sethian, J. A. (1988) · Journal of Computational Physics · doi:10.1016/0021-9991(88)90002-2 · Cited by 14,062
Alur, R., & Dill, D. L. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90010-8 · Cited by 6,689
Level Set Methods and Dynamic Implicit Surfaces
Osher, S., & Fedkiw, R. (2003) · Applied Mathematical Sciences · doi:10.1007/b98879 · Cited by 4,951
Efficient implementation of essentially non-oscillatory shock-capturing schemes
Shu, C.-W., & Osher, S. (1988) · Journal of Computational Physics · doi:10.1016/0021-9991(88)90177-5 · Cited by 4,886
Efficient implementation of essentially non-oscillatory shock-capturing schemes, II
Shu, C.-W., & Osher, S. (1989) · Journal of Computational Physics · doi:10.1016/0021-9991(89)90222-2 · Cited by 4,851
Theory of Games and Economic Behavior
N., E., von Neumann, J., & Morgenstern, O. (1945) · The Journal of Philosophy · doi:10.2307/2019327 · Cited by 4,006
Holzmann, G. J. (1997) · IEEE Transactions on Software Engineering · doi:10.1109/32.588521 · Cited by 3,803
(2010) · AIAA Journal · doi:10.2514/152157 · Cited by 3,801
Level Set Methods and Fast Marching Methods
Sethian, J. A. (1999) · Medical Entomology and Zoology · Cited by 3,616
Introduction to Discrete Event Systems
Cassandras, C. G., & Lafortune, S. (2021) · Springer eBooks · doi:10.1007/978-3-030-72274-6 · Cited by 3,342
Doyle, J. C., Francis, B. A., & Tannenbaum, A. (1992) · Cited by 3,085
The control of discrete event systems
Ramadge, P. J. G., & Wonham, W. M. (1989) · Proceedings of the IEEE · doi:10.1109/5.21072 · Cited by 2,937
Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations
Bardi, M., & Capuzzo-Dolcetta, I. (1997) · Birkhäuser Boston eBooks · doi:10.1007/978-0-8176-4755-1 · Cited by 2,758
Symbolic model checking: 1020 States and beyond
Burch, J. R., Clarke, E. M., McMillan, K. L., Dill, D. L., & Hwang, L. J. (1992) · Information and Computation · doi:10.1016/0890-5401(92)90017-a · Cited by 2,703
Theory of Games and Economic Behavior
Wald, A., Neumann, J. V., & Morgenstern, O. (1947) · The Review of Economics and Statistics · doi:10.2307/1925651 · Cited by 2,329
Larsen, K. G., Pettersson, P., & Yi, W. (1997) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s100090050010 · Cited by 2,193
The algorithmic analysis of hybrid systems
Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T. A., Ho, P.-H., Nicollin, X., Olivero, A., Sifakis, J., & Yovine, S. (1995) · Theoretical Computer Science · doi:10.1016/0304-3975(94)00202-t · Cited by 1,876
Henzinger, T. A. (2002) · Proceedings 11th Annual IEEE Symposium on Logic in Computer Science · doi:10.1109/lics.1996.561342 · Cited by 1,837
Sastry, S. (1999) · Interdisciplinary Applied Mathematics · doi:10.1007/978-1-4757-3108-8 · Cited by 1,764
Introduction to Discrete Event Systems
Cassandras, C. G., & Lafortune, S. (1999) · The Kluwer International Series on Discrete Event Dynamic Systems · doi:10.1007/978-1-4757-4070-7 · Cited by 1,699
PVS: A prototype verification system
Owre, S., Rushby, J. M., & Shankar, N. (1992) · Lecture Notes in Computer Science · doi:10.1007/3-540-55602-8_217 · Cited by 1,415
Some properties of viscosity solutions of Hamilton-Jacobi equations
Crandall, M. G., Evans, L. C., & Lions, P.-L. (1984) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1984-0732102-x · Cited by 1,176
A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games
Mitchell, I. M., Bayen, A. M., & Tomlin, C. J. (2005) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2005.851439 · Cited by 1,152
Self-citationHybrid automata: An algorithmic approach to the specification and verification of hybrid systems
Alur, R., Courcoubetis, C., Henzinger, T. A., & Ho, P. H. (1993) · Lecture Notes in Computer Science · doi:10.1007/3-540-57318-6_30 · Cited by 1,106
HYTECH: a model checker for hybrid systems
Henzinger, T. A., Ho, P.-H., & Wong-Toi, H. (1997) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s100090050008 · Cited by 774
Controllers for reachability specifications for hybrid systems
Lygeros, J., Tomlin, C., & Sastry, S. (1999) · Automatica · doi:10.1016/s0005-1098(98)00193-9 · Cited by 608
Self-citationWhat's decidable about hybrid automata?
Henzinger, T. A., Kopke, P. W., Puri, A., & Varaiya, P. P. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225162 · Cited by 520
A game theoretic approach to controller design for hybrid systems
Tomlin, C. J., Lygeros, J., & Shankar Sastry, S. (2000) · Proceedings of the IEEE · doi:10.1109/5.871303 · Cited by 510
Self-citationLynch, N. A., Roberto Segala, C., & Vaandrager, F. (2003) · Information and Computation · doi:10.1016/s0890-5401(03)00067-1 · Cited by 458
Ellipsoidal Techniques for Reachability Analysis
Kurzhanski, A. B., & Varaiya, P. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-46430-1_19 · Cited by 447
Hybrid Models for Motion Control Systems
Brockett, R. W. (1993) · Essays on Control · doi:10.1007/978-1-4612-0313-1_2 · Cited by 375
Approximate Reachability Analysis of Piecewise-Linear Dynamical Systems
Asarin, E., Bournez, O., Dang, T., & Maler, O. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-46430-1_6 · Cited by 336
Models for hybrid systems: Automata, topologies, controllability, observability
Nerode, A., & Kohn, W. (1993) · Lecture Notes in Computer Science · doi:10.1007/3-540-57318-6_35 · Cited by 301
Impulse differential inclusions: a viability approach to hybrid systems
Aubin, J.-P., Lygeros, J., Quincampoix, M., Sastry, S., & Seube, N. (2002) · IEEE Transactions on Automatic Control · doi:10.1109/9.981719 · Cited by 284
Büchi, J. R. (1964) · Journal of Symbolic Logic · doi:10.2307/2270398 · Cited by 232
Some Properties of Viscosity Solutions of Hamilton-Jacobi Equations
Crandall, M. G., Evans, L. C., & Lions, P. L. (1984) · Transactions of the American Mathematical Society · doi:10.2307/1999247 · Cited by 229
Set-Valued Numerical Analysis for Optimal Control and Differential Games
Cardaliaguet, P., Quincampoix, M., & Saint-Pierre, P. (1999) · Stochastic and Differential Games · doi:10.1007/978-1-4612-1592-9_4 · Cited by 203
The Murphi Verification System
Dill, D. L. (1996) · Computer Aided Verification · Cited by 190
Controlled Invariance of Discrete Time Systems
Vidal, R., Schaffert, S., Lygeros, J., & Sastry, S. (2000) · Lecture notes in computer science · doi:10.1007/3-540-46430-1_36 · Cited by 60
Computing Danger Zones for Provably Safe Closely Spaced Parallel Approaches
Teo, R., & Tomlin, C. J. (2003) · Journal of Guidance Control and Dynamics · doi:10.2514/2.5081 · Cited by 54
Self-citationDeshpande, A., Deshpande, A., & Deshpande, A. (2005) · Series in electrical and computer engineering · doi:10.1142/9781860946905_0010 · Cited by 43
Hybrid verification of an interface for an automatic landing
Oishi, M., Mitchell, I. M., Bayen, A. M., Tomlin, C. J., & Degani, A. (2003) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2002.1184749 · Cited by 43
Self-citation
Cited by
Safety Verification of Hybrid Systems Using Barrier Certificates
Prajna, S., & Jadbabaie, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24743-2_32 · Cited by 642
Zio, E. (2018) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2018.04.020 · Cited by 401
Cooperative Collision Avoidance at Intersections: Algorithms and Experiments
Hafner, M. R., Cunningham, D., Caminiti, L., & Del Vecchio, D. (2013) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2013.2252901 · Cited by 301
Governing AI safety through independent audits
Falco, G., Shneiderman, B., Badger, J., Carrier, R., Dahbura, A., Danks, D., Eling, M., Goodloe, A., Gupta, J., Hart, C., et al. (2021) · Nature Machine Intelligence · doi:10.1038/s42256-021-00370-7 · Cited by 250
Toward verified artificial intelligence
Seshia, S. A., Sadigh, D., & Sastry, S. S. (2022) · Communications of the ACM · doi:10.1145/3503914 · Cited by 215
Metadata
- Authors
- Tomlin, C. J., Mitchell, I., Bayen, A. M., & Oishi, M.
- Venue
- Proceedings of the IEEE
- Published
- 2003-07
- Volume
- 91
- Issue
- 7
- Pages
- 986-1001
- ISSN
- 0018-9219 (ISSN-L)
- OpenAlex
- W2099354898
- Cited by
- 353
- References
- 43
- FWCI
- 14.57
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.