1 Introduction↩︎

Driven by applications in autonomous driving, robotics, and aerospace systems, the topic of safety has recently received a lot of attention in the control theory community. Designing and verifying safe controllers in these domains is particularly challenging due to various sources of uncertainty, such as state estimation errors, imperfect perception, and unmodeled dynamics. Although the study and design of safe controllers that are robust to such sources of uncertainty has received considerable attention in the literature, most existing works assume deterministic and bounded disturbances with known bounds. Such assumptions are uncommon in practice and lead to overly conservative performance. In contrast, this work is motivated by the need to design controllers that maintain safety in the presence of stochastic and potentially unbounded disturbances, conditions that naturally arise when employing techniques such as Kalman filtering or simultaneous localization and mapping (SLAM).

1.1 Literature Review↩︎

There are a variety of tools to design controllers with safety guarantees, including control barrier functions (CBFs) [1], reachability-based controllers [2], and model predictive control [3]. There has been a substantial effort to adapt these techniques for systems with uncertainty. In the CBF literature, this problem has been extensively studied for continuous-time systems and deterministic and bounded disturbances [4]–[8]. Other works have explored the problem under various uncertainty models, such as stochastic and possibly unbounded [9]–[13], Gaussian process-based [14], [15] or through Wasserstein ambiguity sets [16], [17]. For discrete-time systems, the works [12], [13], [18] leverage the theory of martingales to provide bounds on the probability of exiting the safe set within a given time horizon. However, the condition on the control input derived in these papers only leverages the first moment of the distribution and can be conservative if more information about the uncertainty is available or not applicable if such first moment is unknown. On the other hand, [19] introduces the risk-sensitive notion of CVaR safety, and a CBF-based condition that can be used to certify it. However, controllers based on CVaR safety can be quite conservative in practice, and are only tractable for a small class of dynamics and safety constraints. Similar risk-aware approaches are taken in [20], [21]. The recent work [22] leverages the scenario approach [23] to design controllers that are safe with a prescribed probability by forcing them to be safe for a number of different scenarios (i.e., uncertainty realizations). Beyond CBF-based approaches, there exist various works in the literature that study the problem of guaranteeing safety constraints for discrete-time systems subject to stochastic uncertainty, particularly in the context of MPC [24]–[26].

1.2 Statement of Contributions↩︎

We consider the problem of designing safe controllers for discrete-time stochastic systems. Our first contribution is the introduction of a probabilistic notion of CBF which we show can be used to design controllers with probabilistic safety guarantees over a finite time horizon. However, verifying whether a function is a probabilistic CBF is impractical, because it requires knowledge of the uncertainty distribution. In our second contribution we sidestep this difficulty by introducing two different sufficient conditions which guarantee that a function is a probabilistic CBF. These conditions only require knowledge of the moments of the distribution of the value of the CBF at the next time step. The first condition only leverages a known upper bound on the CBF and the first moment of such distribution, whereas the second condition uses its first and second moments. We also study various cases under which these conditions are convex in the control input and are thus amenable to optimization-based control design. Next, we consider the problem of verifying that a function is a probabilistic CBF when moment information is not available but instead we have a dataset consisting of uncertainty realizations. In our third contribution we leverage concentration inequalities, scenario optimization, and conformal prediction to provide different sufficient conditions based on such dataset that ensure that a function is a probabilistic CBF with high confidence. Finally, we validate our results in both simulation and hardware on quadruped robots.

1.3 Notation↩︎

We denote by \(\mathbb{N}, \mathbb{R}\) the set of natural and real numbers, respectively. We use bold symbols to represent vectors and matrices and non-bold symbols to represent scalar quantities. For \(N\in\mathbb{N}\), we let \([N]=\{1,\ldots,N\}\). Given \({\mathbf{x}}\in\mathbb{R}^n\), \(\left\lVert{\mathbf{x}}\right\rVert\) denotes its Euclidean norm. Given a matrix \({\mathbf{M}}\in\mathbb{R}^{n\times n}\), \(\text{Tr}({\mathbf{M}})\) denotes its trace. For a random variable \(Z\), we denote by \(\mathbb{E}[Z]\) and \(\operatorname{Var}(Z)\) its expected value and variance, respectively. If \(Z\) is multivariate, \(\text{Cov}(Z)\) denotes its covariance matrix. Given \(\delta > 0\), and \(k\in\mathbb{N}\) values \(R^{(1)}, \ldots, R^{(k)}\) sorted in non-decreasing order, \(\text{Quantile}_{1-\delta}(R^{(1)}, \ldots, R^{(k)},\infty)\) denotes the \(1-\delta\) quantile of the empirical distribution of the values \(R^{(1)}, \ldots, R^{(k)}, \infty\), which can be equivalently obtained as \(R^{(p)}\), where \(p = \lceil (k+1)(1-\delta) \rceil\), and \(\lceil \cdot \rceil\) denotes the ceiling function.

2 Motivation↩︎

Throughout this paper we consider a discrete-time stochastic system of the form: \[\begin{align} \label{eq:discrete-time-system} {\mathbf{x}}_{t+1} = {\mathbf{F}}({\mathbf{x}}_t, {\mathbf{u}}_t, {\mathbf{d}}_t), \end{align}\tag{1}\] with \({\mathbf{x}}_t\in\mathbb{R}^n\) the state, \({\mathbf{u}}_t\in\mathbb{R}^m\) the control input, and \({\mathbf{d}}_t\in\mathbb{R}^d\) a random variable distributed according to a distribution \({\mathcal{D}}\), i.e., \({\mathbf{d}}_t \sim {\mathcal{D}}\). For simplicity, we assume that \({\mathcal{D}}\) is state and time independent.

Given a user-prescribed safe set \({\mathcal{C}}\subset\mathbb{R}^n\), defined as the \(0\)-superlevel set of a continuous function \(h\), (i.e., \({\mathcal{C}}= \{{\mathbf{x}}\in\mathbb{R}^n : h({\mathbf{x}}) \geq 0\}\)), our goal is to design a state-feedback controller \({\mathbf{k}}:\mathbb{R}^n\to\mathbb{R}^m\) that ensures that the iterates of the closed-loop system obtained from 1 by using \({\mathbf{k}}\) remain in \({\mathcal{C}}\) at all times. However, the presence of the stochastic disturbance in 1 poses a significant challenge in finding such controller. In fact, this is impossible if the distribution \({\mathcal{D}}\) is not supported on a bounded set, because the iterates will exit the set \({\mathcal{C}}\) in finite time with probability \(1\) (cf. [27]). Hence, we are interested in a notion of safety over a finite time horizon and with a prescribed probability, which we formalize next.

Next we introduce the notion of probabilistic CBF, which will prove to be a useful tool to certify probabilistic safety over a finite time horizon.

where \({\mathbf{d}}\sim{\mathcal{D}}\). We note that Definition 2 is simply a probabilistic version of the standard CBF condition for discrete-time systems [28]. In the sequel, whenever the parameter \(\delta\) is clear from the context, we refer to a \(\delta\)-probabilistic CBF simply as a probabilistic CBF. We also fix \(\alpha\in[0,1]\), \(\delta\in(0,1)\) and let \(\Delta h:\mathbb{R}^n\times\mathbb{R}^m\times\mathbb{R}^d \to \mathbb{R}\) be defined as \[\begin{align} \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) = h({\mathbf{F}}({\mathbf{x}},{\mathbf{u}},{\mathbf{d}})) - \alpha h({\mathbf{x}}). \end{align}\] The following result shows that probabilistic CBFs can be used to verify the notion of probabilistic safety over a given time horizon in Definition 1.

Define the event \(\Gamma_{t} := \bigcap_{s=0}^t \{ {\mathbf{x}}_s \in {\mathcal{C}}\}\). By the law of conditional probabilities [29] \[\begin{align} \label{eq:product-conditional-probs} \mathbb{P}\Big( \bigcap_{t=0}^H \{ {\mathbf{x}}_t \in {\mathcal{C}}\} \Big) = \prod_{t=1}^H \mathbb{P}\Big( {\mathbf{x}}_t \in {\mathcal{C}}| \Gamma_{t-1} \Big). \end{align}\tag{2}\] Note that for each \(t\in[H]\), \[\begin{align} &\mathbb{P}\Big( {\mathbf{x}}_t \in {\mathcal{C}}| \Gamma_{t-1} \Big) = \\ &\mathbb{P}\Big( h({\mathbf{F}}({\mathbf{x}}_{t-1},{\mathbf{k}}({\mathbf{x}}_{t-1}),{\mathbf{d}}_{t-1})) \geq 0 | \Gamma_{t-1} \Big) \geq \\ &\mathbb{P}\Big( h({\mathbf{F}}({\mathbf{x}}_{t-1},{\mathbf{k}}({\mathbf{x}}_{t-1}),{\mathbf{d}}_{t-1})) \geq \alpha h({\mathbf{x}}_{t-1}) | \Gamma_{t-1} \Big) \geq 1-\delta, \end{align}\] The first inequality follows from the fact that if \({\mathbf{x}}_{t-1}\in{\mathcal{C}}\), then \(h({\mathbf{x}}_{t-1}) \geq 0\), and \(h({\mathbf{F}}({\mathbf{x}}_{t-1},{\mathbf{k}}({\mathbf{x}}_{t-1}),{\mathbf{d}}_{t-1}) \geq \alpha h({\mathbf{x}}_{t-1}))\) implies that \(h({\mathbf{F}}({\mathbf{x}}_{t-1},{\mathbf{k}}({\mathbf{x}}_{t-1}),{\mathbf{d}}_{t-1}) \geq 0\). The last inequality follows from ?? . Hence, by 2 we have that ?? holds. By taking \(\delta\) to satisfy ?? , it follows that \((1-\delta)^{H} \geq 1-\epsilon\), and \({\mathbf{k}}\) is \(\epsilon\)-safe over a time horizon \(H\).

Proposition 1 shows that controllers obtained from the probabilistic CBF condition ?? can be used to verify the notion of probabilistic safety introduced in Definition 1. Unfortunately, verifying that \(h\) is a probabilistic CBF as per Definition 2 is impractical because it requires computing a probability over the distribution \({\mathcal{D}}\), which is often unknown. In the following sections, we devise various sufficient conditions that can be used to verify Definition 2 without requiring full knowledge of the distribution \({\mathcal{D}}\).

3 Verification of Probabilistic CBFs using known Moments↩︎

In practice, although one generally does not know the full distribution \({\mathcal{D}}\), it is common to have information about some of its moments. In this section we study how to leverage this information to verify that \(h\) is a probabilistic CBF. Our first result establishes a sufficient condition for that to hold by imposing a constraint on the expected value of \(\Delta h\).

Note that by assumption, for each \({\mathbf{x}}\in{\mathcal{C}}\) there exists \({\mathbf{u}}\in\mathbb{R}^m\) and \(b > 0\) such that the random variable \(b - \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}})\) is positive almost surely. By Markov’s inequality [30], \[\begin{align} \mathbb{P}( \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \leq 0 ) &= \mathbb{P}( b - \Delta h( {\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \geq b ) \\ &\leq \frac{ \mathbb{E}[ b-\Delta h( {\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) ] }{ b }. \end{align}\] Now, from ?? we have that \(\mathbb{E}[b-\nabla h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}})] \leq b\delta\) and hence we have for each \({\mathbf{x}}\in{\mathcal{C}}\) there exists \({\mathbf{u}}\in\mathbb{R}^m\) such that \(\mathbb{P}( \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \leq 0 ) \leq \delta\), from where it follows that \(h\) is a \(\delta\)-probabilistic CBF.

Since ?? is derived though Markov’s inequality, we refer to it as the Markov-based condition. Proposition 2 shows that even if the distribution \({\mathcal{D}}\) is unknown, the expected values of the random variable \(\Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}))\) can be used to verify that \(h\) is a probabilistic CBF. Note also that one simple condition that ensures that \(\Delta h\) is uniformly upper bounded is if \(h\) is uniformly upper bounded.

In practice, in order to design a controller that ensures probabilistic safety, we are interested in including input constraints such as ?? as constraints of an optimization problem. However, as it is also the case for deterministic discrete-time CBFs [28], the condition ?? is generally not convex in \({\mathbf{u}}\), which compromises the computational tractability of such optimization-based control design. The following result leverages the convexity properties of \(h\) to derive another set of conditions for which the convexity properties with respect to \({\mathbf{u}}\) are easier to analyze.

First, if \(h\) is convex, by Jensen’s inequality, we have \(h( \mathbb{E}[ {\mathbf{F}}({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) ] ) \leq \mathbb{E}[ h( {\mathbf{F}}({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) ) ]\). Therefore, the satisfaction of ?? implies that ?? holds. By Proposition 2, this means that \(h\) is a \(\delta\)-probabilistic CBF. Second, if \(h\) is concave, by [18] (which is based on a result from [31]), we have that \[\begin{align} \notag &\mathbb{E}[ h({\mathbf{F}}({\mathbf{x}},{\mathbf{u}},{\mathbf{d}})) ] \geq \\ &h( \mathbb{E}[{\mathbf{F}}({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) ]) - \frac{\lambda}{2}\text{Tr}( \text{Cov}({\mathbf{F}}({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) ) ). \end{align}\] Hence, the satisfaction of ?? implies that ?? holds. By Proposition 2, this means that \(h\) is a \(\delta\)-probabilistic CBF.

The following remark comments on the convexity properties with respect to \({\mathbf{u}}\) of the conditions ?? and ?? .

The following result provides another sufficient condition for \(h\) to be a probabilistic CBF. In this case, the condition does not require a known upper bound for \(\Delta h\) but assumes knowledge of its variance (i.e., its second moment).

By Cantelli’s inequality [33], we have that for any \({\mathbf{x}}\in\mathbb{R}^n, {\mathbf{u}}\in\mathbb{R}^m\), and \(\kappa \geq 0\), \[\begin{align} &\mathbb{P}\Big( \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \leq \mathbb{E}[\Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}})] - \kappa \Big) \\ &\leq \frac{ \operatorname{Var}( \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) ) }{ \operatorname{Var}( \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}})) + \kappa^2 } \end{align}\] By taking \(\kappa = \kappa_{{\mathbf{x}},{\mathbf{u}}} := \sqrt{ \operatorname{Var}\Big( \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \Big) \frac{1-\delta}{\delta} }\), we have \[\begin{align} \mathbb{P}\Big( \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \leq \mathbb{E}[\Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}})] - \kappa_{{\mathbf{x}},{\mathbf{u}}} \Big) \leq \delta. \end{align}\] Now, for each \({\mathbf{x}}\in{\mathcal{C}}\), select \({\mathbf{u}}\in\mathbb{R}^m\) so that ?? holds. It follows that \[\begin{align} &\mathbb{P}\Big( \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \leq 0 \Big) \leq \\ &\mathbb{P}\Big( \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \leq \mathbb{E}[ \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) ] - \kappa_{{\mathbf{x}},{\mathbf{u}}} \Big) \leq \delta. \end{align}\] Hence, \(\mathbb{P}\Big( \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \geq 0 \Big) \geq 1-\delta\), and \(h\) is a \(\delta\)-probabilistic CBF.

Since ?? is derived through Cantelli’s inequality, we refer to it as the Cantelli-based condition. Proposition 3 shows that even if the distribution \({\mathcal{D}}\) is unknown, if the expected value and variance of \(\Delta h\) are known, then one can verify that \(h\) is a probabilistic CBF. The following result is an analogue of Corollary 1 for the Cantelli-based condition.

The proof of Corollary 2 follows an argument analogous to that of Corollary 1.

The results in Propositions 2 and 3, leverage knowledge of the first and second moments of the distribution of \(\Delta h\) to provide bounds on the probability of its tails. Although it is possible to derive similar (possibly tighter) results when knowledge of higher moments is available (cf. [35]–[37] for concentration inequalities using higher moments), this usually leads to conditions with complicated dependencies on the control input \({\mathbf{u}}\) and that are computationally not amenable for optimization-based control.

4 Verification of Probabilistic CBFs Using Data↩︎

Section 3 established a set of results that show how to verify that a function is a probabilistic CBF by leveraging moments of the uncertainty distribution. In this section, we take an alternative approach that relies on the availability of samples of the uncertainty distribution, rather than knowledge of its moments. However, since the samples themselves are random, in general it is not possible to exactly certify that \(h\) is a probabilistic CBF. Instead, one can only do that with a given confidence. The following definition formalizes this idea.

The following result shows that the notion of CBF in Definition 3 can be used to verify that safety holds over a finite time horizon with a given probability over the stochasticity of 1 and confidence over \({\mathbf{D}}_N\).

As shown in the proof of Proposition 1 and using the same notation, for any dataset \({\mathbf{D}}_N\), we have \[\begin{align} \mathbb{P}\Big( \bigcap_{t=0}^H \{ & {\mathbf{x}}_t\in{\mathcal{C}}\} \Big) \! \\ & \geq \! \prod_{t=1}^H \mathbb{P}\Big( \Delta h({\mathbf{x}}_{t-1},{\mathbf{k}}({\mathbf{x}}_{t-1}),{\mathbf{d}}_{t-1}) \geq 0 | \Gamma_{t-1} \Big). \end{align}\] Hence, if we let \(A_N\) be the event \[\begin{align} \prod_{t=1}^H \mathbb{P}\Big( \Delta h({\mathbf{x}}_{t-1},{\mathbf{k}}({\mathbf{x}}_{t-1}),{\mathbf{d}}_{t-1}) \geq 0 | \Gamma_{t-1} \Big) \geq 1-\epsilon, \end{align}\] (defined by the randomness of the dataset \({\mathbf{D}}_N\)) we have \[\begin{align} \label{eq:first-inequality} \mathbb{P}_N\Big( \mathbb{P}\Big( \bigcap_{t=0}^H \{ {\mathbf{x}}_t\in{\mathcal{C}}\} \Big) \geq 1-\epsilon \Big) \geq \mathbb{P}_N (A_N). \end{align}\tag{3}\] Now note that if the dataset \({\mathbf{D}}_N\) is such that the event \(B_{t,N}\), defined as \[\begin{align} \mathbb{P}\Big( \Delta h({\mathbf{x}}_{t-1},{\mathbf{k}}({\mathbf{x}}_{t-1}),{\mathbf{d}}_{t-1}) \geq 0 | \Gamma_{t-1} \Big) \geq (1-\epsilon)^{\frac{1}{H}}, \end{align}\] holds for all \(t\in[H]\), then \(A_N\) also holds. Therefore, \[\begin{align} \label{eq:second-inequality} &\mathbb{P}_N( A_N ) \geq \mathbb{P}_N\Big( \bigcap_{t=1}^H B_{t,N} \Big) \geq \sum_{t=1}^H \mathbb{P}_N (B_{t,N}) - (H-1), \end{align}\tag{4}\] where the last inequality follows from Fréchet’s inequality [38]. Now, since \(1-\delta \geq (1-\epsilon)^{\frac{1}{H}}\), if the event \(C_{t,N}\), defined as \[\begin{align} \mathbb{P}\Big( \Delta h({\mathbf{x}}_{t-1},{\mathbf{k}}({\mathbf{x}}_{t-1}),{\mathbf{d}}_{t-1}) \geq 0 | \Gamma_{t-1} \Big) \geq 1-\delta, \end{align}\] holds, then \(B_{t,N}\) also holds. Therefore, \(\mathbb{P}_N(B_{t,N}) \geq \mathbb{P}_N(C_{t,N})\). Now, since \(h\) is a \(\delta\)-probabilistic CBF with confidence \(\beta\), we have \(\mathbb{P}_N(C_{t,N}) \geq 1-\beta\) for all \(t\in[H]\), and 3 , 4 we have \[\begin{align} \mathbb{P}_N\Big( \mathbb{P}\Big( \bigcap_{t=0}^H \{ {\mathbf{x}}_t\in{\mathcal{C}}\} \Big) \geq 1-\epsilon \Big) \geq 1-H\beta. \end{align}\] Now the result follows from the fact that \(\beta \leq \frac{\tilde{\beta}}{H}\).

In the rest of the section, we fix \(\delta,\beta\in(0,1)\), and consider a dataset \({\mathbf{D}}_N\) of \(N\in\mathbb{N}\) samples as defined in Proposition 4. The following result establishes a sufficient condition for \(h\) to be a probabilistic CBF with a given confidence in the case where the random variable \(\Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}))\) is bounded.

Let \({\mathbf{x}}\in{\mathcal{C}}\) and pick \({\mathbf{u}}\in\mathbb{R}^m\) so that ?? holds. Note that such \({\mathbf{u}}\) is dependent on the dataset \({\mathbf{D}}_N\). Now, we have \[\begin{align} &\mathbb{P}_N\Big( \Big\rvert\mathbb{E}[\Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}})] - \frac{1}{N} \sum_{i=1}^N \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}^{(i)}) \Big\rvert \leq \epsilon \Big) \\ &\geq 1 - 2 \exp\Bigg\{ -\frac{2 N \epsilon^2}{ (b-a)^2 } \Bigg\} \geq 1-\beta, \end{align}\] where in the first inequality we have used Hoeffding’s inequality [39], and in the last inequality we have used \(\beta \geq 2 \exp \{ -\frac{2 N \epsilon^2 }{ (b-a)^2 } \}\). This, together with ?? , implies that \[\begin{align} \mathbb{P}_N\Big( \mathbb{E}[ \Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) ] \geq b(1-\delta) \Big) \geq 1-\beta. \end{align}\] Now, the result follows from Proposition 2.

Since ?? is derived through Hoeffding’s inequality, we refer to it as the Hoeffding-based condition.

Next we introduce another result that certifies that \(h\) is a probabilistic CBF with a given confidence. In this case, the result is distribution-free (meaning it holds without any assumptions on the uncertainty distribution) and uses the theory of the scenario approach [23].

Let \({\mathbf{c}}\in\mathbb{R}^m\) and take \({\mathbf{u}}_{{\mathbf{x}}}\in\mathbb{R}^m\) as a minimizer of the optimization problem \[\begin{align} \label{ref:scenario-lp} &\min\limits_{{\mathbf{u}}\in\mathbb{R}^m} {\mathbf{c}}^\top {\mathbf{u}}, \quad \text{s.t.} \;\Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}^{(i)}) \geq 0, \;i\in[N], \end{align}\tag{5}\] which is feasible by assumption. Now, by [40] we have that for each \({\mathbf{x}}\in{\mathcal{C}}\), \[\begin{align} \mathbb{P}_N\Big( \mathbb{P}(\Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \leq 0 ) > \delta \Big) \leq \beta. \end{align}\] Equivalently, \[\begin{align} \label{eq:scenario-inequality-aux} \mathbb{P}_N\Big( \mathbb{P}(\Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \leq 0 ) \leq \delta \Big) \geq 1-\beta. \end{align}\tag{6}\] Now, note that for any \({\mathbf{D}}_N\), if the event \(X_N\) defined as \(\mathbb{P}(\Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \leq 0 ) \leq \delta\) holds, then the event \(Y_N\), defined as \(\mathbb{P}(\Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \geq 0) \geq 1-\delta\) also holds. Hence, \(\mathbb{P}_N(Y_N) \geq \mathbb{P}_N(X_N)\), and the result follows from 6 .

Since condition ?? is derived through the scenario approach, we refer to it as the scenario-based condition. The following remark discusses the assumptions in Proposition 6.

Another method to establish a distribution-free guarantee that \(h\) is a probabilistic CBF with a given confidence is through the theory of conformal prediction [42]. This is leveraged in the following result.

Let \({\mathbf{x}}\in{\mathcal{C}}\) and pick \({\mathbf{u}}\in\mathbb{R}^m\) so that ?? holds. Note that such \({\mathbf{u}}\) is dependent on the dataset \({\mathbf{D}}_N\). By [42], we have \[\begin{align} \label{eq:calibration-conditional-cp-guarantee} \mathbb{P}_N \Big( \mathbb{P}( -\Delta h({\mathbf{x}},{\mathbf{u}}, {\mathbf{d}}) \leq Q_N ) \geq 1-\delta \Big) \geq 1-\beta. \end{align}\tag{7}\] Note that if \({\mathbf{d}}\in\mathbb{R}^d\) satisfies \(-\Delta h({\mathbf{x}},{\mathbf{u}}, {\mathbf{d}}) \leq Q_N\), then we have \(-\Delta h({\mathbf{x}},{\mathbf{u}},{\mathbf{d}}) \leq 0\) by ?? . Hence, for any fixed dataset \({\mathbf{D}}_N\) and \({\mathbf{u}}\) satisfying ?? , we have \[\begin{align} \mathbb{P}\Big( -\Delta h({\mathbf{x}},{\mathbf{u}}, {\mathbf{d}}) \leq Q_N \Big) \leq \mathbb{P}\Big( -\Delta h({\mathbf{x}},{\mathbf{u}}, {\mathbf{d}}) \leq 0 \Big). \end{align}\] Therefore, if the event \(\bar{X}_N\) defined as \(\mathbb{P}\Big( -\Delta h({\mathbf{x}},{\mathbf{u}}, {\mathbf{d}}) \leq Q_N \Big) \geq 1-\delta\) holds, then the event \(\bar{Y}_N\) defined as \(\mathbb{P}\Big( -\Delta h({\mathbf{x}},{\mathbf{u}}, {\mathbf{d}}) \leq 0 \Big) \geq 1-\delta\) also holds. Hence, \(\mathbb{P}_N(\bar{Y}_N) \geq \mathbb{P}_N(\bar{X}_N)\) and by 7 this implies that \(h\) is a \(\delta\)-probabilistic CBF with confidence \(1-\beta\).

Since condition ?? is derived through conformal prediction, we refer to it as the conformal prediction-based condition. We note that as shown in [43], the quantile constraint ?? can be reformulated using mixed-integer programming so that it can be used in optimization-based control design with off-the-shelf solvers.

5 Experimental Validation↩︎

In this section we validate our theoretical results by considering the problem of controlling a quadrupedal robot traversing a narrow corridor, inspired by [27]. We consider the following discrete-time dynamics \[\begin{align} \label{eq:quadruped-dynamics} {\mathbf{x}}_{k+1} = {\mathbf{x}}_k + \Delta t \begin{pmatrix} \cos(\theta) & -\sin(\theta) & 0 \\ \sin(\theta) & \cos(\theta) & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} v_k^x \\ v_k^y \\ \omega_k \end{pmatrix} + {\mathbf{d}}_k, \end{align}\tag{8}\] where \({\mathbf{x}}_k = [x, y, \theta]^\top\) and \(\Delta t > 0\). We let \(h({\mathbf{x}}) = 0.5^2 - y^2\).

5.1 Simulation↩︎

In simulation, we model the uncertainties in the terrain through a Gaussian disturbance with standard deviation \(\sigma\) acting only in the \(y\) direction, i.e., \({\mathbf{d}}_k = [0, d_k, 0]\), with \(d_k \sim {\mathcal{N}}(0,\sigma)\). We consider a time horizon of 20 steps and take \(\delta = 0.1\), \(\beta = 0.01\), \(\alpha = 0.01\) and \(\Delta t = 0.1\). We consider a nominal controller \({\mathbf{k}}_{\text{nom}}({\mathbf{x}}) = [0.2, 0, -\theta]\). For each of the different conditions ——Markov (in the form of ?? ), Cantelli, Hoeffding, scenario approach, and conformal prediction——, we compute the control input at every state through a safety filter, i.e., by solving an optimization problem that finds the closest input to the nominal controller that satisfies the corresponding condition. We generate datasets of size 3252, 113, and 300 for the Hoeffding, scenario, and conformal approaches, respectively. For the Markov, Hoeffding and scenario approach-based condition, the optimization problem at every state is a convex quadratically constrained quadratic program (QCQP), which we solve using the cvxpy library in Python. The Cantelli-based condition leads to a non-convex problem, which we solve using the trust region solver of the minimize function in the SciPy library in Python. Using the reformulation in [43], the conformal prediction-based method leads to a mixed-integer quadratically constrained quadratic program, which we solve using the gurobipy library in Python. We implement each of the approaches (along with the nominal controller and the approach based on [27], which we refer to as the Martingale approach) in 400 different trajectories with initial condition \({\mathbf{x}}_0 = [0, 0, 0]\).

Figure 1 shows the number of unsafe trajectories for different values of \(\sigma\) (and fixed horizon \(20\)) and different time horizon values (and fixed \(\sigma\)). For a fixed time horizon of 20 Proposition 1 ensures that the probability that the trajectory is safe over 20 steps is at least \((1-\delta)^{20} \approx 0.12\), and hence the probability that the trajectory is unsafe over these 20 steps is at most \(0.88\). (for the approaches in Section 4, this is with confidence \(1-\beta \cdot 20 = 0.8\)). As can be seen in Figure 1, all the approaches considered in this paper lead to a fraction of unsafe trajectories significantly lower than the theoretical bound, which suggests that the conditions might be conservative. The source of this conservatism can be attributed to the limited knowledge of the uncertainty distribution, the use of Jensen’s inequality (cf. Corollaries 1 and 2), and the fact that these results do not consider full trajectory information, and instead derive probabilistic bounds only based on a condition at every state.

Figure 2 shows 400 different trajectories generated with the different approaches for \(\sigma = 0.06\) and trajectory length \(20\). Note that we do not plot trajectories from the Markov approach because it is infeasible for such value of \(\sigma\).

Finally, Table 1 shows the average execution times for the different approaches as well as the smallest value of \(\sigma\) that leads to infeasibility of the corresponding condition.

The choice of which of the different approaches should be used depends on a variety of factors. Firstly, on what information is available about the uncertainty distribution. Secondly, on the desired level of conservativeness with respect to the safety constraints. Figure 1 and Table 1 show that there is a tradeoff between the empirical number of safety violations and the smallest variance that leads to infeasibility. Approaches yielding less safety violations generally lead to infeasible conditions for smaller values of \(\sigma\). Thirdly, another point to consider is the computational time (cf. Table 1). Although the martingale approach shows a larger value of \(\sigma_0\) in Table 1, it fails to meet the prescribed safety guarantees that the other approaches successfully satisfy.

5.2 Hardware↩︎

To validate the effectiveness of our approach beyond simulation, we deploy it on a quadruped robot navigating a challenging obstacle course designed to induce substantial disturbances. The course is 3m long and 1m wide, with a laterally slanted wooden ramp covered in slippery plates (Fig. 3). Our system is a Unitree GO2 quadruped, which we assume follows dynamics 8 . The control objective is to traverse the course with a nominal forward velocity of 1 m/s. We compare three controllers: (i) the nominal controller with no safety filter, (ii) a naive CBF-based filter, and (iii) our Hoeffding-based probabilistic CBF filter ². For the latter, we collect disturbance data from 5000 rollout steps on the course to characterize the uncertainty. We use the same \(h\) as in simulation, and estimate the global state of the robot by an external OptiTrack system.

Results are shown in Fig. 4. We plot the trajectories induced by the nominal controller, the naive filter (i.e., the controller that is computed at each state as the smallest deviation from the nominal satisfying the discrete-time CBF condition assuming the disturbance is identically zero), and the Hoeffding-based approach. The nominal controller and the naive filter consistently violate the safety constraint as the sloped terrain pushes the robot laterally out of the safe set. In contrast, our Hoeffding-based filter substantially reduces the frequency and magnitude of constraint violations, correctly accounting for the stochastic disturbance and succeeding on 4/5 of the tested rollouts.

6 Conclusion↩︎

We have introduced probabilistic CBFs, which can be used to design controllers that satisfy safety constraints with a prescribed probability over a finite time horizon. We have proposed a number of different sufficient conditions to verify that a function is a probabilistic CBF. The first set of conditions leverage knowledge of the moments of the uncertainty distribution, whereas the second set of conditions utilize realizations of the uncertainty. We have studied the computational tractability of such conditions for its use in optimization-based control. In particular, we have implemented such controllers on a quadruped, both in simulation and hardware. In future work, we plan to find less conservative conditions to ensure that a function is a probabilistic CBF and bridge the gap between the theoretical probabilistic safety guarantees and the empirical results. The results in this paper also open the door to the design of safe controllers in systems with state estimation errors induced by techniques such as the Kalman Filter or SLAM.

Acknowledgments↩︎

The authors thank Ryan M. Bena for his help with the quadruped hardware experiment.

References↩︎