Decomposed Reachability Analysis for Nonlinear Systems
Authors:
- Xin ChenXCXin Chen
- Sriram SankaranarayananSSSriram Sankaranarayanan
- 1 November 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 13-24
Abstract
We introduce an approach to conservatively abstract a nonlinear continuous system by a hybrid automaton whose continuous dynamics are given by a decomposition of the original dynamics. The decomposed dynamics is in the form of a set of lower-dimensional ODEs with time-varying uncertainties whose ranges are defined by the hybridization domains. We propose several techniques in the paper to effectively compute abstractions and flowpipe overapproximations. First, a novel method is given to reduce the overestimation accumulation in a Taylor model flowpipe construction scheme. Then we present our decomposition method, as well as the framework of on-the-fly hybridization. A combination of the two techniques allows us to handle much larger, nonlinear systems with comparatively large initial sets. Our prototype implementation is compared with existing reachability tools for offline and online flowpipe construction on challenging benchmarks of dimensions ranging from 7 to 30. Our code has successfully passed the artifact evaluation.Keywords
This publication has 23 references indexed in Scilit:
- NLTOOLBOX: A Library for Reachability Computation of Nonlinear Dynamical Systems2013
- Computing differential invariants of hybrid systems as fixedpointsFormal Methods in System Design, 2009
- Computing Reachable States for Nonlinear Biological Models2009
- Hybridization methods for the analysis of nonlinear systemsActa Informatica, 2007
- Synchronization of coupled nonidentical genetic oscillatorsPhysical Biology, 2006
- Mechanisms of noise-resistance in genetic oscillatorsProceedings of the National Academy of Sciences, 2002
- Using simplicity to control complexityIEEE Software, 2001
- Validated solutions of initial value problems for ordinary differential equationsApplied Mathematics and Computation, 1999
- A Molecular Network That Produces Spontaneous Oscillations in Excitable Cells ofDictyosteliumMolecular Biology of the Cell, 1998
- Dynamics of two-component biochemical systems in interacting cells; Synchronization and desynchronization of oscillations and multiple steady statesBioSystems, 1997