More Like this

1. Counterexample-guided computation of polyhedral Lyapunov functions for piecewise linear systems

   https://doi.org/10.1016/j.automatica.2023.111165  

   Berger, Guillaume O.; Sankaranarayanan, Sriram (September 2023, Automatica)

   This paper presents a counterexample-guided iterative algorithm to compute convex, piecewise linear (polyhedral) Lyapunov functions for continuous-time piecewise linear systems. Polyhedral Lyapunov functions provide an alternative to commonly used polynomial Lyapunov functions. Our approach first characterizes intrinsic properties of a polyhedral Lyapunov function including its “eccentricity” and “robustness” to perturbations. We then derive an algorithm that either computes a polyhedral Lyapunov function proving that the system is asymptotically stable, or concludes that no polyhedral Lyapunov function exists whose eccentricity and robustness parameters satisfy some user-provided limits. Significantly, our approach places no a-priori bound on the number of linear pieces that make up the desired polyhedral Lyapunov function. The algorithm alternates between a learning step and a verification step, always maintaining a finite set of witness states. The learning step solves a linear program to compute a candidate Lyapunov function compatible with a finite set of witness states. In the verification step, our approach verifies whether the candidate Lyapunov function is a valid Lyapunov function for the system. If verification fails, we obtain a new witness. We prove a theoretical bound on the maximum number of iterations needed by our algorithm. We demonstrate the applicability of the algorithm on numerical examples. 

   more » « less
2. Lyapunov Neural Network with Region of Attraction Search

   https://doi.org/10.23919/ACC60939.2024.10644877  

   Wang, Zili; Andersson, Sean B; Tron, Roberto (July 2024, Proceedings of the American Control Conference)

   Deep learning methods have been widely used in robotic applications, making learning-enabled control design for complex nonlinear systems a promising direction. Although deep reinforcement learning methods have demonstrated impressive empirical performance, they lack the stability guarantees that are important in safety-critical situations. One way to provide these guarantees is to learn Lyapunov certificates alongside control policies. There are three related problems: 1) verify that a given Lyapunov function candidate satisfies the conditions for a given controller on a region, 2) find a valid Lyapunov function and controller on a given region, and 3) find a valid Lyapunov function and a controller such that the region of attraction is as large as possible. Previous work has shown that if the dynamics are piecewise linear, it is possible to solve problem 1) and 2) by solving a Mixed-Integer Linear Program (MILP). In this work, we build upon this method by proposing a Lyapunov neural network that considers monotonicity over half spaces in different directions. We 1) propose a specific choice of Lyapunov function architecture that ensures non-negativity and a unique global minimum by construction, and 2) show that this can be leveraged to find the controller and Lyapunov certificates faster and with a larger valid region by maximizing the size of a square inscribed in a given level set. We apply our method to a 2D inverted pendulum, unicycle path following, a 3-D feedback system, and a 4-D cart pole system, and demonstrate it can shorten the training time by half compared to the baseline, as well as find a larger ROA. 

   more » « less
3. Distributed Learning-based Stability Assessment for Large Scale Networks of Dissipative Systems

   https://doi.org/10.1109/CDC45484.2021.9683774  

   Jena, Amit; Huang, Tong; Sivaranjani, S.; Kalathil, Dileep; Xie, Le (December 2021, IEEE Conference on Decision and Control (CDC))

   We propose a new distributed learning-based framework for stability assessment of a class of networked nonlinear systems, where each subsystem is dissipative. The aim is to learn, in a distributed manner, a Lyapunov function and associated region of attraction for the networked system. We begin by using a neural network function approximation to learn a storage function for each subsystem such that the subsystem satisfies a local dissipativity property. We next use a satisfiability modulo theories (SMT) solver based falsifier that verifies the local dissipativity of each subsystem by deter- mining an absence of counterexamples that violate the local dissipativity property, as established by the neural network approximation. Finally, we verify network-level stability by using an alternating direction method of multipliers (ADMM) approach to update the storage function of each subsystem in a distributed manner until a global stability condition for the network of dissipative subsystems is satisfied. This step also leads to a network-level Lyapunov function that we then use to estimate a region of attraction. We illustrate the proposed algorithm and its advantages on a microgrid interconnection with power electronics interfaces. 

   more » « less
4. Parameterization of Unstable Manifolds for DDEs: Formal Series Solutions and Validated Error Bounds

   https://doi.org/10.1007/s10884-021-10002-8  

   Hénot, Olivier; Lessard, Jean-Philippe; Mireles James, J. D. (July 2021, Journal of Dynamics and Differential Equations)

   null (Ed.)

   This paper studies the local unstable manifold attached to an equilibrium solution of a system of delay differential equations (DDEs). Two main results are developed. The first is a general method for computing the formal Taylor series coefficients of a function parameterizing the unstable manifold. We derive linear systems of equations whose solutions are the Taylor coefficients, describe explicit formulas for assembling the linear equations for DDEs with polynomial nonlinearities. We also discuss a scheme for transforming non-polynomial DDEs into polynomial ones by appending auxiliary equations. The second main result is an a-posteriori theorem which—when combined with deliberate control of rounding errors— leads to mathematically rigorous computer assisted convergence results and error bounds for the truncated series. Our approach is based on the parameterization method for invariant manifolds and requires some mild non-resonance conditions between the unstable eigenvalues 

   more » « less
5. Approximation of compositional functions with ReLU neural networks

   https://doi.org/10.1016/j.sysconle.2023.105508  

   Gong, Q.; Kang, W.; Fahroo, F. (May 2023, Systems control letters)

   The power of DNN has been successfully demonstrated on a wide variety of high-dimensional problems that cannot be solved by conventional control design methods. These successes also uncover some fundamental and pressing challenges in understanding the representability of deep neural networks for complex and high dimensional input–output relations. Towards the goal of understanding these fundamental questions, we applied an algebraic framework developed in our previous work to analyze ReLU neural network approximation of compositional functions. We prove that for Lipschitz continuous functions, ReLU neural networks have an approximation error upper bound that is a polynomial of the network’s complexity and the compositional features. If the compositional features do not increase exponentially with dimension, which is the case in many applications, the complexity of DNN has a polynomial growth. In addition to function approximations, we also establish ReLU network approximation results for the trajectories of control systems, and for a Lyapunov function that characterizes the domain of attraction. 

   more » « less