Sampling-based Falsification and Verification of Controllers for Continuous Dynamic Systems
Authors:
- 1 November 2008
- journal article
- research article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 27 (11-12) , 1232-1245
Abstract
In this paper, we present a sampling-based verification algorithm for embedded robotic systems with continuous dynamics and uncertainty due to adversaries, unmodeled disturbance inputs, unknown parameters, or initial conditions. The algorithm attempts to find inputs (and resulting trajectories) that falsify the specifications of the system thus providing examples of bad inputs to the system. The system is said to be verified if the algorithm cannot find falsifying inputs. The main contribution of the paper is the analysis of the effects of discretization of the state and input spaces that are inherent to sampling-based techniques. We derive conditions that guarantee resolution completeness. These provide sufficient, although conservative, conditions for verifying Lipschitz continuous (but possibly non-smooth) dynamic systems without known analytical solutions. We analyze the effects of transformations of the input and state space on these conditions. The main results of this paper are illustrated with several simple examples.Keywords
This publication has 19 references indexed in Scilit:
- Systematic Simulation Using Sensitivity Analysis2007
- Incremental Search Methods for Reachability Analysis of Continuous and Hybrid SystemsLecture Notes in Computer Science, 2004
- Randomized Kinodynamic Motion Planning with Moving ObstaclesThe International Journal of Robotics Research, 2002
- Verification of infinite-state dynamic systems using approximate quotient transition systemsIEEE Transactions on Automatic Control, 2001
- Discrete abstractions of hybrid systemsProceedings of the IEEE, 2000
- PATH PLANNING IN EXPANSIVE CONFIGURATION SPACESInternational Journal of Computational Geometry & Applications, 1999
- What's Decidable about Hybrid Automata?Journal of Computer and System Sciences, 1998
- Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstaclesAlgorithmica, 1993
- Cell-to-Cell Mapping1987
- Convergence of discretization procedures in dynamic programmingIEEE Transactions on Automatic Control, 1975