Hopf-Koopman Reachability: Analysis and Control for Autonomous Systems
Abstract
There is a strong need to develop theory and tools for performing reachability analysis over models that are expressive enough to incorporate important nonlinear effects, but scalable enough to perform verification with guarantees that are not overly conservative. Development of such tools would have significant impact on the analysis of realistic models of dynamic systems in practical settings with limited computation, either online (e.g., for fast and safe control synthesis during multi-agent coordination), or offline (e.g., for analysis of high dimensional nonlinear systems).Among these approaches, Hamilton-Jacobi reachability (HJR) is well known for being a robust approach to optimal control and safe path planning. This method is usually used to generate a value function thatimplicitly captures the backward reachable set (BRS) of a system: the set of states from which a system with bounded control can reach (or avoid) a target despite bounded disturbances. This analysis also generates a corresponding optimal controller that rejects bounded disturbances. When feasible, it is a powerful tool for autonomous guidance and other stochastic control problems because of its derivation from the theory of differential games, which describes how to optimally drive a system to counter antagonistic or stochastic, bounded disturbances.HJR is, however, often not the most practical approach because of its dependency on spatial gradient approximations in a dynamic-programming (DP) scheme which makes it sensitive to the curse of dimensionality. If this theory could be extended to higher dimensional systems, engineering efforts in diverse naval domains, particularly in multi-agent coordination, oceanmodeling, and biological system modeling, could make strides where simpler (dimension-robust) controllers are unable to overcome disturbances or model uncertainty.The goal of this project is to speed up the construction of value functions to produce reachable sets and controllers for high-dimensional nonlinear systems. We propose to achieve this by merging three recent advances:1. the Hopf formula for efficient safety and reachability analysis of linear time varying systems,2. Koopman lifting to lift nonlinear systems tohigh-dimensional linear spaces, and3. the HJ-Prox procedure for approximating non-convex or irregular proximal maps.Using these three approaches, we propose to pair Koopman theory with the Hopf formula to develop and analyze a general algorithm for fast safety analysis and control of previously intractable high-dimensional, nonlinear systems. Specifically, we will pursue research in the following four thrusts:T1. Koopman-Hopf Reachability using Proximal Algorithms. We will use Koopman operators to produce linearized dynamics that can be used to initialize Hopf reachability analysis for efficient and parallelizable value function computation. T2. Improving Koopman-Hopf Reachability Proximal Algorithms using HJ-Prox. To combine Koopman and Hopf theories, we will need to handle the effects of expressive lifting functions, namely the non-convex or irregular-convex lifting of the target, control and disturbance sets, and the corresponding irregular or non-convex proximal maps. We, therefore, propose the use of the HJ-Prox method to solve the resulting irregular or non-convex proximal operators. T3. Relaxing Assumptions on Convex Target Sets. The Hopf formulation for reachability analysis is built on an assumption that the target set (i.e. goal or failure set) is convex. This impacts the Koopman operators that can be used for lifting the dynamics. We propose a method to relax this convexity requirement. T4. Incorporation of Model Error as a Disturbance. Reachability analysis is often used for guarantees on safety and liveness. We propose to quantify error introduced by incorrect modeling (due to lifting) and use this error bound as an adversarial disturbance in Hopf reachability to provide guaranteed conservative r
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 09, 2024
- Source ID
- N000142412661
Entities
People
- Sylvia Herbert
Organizations
- Office of Naval Research
- United States Navy
- University of California, San Diego