An official website of the United States government
Many dynamical systems described by nonlinear ODEs are unstable. Their associated solutions do not converge towards an equilibrium point, but rather converge towards some invariant subset of the state space called an attractor set. For a given ODE, in general, the existence, shape and structure of the attractor sets of the ODE are unknown. Fortunately, the sublevel sets of Lyapunov functions can provide bounds on the attractor sets of ODEs. In this paper we propose a new Lyapunov characterization of attractor sets that is well suited to the problem of finding the minimal attractor set. We show our Lyapunov characterization is non-conservative even when restricted to Sum-of-Squares (SOS) Lyapunov functions. Given these results, we propose a SOS programming problem based on determinant maximization that yields an SOS Lyapunov function whose \begin{document}$ 1 $$\end{document}$-sublevel set has minimal volume, is an attractor set itself, and provides an optimal outer approximation of the minimal attractor set of the ODE. Several numerical examples are presented including the Lorenz attractor and Van-der-Pol oscillator.
more »
« less
Neural Lyapunov Control
We propose new methods for learning control policies and neural network Lyapunov functions for nonlinear control problems, with provable guarantee of stability. The framework consists of a learner that attempts to find the control and Lyapunov functions, and a falsifier that finds counterexamples to quickly guide the learner towards solutions. The procedure terminates when no counterexample is found by the falsifier, in which case the controlled nonlinear system is provably stable. The approach significantly simplifies the process of Lyapunov control design, provides end-to-end correctness guarantee, and can obtain much larger regions of attraction than existing methods such as LQR and SOS/SDP. We show experiments on how the new methods obtain high-quality solutions for challenging robot control problems such as path tracking for wheeled vehicles and humanoid robot balancing.
more »
« less
- Award ID(s):
- 1830399
- PAR ID:
- 10191111
- Date Published:
- Journal Name:
- Advances in neural information processing systems
- ISSN:
- 1049-5258
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Inverse kinematics solves the problem of how to control robot arm joints to achieve desired end effector positions, which is critical to any robot arm design and implemen- tations of control algorithms. It is a common misunderstanding that closed-form inverse kinematics analysis is solved. Popular software and algorithms, such as gradient descent or any multi-variant equations solving algorithm, claims solving inverse kinematics but only on the numerical level. While the numerical inverse kinematics solutions are rela- tively straightforward to obtain, these methods often fail, due to dependency on specific numerical values, even when the inverse kinematics solutions exist. Therefore, closed-form inverse kinematics analysis is superior, but there is no generalized automated algorithm. Up till now, the high-level logical reasoning involved in solving closed-form inverse kine- matics made it hard to automate, so it’s handled by human experts. We developed IKBT, a knowledge-based intelligent system that can mimic human experts’ behaviors in solving closed-from inverse kinematics using Behavior Tree. Knowledge and rules used by engineers when solving closed-from inverse kinematics are encoded as actions in Behavior Tree. The order of applying these rules is governed by higher level composite nodes, which resembles the logical reasoning process of engineers. It is also the first time that the dependency of joint variables, an important issue in inverse kinematics analysis, is automatically tracked in graph form. Besides generating closed-form solutions, IKBT also explains its solving strategies in human (engineers) interpretable form. This is a proof-of-concept of using Behavior Trees to solve high-cognitive problems.more » « less
-
Designing stabilizing controllers is a fundamental challenge in autonomous systems, particularly for high-dimensional, nonlinear systems that can hardly be accurately modeled with differential equations. The Lyapunov theory offers a solution for stabilizing control systems, still, current methods relying on Lyapunov functions require access to complete dynamics or samples of system executions throughout the entire state space. Consequently, they are impractical for high-dimensional systems. This paper introduces a novel framework, LYapunov-Guided Exploration (LYGE), for learning stabilizing controllers tailored to high-dimensional, unknown systems. LYGE employs Lyapunov theory to iteratively guide the search for samples during exploration while simultaneously learning the local system dynamics, control policy, and Lyapunov functions. We demonstrate its scalability on highly complex systems, including a high-fidelity F-16 jet model featuring a 16D state space and a 4D input space. Experiments indicate that, compared to prior works in reinforcement learning, imitation learning, and neural certificates, LYGE reduces the distance to the goal by 50% while requiring only 5% to 32% of the samples. Furthermore, we demonstrate that our algorithm can be extended to learn controllers guided by other certificate functions for unknown systems.more » « less
-
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
-
In many automated motion planning systems, vehicles are tasked with tracking a reference path or trajectory that is safe by design. However, due to various uncertainties, real vehicles may deviate from such references, potentially leading to collisions. This paper presents rigorous reachable set bounding methods for rapidly enclosing the set of possible deviations under uncertainty, which is critical information for online safety verification. The proposed approach applies recent advances in the theory of differential inequalities that exploit redundant model equations to achieve sharp bounds using only simple interval calculations. These methods have been shown to produce very sharp bounds at low cost for nonlinear systems in other application domains, but they rely on problem-specific insights to identify appropriate redundant equations, which makes them difficult to generalize and automate. Here, we demonstrate the application of these methods to tracking problems for the first time using three representative case studies. We find that defining redundant equations in terms of Lyapunov-like functions is particularly effective. The results show that this technique can produce effective bounds with computational times that are orders of magnitude less than the planned time horizon, making this a promising approach for online safety verification. This performance, however, comes at the cost of low generalizability, specifically due to the need for problem-specific insights and advantageous problem structure, such as the existence of appropriate Lyapunov-like functions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
