Safety verification of nonlinear hybrid systems based on invariant clusters

H. Kong, S. Bogomolov, C. Schilling, Y. Jiang, T.A. Henzinger, in:, Proceedings of the 20th International Conference on Hybrid Systems, ACM, 2017, pp. 163–172.

Download
OA IST-2017-817-v1+1_p163-kong.pdf 1.65 MB

Conference Paper | Published | English

Scopus indexed
Author
Kong, HuiIST Austria ; Bogomolov, Sergiy ; Schilling, Christian; Jiang, Yu; Henzinger, Thomas AIST Austria
Department
Abstract
In this paper, we propose an approach to automatically compute invariant clusters for nonlinear semialgebraic hybrid systems. An invariant cluster for an ordinary differential equation (ODE) is a multivariate polynomial invariant g(u→, x→) = 0, parametric in u→, which can yield an infinite number of concrete invariants by assigning different values to u→ so that every trajectory of the system can be overapproximated precisely by the intersection of a group of concrete invariants. For semialgebraic systems, which involve ODEs with multivariate polynomial right-hand sides, given a template multivariate polynomial g(u→, x→), an invariant cluster can be obtained by first computing the remainder of the Lie derivative of g(u→, x→) divided by g(u→, x→) and then solving the system of polynomial equations obtained from the coefficients of the remainder. Based on invariant clusters and sum-of-squares (SOS) programming, we present a new method for the safety verification of hybrid systems. Experiments on nonlinear benchmark systems from biology and control theory show that our approach is efficient.
Publishing Year
Date Published
2017-04-01
Proceedings Title
Proceedings of the 20th International Conference on Hybrid Systems
Page
163 - 172
Conference
HSCC: Hybrid Systems Computation and Control
Conference Location
Pittsburgh, PA, United States
Conference Date
2017-04-18 – 2017-04-20
IST-REx-ID
663

Cite this

Kong H, Bogomolov S, Schilling C, Jiang Y, Henzinger TA. Safety verification of nonlinear hybrid systems based on invariant clusters. In: Proceedings of the 20th International Conference on Hybrid Systems. ACM; 2017:163-172. doi:10.1145/3049797.3049814
Kong, H., Bogomolov, S., Schilling, C., Jiang, Y., & Henzinger, T. A. (2017). Safety verification of nonlinear hybrid systems based on invariant clusters. In Proceedings of the 20th International Conference on Hybrid Systems (pp. 163–172). Pittsburgh, PA, United States: ACM. https://doi.org/10.1145/3049797.3049814
Kong, Hui, Sergiy Bogomolov, Christian Schilling, Yu Jiang, and Thomas A Henzinger. “Safety Verification of Nonlinear Hybrid Systems Based on Invariant Clusters.” In Proceedings of the 20th International Conference on Hybrid Systems, 163–72. ACM, 2017. https://doi.org/10.1145/3049797.3049814.
H. Kong, S. Bogomolov, C. Schilling, Y. Jiang, and T. A. Henzinger, “Safety verification of nonlinear hybrid systems based on invariant clusters,” in Proceedings of the 20th International Conference on Hybrid Systems, Pittsburgh, PA, United States, 2017, pp. 163–172.
Kong H, Bogomolov S, Schilling C, Jiang Y, Henzinger TA. 2017. Safety verification of nonlinear hybrid systems based on invariant clusters. Proceedings of the 20th International Conference on Hybrid Systems. HSCC: Hybrid Systems Computation and Control 163–172.
Kong, Hui, et al. “Safety Verification of Nonlinear Hybrid Systems Based on Invariant Clusters.” Proceedings of the 20th International Conference on Hybrid Systems, ACM, 2017, pp. 163–72, doi:10.1145/3049797.3049814.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
b7667434cbf5b5f0ade3bea1dbe5bf63


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search