Reachability Analysis of Nonlinear Systems using Conservative Approximations

Abstract. In this paper we present an approach to approximate reacha-bility computation for nonlinear continuous systems. Rather than study-ing a complex nonlinear system x ̇ = g(x), we study an approximating system x ̇ = f(x) which is easier to handle. The class of approximating systems we consider in this paper is piecewise linear, obtained by inter-polating g over a mesh. In order to be conservative, we add a bounded input in the approximating system to account for the interpolation error. We thus develop a reachability method for systems with input, based on the relation between such systems and the corresponding autonomous systems in terms of reachable sets. This method is then extended to the approximate piecewise linear systems arising in our construction. The final result is a reachability algorithm for nonlinear continuous systems which allows to compute conservative approximations with as great de-gree of accuracy as desired, and more importantly, it has good conver-gence rate. If g is a C2 function, our method is of order 2. Furthermore, the method can be straightforwardly extended to hybrid systems.