The Lyapunov Neural Network: Adaptive Stability Certification for Safe Learning of Dynamical Systems

Introduction

Safety is among the foremost open problems in robotics and artificial intelligence . Many autonomous systems, such as self-driving cars and robots for palliative care, are safety-critical due to their interaction with human life. At the same time, learning is necessary for these systems to perform well in a priori unknown environments. During learning, they must safely explore their environment by avoiding dangerous states from which they cannot recover. For example, consider an autonomous robot in an outdoor environment affected by rough terrain and adverse weather conditions. These factors introduce uncertainty about the relationship between the robot’s speed and maneuverability. While the robot should learn about its capabilities in such conditions, it must not perform a maneuver at a high speed that would cause it to crash. Conversely, traveling at only slow speeds to avoid accidents is not conducive to learning about the extent of the robot’s capabilities.

To ensure safe learning, we must verify a safety certificate for a state before it is explored. In control theory, a set of states is safe if system trajectories are bounded within it and asymptotically converge to a fixed point under a fixed control policy. Within such a region of attraction (ROA) , the system can collect data during learning and can always recover to a known safe point. In this paper, we leverage Lyapunov stability theory to construct provable, neural network-based safety certificates, and adapt them to the size and shape of the largest ROA of a general nonlinear dynamical system.

Lyapunov functions are convenient tools for stability (i.e., safety) certification of dynamical systems and for ROA estimation . These functions encode long-term behaviour of state trajectories in a scalar value , such that a ROA can be encoded as a level set of the Lyapunov function. However, Lyapunov functions for general dynamical systems are difficult to find; computational approaches are surveyed in . A Lyapunov function can be identified efficiently via a semi-definite program (SDP, ) when the dynamics are polynomial and the Lyapunov function is restricted to be a sum-of-squares (SOS) polynomial . Other methods to compute ROAs include maximization of a measure of ROA volume over system trajectories , and sampling-based approaches that generalize information about stability at discrete points to a continuous region .

This paper is particularly concerned with safety certificates for dynamical systems with uncertainties in the form of model errors. In robust control , the formulation of SDPs with SOS Lyapunov functions is used to compute ROA estimates for uncertain linear dynamical systems with the assumption of a worst-case linear perturbation from a known bounded set . Learning-based control methods with a Gaussian process (GP, ) model of the system instead consider uncertainty in a Bayesian manner, where model errors are reduced in regions where data has been collected. The methods in estimate a ROA with Lyapunov stability certificates computed on a discretization of the state space, which is used for safe reinforcement learning (RL, ). The Lyapunov function is assumed to be given in , while uses the negative value (i.e., cost) function from RL with a quadratic reward. Ultimately, this approach is limited by a shape mismatch between level sets of the Lyapunov function and the true largest ROA. For example, a quadratic Lyapunov function has ellipsoidal level sets, which cannot characterize a non-ellipsoidal ROA, while the SOS approach is restricted to fixed monomial features. To improve safe exploration for general nonlinear dynamics, we want to learn these features to determine a Lyapunov function with suitably shaped level sets.

In this paper, we present a novel method for learning accurate safety certificates for general nonlinear dynamical systems. We construct a neural network Lyapunov candidate and, unlike past work in , we structure our candidate such that it always inherently yields a provable safety certificate. Then, we specify a training algorithm that adapts the candidate to the shape of the dynamical system’s trajectories via classification of states as safe or unsafe. We do not depend on any specific structure of the dynamics for this. We show how our construction relates to SOS Lyapunov functions, and compare our approach to others on a simulated inverted pendulum benchmark. We also discuss how our method can be used to make safe learning more effective.

Problem Statement and Background

We consider a discrete-time, time-invariant, deterministic dynamical system of the form

One way to estimate the safe region $\mathcal{S}_{\pi}$ is by using a Lyapunov function. Given a suitable Lyapunov function $v$, a safe region for the closed-loop dynamical system $\bm{\mathbf{x}}_{t+1}=f_{\pi}(\bm{\mathbf{x}}_{t})$ can be determined.

2 Computing SOS Lyapunov Functions

In general, a suitable Lyapunov candidate $v$ is difficult to find. Computational methods often restrict $v$ to a particular function class for tractability. The SOS approach restricts $v(\bm{\mathbf{x}})$ to be polynomial, but is limited to polynomial dynamical systems, i.e., when $f_{\pi}(\bm{\mathbf{x}})$ is a vector of polynomials in the elements of $\bm{\mathbf{x}}$ . In particular, the SOS approach enforces $v(\bm{\mathbf{x}})=m(\bm{\mathbf{x}})^{\!\top}\!\bm{\mathbf{Q}}m(\bm{\mathbf{x}})$, where $m(\bm{\mathbf{x}})$ is a vector of a priori fixed monomial features in the elements of $\bm{\mathbf{x}}$, and $\bm{\mathbf{Q}}$ is an unknown positive-semidefinite matrix. This makes $v(\bm{\mathbf{x}})$ a quadratic function on a monomial feature space. A SDP can be efficiently solved to yield a $\bm{\mathbf{Q}}$ that simultaneously guarantees that $v$ satisfies the assumptions of Theorem 1 and has the largest possible level set in its decrease region $\mathcal{D}_{v}$. That is, the positive-definiteness of $v$ and the negative-definiteness of $\Delta v$ in $\mathcal{D}_{v}$ are enforced as constraints in the SDP. This contrasts the more general approach described in Sec. 2.1, where a Lyapunov candidate $v$ is given and then the assumptions of Theorem 1 are verified by checking discrete points.

1y=+1 (i.e., $\bm{\mathbf{x}}\in\mathcal{S}_{\pi}$) or “unsafe” with $y=-1$ (i.e., $\bm{\mathbf{x}}\notin\mathcal{S}_{\pi}$). With the SOS approach and a suitable choice of $m(\bm{\mathbf{x}})$, $\mathcal{S}_{\pi}$ can be estimated well with a level set $\mathcal{V}(c)$ of $v$, since the monomial features allow Lyapunov functions with shapes beyond simple ellipsoids to be found. However, the SOS approach requires polynomial dynamics, and the best choice of $m(\bm{\mathbf{x}})$ can be difficult to determine. Without a suitable Lyapunov function, we face the problem of a shape mismatch between $\mathcal{V}(c)$ and $\mathcal{S}_{\pi}$. This is exemplified in Fig. 1(a), where level sets of quadratic $v$ are ellipsoidal while $\mathcal{S}_{\pi}$ is not, which limits the region of the state space that is certifiable as safe by $v$.

Learning Lyapunov Candidates

In this section, we establish a more flexible class of parameterized Lyapunov candidates that can satisfy the assumptions on $v$ in Theorem 1 by virtue of their structure and gradient-based parameter training. In particular, we show how a binary classification problem based on whether each state $\bm{\mathbf{x}}$ lies within the safe region $\mathcal{S}_{\pi}$ can be formulated to train the parameterized Lyapunov candidate.

2 Learning a Safe Set via Classification

Previously, we constructed a neural network Lyapunov candidate $v_{\bm{\mathbf{\theta}}}$ in Theorem 2 that satisfies the positive-definiteness and Lipschitz continuity requirements in Theorem 1. As a result, we can always use the one-step decrease condition $\Delta v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})\coloneqq v_{\bm{\mathbf{\theta}}}(f_{\pi}(\bm{\mathbf{x}}))-v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})<0$ as a provable safety certificate to identify safe level sets that are subsets of the largest safe region $\mathcal{S}_{\pi}$. Now, we design a training algorithm to adapt the parameters $\bm{\mathbf{\theta}}$ such that the resulting Lyapunov candidate $v_{\bm{\mathbf{\theta}}}$ satisfies $\Delta v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})<0$ throughout as large of a decrease region $\mathcal{D}_{v_{\bm{\mathbf{\theta}}}}\subseteq\mathcal{X}$ as possible. This also makes $v_{\bm{\mathbf{\theta}}}$ a valid Lyapunov function for the closed-loop dynamics $f_{\pi}$.

For now, we assume the entire safe region $\mathcal{S}_{\pi}$ is known. We want to use a level set $\mathcal{V}_{\bm{\mathbf{\theta}}}(c)$ of $v_{\bm{\mathbf{\theta}}}$ to certify the entire set $\mathcal{S}_{\pi}$ as safe. According to Theorem 1, this requires the Lyapunov decrease condition $\Delta v_{\bm{\mathbf{{\theta}}}}(\bm{\mathbf{x}})<0$ to be satisfied for each state $\bm{\mathbf{x}}\in\mathcal{S}_{\pi}$. We formally state this problem as

That is, each state within the level set $\mathcal{V}(c_{\mathcal{S}})$ obtains the label $y=+1$. However, we must also satisfy the Lyapunov decrease condition imposed by Theorem 1. This can be written as the constraint

which means that we can assign the label $y=+1$ only if the decrease condition is also satisfied. The decision rule 4 together with the constraint 5 ensures that the resulting estimated safe set $\mathcal{V}(c_{\mathcal{S}})$ satisfies all of the conditions in Theorem 1. We want to select the neural network parameters $\bm{\mathbf{\theta}}$ so that this rule can perfectly classify $\bm{\mathbf{x}}\in\mathcal{S}_{\pi}$ as “safe” with $\hat{y}_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})=+1$ (i.e., ${c_{\mathcal{S}}-v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})>0}$) or $\bm{\mathbf{x}}\notin\mathcal{S}_{\pi}$ as “unsafe” with $\hat{y}_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})=-1$ (i.e., $c_{\mathcal{S}}-v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})\leq 0$). To this end, the decision boundary $v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})=c_{\mathcal{S}}$ must exactly delineate the boundary of $\mathcal{S}_{\pi}$. Furthermore, the value of $\bm{\mathbf{\theta}}$ must ensure 5 holds, such that $v_{\bm{\mathbf{\theta}}}$ satisfies the decrease condition of Theorem 1 on $\mathcal{S}_{\pi}$.

where the batch $\mathcal{X}_{b}$ is re-sampled after every gradient step. We can apply a Lagrangian relaxation

However, there are two issues when this formulation is compared to the exact problem in 3. Firstly, the objective 7 only penalizes violations of the decrease condition $\Delta v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})<0$, rather than constraining $\bm{\mathbf{\theta}}$ to enforce it. Thus, while $\Delta v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})<0$ is always a provable safety certificate, we must verify that it holds over some level set whenever we update $\bm{\mathbf{\theta}}$. Secondly, ground-truth labels of $\mathcal{S}_{\pi}$ are not known in practice. To address these issues, we can use any method to check Lyapunov safety certificates over continuous state spaces to certify a level set $\mathcal{V}_{\bm{\mathbf{\theta}}}(c)$ as safe, and then use $\mathcal{V}_{\bm{\mathbf{\theta}}}(c)$ to estimate labels $y$ from $\mathcal{S}_{\pi}$. For this work, we check the tightened certificate $\Delta v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})<-L_{\Delta v_{\bm{\mathbf{\theta}}}}\tau$ on a discretization of $\mathcal{X}$, as described in Sec. 2.1. This method exposes the Lipschitz constant $L_{\Delta v_{\bm{\mathbf{\theta}}}}$ of $\Delta v_{\bm{\mathbf{\theta}}}$, which can conveniently be used for regularization in practice . Possible alternatives to this safety verification method include the use of an adaptive discretization for better scaling to higher-dimensional state spaces , and formal verification methods for neural networks .

Experiments and Discussion

In the previous section, we developed Algorithm 1 to train the parameters $\bm{\mathbf{\theta}}$ of a neural network Lyapunov candidate $v_{\bm{\mathbf{\theta}}}$ constructed according to Theorem 2. This construction ensures the positive-definiteness and Lipschitz continuity assumptions on $v_{\bm{\mathbf{\theta}}}$ in Theorem 1 are satisfied. Algorithm 1 encourages $v_{\bm{\mathbf{\theta}}}$ to satisfy the decrease condition and match the true largest ROA $\mathcal{S}_{\pi}$ for the closed-loop dynamics $f_{\pi}$ with a level set $\mathcal{V}_{\bm{\mathbf{\theta}}}(c_{\mathcal{S}})$. In this section, we present details for the implementation of Algorithm 1 to learn the largest safe region of a simulated inverted pendulum system, and experimental results in a comparison to other methods of computing Lyapunov functions.

To train the parameters of the Lyapunov candidate $v_{\bm{\mathbf{\theta}}}$ to adapt to the shape of $\mathcal{S}_{\pi}$, we use Algorithm 1 with SGD. To certify the safety of continuous level sets of $v_{\bm{\mathbf{\theta}}}$ whenever $\bm{\mathbf{\theta}}$ is updated, we check the stricter decrease condition $\Delta v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})<-L_{\Delta v_{\bm{\mathbf{\theta}}}}\tau$ at a discrete set of points that cover $\mathcal{X}$ in increasing order of the value of $v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})$, as in . Algorithm 1 does not guarantee that the safe level set estimate $\mathcal{V}_{\bm{\mathbf{\theta}}}(c_{k})$ grows monotonically in volume towards $\mathcal{S}_{\pi}$ with each iteration $k$. In fact, the estimate $\mathcal{V}_{\bm{\mathbf{\theta}}}(c_{k})$ may shrink if $v_{\bm{\mathbf{\theta}}}$ initially succeeds and then fails to satisfy the decrease condition $\Delta v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})<0$ in some regions of the state space. This tends to occur near the origin, where ${v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{0}})=\Delta v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{0}})=0}$ and the “basin of attraction” characterized by $v_{\bm{\mathbf{\theta}}}$ “flattens”. To alleviate this, we use a large Lagrange multiplier $\lambda=1000$ in the SGD objective 7 to strongly “push” $\bm{\mathbf{\theta}}$ towards values that ensure $v_{\bm{\mathbf{\theta}}}$ continues to satisfy the decrease condition. In addition, we normalize the Lyapunov decrease loss \lambda((y+1)/2)\max\mathinner{\bigl{(}0,\Delta v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})\bigr{)}} in 7 by $v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})$. This more heavily weighs sampled states near the origin, i.e., where $v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})$ is small.

Fig. 3(a) demonstrates that a neural network Lyapunov candidate $v_{\bm{\mathbf{\theta}}}$ can certify more of the true largest safe region $\mathcal{S}_{\pi}$ than other common Lyapunov candidates. This has important implications for safe exploration during learning for dynamical systems; with more safe states available to visit, an agent can better learn about itself and its environment under a wider range of operating conditions. For example, our method is applicable in the safe reinforcement learning framework of . This past work provides safe exploration guarantees for a GP model of the dynamics $f_{\pi}$ with confidence bounds on the Lyapunov stability certificate, but these guarantees are limited by the choice of Lyapunov function. As our results have shown, certain Lyapunov candidates may poorly characterize the shape of the true largest safe region $\mathcal{S}_{\pi}$. Since our neural network Lyapunov candidate can adapt to the shape of $\mathcal{S}_{\pi}$ during learning by using, for example, the mean estimate of $f_{\pi}$ from the GP model, we could enlarge the estimated safe region more quickly as data is collected. Our method is also applicable to exploration algorithms within safe motion planning that depends on knowledge of a safe region, such as in . Overall, our method strongly warrants consideration for use in safe learning methods that leverage statistical models of dynamical systems.

Conclusion

We have demonstrated a novel method for learning safety certificates for general nonlinear dynamical systems. Specifically, we developed a flexible class of parameterized Lyapunov candidate functions and a training algorithm to adapt them to the shape of the largest safe region for a closed-loop dynamical system. We believe that our method is appealing due to its applicability to a wide range of dynamical systems in theory and practice. Furthermore, it can play an important role in improving safe exploration during learning for real autonomous systems in uncertain environments.

This research was supported in part by SNSF grant 200020_159557, the Vector Institute, and a fellowship by the Open Philanthropy Project.

References

Appendix A Proofs

We now use this property of $\phi_{\bm{\mathbf{\theta}}}$ to prove that the Lyapunov candidate $v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})=\phi_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})^{\!\top}\!\phi_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})$ is positive-definite on $\mathcal{X}$. As an inner product, $\phi_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})^{\!\top}\!\phi_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})$ is positive-definite on the transformed space $\mathcal{Y}\coloneqq\mathinner{\left\{\phi_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}}),\ \forall\bm{\mathbf{x}}\in\mathcal{X}\right\}}$. Thus, $v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})=0\iff\phi_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})=\bm{\mathbf{0}}$ and $v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})>0$ otherwise. Since we have already proven $\phi_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})=\bm{\mathbf{0}}\iff\bm{\mathbf{x}}=\bm{\mathbf{0}}$, combining these statements shows that $v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})=0\iff\bm{\mathbf{x}}=\bm{\mathbf{0}}$ and $v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})>0$ otherwise. As a result, $v_{\bm{\mathbf{\theta}}}(\bm{\mathbf{x}})$ is positive-definite on $\mathcal{X}$.