Sampling-based resolution-complete safety falsification of linear hybrid systems
Authors:
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 01912216,p. 3405-3411
Abstract
In this paper, we consider a class of analysis problems for control systems, aimed at safety falsification, i.e., checking whether a controlled trajectory exists that violates a given safety property. We introduce a notion of resolution completeness for safety falsification, and present a resolution-complete algorithm applicable to discrete- time LTI hybrid systems. The algorithm is based on deterministic incremental search procedures, building feasible trajectories exploring the reachable set at increasing resolution levels. Given a target resolution, the algorithm terminates either with a trajectory that violates the safety specification, or proves that no input within a certain class exists that violates the specification.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Sampling-Based Falsification and Verification of Controllers for Continuous Dynamic Systems2008
- Resolution-complete safety falsification of continuous time systems2006
- Computational Techniques for Analysis of Genetic Network DynamicsThe International Journal of Robotics Research, 2005
- Reachability of Uncertain Linear Systems Using Zonotopes2005
- Safety Verification of Hybrid Systems Using Barrier Certificates2004
- Incremental Search Methods for Reachability Analysis of Continuous and Hybrid SystemsLecture Notes in Computer Science, 2004
- An assessment of the current status of algorithmic approaches to the verification of hybrid systems2003
- Reachability Analysis of Hybrid Systems via Predicate Abstraction2002
- Ellipsoidal Techniques for Reachability Analysis2000
- Verification of Polyhedral-Invariant Hybrid Automata Using Polygonal Flow Pipe Approximations1999