Learning Hybrid Control Barrier Functions from Data

Introduction

Consider the following safety-critical scenarios: autonomous vehicles in urban areas , exoskeletons for improving mobility of lower-body impaired users , and robots navigating a warehouse using semantic logic . These systems are all described by hybrid dynamics, i.e., states and transitions are both continuous and discrete, due to either their physics, or to higher level logical decision making and importantly, share that: 1) data exhibiting safe behavior is readily available or easily collected, and 2) in most cases, their hybrid system dynamics are well understood and can be identified. Based on these observations, we propose an optimization-based approach to learning provably safe controllers for hybrid systems using hybrid control barrier functions (HCBF).

Related work: Barrier functions (BFs) were introduced in to certify the safety of continuous-time systems. Nonsmooth and hybrid BFs have also been defined. Different to our work, these focus on BFs with jumps for discontinuous systems. Control barrier functions (CBFs) for continuous-time control systems appeared in for synthesizing feedback control laws that ensure safety by enforcing forward invariance of a desired safe set. Reciprocal and zeroing CBFs were proposed as less restrictive alternatives that do not enforce forward invariance on subsets of the safe set. Such CBFs can be used as a safety guard via convex quadratic programs , a feature that has been used for safe learning . CBFs for discrete-time control systems can be found in . Related to this paper, hybrid BFs were proposed in in the hybrid systems framework of as a means of certifying the safety of hybrid systems. Analogous hybrid BFs are introduced in for the hybrid automata modeling framework of .

The underlying challenge and bottleneck in ensuring safety using (control) BFs is the construction of these functions. In , the authors propose a sum-of-squares programming approach for finding polynomial (hybrid) barrier functions for polynomial (hybrid) systems and semi-algebraic sets. For finding CBFs, bilinear sum-of-squares programming and analytic approaches are proposed in ; such methods, however, only apply to a restrictive class of systems and have limited scalability. Recent approaches attempt to circumvent these limitations by treating the CBF synthesis task as a machine learning problem. In , a deep neural network is trained to imitate the control law obtained from a CBF, whereas in , a CBF is synthesized from safe and unsafe data samples using support vector machines. In , the authors cluster observed data and learn a linear CBF for each cluster. While the aforementioned works present detailed empirical validation of their methods, no formal correctness proofs are provided. In , a Lyapunov, barrier, and a policy function is learned from data: the validity of the learned certificates are then verified post-hoc using Lipschitz arguments. In , a method is proposed that learns a provably correct neural net safety guard for kinematic bicycle models. Finally, propose a data-driven approach for learning CBFs for smooth nonlinear systems assuming known Lipschitz dynamics, as well as availability of expert demonstrations illustrating safe behavior. Sufficient conditions ensuring correctness of the learned CBF using a Lipschitz argument are also given.

Contributions: For a class of hybrid control systems, we define hybrid control BFs as a means to enforce forward invariance of a safe set. We provide sufficient conditions in terms of a HCBF that, if satisfied by a control law, ensure safety. We then show that learning HCBFs from data can be cast as a constrained optimization problem, and provide conditions under which a feasible solution is a valid HCBF. Finally, we present simulations showcasing the benefits of our framework.

Preliminaries and Problem Formulation

The next result follows mainly from . We provide a slightly modified version to account for [19, Remark 5] and to not require that $\nabla h(x)\neq 0$ when $x\in\text{bd}(\mathcal{C})$ by using the Comparison Lemma [28, Lemma 3.4].

Assume that $h(x)$ is a valid control barrier function on $\mathcal{D}$ and that $u:\mathcal{D}\to\mathcal{U}$ is a continuous function with $u(x)\in K_{\text{CBF}}(x)$. Then $x(0)\in\mathcal{C}$ implies $x(t)\in\mathcal{C}$ for all $t\in\mathcal{I}$. If $\mathcal{C}$ is compact, it follows that $\mathcal{C}$ is forward invariant under $u(x)$, i.e., $\mathcal{I}=[0,\infty)$.

First note that $\dot{v}(t)=-\alpha(v(t))$ with $v(0)\geq 0$ admits a unique solution $v(t)$ that is such that $v(t)\geq 0$ for all $t\geq 0$ [28, Lemma 4.4]. Each solution $x(t)$ to (1) under $u(x)$ is now, due to the chain rule and since $u(x)\in K_{\text{CBF}}(x)$, such that $\dot{h}(x(t))\geq-\alpha(h(x(t)))$ for all $t\in\mathcal{I}$. Using the Comparison Lemma [28, Lemma 3.4] and assuming that $h(x(0))\geq 0$, it follows that $h(x(t))\geq v(t)\geq 0$ for all $t\in\mathcal{I}$, i.e., $x(0)\in\mathcal{C}$ implies $x(t)\in\mathcal{C}$ for all $t\in\mathcal{I}$. Note next that (1) is defined on $\mathcal{D}$ since $u(x)$ is only defined for $x\in\mathcal{D}$. Since $x\in\mathcal{C}$ for all $t\in\mathcal{I}$ and when $\mathcal{C}$ is compact, it follows by [28, Theorem 3.3] that $\mathcal{I}=[0,\infty)$, i.e., $\mathcal{C}$ is forward invariant. ∎

Hybrid Systems

We model and analyze hybrid systems using the formalism of .

A function $z:\mathcal{E}\to C\cup D$ is a hybrid solution to $\mathcal{H}$ if $z(0,0)\in C\cup D$ and

for each $(t,j)\in\text{dom}(z)$ s.t. $(t,j+1)\in\text{dom}(z)$, $z(t,j)\in D$ and $z(t,j+1)=G(z(t,j))$.

Problem Formulation

The class of hybrid control systems that we consider is

We are additionally given a set of expert trajectories consisting of $N_{c}$ and $N_{d}$ discretely sampled data-points along flows and jumps as

is a subset of the geometric safe set $\mathcal{S}$, and that $\mathcal{C}$ can be made forward invariant by appropriate control actions $u_{c}(z)\in\mathcal{U}_{c}$ and $u_{d}(z)\in\mathcal{U}_{d}$.

Learning Hybrid Control Barrier Functions from Data

We begin by defining a suitable notion of hybrid control barrier functions, and show that they provide a mechanism for safe control of the hybrid control system (3). We then show how such HCBFs can be learned from data via a constrained optimization problem, and provide sufficient conditions under which a feasible solution is a valid HCBF.

so that $\mathcal{C}\subseteq\mathcal{D}_{C}\cup\mathcal{D}_{D}$ This follows as we assume that $\mathcal{C}\subseteq C\cup D$, which results in $(\mathcal{C}\cap C)\cup(\mathcal{C}\cap D)=\mathcal{C}\cap(C\cup D)=\mathcal{C}$, and since $(\mathcal{C}\cap C)\cup(\mathcal{C}\cap D)\subseteq\mathcal{D}_{C}\cup\mathcal{D}_{D}$ by the choices of the sets $\mathcal{D}_{C}$ and $\mathcal{D}_{D}$. , which ensures that the set $\mathcal{D}:=\mathcal{D}_{C}\cup\mathcal{D}_{D}$ fully covers $\mathcal{C}$ – see Fig. 1(middle) and (right). The sets $\mathcal{D}_{C}$ and $\mathcal{D}_{D}$ are the equivalent to the set $\mathcal{D}$ in Section 2, but now considered separately for flows and jumps.

Based on the above definition, we define the sets of HCBF consistent inputs to be

We further assume for the remainder of the paper that the set $\mathcal{D}_{C}$ is open. If $\mathcal{D}_{C}$ is not open, one can instead assume that $\mathcal{C}\setminus\mathcal{D}_{D}$ is strictly contained within $\mathcal{D}_{C}\cup\mathcal{D}_{D}$. This will allow us, in the next result, to establish forward invariance of the set $\mathcal{C}$ under control laws $u_{c}(z)$ and $u_{d}(z)$ when the set $\mathcal{C}$ is compact.

Assume that $h(z)$ is a valid hybrid control barrier function on $\mathcal{D}$ and that $u_{c}:\mathcal{D}_{C}\to\mathcal{U}_{c}$ and $u_{d}:\mathcal{D}_{D}\to\mathcal{U}_{d}$ are continuous functions with $u_{c}(z)\in K_{\text{HCBF},c}(z)$ and $u_{d}(z)\in K_{\text{HCBF},d}(z)$. Then $z(0,0)\in\mathcal{C}$ implies $z(t,j)\in\mathcal{C}$ for all $(t,j)\in\text{dom}(z)$. If $\mathcal{C}$ is compact and satisfies $\mathcal{C}\subseteq C\cup D$, then the set $\mathcal{C}$ is forward invariant under $u_{c}(z)$ and $u_{d}(z)$, i.e., $\text{dom}(z)$ is unbounded.

During flows with $I_{j}$ not being a singleton, and if $h(z(\min(I_{j}),j))\geq 0$, we infer that $h(z(t,j))\geq 0$ for all $t\in[\min I_{j},\sup I_{j})$ due to (5) and as in the proof of Lemma 1. By continuity of $h(z)$ and $z(t,j)$ and since $\mathcal{C}$ is closed, it also holds that $h(z(\sup I_{j},j))\geq 0$ if $I_{j}=[t_{j},t_{j+1}]\times\{j\}$, i.e., the right end point is included in $I_{j}$. After each jump, it holds that $h(z(t_{j+1},j+1))\geq 0$ as a consequence of (6). Consequently, $z(0,0)\in\mathcal{C}$ implies $z(t,j)\in\mathcal{C}$ for all $(t,j)\in\text{dom}(z)$.

We next show that $\mathcal{C}$ is forward invariant under $u_{c}(z)$ and $u_{d}(z)$, i.e., $\text{dom}(z)$ is unbounded, if $\mathcal{C}$ is compact and if $\mathcal{C}\subseteq C\cup D$. First recall that $\mathcal{C}\subseteq\mathcal{D}_{C}\cup\mathcal{D}_{D}$ due to $\mathcal{C}\subseteq C\cup D$ and since $\mathcal{C}\cap C\subseteq\mathcal{D}_{C}$ and $\mathcal{C}\cap D\subseteq\mathcal{D}_{D}$. Assume now that the hybrid solution $z(t,j)$ to the system (3) under control laws $u_{c}(z)$ and $u_{d}(z)$ is maximal A hybrid solution $z(t,j)$ is maximal if there exists no other hybrid solution $z^{\prime}(t,j)$ with $\text{dom}(z)\subset\text{dom}(z^{\prime})$ and with $z(t,j)=z^{\prime}(t,j)$ for all $(t,j)\in\text{dom}(z)$. and that the hybrid time domain $\text{dom}(z)$ is bounded. By defining $(T,J):=\sup_{(t,j)}\text{dom}(z)$, we distinguish between the two cases: 1) $z(T,J)\not\in\text{dom}(z)$ and 2) $z(T,J)\in\text{dom}(z)$. 1) Note that $z(T,J)\not\in\text{dom}(z)$ can only happen when $I_{J}$ is not a singleton and when $z(t,j)$ has left the set $\mathcal{D}_{C}$ by flowing without entering $\mathcal{D}_{D}$, which would enable a successive jump that is not possible since it is assumed that the solution $z(t,j)$ is maximal. Since the set $\mathcal{C}$ is compact and since $\mathcal{D}_{C}$ is open, there has to exist a time $t<T$ such that $z(t,J)\in\mathcal{D}_{C}\setminus\mathcal{C}$ according to [28, Theorem 3.3], which does not hold since $(t,J)\in\text{dom}(z)$ and since $z(t,J)\in\mathcal{C}$ as shown previously. Since $z(t,j)$ is maximal, it follows by contradiction that $\text{dom}(z)$ is unbounded. 2) If $z(T,J)\in\text{dom}(z)$, it holds that $z(T,J)\in\mathcal{C}$ so that either $z(T,J)\in\mathcal{D}_{D}\cap\mathcal{C}$ or $z(T,J)\in(\mathcal{D}_{C}\cap\mathcal{C})\setminus(\mathcal{D}_{D}\cap\mathcal{C})$. In the former case, the solution $z(t,j)$ can be extended by a jump. In the latter case, note that $z(T,J)$ is strictly contained within the set $\mathcal{D}_{C}\cup\mathcal{D}_{D}$ so that the solution $z(t,j)$ can be extended into $\mathcal{D}_{C}$ or into $\mathcal{D}_{D}$ by flowing. By contradiction, it again follows that $\text{dom}(z)$ is unbounded. ∎

Consider again the bouncing ball example from Example 1, here artificially equipped with continuous and discrete control inputs for illustrative purposes. The dynamics are

An Optimization Based Approach

Towards the goal of learning a valid HCBF, we now define, for $\epsilon_{c},\epsilon_{d}>0$ and $p\geq 1$, the data sets

that need to be such that $\mathcal{D}=\mathcal{D}_{C}\cup\mathcal{D}_{D}\subseteq\mathcal{S}$, which can be easily achieved even when data-points $z^{i}$ are close to $\text{bd}(\mathcal{S})$ by adjusting $\epsilon_{c}$ and $\epsilon_{d}$ or by omitting $z^{i}$. Note that the set $\mathcal{D}_{C}$ is open by definition. For $\sigma>0$, define

where $\mathcal{N}$ is a ring of diameter $\sigma$ that surrounds the set $\mathcal{D}$ (see the golden ring in Figure 1). We will use the set $\mathcal{N}$ to enforce that the value of the learned HCBF $h(z)$ is negative on $\mathcal{N}$ to ensure that the set $\mathcal{C}$ is contained within the set $\mathcal{D}$, which is a necessary condition for $h(z)$ to be valid. Hence, also assume that points

The optimization problem: We now propose an optimization problem for learning a valid local HCBF, and then prove its correctness. We solve

where $\mathcal{H}$ is a normed function space and where the positive constants $\gamma_{\text{safe}}$, $\gamma_{\text{unsafe}}$, $\gamma_{\text{dyn}}^{c}$,$\gamma_{\text{dyn}}^{d}$, $L_{h}$, $L_{q}^{c}$, and $L_{q}^{d}$ are hyperparameters determined by the data-sets $Z_{\text{safe}}^{c}$, $Z_{\text{safe}}^{d}$, and $Z_{N}$, which must be sufficiently dense, as quantified by $\bar{\epsilon}$, $\epsilon_{c}$, and $\epsilon_{d}$ (conditions given below).

Lipschitz bounds: The constraints in (9c), (9e), and (9g) assume a function $\text{Lip}(\cdot,\epsilon)$ that returns an upper bound on the Lipschitz constant of its argument with respect to the state $z$ in an $\epsilon$ neighborhood of $z^{i}$ using the $p$-norm as detailed in Appendix A. It may be difficult to enforce the constraints (9c), (9e), and (9g) in the optimization problem (9). One can resort to bootstrapping the values of $L_{h}$, $L_{q}^{c}$, and $L_{q}^{d}$ by iteratively solving the optimization problem (9), calculating the values of $L_{h}$, $L_{q}^{c}$, and $L_{q}^{d}$ to verify if constraints (9c), (9e), and (9g) hold, and adjusting regularization hyperparameters accordingly. Appendix A explains how to compute Lipschitz constants for DNNs and RKHS.

Should we trust the experts? Optimization problem (9) approximates the supremums over continuous and discrete inputs in the constraints (5) and (6) with the expert actions – while computationally expedient, this may prove conservative. We note that in many cases of interest, the supremum over the continuous input $u_{c}\in\mathcal{U}_{c}$ in constraint (5) admits a closed form expression. For example, when $\mathcal{U}_{c}$ is an $\|\cdot\|$-norm ball, the left hand side of constraint (5) reduces to $\langle\nabla h(z^{i}),f_{c}(z^{i})\rangle+\|\nabla h(z^{i})g_{c}^{T}(z^{i})\|_{\star}+\alpha(h(z^{i}))$, for $\|\cdot\|_{\star}$ the dual norm. This in turn can be used to simplify constraint (9d) in optimization problem (9), and in particular eliminates the dependency on $u^{i}_{c}$. Nevertheless, the availability of expert demonstrations is still valuable as they indicate that a safe action exists, and we therefore expect a feasible HCBF $h$ and control action $u_{c}$ to exist.

Guaranteeing Safety

We next show correctness of the learned HCBF $h(z)$ obtained from (9) in two steps by:

showing that the certified safe set (8) is contained within the geometric safe set, i.e., that $\mathcal{C}\subset\mathcal{D}\subseteq\mathcal{S}$, and

proving that $h(z)$ is a valid local HCBF by ensuring that the set $\mathcal{C}$ is forward invariant under control laws $u_{c}(z)\in\mathcal{U}_{c}$ and $u_{d}(z)\in\mathcal{U}_{d}$.

1) Guaranteeing $\mathcal{C}\subset\mathcal{D}\subseteq\mathcal{S}$: First assume that $Z_{N}$ is an $\bar{\epsilon}$-net of $\mathcal{N}$, i.e., for all $z\in\mathcal{N}$, there exists $z^{i}\in Z_{N}$ such that $\|z^{i}-z\|_{p}\leq\bar{\epsilon}$. Using a standard covering and Lipschitz argument, we next show that if $h(z)$ satisfies constraint (9b) for all $z^{i}\in Z_{N}$, we have that $h(z)<0$ for all $z\in\mathcal{N}$.

Let $h(z)$ be Lipschitz continuous with local constant $L_{h}(z)$ By local constant, we here mean a Lipschitz constant in an $\bar{\epsilon}$ neighborhood of $z$., $\gamma_{\text{unsafe}}>0$ and $Z_{N}$ be an $\bar{\epsilon}$-net of $\mathcal{N}$ with

Then, if $h(z)$ satisfies constraint (9b), we have that $h(z)<0$ for all $z\in\mathcal{N}$.

Note first that, for all $z\in\mathcal{N}$, it follows that there exists a point $z^{i}\in Z_{N}$ satisfying $\|z-z^{i}\|_{p}\leq\bar{\epsilon}$ due to the assumption that $Z_{N}$ is an $\bar{\epsilon}$-net of $\mathcal{N}$. For any $z\in\mathcal{N}$, we can now select a point $z^{i}\in Z_{N}$ satisfying $\|z-z^{i}\|_{p}\leq\bar{\epsilon}$ for which it follows that

In particular, inequality $(a)$ follows from the constraint (9b) which says that $h(z^{i})\leq-\gamma_{\text{unsafe}}$ for all $z^{i}\in Z_{N}$. Inequality $(b)$ follows by the local Lipschitz constant $L_{h}(z)$ on $h(z)$ in an $\bar{\epsilon}$ neighborhood of $z^{i}$, while inequality $(c)$ follows again by the assumption that $Z_{N}$ forms an $\bar{\epsilon}$-net of $\mathcal{N}$. The strict inequality $(d)$ follows simply by the assumption that $\bar{\epsilon}<\gamma_{\text{unsafe}}/L_{h}(z^{i})$ for all $z^{i}\in Z_{N}$. ∎

We can use a similar argument on constraint (9a), which ensures that the set $\mathcal{C}$ over which $h(z)\geq 0$, as defined in equation (8), has non-empty interior.

Let $h(z)$ be Lipschitz continuous with local constant $L_{h}(z)$, and $Z_{\text{safe}}^{c}$ and $Z_{\text{safe}}^{d}$ be ${\epsilon}_{c}$- and ${\epsilon}_{d}$-nets of $\mathcal{D}_{C}$ and $\mathcal{D}_{D}$, respectively, with

and $\gamma_{\text{safe}}>0$. Then, if $h(z)$ satisfies constraint (9a), we have that $h(z)\geq 0$ for all $z\in\mathcal{D}$.

Note first that, for all $z\in\mathcal{D}_{C}$, it again follows that there exists a point $z^{i}\in Z_{\text{safe}}^{c}$ satisfying $\|z-z^{i}\|_{p}\leq\epsilon_{c}$ due to the assumption that $Z_{\text{safe}}^{c}$ is an $\epsilon_{c}$-net of $\mathcal{D}_{C}$. For any $z\in\mathcal{D}_{C}$, we can now select a point $z^{i}\in Z_{\text{safe}}^{c}$ satisfying $\|z-z^{i}\|_{p}\leq\epsilon_{c}$ for which it follows that

In particular, inequality $(a)$ follows from the constraint (9a) which says that $h(z^{i})\geq\gamma_{\text{safe}}$ for all $z^{i}\in Z_{\text{safe}}^{c}$. Inequality $(b)$ follows by the local Lipschitz constant $L_{h}(z)$ on $h(z)$ in an $\epsilon_{c}$ neighborhood of $z^{i}$, while inequality $(c)$ follows again by the assumption that $Z_{\text{safe}}^{c}$ is an $\epsilon_{c}$-net of $\mathcal{D}_{C}$. The inequality $(d)$ follows simply by the assumption that $\max({\epsilon}_{c},{\epsilon}_{d})\leq\gamma_{\text{safe}}/L_{h}(z^{i})$ for all $z^{i}\in Z_{\text{safe}}^{c}\cup Z_{\text{safe}}^{d}$. The same analysis holds for all $z\in\mathcal{D}_{D}$, so that $h(z)\geq 0$ for all $z\in\mathcal{D}$. ∎

Propositions 1 and 2 then ensure that $\mathcal{C}\subset\mathcal{D}\subseteq\mathcal{S}$, i.e., the zero level-set of $h(z)$ is contained within the geometric safe set $\mathcal{S}$. Note that the constraints (9a) and (9b) may, in practice, lead to infeasibility of (9). We resort to the same remedy as proposed in [27, equation (3.4)], i.e., enforcing constraint (9a) on smaller sets $\bar{Z}_{\text{safe}}^{c}$ and $\bar{Z}_{\text{safe}}^{d}$ with $\bar{Z}_{\text{safe}}^{c}\subset Z_{\text{safe}}^{c}$ and $\bar{Z}_{\text{safe}}^{d}\subset Z_{\text{safe}}^{d}$ to allow for smoother HCBFs to be learned at the expense of a smaller invariant safe set $\mathcal{C}$, i.e., replace (9a) by

2) Guaranteeing a valid local HCBF: For a state $z\in\mathcal{D}_{C}$, recall the definition of the function

where the control sample $u_{c}^{i}$ is associated with the sample $z^{i}$ that is such that $\|z^{i}-z\|_{p}\leq\epsilon_{c}$. Note that such a pair $(z^{i},u_{c}^{i})\in Z_{\text{dyn}}^{c}$ is guaranteed to exist when the set $Z_{\text{safe}}^{c}$ is an $\epsilon_{c}$-net of $\mathcal{D}_{D}$. The function $q_{c}(z,u_{c}^{i})$ is Lipschitz continuous in $z$ with local constant denoted by $L_{q}^{c}(z,u_{c}^{i})$, as we have assumed $h$ to be twice continuously differentiable. Recall also that

and note similarly that $q_{d}(z,u_{d}^{i})$ is Lipschitz continuous with local constant denoted by $L_{q}^{d}(z,u_{d}^{i})$. We next provide conditions guaranteeing that the learned HCBF satisfies the constraint (5) for all $z\in\mathcal{D}_{C}$ and the constraint (6) for all $z\in\mathcal{D}_{D}$.

Suppose $q_{c}(z,u_{c}^{i})$ and $q_{d}(z,u_{d}^{i})$ are Lipschitz continuous with local constants $L_{q}^{c}(z,u_{c}^{i})$ and $L_{q}^{d}(z,u_{d}^{i})$, respectively. Let $\gamma_{\text{dyn}}^{c},\gamma_{\text{dyn}}^{d}>0$, and assume that (i) $Z_{\text{safe}}^{c}$ is an $\epsilon_{c}$-net of $\mathcal{D}_{C}$ with

and (ii) $Z_{\text{safe}}^{d}$ is an $\epsilon_{d}$-net of $\mathcal{D}_{D}$ with

Then, if $h(z)$ satisfies constraints (9d) and (9f), we have that $q_{c}(z,u_{c}^{i})\geq 0$ for all $z\in\mathcal{D}_{C}$ and $q_{d}(z,u_{d}^{i})\geq 0$ for all $z\in\mathcal{D}_{D}$.

Note first that, for all $z\in\mathcal{D}_{C}$, it follows that there exists a pair $(z^{i},u_{c}^{i})\in Z_{\text{dyn}}^{c}$ satisfying $\|z-z^{i}\|_{p}\leq\epsilon_{c}$ due to the assumption that $Z_{\text{safe}}^{c}$ is an $\epsilon_{c}$-net of $\mathcal{D}_{C}$. For any $z\in\mathcal{D}_{C}$, we can now select a pair $(z^{i},u_{c}^{i})\in Z_{\text{dyn}}^{c}$ satisfying $\|z-z^{i}\|_{p}\leq\epsilon_{c}$ for which it follows that

In particular, inequality $(a)$ follows from the constraint (9d) which says that $q_{c}(z^{i},u_{c}^{i})\geq\gamma_{\text{dyn}}^{c}$ for all $(z^{i},u_{c}^{i})\in Z_{\text{dyn}}^{c}$. Inequality $(b)$ follows by the local Lipschitz constant $L_{q}^{c}(z,u_{c}^{i})$ on $q_{c}(z,u_{c}^{i})$ in an $\epsilon_{c}$ neighborhood of $z^{i}$, while inequality $(c)$ follows again by the assumption that $Z_{\text{safe}}^{c}$ is an $\epsilon_{c}$-net of $\mathcal{D}_{C}$. The inequality $(d)$ follows simply by the assumption that $\epsilon_{c}\leq\gamma_{\text{dyn}}^{c}/L_{q}^{c}(z^{i},u_{c}^{i})$ for all $z^{i}\in Z_{\text{safe}}^{c}$. This implies that $q_{c}(z,u_{c}^{i})\geq 0$ for all $z\in\mathcal{D}_{C}$. The same analysis holds for all $z\in\mathcal{D}_{D}$, so that $q_{d}(z,u_{d}^{i})\geq 0$ for all $z\in\mathcal{D}$. ∎

By combining the previous arguments, we can ensure that the learned function $h(z)$ defines an appropriate safe set, as captured by the condition $\mathcal{C}\subset\mathcal{D}\subseteq\mathcal{S}$, that can be rendered forward invariant by choosing control actions satisfying the constraints (5) and (6). The next theorem summarizes these results and guarantees that $h(z)$ from (9) is a valid HCBF.

Let $h(z)$ be a twice continuously differentiable function and let the sets $\mathcal{S}$, $\mathcal{N}$, $\mathcal{D}_{C}$, $\mathcal{D}_{D}$, $\mathcal{D}$, $\mathcal{C}$, and the data-sets $Z_{\text{dyn}}^{c}$, $Z_{\text{dyn}}^{d}$, $Z_{\text{safe}}^{c}$, $Z_{\text{safe}}^{d}$, and $Z_{N}$ be defined as above. Suppose that $Z_{N}$ forms an $\bar{\epsilon}$-net of $\mathcal{N}$ satisfying $\bar{\epsilon}<\gamma_{\text{unsafe}}/L_{h}(z^{i})$ for all $z^{i}\in Z_{N}$, and that $Z_{\text{safe}}^{c}$ and $Z_{\text{safe}}^{d}$ are ${\epsilon}_{c}$- and ${\epsilon}_{d}$-nets of $\mathcal{D}_{C}$ and $\mathcal{D}_{D}$, respectively, satisfying the conditions of Propositions 2 & 3. Let $h(z)$, $q_{c}(z,u_{c}^{i})$, and $q_{d}(z,u_{c}^{i})$ be Lipschitz continuous with local constants $L_{h}(z)$, $L_{q}^{c}(z,u_{c}^{i})$, and $L_{q}^{d}(z,u_{d}^{i})$, respectively. Then if $h(z)$ satisfies constraints (10), (9b), (9d), and (9f), the set $\mathcal{C}$ is non-empty, $\mathcal{C}\subset\mathcal{D}\subseteq\mathcal{S}$, and the function $h(z)$ is a valid local hybrid control barrier function on $\mathcal{D}$ with domain $\mathcal{N}\cup\mathcal{D}$.

Case Studies

The code for both case studies is available at https://github.com/unstable-zeros/learning-hcbfs. In both our simulations, we numerically integrate the hybrid dynamics of interest using an integrator implementation inspired by Drake . We build our implementation on top of scipy.integrate.solve_ivp’s event detection API. This allows us to get precise notifications for when a system makes a discrete jump.

We parametrize the HCBF candidate $h$ as a two-hidden-layer fully-connected DNN with tanh activation functions and 64 neurons in each hidden layer. The training is implemented using jax and the Adam algorithm with a cosine decay learning rate. We craft a loss function by relaxing the constraints in (9) – hyperparameter choices and other training details can be found in Appendix B. The set $\mathcal{C}$ of the learned HCBF is shown as green dots in the middle subplot of Figure 2. One may clearly observe that $\mathcal{C}$ is strictly contained within the geometric safe set, i.e. $\mathcal{C}\subset\mathcal{S}$.

We now test if the learned HCBF is able to produce safe control inputs that keep the system within the set $\mathcal{C}$. We consider a nominal control law $u_{c,\text{nom}}$ that looks to track the reference path shown in dash-dotted blue in Fig. 2(middle) and (right): as the system has full control, it can exactly track the reference path, but without correction, this would lead to violation of the velocity constraint. Starting from an initial state $(0.2,-1.9)$, we simulate the controlled system for $2.25$ seconds. During flow, we solve the CBF-QP problem for the continuous input $u_{c}$ (see Appendix B.2). During jump, we perform line search with a decay factor $0.95$ to find the scalar discrete input $u_{d}$ that satisfies (6). The closed-loop trajectory produced by the learned HCBF is plotted in Figure 2 (middle). As a comparison, we also plot in Figure 2 (right) the trajectory obtained using the analytical HCBF. Albeit slightly more conservative, the learned HCBF keeps the ball within $\mathcal{C}$ at all times during both flow and jump.

Compass gait

We consider the compass gait walker . Originally introduced by , the compass gait dynamics describe a passive bipedal robot walking down an inclined plane at a constant velocity. This system is described by a four-dimensional continuous state

consisting of the angle $\theta$ and angular velocity $\dot{\theta}$ of each leg. In this notation, the “stance” foot corresponds to the foot that is in contact with the ground as the compass gait walker makes its descent down the ramp; hence, the “swing” foot refers to the foot that is not in contact with the ramp at a particular instant in time. In our simulations, the walker’s initial stance leg is its left leg, and therefore its initial swing leg is its right leg. To improve the walking capabilities, we add actuation to hip joint and the ankle of the stance leg. To collect expert trajectories, we use the energy-based controller of . All implementation details for the compass gait walker can be found in Appendix C.

Learning and analyzing an HCBF for the compass gait walker hybrid system poses several challenges, including the well-known sensitivity of the compass gait walker to its initial conditions and the inherent difficulties in visualizing a four-dimensional state space. To facilitate a meaningful visualization of the four-dimensional state space, when collecting expert data, we fix the stance leg initial condition to the point $[\theta_{\text{stance}},\dot{\theta}_{\text{stance}}]=[0,0.4]$ on the passive limit cycle, and vary the initial condition of the swing leg by adding uniform noise to corresponding passive limit cycle state $[\theta_{\text{swing}},\dot{\theta}_{\text{swing}}]=[0,2.0]$ of the swing leg.

We again parameterize the candidate HCBF $h$ with a two-hidden-layer fully-connected neural network with tanh activations and with 32 and 16 neurons in the first and second hidden layers, respectively; as before, we determine the hyperpameters by grid search. However, unlike the previous example, the task of identifying boundary points is complicated by the higher dimensionality of the state space. Therefore, we propose a novel algorithm that can be used to identify boundary points by sampling from the space of expert trajectories. The algorithm, described in Appendix C, identifies boundary points by computing the pairwise distances between all of the expert states and thresholding based on the number of neighbors a point has within an $\epsilon$-norm ball.

In Figure 3, we show the constraint satisfaction rates, the training loss, and the state separation attained by the learned HCBF. Note that these figures highlight the challenges of multi-objective optimization, i.e., trying to achieve all of the constraints in the optimization problem (9) via its unconstrained relaxation. Nevertheless, we emphasize that the use of robust optimization by including slack variables $\gamma_{\text{safe}}$, $\gamma_{\text{unsafe}}$, $\gamma_{\text{dyn}}^{c}$, and $\gamma_{\text{dyn}}^{d}$ leads to HCBFs that perform well in practice.

In the left panel of Fig. 4, we visualize the learned HCBF. Starting from an initial condition with the same left leg state as the expert trajectories, we identify the values for $h(z)$ at which $u_{\text{HCBF}}\neq u_{\text{nom}}$ in green, i.e. where the HCBF controller corrects the nominal controller. In red, we plot the phase portrait for the right leg corresponding to a trajectory using the HCBF-QP controller. To demonstrate the physical interpretation of this learned HCBF, in the right top panel of Fig. 4, we show the motion of the compass gait walker down the ramp, marking in green where the HCBF-based controller takes over; in the right lower panel of Fig. 4 we see the failure of a zero-valued controller from the same initial condition, showing that the learned HCBF preserves safety. Videos of both the safe HCBF and unsafe nominal controller trajectories can be found in the supplementary material.

To visualize the safe set of the learned HCBF, in Figure 5, we show that despite the fact that our nominal controller is not providing any control inputs, the HCBF-based controller has a similar safe set to that of the energy-based controller. In this way, the HCBF causes the uncontrolled system to match the safety characteristics of the expert energy-based controller. In particular, it can be observed that the safe set $\mathcal{C}$, which is described by the zero superlevel set of $h(z)$, under-approximates the safe expert behavior. As can further be observed, there are regions in the state space where our HCBF-based controller provides safe system trajectories while the energy-based controller results in unsafe system trajectories (e.g., the bottom right corner of both plots shown in Figure 5). We suspect that the safe set $\mathcal{C}$ enjoys asymptotic stability properties similar to those of the continuous case , allowing for an expanded region of safety as compared to that of the expert. A more detailed investigation of this observation is, however, subject to future work.

Conclusion

We presented a framework for learning safe control laws for hybrid systems. We introduced HCBFs and sufficient conditions under which an HCBF based control law guarantees safety, i.e., a desired safe set is made forward invariant. We then showed how to learn such HCBFs from data using an optimization-based framework. We gave sufficient conditions under which feasible solutions to the optimization problem are valid HCBFs, and illustrated our methods on two case studies. Future work will look to extend this approach to hybrid systems described by differential inclusions, so as to be applicable to systems with friction and stiction, as well as to develop statistical guarantees of correctness to alleviate the sampling burden of our method.

References

Appendix A Appendix A

To verify (9c), (9e), and (9g), the Lipschitz constant $L_{h}$ of the learned function $h(z)$ as well the Lipschitz constant $L_{\nabla h}$ of its gradient $\nabla h(z)$ need to be calculated first. The following discussion is mainly taken from [27, Section 3.4.2]. When $\mathcal{H}$ consists of twice differentiable functions, as is the case when $h\in\mathcal{H}$ is parametrized by a Deep Neural Net with twice differentiable activation functions or a Reproducing Kernel Hilbert Space, the following is shown to hold.

an upper bound on the Lipschitz constant of $h(z)$ is provided as $\sqrt{2\sigma^{2}}(1+\sqrt{n_{z}/l}+\sqrt{(2/l)\log(1/\delta)})\|\theta\|_{2}$ with probability at least $1-\delta$ where $\sigma$ is as explained in [27, Section 3.4.2]. An upper bound on the Lipschitz constant of $\nabla h(z)$ can be derived by the bound $\|\nabla^{2}h(z)\|\leq 3\sqrt{2}\|\theta\|_{\infty}\sigma^{2}(l+n_{z}+2\log(1/\delta))/\sqrt{l}$ that holds with probability at least $1-\delta$.

Deep Neural Net: When $h(z)$ is a DNN, the problem of exactly computing the Lipschitz constant of $h(z)$ is known to be NP-hard. Because most commonly-used activation functions $\phi$ are known to be 1-Lipschitz (e.g., ReLU, tanh, sigmoid), a naive upper bound on the Lipschitz constant of $h(z)$ is given by the product of the norms of the weight matrices; that is, $L_{h}\leq\prod_{k}\|W^{k}\|$. However, this bound is known to be quite loose . Recently, the authors of proposed a semidefinite-programming based approach to efficiently compute an accurate upper bound on $L_{h}$. On the other hand, there are relatively few results that provide accurate upper bounds for the Lipschitz constant of the gradient of $h(z)$. The only general method for computing an upper bound on $L_{\nabla h}$ is through post-hoc sampling.

Now, using these Lipschitz constants $L_{h}$ and $L_{\nabla h}$ of $h(z)$ and $\nabla h(z)$, respectively, it can be seen that the functions $q_{c}(z,u_{c}^{i})$ and $q_{d}(z,u_{d}^{i})$ in (9d) and (9f) are locally Lipschitz continuous in $z$ since $\nabla h(z)$, $f_{c}(z)$, $f_{d}(z)$, $g_{c}(z)$, $g_{d}(z)$, and $\alpha(h(z))$ are locally Lipschitz continuous and since function composition preserves Lipschitz continuity. Upper bounds of the Lipschitz constants $L_{q}^{c}$ and $L_{q}^{d}$ follow immediately.

Appendix B Appendix B: Bouncing Ball

The code for the bouncing ball case study can be found at https://github.com/unstable-zeros/learning-hcbfs.

The control goal of the bouncing ball case study is to track a desired reference path shown as dash-dotted blue lines in Fig. 2 (middle and right). This reference path is obtained by dropping the ball from $(1,0)$ without applying any control input, i.e., $u_{c}:=0$, until it hits the ground. The discrete control input $u_{d}$ is set to $1.0$ when this happens. Reversing the velocity in sign while keeping the position unchanged gives the reference path in the right half plane.

In order to track the reference path, we design a linear error-feedback control law $u_{c,\text{nom}}=K(z(t,j)-z_{\text{ref}}(t))$ with $K=\begin{bmatrix}10&5.48\end{bmatrix}^{T}$ via solving the Riccati equation. The reference state $z_{\text{ref}}(t)$ is selected as the state on the reference path that is the closet to $z(t,j)$ in Euclidean distance. We set the nominal discrete input to be $u_{d,\text{nom}}=1.2$ such that it amplifies the velocities after collisions and thus is more likely to cause constraint violation. Note that neither the reference path nor the closed-loop trajectory obtained by applying the nominal controllers $u_{c,\text{nom}}$ and $u_{d,\text{nom}}$ complies with the geometric safe set $\mathcal{S}$.

B.2 Training data

To obtain training data during flows, we use the above reference controller $u_{c,\text{nom}}$ together with the analytical HCBF in Example 2, which, per solving the CBF-QP problem , gives a safe controller $u_{c}$ during flow. The CBF-QP basically consists of solving a convex quadratic program with decision variable $u_{c}$, cost function $\|u_{c}-u_{c,\text{nom}}\|$, and the constraint $\langle\nabla h(z),f_{c}(z)+g_{c}(z)u_{c}\rangle\geq-\alpha(h(z))$. The safe control input $u_{d}$ used to obtain training data during jumps is essentially a thresholding function and can be found analytically as mentioned in Example 2. Based on these safe controllers $u_{c}$ and $u_{d}$, we obtain data-sets $Z^{c}_{\text{safe}}$ and $Z^{d}_{\text{safe}}$ containing 5000 safe states $z^{i}$ and associated expert demonstrations $u^{i}_{c}$ and $u^{i}_{d}$, which are shown as the green and magenta dots in the left subplot of Figure 2.

B.3 Hyperparameters for training the neural network

We train the neural network for $1.5\times 10^{3}$ epochs using the loss given by unconstrained relaxation of Problem (9) in Section 3. The hyperparameters, shown in Table 1, are found by grid search.

B.4 Visualization of the learned HCBF

We visualize the learned and analytical HCBFs in $(v,x,h(z))$-space in Figure 6 by plotting their level sets. The green dots indicate where $h(z)\geq 0$ on $C\cup D$, while the purple dots additionally indicate where $h(z)\geq 0$ on $\{z\in C\mid\ x=0\ ,\ 0\leq v\leq 2\}$, i.e. the possible set of states after an impact with the ground.

B.5 Validness of the learned HCBF

We performed post-verification of the learned HCBF satisfying Propositions 1, 2 and 3, which serve as sufficient conditions for learning a valid HCBF as stated in Theorem 2. Since all of our data sets were gridded evenly on the state space, densities of the $\epsilon$-nets are equal to the gridding resolutions, which are $\bar{\epsilon}=0.01$ and $\epsilon_{c}=\epsilon_{d}=0.02$. The local Lipschitz constants $L_{h}(\cdot),L_{q}^{c}(\cdot),L_{q}^{d}(\cdot)$ were approximated using the norm of their gradients, e.g. $L_{h}(z)\approx\|\nabla h(z)\|_{2}$, which gives a tight estimation of the Lipschitz constants due to our dense gridding scheme. The percentages of data points that satisfy those conditions are summarized in Table 2.

Appendix C Appendix C: Compass Gait Walker

The code for the compass gait walker case study can be found at https://github.com/unstable-zeros/learning-hcbfs.

The approach we have described crucially relies on being able to sample from “unsafe” regions of state space, i.e. to sample states $z^{i}\in Z_{N}$. For low-dimensional state spaces, it is often possible to take advantage of the underlying geometry of the hybrid system to sample from this region as for instance in the bouncing ball case study. However, for higher-dimensional state spaces such as the compass gait walker, it may not be possible to easily leverage the underlying geometry to obtain these states.

Before demonstrating how we used this algorithm in the compass gait case study, we provide some simple examples to illustrate the efficacy of this algorithm toward identifying the boundaries of different sets of points. In Figure 7(c), we show the result of running Algorithm 1 on mixtures of two Gaussians. In Figure 8, we show a three-dimensional example in the unit cube. Finally, we show the result of running Algorithm 1 on 100,000 states taken from the expert compass gait walker in Figure 9.

C.2 Implementation details

Our implementation of the compass gait walker relies heavily on the C++ implementation in the Drake package . In particular, we re-implement the compass gait walker in Python with Jax : our implementation is publicly available on the project Github repository. We use the same default settings for the compass gait walker as are used in the Drake implementation; these values are detailed in Table 3.

The hyperparameters used for training a HCBF for the compass gait walker are given in Table 4. These hyperparameters were chosen via grid search.

C.3 Collecting expert trajectories

To collect expert trajectories, we use the energy-based controller described in eq. (24) in . This controller applies actuation to the hip joint, leaving the ankle joints unactuated. In particular, this controller takes the following form

where we set $\lambda:=0.3$ and where $E^{*}$ is the reference energy from the passive limit cycle, and $E$ is the current total mechanical energy of the compass gait walker. Throughout, we use a reference energy of $E^{*}=153.244J$ as suggested by .

As described in the main text, we collect expert trajectories by fixing the initial condition of the left leg to $[\theta_{\text{stance}},\dot{\theta}_{\text{stance}}]=[0,0.4]$ and varying the initial condition of the right foot $[\theta_{\text{swing}},\dot{\theta}_{\text{swing}}]=[0+u_{1},2.0+u_{2}]$ where $u_{1}\sim\text{Uniform}([-0.2,0.2])$ and $u_{2}\sim\text{Uniform}([-0.5,0.5])$. In Figure 5 (right), we show the successful right foot initial conditions for the energy-based controller corresponding to this initial condition. In particular, to train the HCBF, we collected 500 rollouts using this scheme. For each rollout, we used a horizon of $T=750$ steps and a time interval of $\Delta t=0.01$.