Feasibility Analysis and Regularity Characterization
of Distributionally Robust Safe Stabilizing Controllers

Pol Mestres Kehan Long Nikolay Atanasov Jorge Cortés The authors are with the Contextual Robotics Institute, UC San Diego (e-mails: {pomestre,k3long,natanasov,cortes}@ucsd.edu).The authors gratefully acknowledge support from NSF under grants IIS-2007141 and CCF-2112665.

Abstract

This paper studies the well-posedness and regularity of safe stabilizing optimization-based controllers for control-affine systems in the presence of model uncertainty. When the system dynamics contain unknown parameters, a finite set of samples can be used to formulate distributionally robust versions of control barrier function and control Lyapunov function constraints. Control synthesis with such distributionally robust constraints can be achieved by solving a (convex) second-order cone program (SOCP). We provide one necessary and two sufficient conditions to check the feasibility of such optimization problems, characterize their computational complexity and numerically show that they are significantly faster to check than direct use of SOCP solvers. Finally, we also analyze the regularity of the resulting control laws.

{IEEEkeywords}

Safety-critical control, control barrier functions, distributionally robust control synthesis.

1 Introduction

\IEEEPARstart

Recent years have seen increasing deployment of control systems and robots to aid transportation, warehouse management, and home automation. In these applications, it is crucial to implement controllers with provable safety and stability guarantees despite uncertainty in the system models and operational conditions. Recent work [1, 2, 3, 4, 5, 6] tackles this when some prior information about the uncertainty is known. Instead, here we rely on a line of work initiated in [7] that circumvents the need for knowledge about the uncertainty distribution and uses only uncertainty samples to formulate distributionally robust constraints for control synthesis. This approach is robust to distributional shift at deployment time and enjoys provable out-of-sample performance. However, it also introduces several challenges, which we focus on here: the characterization of the quality and number of uncertainty samples needed to guarantee the feasibility of the safety and stability constraints, and the study of the regularity properties of the resulting controllers.

Literature Review

Control Lyapunov functions (CLFs) [8] are a well-established tool to design stabilizing controllers for nonlinear systems. More recently, control barrier functions (CBFs) [9] have gained popularity as a tool to render a desired subset of the system state space safe. If the system is control affine, CLF and CBF constraints are linear in the control input and can be incorporated in a quadratic program (QP) [10] that, if feasible, can be solved efficiently to obtain control inputs guaranteeing safety and stability. Recent work has explored alternative optimization formulations when the system model is uncertain. Under the assumption that the uncertainty follows a Gaussian Process (GP) or satisfies worst-case bounds,[2, 11, 12, 1, 3, 5] formulate second-order cone constraints that can be used to design controllers achieving safe stabilization of the true system. The paper [4] gives sufficient conditions for the feasibility of such second-order cone constraints. Our work here is closely related to [7], which leverages ideas from distributionally robust optimization (DRO) [13, 14] to model the uncertainty. The DRO framework constructs an ambiguity set of probability distributions that contains the true (unknown) one with high confidence. Such ambiguity sets are constructed with only finitely many samples and are used to formulate distributionally robust versions of the control design problem.

Statement of Contributions

We study the problem of safe stabilization of control-affine systems under uncertainty. We assume that the distribution of the uncertainty is unknown and formulate a second-order cone program (SOCP) using distributionally robust versions of the CLF and CBF constraints constructed on the basis of uncertainty samples. Our first contribution is the derivation of a necessary condition and two sufficient conditions for the feasibility of the optimization problem. We characterize the computational complexity of these conditions and show that, for a large number of samples, it is significantly smaller than solving the SOCP directly, which makes them useful to efficiently check whether the problem is feasible without having to solve it. Our first sufficient condition is dependent on the quality of the uncertainty samples but is limited to a single control objective. Our second sufficient condition is only dependent on the number of samples but can be used for any number of constraints. Our final contribution shows that the solution of this distributionally robust optimization problem is point-Lipschitz, and hence continuous, which means that solutions of the closed-loop system are guaranteed to exist and the controller obtained from it can be implemented without inducing chattering.

2 Preliminaries

We review distrib. robust chance-constrained programs and control Lyapunov and barrier functions under uncertainty.

2.1 Distributionally Robust Chance Constrained Programs

Given a random vector $\boldsymbol{\xi}$ following distribution $\mathbb{P}^{*}$ supported on set $\Xi\subseteq^{k}$ and a closed convex set $\mathcal{Z}\subset^{n}$ , let $G:\mathcal{Z}\times\Xi\to$ define a probabilistic constraint $G(z,\boldsymbol{\xi})\leq 0$ . We are interested in satisfying this constraint with a prescribed confidence $1-\epsilon$ , with $\epsilon\in(0,1)$ , while minimizing a convex objective function $c:\mathcal{Z}\to$ . To achieve this¹¹1We denote by $\mathbb{Z}_{>0}$ , and _≥0 the set of positive integers, real, and nonnegative real numbers, resp. We denote by $\textbf{0}_{n}$ the $n$ -dimensional zero vector. We write $\partial\mathcal{S}$ for the boundary of the set $\mathcal{S}$ . Given $N\in\mathbb{Z}_{>0}$ , we denote $[N]=\{1,\ldots,N\}$ . Given $x\in^{n}$ , $\left\lVert x\right\rVert$ denotes the Euclidean norm of $x$ . For $x\in$ , we define $(x)_{+}=\max(x,0)$ . A function $\beta:_{\geq 0}\to$ is of class $\mathcal{K}_{\infty}$ if $\beta(0)=0$ , $\beta$ is strictly increasing and $\lim\limits_{t\to\infty}\beta(t)=\infty$ . A function $V:^{n}\to$ is positive definite if $V(0)=0$ and $V(x)>0$ for all $x\neq 0$ , and proper in a set $\Gamma$ if $\{x\in\Gamma\;:\;V(x)\leq c\}$ is compact for any $c\geq 0$ . Given an $m\times n$ matrix $A$ and two integers $i,j$ such that $1\leq i<j\leq m$ , $A_{i:j}$ denotes the $(j-i+1)\times n$ matrix obtained by selecting the rows from $i$ to $j$ of $A$ . A function $f:^{n}\to^{q}$ is point-Lipschitz at a point $x_{0}\in^{n}$ if there exists a neighborhood $U$ of $x_{0}$ and a constant $L_{x_{0}}>0$ such that $\left\lVert f(x)-f(x_{0})\right\rVert\leq L_{x_{0}}\left\lVert x-x_{0}\right\rVert$ for all $x\in U$ ., define the chance-constrained program:

		$\displaystyle\min\limits_{z\in\mathcal{Z}}c(z)$		(1)
	s.t.	$\displaystyle\ \mathbb{P}^{*}(G(z,\boldsymbol{\xi})\leq 0)\geq 1-\epsilon.$

The feasible set of (1) is not convex in general. Nemirosvski and Shapiro [15, Section 2] propose a convex approximation of the feasible set of (1) by replacing the chance constraint with a conditional value-at-risk ( $\operatorname{CVaR}$ ) constraint. CVaR of $G(z,\boldsymbol{\xi})$ can be formulated as the following convex program:

\displaystyle\operatorname{CVaR}_{1-\epsilon}^{\mathbb{P}^{*}}(G(z,\boldsymbol{\xi})):=\inf\limits_{t\in}[\epsilon^{-1}\mathbb{E}_{\mathbb{P}^{*}}[(G(z,\boldsymbol{\xi})+t)_{+}]\!-\!t].

(2)

The resulting problem

		$\displaystyle\min\limits_{z\in\mathcal{Z}}c(z)$		(3)
	s.t.	$\displaystyle\ \operatorname{CVaR}_{1-\epsilon}^{\mathbb{P}^{*}}(G(z,\boldsymbol{\xi}))\leq 0,$

is convex and its feasible set is contained in that of (1).

Both (1) and (3) assume that $\mathbb{P}^{*}$ is known. Instead, suppose that it is unknown and we only have access to samples $\{\boldsymbol{\xi}_{i}\}_{i\in[N]}$ from $\mathbb{P}^{*}$ . We describe a way of constructing a set of distributions that could have generated the samples. Let $\mathcal{P}_{p}(\Xi)$ be the set of probability measures with finite $p$ -th moment supported on $\Xi$ . Let $\hat{\mathbb{P}}_{N}:=\frac{1}{N}\sum_{i=1}^{N}\delta_{\boldsymbol{\xi}_{i}}$ be the empirical distribution constructed from the samples $\{\boldsymbol{\xi}_{i}\}_{i=1}^{N}$ . Let $W_{p}$ be the $p$ -Wasserstein distance [14, Definition 3.1] between two probability measures in $\mathcal{P}_{p}(\Xi)$ and let $\mathcal{M}_{N}^{r}:=\{\mu\in\mathcal{P}_{p}(\Xi)\;:\;W_{p}(\mu,\hat{\mathbb{P}}_{N})\leq r\}$ be the ball of radius $r$ centered at $\hat{\mathbb{P}}_{N}$ . We define a distributionally robust chance-constrained program:

		$\displaystyle\min\limits_{z\in\mathcal{Z}}c(z)$		(4)
	s.t.	$\displaystyle\inf_{\mathbb{P}\in\mathcal{M}_{N}^{r}}\mathbb{P}(G(z,\boldsymbol{\xi})\leq 0)\geq 1-\epsilon.$

We can use CVaR to obtain a convex conservative approximation of (4):

		$\displaystyle\min_{z\in\mathcal{Z}}c(z)$		(5)
	s.t.	$\displaystyle\sup_{\mathbb{P}\in\mathcal{M}_{N}^{r}}\operatorname{CVaR}_{1-\epsilon}^{\mathbb{P}}(G(z,\boldsymbol{\xi}))\leq 0.$

If (5) is feasible, then (4) is also feasible [15, Section 2].

We say that a distribution $\mathbb{P}$ is light-tailed if there exists $a>0$ such that $A:=\mathbb{E}_{\mathbb{P}}[\exp{\left\lVert\boldsymbol{\xi}\right\rVert^{a}}]=\int_{\Xi}\exp{\left\lVert\boldsymbol{\xi}\right\rVert^{a}}\mathbb{P}(d\boldsymbol{\xi})<\infty$ . If $\mathbb{P}^{*}$ is light-tailed, the following observation specifies how the radius of $\mathcal{M}_{N}^{r}$ should be selected so that the true distribution lies in the ball with high confidence.

Remark 2.1

(Choice of Wasserstein ball radius): If the true distribution $\mathbb{P}^{*}$ is light-tailed, the choice of $r=r_{N}(\bar{\epsilon})$ given in [14, Theorem 3.5],

\displaystyle r_{N}(\bar{\epsilon})=\begin{cases}(\frac{\log(c_{1}\bar{\epsilon}^{-1})}{c_{2}N})^{\frac{1}{\max\{k,2\}}}\quad&\text{if}\ N\geq\frac{\log(c_{1}\bar{\epsilon}^{-1})}{c_{2}},\\ (\frac{\log(c_{1}\bar{\epsilon}^{-1})}{c_{2}N})^{\frac{1}{a}}\quad&\text{else},\end{cases}

(6)

where $c_{1},c_{2}$ and $a$ are positive constants that only depend on $a$ , $A$ and $k$ (cf. [14, Theorem 3.4]), ensures that the ball $\mathcal{M}_{N}^{r_{N}(\bar{\epsilon})}$ contains $\mathbb{P}^{*}$ with probability at least $1-\bar{\epsilon}$ . Then, a solution $z^{*}$ of (5) satisfies the constraint $\operatorname{CVaR}_{1-\epsilon}^{\mathbb{P}^{*}}(G(z^{*},\boldsymbol{\xi}))\leq 0$ with probability at least $1-\bar{\epsilon}$ . Note that $c_{1}$ , $c_{2}$ and $a$ can be computed by knowing the class of distributions to which $\mathbb{P}^{*}$ belongs to, without having actual knowledge of $\mathbb{P}^{*}$ . If exact values are not known, but upper and lower bounds are, these can be used instead to compute an upper bound of $r_{N}(\bar{\epsilon})$ . $\bullet$

Remark 2.2

(Choice of $\epsilon$ ): The parameter $\epsilon$ determines the confidence level $1-\epsilon$ for constraint satisfaction. Throughout the paper, we assume $\epsilon\leq\frac{1}{N}$ , albeit results are valid generally, with explicit expressions becoming more involved. $\bullet$

2.2 Distributionally Robust Safety and Stability

The notions of CLF [8] and CBF [9] can be used to design controllers in uncertainty-free systems that enforce stability and safety, resp. Here we extend these notions for systems with uncertainty in the dynamics. Consider a nominal model $F$ and a linear combination of $k$ perturbations,

\displaystyle\dot{x}

\displaystyle=(F(x)+\sum_{j=1}^{k}W_{j}(x)\xi_{j})\underaccent{\bar}{u},

(7)

where for $1\leq j\leq k$ , $W_{j}(x)\in^{n\times(m+1)}$ denotes known model perturbations, and $\xi_{j}\in$ denotes the corresponding unknown weight, and $\underaccent{\bar}{u}=[1;u]\in\underaccent{\bar}{\Uc}:=\{1\}\times^{m}$ . We let $\boldsymbol{\xi}=[\xi_{1},\xi_{2},\ldots,\xi_{k}]^{T}\in\Xi\subseteq^{k}$ . We assume that $\boldsymbol{\xi}$ follows an unknown distribution $\mathbb{P}^{*}$ but a set of samples $\{\boldsymbol{\xi}_{i}\}_{i=1}^{N}$ is available. We are interested in extending the notions of CLF [8] and CBF [9] for systems of the form (7). To do so, note that as shown in [7, Section IV], the CBF condition for a system of the form (7) and a function $h:^{n}\to$ reads as $\operatorname{CBC}(x,\underaccent{\bar}{u},\boldsymbol{\xi}):=\underaccent{\bar}{u}^{T}q_{h}(x)+\underaccent{\bar}{u}^{T}R_{h}(x)\boldsymbol{\xi}\geq 0$ , where the exact forms of $q_{h}$ and $R_{h}$ are given in [7, Section IV] and depend on $h$ and its gradient. Now, since $\boldsymbol{\xi}$ follows a distribution $\mathbb{P}^{*}$ , we extend the definition of CBF by requiring that for all $x$ in the safe set, there exist $\underaccent{\bar}{u}\in\underaccent{\bar}{\Uc}$ such that

\displaystyle\mathbb{P}^{*}(\operatorname{CBC}(x,\underaccent{\bar}{u},\boldsymbol{\xi})\geq 0)\geq 1-\epsilon.

(8)

The CLF condition for (7) takes a similar form and is written as $\operatorname{CLC}(x,\underaccent{\bar}{u},\boldsymbol{\xi})\leq 0$ (cf. [7, Section IV]). As shown in Section 2.1, $\operatorname{CVaR}$ can be used as a convex approximation of (8) and its analogue with $\operatorname{CLC}$ . We use


	$\displaystyle\operatorname{CVaR}_{1-\epsilon}^{\mathbb{P}^{*}}(\operatorname{CBC}(x,\underaccent{\bar}{u},\boldsymbol{\xi}))\geq 0,$		(9a)
	$\displaystyle\operatorname{CVaR}_{1-\epsilon}^{\mathbb{P}^{*}}(\operatorname{CLC}(x,\underaccent{\bar}{u},\boldsymbol{\xi}))\geq 0,$		(9b)

as the distributionally robust analogues of the CLF and CBF conditions from [8] and [9], resp. The existence of a controller satisfying (9) implies the existence of a controller that makes the CLC (resp. the CBC) condition hold at every point with probability at least $1-\epsilon$ , paving the way for the design of controllers that make the system stable (resp. safe) with arbitrarily high probability.

3 Problem Statement

Consider the system model in (7) with distributional uncertainty, meaning that the true distribution $\mathbb{P}^{*}$ of the parameter $\boldsymbol{\xi}$ is unknown. We assume that the system admits a CLF and a CBF, which allow us to formulate the constraints (9). Given a nominal controller specified by a smooth function $\underaccent{\bar}{k}:^{n}\to\underaccent{\bar}{\mathcal{U}}$ , we would like to synthesize a controller closest to it that respects safety and stability constraints. Using (2), this problem can be written in general form as

		$\displaystyle\min\limits_{\underaccent{\bar}{u}\in\underaccent{\bar}{\mathcal{U}}}\left\lVert\underaccent{\bar}{u}-\underaccent{\bar}{k}(x)\right\rVert^{2}$		(10)
	s.t.	$\displaystyle\sup_{\mathbb{P}\in\mathcal{M}_{N}^{r}}\inf_{t\in}[\epsilon^{-1}\mathbb{E}_{\mathbb{P}}[(G_{l}(x,\underaccent{\bar}{u},\boldsymbol{\xi})+t)_{+}]-t]\leq 0,\ \forall l\in[M],$

where $M\in\mathbb{Z}_{>0}$ and each $G_{l}:^{n}\times\underaccent{\bar}{\Uc}\times\Xi\to$ is an affine function in $\underaccent{\bar}{u}$ and $\boldsymbol{\xi}$ , $G_{l}(x,\underaccent{\bar}{u},\boldsymbol{\xi})=\underaccent{\bar}{u}^{T}q_{l}(x)+\underaccent{\bar}{u}^{T}R_{l}(x)\boldsymbol{\xi}$ , for smooth functions $q_{l}:^{n}\to^{m+1}$ and $R_{l}:^{n}\to^{(m+1)\times k}$ . With $M=2$ and constraints corresponding to $\operatorname{CBC}$ and $\operatorname{CLC}$ , this corresponds to a stable and safe control synthesis problem. The case $M=1$ with the constraint $\operatorname{CBC}$ corresponds to a distributionally robust version of a safety filter of $\underaccent{\bar}{k}$ .

Although the constraints in (10) are convex, the program is intractable due to the search of suprema over the Wasserstein set. Fortunately, [7, Proposition IV.1] shows that when $\Xi=^{k}$ and $p=1$ , the following SOCP is equivalent to (10):


	$\displaystyle\min_{\underaccent{\bar}{u}\in\underaccent{\bar}{\Uc},y\in,t\in,s_{i}\in}y$	(11a)
s.t.	$\displaystyle\quad r\left\lVert R_{l}^{T}(x)\underaccent{\bar}{u}\right\rVert+\frac{1}{N}\sum_{i=1}^{N}s_{i}-t\epsilon\leq 0,\ \forall l\in[M],~{}$	(11b)
	$\displaystyle\quad s_{i}\geq G_{l}(x,\underaccent{\bar}{u},\boldsymbol{\xi}_{i})+t,\ \forall i\in[N],\ \forall l\in[M],~{}$	(11c)
	$\displaystyle\quad s_{i}\geq 0,\ \forall i\in[N],~{}$	(11d)
	$\displaystyle\quad y+1\geq\sqrt{\left\lVert 2(\underaccent{\bar}{u}-\underaccent{\bar}{k}(x))\right\rVert^{2}+(y-1)^{2}}~{}.$	(11e)

We refer to (11) as the DRO-SOCP and take $\Xi=^{k}$ and $p=1$ Wasserstein distance throughout the paper.

A critical observation about problem (11) is that, in general, it might be infeasible, leading to controllers that are undefined.

Furthermore, even if the problem is feasible, the controller obtained from it might not be continuous, hence resulting in implementation problems (it might induce chattering behavior when implemented on physical systems) and theoretical problems (lack of existence of solutions of the closed-loop system). Hence, our goal in this paper is twofold. First, we derive conditions to ensure the feasibility of (11). Given the complexity of obtaining characterizations for the feasibility of such problems, we focus on identifying conditions that are easy to evaluate computationally as opposed to directly attempting to solve the optimization problem: either sufficient conditions, to quickly ensure feasibility, or necessary, to quickly discard it. Second, assuming that the problem (11) is feasible, we characterize the regularity properties of the resulting controller.

4 Feasibility Analysis

In this section, we study the feasibility properties of (11). We start by giving a necessary condition for its feasibility.

Proposition 4.1

(Necessary condition for feasibility of DRO-SOCP): Let $\epsilon\in(0,\frac{1}{N}]$ and $r>0$ . For $x\in^{n}$ , let

	$\displaystyle\bar{Q}_{l}(x)=rR_{l}(x)_{2:(m+1)}\in^{m\times k},\ \bar{r}_{l}(x)=rR_{l}(x)_{1}\in^{1\times k},$
	$\displaystyle\bar{w}_{l,i}(x)=(-\epsilon q_{l}(x)-\epsilon R_{l}(x)\boldsymbol{\xi}_{i})_{2:(m+1)}\in^{m},$
	$\displaystyle\bar{v}_{l,i}(x)=(-\epsilon q_{l}(x)-\epsilon R_{l}(x)\boldsymbol{\xi}_{i})_{1}\in,$
	$\displaystyle\bar{F}_{l,i}(x)=\bar{Q}_{l}(x)\bar{Q}_{l}(x)^{T}-\bar{w}_{l,i}(x)\bar{w}_{l,i}(x)^{T}\in^{m\times m},$
	$\displaystyle\bar{J}_{l,i}(x)=\bar{r}_{l}(x)\bar{Q}_{l}(x)^{T}-\bar{v}_{l,i}(x)\bar{w}_{l,i}^{T}\in^{1\times m},$
	$\displaystyle\bar{H}_{l,i}(x)=\begin{pmatrix}\bar{r}_{l}\bar{r}_{l}^{T}-\bar{v}_{l,i}^{2})(x)&\bar{J}_{l,i}(x)\\ \bar{J}_{l,i}^{T}(x)&\bar{F}_{l,i}(x)\end{pmatrix}\in^{(m+1)\times(m+1)}$

for $l\in[M]$ and $i\in[N]$ . Let $\bar{\lambda}_{l,i}(x)$ be the minimum eigenvalue of $\bar{F}_{l,i}(x)$ and suppose $\bar{Q}_{l}(x)\bar{Q}_{l}(x)^{T}$ is invertible for all $l\in[M]$ . If (11) is feasible, then for each $l\in[M]$ , there exists $i\in[N]$ such that $\bar{H}_{l,i}(x)$ is not positive definite and one of the following holds:

(i)

$\bar{\lambda}_{l,i}(x)\!<\!0$ ,
(ii)

$\bar{\lambda}_{l,i}(x)\!>\!0$ and $\big{(}\bar{v}_{l,i}-\bar{w}_{l,i}^{T}\bar{F}_{l,i}^{-1}(\bar{Q}_{l}\bar{r}_{l}^{T}\!-\!\bar{w}_{l,i}\bar{v}_{l,i})\big{)}(x)\!\geq\!0$ ,
(iii)

$\bar{\lambda}_{l,i}(x)=0$ , and $\big{(}\bar{v}_{l,i}-\bar{w}_{l,i}^{T}(\bar{Q}_{l}\bar{Q}_{l}^{T})^{-1}\bar{Q}_{l}\bar{r}_{l}^{T}\big{)}(x)>0$ .

Proof 4.2.

Note that (10) (and hence (11)) is equivalent to

		$\displaystyle\min\limits_{\underaccent{\bar}{u}\in\underaccent{\bar}{\Uc}}\left\lVert\underaccent{\bar}{u}-\underaccent{\bar}{k}(x)\right\rVert^{2}$		(12)
		$\displaystyle\text{s.t.}\ r\left\lVert R_{l}^{T}(x)\underaccent{\bar}{u}\right\rVert+\inf_{t\in}\Big{[}\frac{1}{N}\sum_{i=1}^{N}(G_{l}(x,\underaccent{\bar}{u},\boldsymbol{\xi}_{i})+t)_{+}-t\epsilon\Big{]}\leq 0,$

for $l\in\{1,\dots,M\}$ , cf. [7, Proposition IV.1]. For $(x,\underaccent{\bar}{u})\in^{n}\times\underaccent{\bar}{\Uc}$ , the function $A_{x,\underaccent{\bar}{u}}^{l}(t)=\frac{1}{N}\sum_{i=1}^{N}(G_{l}(x,\underaccent{\bar}{u},\boldsymbol{\xi}_{i})+t)_{+}-t\epsilon$ is a piecewise linear function in $t$ . Since $\epsilon\leq\frac{1}{N}$ , it is decreasing for $t<t_{l}^{*}(x,\underaccent{\bar}{u}):=\min_{i\in[N]}-G_{l}(x,\underaccent{\bar}{u},\boldsymbol{\xi}_{i})$ and increasing for $t>t_{l}^{*}(x,\underaccent{\bar}{u})$ . Hence, it achieves its minimum at $t_{l}^{*}(x,\underaccent{\bar}{u})$ . Thus, (11) is feasible if and only if for all $l\in[M]$ the following inequalities are simultaneously feasible:

\displaystyle r\left\lVert R_{l}^{T}(x)\underaccent{\bar}{u}\right\rVert+\epsilon\underaccent{\bar}{u}^{T}q_{l}(x)+\epsilon\max_{i\in[N]}\underaccent{\bar}{u}^{T}R_{l}(x)\boldsymbol{\xi}_{i}\leq 0.

(13)

Note that, if for some $l\in[M]$ , the constraint $r\left\lVert R_{l}^{T}(x)\underaccent{\bar}{u}\right\rVert+\epsilon\underaccent{\bar}{u}^{T}q_{l}(x)+\epsilon\underaccent{\bar}{u}^{T}R_{l}(x)\boldsymbol{\xi}_{i}\leq 0$ is infeasible for all $i\in[N]$ , then (11) is infeasible. Note that this is only a sufficient, but not necessary, condition for infeasibility (or equivalently, a necessary, but not sufficient, condition for feasibility). The result follows from [2, Theorem 2], which characterizes the feasibility of a single second-order cone constraint.

Next, we state a sufficient condition for the feasibility of (11) in the case $M=1$ .

Proposition 4.3.

(Sufficient condition for feasibility of DRO-SOCP with one constraint): Let $r>0$ , $M=1$ , and $0<\epsilon\leq\frac{1}{N}$ . Given $x\in^{n}$ , define

	$\displaystyle\hat{Q}(x)=(r+\epsilon\max_{i\in[N]}\left\lVert\boldsymbol{\xi}_{i}\right\rVert)R_{1}(x)_{2:(m+1)}\in^{m\times k},$
	$\displaystyle\hat{r}(x)=(r+\epsilon\max_{i\in[N]}\left\lVert\boldsymbol{\xi}_{i}\right\rVert)R_{1}(x)_{1}\in^{1\times k},$
	$\displaystyle\hat{w}(x)=-\epsilon q_{1}(x)_{2:(m+1)}\in^{m},\ \hat{v}(x)=-\epsilon q_{1}(x)_{1}\in,$
	$\displaystyle\hat{F}(x)=Q(x)Q(x)^{T}-w(x)w(x)^{T}\in^{m\times m},$
	$\displaystyle\hat{J}(x)=\hat{r}(x)\hat{Q}(x)^{T}-\hat{v}(x)\hat{w}(x)^{T}\in^{1\times m},$
	$\displaystyle\hat{H}(x)=\begin{pmatrix}(\hat{r}\hat{r}^{T}-\hat{v}^{2})(x)&\hat{J}(x)\\ \hat{J}(x)^{T}&\hat{F}(x)\end{pmatrix}\in^{(m+1)\times(m+1)}.$

Let $\hat{\lambda}(x)$ be the minimum eigenvalue of $\hat{F}(x)$ . Suppose that $Q(x)Q(x)^{T}$ is invertible, $\hat{H}(x)$ is not positive definite and one of the following holds:

(i)

$\hat{\lambda}(x)<0$ ,
(ii)

$\hat{\lambda}(x)>0$ and $\big{(}\hat{v}-\hat{w}^{T}\hat{F}^{-1}(\hat{Q}\hat{r}^{T}-\hat{w}\hat{v}\big{)}(x)\geq 0$ ,
(iii)

$\hat{\lambda}(x)=0$ and $\big{(}\hat{v}-\hat{w}^{T}(\hat{Q}\hat{Q}^{T})^{-1}\hat{Q}\hat{r}^{T}\big{)}(x)>0$ .

Then, (11) is feasible at $x$ .

Proof 4.4.

By repeating an argument similar to the one in the proof of Proposition 4.1, (11) is feasible in the case $M=1$ if and only if the following inequality is feasible:

\displaystyle r\left\lVert R(x)^{T}\underaccent{\bar}{u}\right\rVert+\epsilon\underaccent{\bar}{u}^{T}q(x)+\epsilon\max_{i\in[N]}\underaccent{\bar}{u}^{T}R(x)\boldsymbol{\xi}_{i}\leq 0.

(14)

Using the Cauchy-Schwartz inequality, the following inequality being feasible implies that (14) is feasible,

\displaystyle(r+\epsilon\max_{i\in[N]}\left\lVert\boldsymbol{\xi}_{i}\right\rVert)\left\lVert R(x)^{T}\underaccent{\bar}{u}\right\rVert+\epsilon\underaccent{\bar}{u}^{T}q(x)\leq 0.

(15)

If (15) is feasible, there exists $\hat{\underaccent{\bar}{u}}$ such that $r\left\lVert\hat{\underaccent{\bar}{u}}^{T}R(x)\right\rVert+\epsilon\hat{\underaccent{\bar}{u}}^{T}q(x)+\epsilon\hat{\underaccent{\bar}{u}}^{T}R(x)\boldsymbol{\xi}_{i}\leq 0$ for all $i\in[N]$ , and thus $\hat{\underaccent{\bar}{u}}$ satisfies (14). The result follows by [2, Thm. 2].

Remark 4.5.

(More data leads to better feasibility guarantees): For a fixed $r$ , the addition of new data points (larger $N$ ) implies that there are more chances that either of (i)-(iii) in Proposition 4.1 are satisfied for each $l\in\{1,\dots,M\}$ . Moreover, if $\mathbb{P}^{*}$ is light-tailed, $r_{N}(\bar{\epsilon})$ decreases with $N$ . The choice $r=r_{N}(\bar{\epsilon})$ means that for each fixed $i\in[N]$ and $l\in[M]$ , the feasible set of the inequality $r\left\lVert R_{l}(x)^{T}\underaccent{\bar}{u}\right\rVert+\epsilon\underaccent{\bar}{u}^{T}q_{l}(x)+\epsilon\underaccent{\bar}{u}^{T}R_{l}(x)\boldsymbol{\xi}_{i}\leq 0$ increases, which from the proof of Proposition 4.1, also means that there are more chances that either of (i)-(iii) are met. Similarly, under the assumption that the norm of additional samples is upper bounded by $\max_{i\in[N]}\left\lVert\boldsymbol{\xi}_{i}\right\rVert$ , the choice $r=r_{N}(\bar{\epsilon})$ also leads to a larger feasible set of (15) and thus the sufficient condition in Proposition 4.3 has more chances of being satisfied. $\bullet$

We next give a sufficient condition for the feasibility of (11) with high probability for an arbitrary number of constraints.

Proposition 4.6.

(Sufficient condition for feasibility of DRO-SOCP): Let $r>0$ , $\epsilon\in(0,1)$ and $\bar{\epsilon}\in(0,1)$ . Suppose that there exists a controller $\hat{k}:^{n}\to\underaccent{\bar}{\Uc}$ and non-negative functions $S_{l}:^{n}\to_{\geq 0}$ for $l\in[M]$ satisfying

\displaystyle\operatorname{CVaR}_{1-\epsilon}^{\mathbb{P}^{*}}(G_{l}(x,\hat{k}(x),\boldsymbol{\xi}))

\displaystyle\leq-S_{l}(x),\quad\forall l\in[M].

(16)

Moreover, suppose that $\mathbb{P}^{*}$ is light-tailed and let $r_{N}(\bar{\epsilon})$ be defined as in (6). Let $x\in^{n}$ be such that $\left\lVert R_{l}(x)\right\rVert\neq 0$ for all $l\in[M]$ , and let $B:^{n}\to_{\geq 0}$ be an upper bound on the norm of $\hat{k}$ . Then, if

\displaystyle~{}r_{N}(\bar{\epsilon})<\min\limits_{l\in[M]}\frac{\epsilon S_{l}(x)}{2\left\lVert R_{l}(x)\right\rVert B(x)},

(17)

(11) is strictly feasible at $x$ with probability at least $1-\bar{\epsilon}$ for any $r\leq r_{N}(\bar{\epsilon})$ .

Proof 4.7.

Note that by definition, the first component of $\hat{k}(x)$ is $1$ for all $x\in^{n}$ . Hence, $B(x)\geq\left\lVert\hat{k}(x)\right\rVert\geq 1$ for all $x\in^{n}$ so (17) is well-defined. Let $t_{1}^{*}\in$ be such that

\displaystyle\operatorname{CVaR}_{1-\epsilon}^{\mathbb{P}^{*}}(G_{1}(x,\underaccent{\bar}{u},\boldsymbol{\xi}))=\frac{1}{\epsilon}\mathbb{E}_{\mathbb{P}^{*}}[(G_{1}(x,\underaccent{\bar}{u},\boldsymbol{\xi})+t_{1}^{*})_{+}]-t_{1}^{*},

and define $\hat{G}(x,\boldsymbol{\xi})=\frac{1}{\epsilon}(G_{1}(x,\hat{k}(x),\boldsymbol{\xi})+t_{1}^{*})_{+}-t_{1}^{*}$ . Note that for any $\boldsymbol{\xi},\boldsymbol{\xi^{{}^{\prime}}}\in^{k}$ ,

\displaystyle|\hat{G}(x,\boldsymbol{\xi})\!-\!\hat{G}(x,\boldsymbol{\xi}^{{}^{\prime}})|\!\leq\!\frac{1}{\epsilon}\left\lVert R_{1}(x)\right\rVert\!\cdot\!\left\lVert\hat{k}(x)\right\rVert\!\cdot\!\left\lVert\boldsymbol{\xi}-\boldsymbol{\xi^{{}^{\prime}}}\right\rVert,

(18)

where we have used the fact that the operator $(\cdot)_{+}$ is Lipschitz with constant 1. Using (18) in [14, Theorem 3.2], we conclude that for any $\mathbb{\hat{P}}\in\mathcal{P}_{p}(\Xi)$ , $|\mathbb{E}_{\mathbb{P}^{*}}\!(\hat{G}(x,\boldsymbol{\xi}))\!-\!\mathbb{E}_{\hat{\mathbb{P}}}(\hat{G}(x,\boldsymbol{\xi}))|\!\leq\!\frac{1}{\epsilon}\left\lVert R_{1}(x)\right\rVert\!\cdot\!\left\lVert\hat{k}(x)\right\rVert\!\cdot\!W_{1}(\mathbb{P}^{*}\!,\!\mathbb{\hat{P}})$ .

From (17), together with the fact that $\mathcal{M}_{N}^{r_{N}(\bar{\epsilon})}$ contains $\mathbb{P}^{*}$ with probability at least $1-\bar{\epsilon}$ , cf. Remark 2.1, and since the maximum Wasserstein distance between two distributions in $\mathcal{M}_{N}^{r_{N}(\bar{\epsilon})}$ is $2r_{N}(\bar{\epsilon})$ , with probability at least $1-\bar{\epsilon}$ ,

\displaystyle|\!\operatorname{CVaR}_{1-\epsilon}^{\mathbb{P}^{*}}(G_{1}(x,\hat{k}(x),\boldsymbol{\xi}))\!-\!\mathbb{E}_{\hat{\mathbb{P}}}(\hat{G}(x,\boldsymbol{\xi}))|<S_{1}(x).

(19)

for any $\mathbb{\hat{P}}\in\mathcal{M}_{N}^{r_{N}(\bar{\epsilon})}$ . By definition of $\operatorname{CVaR}$ , cf. (2), for any $\mathbb{\hat{P}}\in\mathcal{P}_{p}(\Xi)$ , $\operatorname{CVaR}_{1-\epsilon}^{\hat{\mathbb{P}}}(G_{1}(x,\hat{k}(x),\boldsymbol{\xi}))\leq\mathbb{E}_{\hat{\mathbb{P}}}(\hat{G}(x,\boldsymbol{\xi}))$ . Combining this with (19) and (16), we get that with probability at least $1-\bar{\epsilon}$ , $\operatorname{CVaR}_{1-\epsilon}^{\hat{\mathbb{P}}}(G_{1}(x,\hat{k}(x),\boldsymbol{\xi}))<0$ for all $\mathbb{\hat{P}}\in\mathcal{M}_{N}^{r_{N}(\bar{\epsilon})}$ . This argument holds for $l\in\{2,\ldots,N\}$ , implying that $\hat{k}(x)$ is strictly feasible for (10) (and hence, (11)) with probability at least $1-\bar{\epsilon}$ for any $r\leq r_{N}(\bar{\epsilon})$ .

Remark 4.8.

(Dependency of sufficient condition on slack terms): Condition (16) on the controller $\hat{k}$ guarantees the satisfaction of the constraints in (10) with a slack term $S_{l}(x)$ on the righthand side. Larger values of these slack terms mean that fewer samples are needed to satisfy (17). Moreover, for the constraints in (9), [4, Remark 2.3] shows how to obtain such functions $S_{l}$ , even without knowledge of $\hat{k}$ . $\bullet$

Remark 4.9.

(Applicability of the sufficient condition): Checking condition (17) does not require precise knowledge of $\hat{k}$ , just an upper bound of its norm. In particular, if bounds on the control norm are included as constraints in (11), those can be used to construct $B$ . Moreover, unlike Proposition 4.3, condition (17) is agnostic to the samples $\{\boldsymbol{\xi}_{1},\ldots,\boldsymbol{\xi}_{N}\}$ and instead solely depends on its number $N$ . Note that for each $x\in^{n}$ with $\left\lVert R_{l}(x)\right\rVert\neq 0$ for all $l\in[M]$ , if $S_{l}(x)>0$ for all $l\in[M]$ , there exists $\hat{N}_{x}$ such that condition (17) holds for all $N\geq\hat{N}_{x}$ . This is because $r_{N}(\bar{\epsilon})$ is decreasing in $N$ and $\lim_{N\to\infty}r_{N}(\bar{\epsilon})=0$ . The value $\hat{N}_{x}$ is state-dependent, larger for smaller values of $\epsilon$ , $S_{l}(x)$ and larger values of $B(x)$ . $\bullet$

Remark 4.10.

(Checking for (in)feasibility efficiently): A commonly used algorithm for solving SOCPs is the method in [16]. For an SOCP with $r_{S}$ constraints and optimization variable of dimension $n_{S}$ , it requires solving $\sqrt{r_{S}}$ linear systems of dimension $n_{S}$ , and hence has complexity $\mathcal{O}(\sqrt{r_{S}}n_{S}^{3})$ , cf. [17]. Therefore, (11) has complexity $\mathcal{O}(\sqrt{MN}(m+N)^{3})$ . Instead, since checking the positive definiteness of a symmetric matrix of dimension $n_{P}$ can be done by checking if its Cholesky factorization exists (which has complexity $\mathcal{O}(n_{P}^{3})$ ), the complexity of checking the condition in Proposition 4.1 is $\mathcal{O}(NMm^{3})$ . Hence, for large $N$ , it is much more efficient than solving the SOCP (11) directly. We also note that the scaling in $M$ for the complexity of the SOCP solver is more favorable than that of checking the necessary condition. On the other hand, the complexity of checking the sufficient condition in Proposition 4.3 reduces to finding a maximum of $N$ numbers (which has complexity linear in $N$ ) and checking the positive definiteness of two symmetric matrices of dimension $m+1$ and $m$ , resp. Hence, its complexity is $\mathcal{O}(N+m^{3})$ , which is also more efficient than solving the SOCP. Finally, note that the complexity of checking the conditions in Proposition 4.6 is constant in $N$ and $m$ , and is linear in $M$ due to the minimum in (17). Table 1 summarizes this complexity analysis. $\bullet$

Table 1: Complexity of SOCP solver versus the results in this section.

Method	Necessary/Sufficient	Complexity	$M$
Prop. 4.1	Necessary	$\mathcal{O}(NMm^{3})$	any
Prop. 4.3	Sufficient	$\mathcal{O}(N+m^{3})$	$1$
Prop. 4.6	Sufficient	$\mathcal{O}(M)$	any
SOCP solver	Necessary and sufficient	$\mathcal{O}(\sqrt{NM}(m+N)^{3})$	any

Proposition 4.1 provides necessary conditions for feasibility. If the conditions are not met, it is reasonable to gather more data for verifying feasibility without having to directly solve the program. Moreover, if the conditions in Propositions 4.3 and 4.6 are not met (which does not mean that (11) is not feasible), this might be an indication that more data is needed to certify feasibility, cf. Remarks 4.5 and 4.9.

5 Regularity Analysis

In this section, we show that the controller obtained by solving (11) is point-Lipschitz.

Proposition 5.1.

(Point-Lipschitzness of SOCP DRO): Let $r>0$ , $0<\epsilon\leq\frac{1}{N}$ and suppose $R_{l}$ and $q_{l}$ are twice continuously differentiable for all $l\in[M]$ . Let $\underaccent{\bar}{u}^{*}:^{n}\to^{m}$ be the function mapping $x\in^{n}$ to the solution of (11) in $\underaccent{\bar}{u}$ at $x$ . If (10) is strictly feasible at $x_{0}\in^{n}$ (i.e., there exists a solution satisfying all the constraints strictly), then $\underaccent{\bar}{u}^{*}$ is point-Lipschitz at $x_{0}$ .

Proof 5.2.

We first show the result for $M=1$ . Let $\mathcal{I}:=\mathrm{arg}\max_{i\in[N]}G_{1}(x_{0},\underaccent{\bar}{u}^{*}(x_{0}),\boldsymbol{\xi}_{i})$ , note that the set $\mathcal{I}$ is dependent on $x_{0}$ , but we omit this dependency to simplify the notation. Note also that since $G_{1}(x,\underaccent{\bar}{u},\boldsymbol{\xi}_{i})$ is continuous in $x$ and $\underaccent{\bar}{u}$ for all $i\in[N]$ , there exists a neighborhood $\mathcal{N}=\mathcal{N}_{x}\times\mathcal{N}_{\underaccent{\bar}{u}}\subset^{n}\times\underaccent{\bar}{\Uc}$ of $(x_{0},\underaccent{\bar}{u}^{*}(x_{0}))$ such that for all $(\hat{x},\hat{\underaccent{\bar}{u}})\in\mathcal{N}$ , there exists $i_{\hat{x},\hat{\underaccent{\bar}{u}}}\in\mathcal{I}$ such that $i_{\hat{x},\hat{\underaccent{\bar}{u}}}\in\mathrm{arg}\max_{i\in[N]}G_{1}(\hat{x},\hat{\underaccent{\bar}{u}},\boldsymbol{\xi}_{i})$ . Recall from the proof of Proposition 4.1 that, for any $x,\underaccent{\bar}{u}\in^{n}\times\underaccent{\bar}{\Uc}$ , the function $A_{x,\underaccent{\bar}{u}}(t):=\frac{1}{N}\sum_{i=1}^{N}(G_{1}(x,\underaccent{\bar}{u},\boldsymbol{\xi}_{i})+t)_{+}-t\epsilon$ attains its minimum at $t^{*}(x,\underaccent{\bar}{u}):=\max_{i\in[N]}{G_{1}(x,\underaccent{\bar}{u},\boldsymbol{\xi}_{i})}$ . Therefore, for $(\hat{x},\hat{\underaccent{\bar}{u}})\in\mathcal{N}$ , $t^{*}(\hat{x},\hat{\underaccent{\bar}{u}})=G_{1}(\hat{x},\hat{\underaccent{\bar}{u}},\boldsymbol{\xi}_{i_{\hat{x},\hat{\underaccent{\bar}{u}}}})$ .

For each $i\in\mathcal{I}$ , let $\underaccent{\bar}{u}_{i}^{*}:^{n}\to^{m}$ be defined as:

	$\displaystyle\underaccent{\bar}{u}_{i}(x):=$	$\displaystyle\min\limits_{\underaccent{\bar}{u}\in\underaccent{\bar}{\Uc}}\left\lVert\underaccent{\bar}{u}-\underaccent{\bar}{k}(x)\right\rVert^{2}$		(20)
		$\displaystyle\text{s.t.}\ r\left\lVert R_{1}(x)^{T}\underaccent{\bar}{u}\right\rVert+\epsilon G_{1}(x,\underaccent{\bar}{u},\boldsymbol{\xi}_{i})\leq 0.$

Note that since (10) is strictly feasible at $x_{0}$ , there exists $\tilde{\underaccent{\bar}{u}}\in\underaccent{\bar}{\Uc}$ such that $r\left\lVert R_{1}(x_{0})^{T}\underaccent{\bar}{\tilde{u}}\right\rVert+\max_{i\in[N]}\epsilon G_{1}(x_{0},\tilde{\underaccent{\bar}{u}},\boldsymbol{\xi}_{i})<0$ . By continuity of $R_{1}$ and $G_{1}$ in $x$ , there exists a neighborhood $\tilde{\mathcal{N}}_{x}\subset\mathcal{N}_{x}$ of $x_{0}$ such that $r\left\lVert R_{1}(x)^{T}\underaccent{\bar}{\tilde{u}}\right\rVert+\epsilon G_{1}(x,\tilde{\underaccent{\bar}{u}},\boldsymbol{\xi}_{i})<0$ for all $x\in\tilde{\mathcal{N}}_{x}$ and $i\in\mathcal{I}$ . This implies that (20) is strictly feasible for any $x\in\tilde{\mathcal{N}}_{x}$ . Hence, by [4, Proposition 5.4], $\underaccent{\bar}{u}_{i}^{*}$ is point-Lipschitz at $x_{0}$ for each $i\in\mathcal{I}$ . Now, since for all $y\in\mathcal{N}_{x}$ there exists $i\in\mathcal{I}$ such that $\underaccent{\bar}{u}^{*}(y)=\underaccent{\bar}{u}_{i}^{*}(y)$ , and $\tilde{\mathcal{N}}_{x}\subset\mathcal{N}_{x}$ , it follows $\left\lVert\underaccent{\bar}{u}^{*}(y)-\underaccent{\bar}{u}^{*}(x_{0})\right\rVert=\left\lVert\underaccent{\bar}{u}_{i}^{*}(y)-\underaccent{\bar}{u}_{i}^{*}(x_{0})\right\rVert\leq\gamma_{i}\left\lVert y-x_{0}\right\rVert$ for some $\gamma_{i}>0$ . Now, by taking $\gamma:=\max_{i\in\mathcal{I}}\gamma_{i}$ , it follows that $\left\lVert\underaccent{\bar}{u}^{*}(y)-\underaccent{\bar}{u}^{*}(x_{0})\right\rVert\leq\gamma\left\lVert y-x_{0}\right\rVert$ for all $y\in\mathcal{N}_{x}$ and hence $\underaccent{\bar}{u}^{*}$ is point-Lipschitz at $x_{0}$ . The argument if $M>1$ is analogous, defining a set $\mathcal{I}_{l}$ similar to $\mathcal{I}$ for each $l\in[M]$ .

Proposition 5.1 implies in particular that $u^{*}$ is continuous at $x_{0}$ . Note also that the strict feasibility assumption in Proposition 5.1 is satisfied with a prescribed probability if the hypothesis of Proposition 4.6 is satisfied.

6 Simulations

In this section, we evaluate our results in a ground-robot navigation example. We model the robot motion using unicycle kinematics and take a small distance $a=0.05$ off the wheel axis, cf.[18] to obtain a relative-degree-one model:

\begin{bmatrix}\dot{x}_{1}\\ \dot{x}_{2}\\ \dot{\theta}\end{bmatrix}=\Bigg{(}\begin{bmatrix}0&\cos(\theta)&-a\sin(\theta)\\ 0&\sin(\theta)&a\cos(\theta)\\ 0&0&1\end{bmatrix}+\sum_{j=1}^{3}W_{j}(x)\xi_{j})\Bigg{)}\begin{bmatrix}1\\ v\\ \omega\end{bmatrix},

where $v$ , $\omega$ are the linear and angular velocity, and

		$\displaystyle W_{1}(x)\!=\!\begin{bmatrix}0.02&0&0\\ 0.02&0&0\\ 0.01&0&0\end{bmatrix}\!\!,\,W_{2}(x)=\begin{bmatrix}0&0&0\\ 0&0&0\\ 0&0&-0.02\end{bmatrix}\!\!,\,$
		$\displaystyle W_{3}(x)\!=\!\begin{bmatrix}0&0.02\cos(\theta)&-0.02a\sin(\theta)\\ 0&0.02\sin(\theta)&0.02a\cos(\theta)\\ 0&0&0\end{bmatrix}\!\!,$

represent the model perturbations in the drift, angular velocity, and orientation. We consider uncertainty samples: $\xi_{1}\sim\mathcal{N}(0.5,1)$ , $\xi_{2}\sim\mathcal{U}(-1,1)$ , and $\xi_{3}\sim\mathcal{B}(2,0.2)$ , where $\mathcal{N}$ , $\mathcal{U}$ , $\mathcal{B}$ denote normal, uniform, and beta distributions, resp. The optimization programs are solved using the Embedded Conic Solver in CVXPY [19] with an Intel i7 9700K CPU.

We first consider the problem of stabilizing the uncertain unicycle system to a goal position $[x_{1}^{*},x_{2}^{*}]=[7,7]$ with initial state $[0,0,0]$ , so we take $M=1$ in (10). At the initial state, the robot is assumed to have $3$ samples $\{\boldsymbol{\xi}_{i}\}_{i=1}^{3}$ and initial Wasserstein radius $r=0.5$ with risk tolerance $\epsilon=0.01$ . As the robot moves, each unsuccessful solver attempt prompts the collection of additional samples, and a corresponding reduction in the ambiguity radius as prescribed by (6). In all the figures presented, the $x$ -axis represents the simulation timestep, where each timestep is equivalent to $0.02$ seconds, and the $y$ -axis denotes the time spent for carrying out the necessary and sufficient condition checks, as well as for running the solver at each timestep.

The time complexity, validity, and precision of Proposition 4.1 are explored in Fig. 1(a) and Fig. 1(b). Fig. 1(a) compares the time complexity of checking the necessary condition in Proposition 4.1 and of solving the corresponding SOCP along the whole robot trajectory. Notably, the SOCP becomes infeasible at around $t=3$ s and more uncertainty samples are given until feasibility is regained. As expected, when Proposition 4.1 predicts the program is infeasible, such inference is consistently mirrored by the solver. Fig. 1(b) specifically emphasizes the time complexity during data collection stages. As the number of samples increases, the SOCP’s time complexity escalates at a much faster rate than the necessary condition verification, in agreement with Remark 4.10.

Fig. 1(c) compares the time complexity of solving the SOCP and of checking the sufficient conditions in Propositions 4.3 and 4.6. As expected, feasibility validation by either result ensures the actual feasibility of the program by the solver. Checking Proposition 4.3 is more time-consuming than checking Proposition 4.6, cf. Remark 4.10, but has greater accuracy in validating feasibility. Notably, both checks are significantly more efficient than solving the SOCP problem.

We also consider the safe stabilizing problem of the unicycle system. The stabilization goal is $[x_{1}^{*},x_{2}^{*}]=[5,5]$ while the safety goal is to avoid a circular obstacle centered at $[3,2]$ with radius $1$ . Fig. 2 compares the time complexity and conservativeness of Proposition 4.1 and Proposition 4.6 for the case $M=2$ in (10). Proposition 4.1 is valid and requires significantly less time than solving the SOCP, while Proposition 4.6 is also valid and even more efficient.

7 Conclusions

We studied the feasibility of SOCP problems whose solution provide safe stabilizing controllers for uncertain systems with no prior knowledge of the uncertainty distribution and only a finite number of samples available. We provided a necessary condition and two sufficient conditions to check feasibility, characterized their computational complexity, and showed through simulations their usefulness in practical scenarios. We also showed that the controller obtained by solving the SOCP is point-Lipschitz under fairly general conditions. Future work will consider leveraging the identified feasibility conditions to guide online data-gathering policies that aim to reduce uncertainty about the system dynamics.

References

[1] K. Long, V. Dhiman, M. Leok, J. Cortés, and N. Atanasov, “Safe control synthesis with uncertain dynamics and constraints,” IEEE Robotics and Automation Letters, vol. 7, no. 3, pp. 7295–7302, 2022.
[2] F. Castañeda, J. J. Choi, B. Zhang, C. J. Tomlin, and K. Sreenath, “Pointwise feasibility of Gaussian process-based safety-critical control under model uncertainty,” in IEEE Conference on Decision and Control, Austin, Texas, USA, 2021, pp. 6762–6769.
[3] A. J. Taylor, V. D. Dorobantu, S. Dean, B. Recht, Y. Yue, and A. D. Ames, “Towards robust data driven control synthesis for nonlinear systems with actuation uncertainty,” in IEEE Conf. on Decision and Control, Austin, Texas, USA, 2021, pp. 6469–6476.
[4] P. Mestres and J. Cortés, “Feasibility and regularity analysis of safe stabilizing controllers under uncertainty,” Automatica, 2023, submitted.
[5] A. Lederer, A. Begzadic, N. Das, and S. Hirche, “Safe learning-based control of elastic joint robots via control barrier functions,” arXiv 2212.00478, 2023.
[6] P. Seiler, M. Jankovic, and E. Hellstrom, “Control barrier functions with unmodeled input dynamics using integral quadratic constraints,” IEEE Control Systems Letters, vol. 6, pp. 1664–1669, 2022.
[7] K. Long, Y. Yi, J. Cortés, and N. Atanasov, “Safe and stable control synthesis for uncertain system models via distributionally robust optimization,” in American Control Conference, Jun. 2023, pp. 4651–4658.
[8] E. D. Sontag, Mathematical Control Theory: Deterministic Finite Dimensional Systems, 2nd ed., ser. TAM. Springer, 1998, vol. 6.
[9] A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, and P. Tabuada, “Control barrier functions: theory and applications,” in European Control Conference, Naples, Italy, Jun. 2019, pp. 3420–3431.
[10] A. D. Ames, X. Xu, J. W. Grizzle, and P. Tabuada, “Control barrier function based quadratic programs for safety critical systems,” IEEE Transactions on Automatic Control, vol. 62, no. 8, pp. 3861–3876, 2017.
[11] F. Castañeda, J. J. Choi, B. Zhang, C. J. Tomlin, and K. Sreenath, “Gaussian process-based min-norm stabilizing controller for control-affine systems with uncertain input effects and dynamics,” in American Control Conference, New Orleans, LA, May 2021, pp. 3683–3690.
[12] K. Long, C. Qian, J. Cortés, and N. Atanasov, “Learning barrier functions with memory for robust safe navigation,” IEEE Robotics and Automation Letters, vol. 6, no. 3, pp. 4931–4938, 2021.
[13] A. Ben-Tal, L. E. Ghaoui, and A. Nemirovski, Robust Optimization, ser. Applied Mathematics Series. Princeton University Press, 2009.
[14] P. M. Esfahani and D. Kuhn, “Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations,” Mathematical Programming, vol. 171, no. 1-2, pp. 115–166, 2018.
[15] A. Nemirovski and A. Shapiro, “Convex approximations of chance constrained programs,” SIAM Journal on Optimization, vol. 17, no. 4, pp. 969–996, 2006.
[16] M. S. Lobo, L. Vandenberghe, S. Boyd, and H. Levret, “Applications of second-order cone programming,” Linear algebra and its applications, vol. 284, pp. 193–228, 1997.
[17] A.-L. Cholesky, “Sur la résolution numerique des systèmes d’équations linéaires,” Bulletin de la société des amis de la bibliothèque de l’École polytechnique, vol. 39, 2005.
[18] J. Cortés and M. Egerstedt, “Coordinated control of multi-robot systems: A survey,” SICE Journal of Control, Measurement, and System Integration, vol. 10, no. 6, pp. 495–503, 2017.
[19] S. Diamond and S. Boyd, “CVXPY: A Python-embedded modeling language for convex optimization,” Journal of Machine Learning Research, 2016.

Feasibility Analysis and Regularity Characterization of Distributionally Robust Safe Stabilizing Controllers