More Like this

1. Reachability Analysis Using Message Passing over Tree Decompositions

   Sankaranarayanan, Sriram ( July 2020 , International Conference on Computer Aided Verification)

   In this paper, we study efficient approaches to reachability analysis for discrete-time nonlinear dynamical systems when the dependencies among the variables of the system have low treewidth. Reachability analysis over nonlinear dynamical systems asks if a given set of target states can be reached, starting from an initial set of states. This is solved by computing conservative over approximations of the reachable set using abstract domains to represent these approximations. However, most approaches must tradeoff the level of conservatism against the cost of performing analysis, especially when the number of system variables increases. This makes reachability analysis challenging for nonlinear systems with a large number of state variables. Our approach works by constructing a dependency graph among the variables of the system. The tree decomposition of this graph builds a tree wherein each node of the tree is labeled with subsets of the state variables of the system. Furthermore, the tree decomposition satisfies important structural properties. Using the tree decomposition, our approach abstracts a set of states of the high dimensional system into a tree of sets of lower dimensional projections of this state. We derive various properties of this abstract domain, including conditions under which the original high dimensional set can be fully recovered from its low dimensional projections. Next, we use ideas from message passing developed originally for belief propagation over Bayesian networks to perform reachability analysis over the full state space in an efficient manner. We illustrate our approach on some interesting nonlinear systems with low treewidth to demonstrate the advantages of our approach. 

   more » « less
2. Interval Reachability of Nonlinear Dynamical Systems with Neural Network Controllers

   Jafarpour, Saber ; Harapanahalli, Akash ; Coogan, Samuel ( June 2023 , 5th Annual Learning for Dynamics & Control Conference)

   N. Matni, M. Morari (Ed.)

   This paper proposes a computationally efficient framework, based on interval analysis, for rigorous verification of nonlinear continuous-time dynamical systems with neural network controllers. Given a neural network, we use an existing verification algorithm to construct inclusion functions for its input-output behavior. Inspired by mixed monotone theory, we embed the closed-loop dynamics into a larger system using an inclusion function of the neural network and a decomposition function of the open-loop system. This embedding provides a scalable approach for safety analysis of the neural control loop while preserving the nonlinear structure of the system. We show that one can efficiently compute hyper-rectangular over-approximations of the reachable sets using a single trajectory of the embedding system. We design an algorithm to leverage this computational advantage through partitioning strategies, improving our reachable set estimates while balancing its runtime with tunable parameters. We demonstrate the performance of this algorithm through two case studies. First, we demonstrate this method’s strength in complex nonlinear environments. Then, we show that our approach matches the performance of the state-of-the art verification algorithm for linear discretized systems. 

   more » « less
3. Bayesian Parameter Estimation for Nonlinear Dynamics Using Sensitivity Analysis

   https://doi.org/10.24963/ijcai.2019/791  

   Chou, Yi ; Sankaranarayanan, Sriram ( August 2019 , International Joint Conference on Artificial Intelligence (IJCAI))

   We investigate approximate Bayesian inference techniques for nonlinear systems described by ordinary differential equation (ODE) models. In particular, the approximations will be based on set-valued reachability analysis approaches, yielding approximate models for the posterior distribution. Nonlinear ODEs are widely used to mathematically describe physical and biological models. However, these models are often described by parameters that are not directly measurable and have an impact on the system behaviors. Often, noisy measurement data combined with physical/biological intuition serve as the means for finding appropriate values of these parameters.Our approach operates under a Bayesian framework, given prior distribution over the parameter space and noisy observations under a known sampling distribution. We explore subsets of the space of model parameters, computing bounds on the likelihood for each subset. This is performed using nonlinear set-valued reachability analysis that is made faster by means of linearization around a reference trajectory. The tiling of the parameter space can be adaptively refined to make bounds on the likelihood tighter. We evaluate our approach on a variety of nonlinear benchmarks and compare our results with Markov Chain Monte Carlo and Sequential Monte Carlo approaches.

    

   more » « less
4. Rigorous data‐driven computation of spectral properties of Koopman operators for dynamical systems

   https://doi.org/10.1002/cpa.22125  

   Colbrook, Matthew J. ; Townsend, Alex ( July 2023 , Communications on Pure and Applied Mathematics)

   Koopman operators are infinite‐dimensional operators that globally linearize nonlinear dynamical systems, making their spectral information valuable for understanding dynamics. However, Koopman operators can have continuous spectra and infinite‐dimensional invariant subspaces, making computing their spectral information a considerable challenge. This paper describes data‐driven algorithms with rigorous convergence guarantees for computing spectral information of Koopman operators from trajectory data. We introduce residual dynamic mode decomposition (ResDMD), which provides the first scheme for computing the spectra and pseudospectra of general Koopman operators from snapshot data without spectral pollution. Using the resolvent operator and ResDMD, we compute smoothed approximations of spectral measures associated with general measure‐preserving dynamical systems. We prove explicit convergence theorems for our algorithms (including for general systems that are not measure‐preserving), which can achieve high‐order convergence even for chaotic systems when computing the density of the continuous spectrum and the discrete spectrum. Since our algorithms have error control, ResDMD allows aposteri verification of spectral quantities, Koopman mode decompositions, and learned dictionaries. We demonstrate our algorithms on the tent map, circle rotations, Gauss iterated map, nonlinear pendulum, double pendulum, and Lorenz system. Finally, we provide kernelized variants of our algorithms for dynamical systems with a high‐dimensional state space. This allows us to compute the spectral measure associated with the dynamics of a protein molecule with a 20,046‐dimensional state space and compute nonlinear Koopman modes with error bounds for turbulent flow past aerofoils with Reynolds number >10⁵that has a 295,122‐dimensional state space.

    

   more » « less
5. Using Information Flow for Whole System Understanding From Component Dynamics

   https://doi.org/10.1029/2019WR025820  

   Jiang, Peishi ; Kumar, Praveen ( November 2019 , Water Resources Research)

   Complex systems that exhibit emergent behaviors arise as a result of nonlinear interdependencies among multiple components. Characterizing how such whole system dynamics are sustained through multivariate interaction remains an open question. In this study, we propose an information flow‐based framework to investigate how the present state of any component arises as a result of the past interactions among interdependent variables, which is termed as causal history. Using a partitioning time lag, we divide this into immediate and distant causal history components and then characterize the information flow‐based interactions within these as self‐ and cross‐feedbacks. Such a partition allows us to characterize the information flow from the two feedbacks in both histories by using partial information decomposition as unique, synergistic, or redundant interactions. We employ this casual history analysis approach to investigate the information flows in a short‐memory coupled logistic model and a long‐memory observed stream chemistry dynamics. While the dynamics of the short‐memory system are mainly maintained by its recent historical states, the current state of each stream solute is sustained by self‐feedback‐dominated recent dynamics and cross‐dependency‐dominated earlier dynamics. The analysis suggests that the observed 1/fsignature of each solute is a result of the interactions with other variables in the stream. Based on high‐density data streams, the approach developed here for investigating multivariate evolutionary dynamics provides an effective way to understand how components of dynamical system interact to create emergent whole system behavioral patterns such as long‐memory dependency.

    

   more » « less