Resolution-complete safety falsification of continuous time systems
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 3297-3302
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 continuous-time LTI 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 specificationKeywords
This publication has 9 references indexed in Scilit:
- Sampling-Based Falsification and Verification of Controllers for Continuous Dynamic Systems2008
- Primal–Dual Tests for Safety and ReachabilityLecture Notes in Computer Science, 2005
- Reachability of Uncertain Linear Systems Using Zonotopes2005
- 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
- The d/dt Tool for Verification of Hybrid Systems2002
- Reachability Analysis of Hybrid Systems via Predicate Abstraction2002
- Ellipsoidal Techniques for Reachability Analysis2000
- Verification of Polyhedral-Invariant Hybrid Automata Using Polygonal Flow Pipe Approximations1999