1. SpaceEx: Scalable Verification of Hybrid Systems
- Author
-
Rodolfo Ripado, Alexandre Donzé, Thao Dang, Antoine Girard, Colas Le Guernic, Goran Frehse, Olivier Lebeltel, Oded Maler, Rajarshi Ray, Scott Cotton, VERIMAG (VERIMAG - IMAG), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF), Courant Institute of Mathematical Sciences [New York] (CIMS), New York University [New York] (NYU), NYU System (NYU)-NYU System (NYU), Calculs Algébriques et Systèmes Dynamiques (CASYS), Laboratoire Jean Kuntzmann (LJK), Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF)-Université Pierre Mendès France - Grenoble 2 (UPMF), and Ganesh Gopalakrishnan, Shaz Qadeer
- Subjects
0209 industrial biotechnology ,Computer science ,Computation ,Variable time ,020207 software engineering ,02 engineering and technology ,Support function ,Polyhedron ,020901 industrial engineering & automation ,Reachability ,Hybrid system ,Scalability ,0202 electrical engineering, electronic engineering, information engineering ,Hybrid automaton ,[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] ,Algorithm - Abstract
International audience; We present a scalable reachability algorithm for hybrid systems with piecewise affine, non-deterministic dynamics. It combines polyhedra and support function representations of continuous sets to compute an over-approximation of the reachable states. The algorithm improves over previous work by using variable time steps to guarantee a given local error bound. In addition, we propose an improved approximation model, which drastically improves the accuracy of the algorithm. The algorithm is implemented as part of SpaceEx, a new verification platform for hybrid systems, available at spaceex.imag.fr. Experimental results of full fixed-point computations with hybrid systems with more than 100 variables illustrate the scalability of the approach.
- Published
- 2011
- Full Text
- View/download PDF