Files in this item

FilesDescriptionFormat

application/pdf

application/pdfFAN-THESIS-2016.pdf (716kB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Automatic simulation-driven reachability using matrix measures
Author(s):Fan, Chuchu
Advisor(s):Mitra, Sayan
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):Reachability
Nonlinear systems
Matrix measures
Abstract:Simulation-driven verification is a promising approach that provides formal safety guarantees for otherwise intractable nonlinear and hybrid system models. A key step in simulation-driven algorithms is to compute the reach set over-approximations from a set of initial states through numerical simulations. This thesis introduces algorithms for this key step, which relies on computing piece-wise exponential bounds on the rate at which trajectories starting from neighboring states converge or diverge. We call this discrepancy function. The algorithms rely on computing local bounds on the matrix measure of the Jacobian matrices. We discuss different techniques to compute the matrix measures under different norms: regular Euclidean norm or Euclidean norm under coordinate transformation, such that the exponential rate of the discrepancy function is locally minimized. The proposed methods enable automatic reach set computations of general nonlinear systems and have been successfully used on several challenging benchmark models. All proposed algorithms for computing discrepancy function give soundness and relative completeness of the overall simulation-driven safety verification algorithm. We present a series of experiments to illustrate the accuracy and performance of the approach.
Issue Date:2016-07-18
Type:Thesis
URI:http://hdl.handle.net/2142/93069
Rights Information:Copyright 2016 Chuchu Fan
Date Available in IDEALS:2016-11-10
Date Deposited:2016-08


This item appears in the following Collection(s)

Item Statistics