Eliminating spurious transitions in reachability with support functions

G. Frehse, S. Bogomolov, M. Greitschus, T. Strump, A. Podelski, in:, Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 149–158.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
; ; ; ;
Department
Abstract
Computing an approximation of the reachable states of a hybrid system is a challenge, mainly because overapproximating the solutions of ODEs with a finite number of sets does not scale well. Using template polyhedra can greatly reduce the computational complexity, since it replaces complex operations on sets with a small number of optimization problems. However, the use of templates may make the over-approximation too conservative. Spurious transitions, which are falsely considered reachable, are particularly detrimental to performance and accuracy, and may exacerbate the state explosion problem. In this paper, we examine how spurious transitions can be avoided with minimal computational effort. To this end, detecting spurious transitions is reduced to the well-known problem of showing that two convex sets are disjoint by finding a hyperplane that separates them. We generalize this to owpipes by considering hyperplanes that evolve with time in correspondence to the dynamics of the system. The approach is implemented in the model checker SpaceEx and demonstrated on examples.
Publishing Year
Date Published
2015-04-14
Proceedings Title
Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control
Page
149 - 158
Conference
HSCC: Hybrid Systems - Computation and Control
Conference Location
Seattle, WA, United States
Conference Date
2015-04-14 – 2015-04-16
IST-REx-ID

Cite this

Frehse G, Bogomolov S, Greitschus M, Strump T, Podelski A. Eliminating spurious transitions in reachability with support functions. In: Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control. ACM; 2015:149-158. doi:10.1145/2728606.2728622
Frehse, G., Bogomolov, S., Greitschus, M., Strump, T., & Podelski, A. (2015). Eliminating spurious transitions in reachability with support functions. In Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control (pp. 149–158). Seattle, WA, United States: ACM. https://doi.org/10.1145/2728606.2728622
Frehse, Goran, Sergiy Bogomolov, Marius Greitschus, Thomas Strump, and Andreas Podelski. “Eliminating Spurious Transitions in Reachability with Support Functions.” In Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, 149–58. ACM, 2015. https://doi.org/10.1145/2728606.2728622.
G. Frehse, S. Bogomolov, M. Greitschus, T. Strump, and A. Podelski, “Eliminating spurious transitions in reachability with support functions,” in Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, Seattle, WA, United States, 2015, pp. 149–158.
Frehse G, Bogomolov S, Greitschus M, Strump T, Podelski A. 2015. Eliminating spurious transitions in reachability with support functions. Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control. HSCC: Hybrid Systems - Computation and Control 149–158.
Frehse, Goran, et al. “Eliminating Spurious Transitions in Reachability with Support Functions.” Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, ACM, 2015, pp. 149–58, doi:10.1145/2728606.2728622.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search