Reachability Analysis of Nonlinear and Hybrid Systems Using Hybrid Zonotopes and Graphs of Functions
Open Access
- Author:
- Siefert, Jacob
- Graduate Program:
- Mechanical Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- December 08, 2023
- Committee Members:
- Herschel Pangborn, Chair & Dissertation Advisor
Constantino Lagoa, Outside Field Member
Jacob Langelaan, Outside Unit Member
Brandon Hencey, Special Member
Sean Brennan, Major Field Member
Robert Kunz, Professor in Charge/Director of Graduate Studies - Keywords:
- Verification
Control
Set-Theoretic Methods
Reachability Analysis
Estimation
Hybrid Zonotopes - Abstract:
- Reachable sets are used to evaluate system performance and ensure constraint satisfaction in safety-critical applications while accounting for the effects of input, disturbance, and parameter uncertainties. However, many reachability approaches are not applicable to nonlinear systems or hybrid dynamics consisting of both continuous and discrete dynamics. Furthermore, both computational complexity and set representation complexity grow rapidly with system dimension and the duration over which sets are propagated. While computational complexity and set representation complexity can be reduced by over-approximating reachable sets, approximation techniques can suffer from significant error as over-approximations are propagated through the dynamics. This dissertation develops methods to enable efficient reachability analysis of hybrid and nonlinear systems using a novel set representation, the hybrid zonotope, with sets representing the mapping of functions called graphs of functions. Examples demonstrate how these methods can be applied to verify safety and performance of many classes of systems of engineering interest, including closed-loop systems with advanced controllers. First, this dissertation proposes methods using graphs of functions, including set identities for calculating a set of outputs given a set of inputs, and vice versa. For reachability analysis of an autonomous system, this corresponds to one-step forward and backward reachability. The computational complexity and memory complexity of the proposed identities, when executed using hybrid zonotopes, motivates additional contributions. This includes techniques to represent and approximate graphs of functions as hybrid zonotopes by leveraging special ordered sets (SOS), and methods to improve scalability for constructing graphs of high-dimensional functions via functional decomposition. Then, the proposed techniques are applied to perform reachability analysis of diverse classes of systems including mixed-logical dynamical (MLD) systems, linear systems in closed-loop with model predictive control (MPC), discrete hybrid automata (DHA), logical systems, neural nets, and nonlinear systems. Methods exploit the structure inherent to many of these classes of systems to generate a functional decomposition, which can be used to efficiently construct graphs of functions. The reachability techniques for each class are compared to existing state-of-the-art techniques using benchmark problems where applicable. Lastly, the dissertation applies the techniques to set-valued state estimation (SVSE) and set-valued parameter identification (SVPI). Examples demonstrate how nonlinear measurement models can result in nonconvex and disjoint sets, and compare results to an idealized convex approach. Numerical results demonstrate that proposed methods enable analyses which cannot be performed with other state-of-the-art tools, such as verification of large initial sets.