Blog

Abstract: In this paper, we solve the problem of finding a certified control policy that drives a robot from any given initial state and under any bounded disturbance to the desired reference trajectory, with guarantees on the convergence or bounds on the tracking error. Such a controller is crucial in safe motion planning. We leverage the advanced theory in Control Contraction Metric and design a learning framework based on neural networks to co-synthesize the contraction metric and the controller for control-affine systems. We further provide methods to validate the convergence and bounded error guarantees. We demonstrate the performance of our method using a suite of challenging robotic models, including models with learned dynamics as neural networks. We compare our approach with leading methods using sum-of-squares programming, reinforcement learning, and model predictive control. Results show that our methods indeed can handle a broader class of systems with less tracking error and faster execution speed. Code is available at https://github.com/sundw2014/C3M. The paper is available at https://arxiv.org/abs/2011.12569.

Problem definition

Formally, given a control-affine system $\dot{x}=f(x)+B(x)u$, we want to find a feedback controller $u(\cdot ,\cdot ,\cdot )$, so that for any reference $(x^{\ast }(t),u^{\ast }(t))$ solving the ODE, the closed-loop system perturbed by $d$ $$\dot{x}=f(x(t))+B(x(t))u(x(t),x^{\ast }(t),u^{\ast }(t))+d(t)$$ satisfies that the tracking error $|x(t)–x^{\ast }(t)|$ is upper bounded, for all $|d(t)|\le ϵ$ and all initial condition $x(0)\in \mathcal{X}$.

Contraction analysis

Contraction analysis can be viewed as a differential version of Lyapunov’s theory. It analyzes the incremental stability by considering the evolution of the distance between two neighboring trajectories of the system. Lyapunov’s theory considers whether the trajectories will finally converge to a point (equilibrium), while contraction theory considers whether all the trajectories converge to a common trajectory. Control contraction metric (CCM) theory extends the analysis to cases with control input, which enables tracking controller synthesis.

Consider a system $\dot{x}=f(x)+B(x)u$, its virtual displacement ${\delta }_x$ between any pair of arbitrarily close neighboring trajectories evolves as ${\dot{\delta }}_x=A(x,u){\delta }_x+B(x){\delta }_u$, where $A(x,u):=\frac{\partial f}{\partial x}+\sum _{i=1}^m{u}^i\frac{\partial b_i}{\partial x}$.

We say $M:\mathcal{X}\mapsto {\mathbb{S}}_n^{\ge 0}$ is a CCM if there exists a controller $u(x,x^{\ast },u^{\ast })$ s.t. $\mathrm{\forall }x,x^{\ast },u^{\ast }\in \mathcal{X}\times \mathcal{X}\times \mathcal{U}$, $\mathrm{\forall }{\delta }_x\in {\mathcal{T}}_x\mathcal{X}$, $$\frac{d}{dt}({\delta }_x^{⊺}M(x){\delta }_x)\le -\lambda {\delta }_x^{⊺}M(x){\delta }_x,$$ which implies $\Vert {\delta }_x{\Vert }_M:=\sqrt{{\delta }_x^{⊺}M(x){\delta }_x}$ converges to zero exponentially at rate $\lambda$. Such a closed-loop system is referred to be contracting (under metric $M$), which implies good tracking performance.

$$\frac{d}{dt}({\delta }_x^{⊺}M(x){\delta }_x)\le -\lambda {\delta }_x^{⊺}M(x){\delta }_x,\mathrm{\forall }{\delta }_x,\mathrm{\forall }x,x^{\ast },u^{\ast },$$ $${\dot{\delta }}_x=A(x,u){\delta }_x+B(x){\delta }_u,$$ is equivalent to $\mathrm{\forall }x,x^{\ast },u^{\ast }$, $$\dot{M}+\mathtt{sym}(M(A+BK))+2\lambda M⪯0,(\ast )$$ where $K:=\frac{\partial u}{\partial x}$ and $\mathtt{sym}\left(A\right)=A+A^{⊺}$.

Learning a controller with a controller

The loss function is designed as follows.

$$\begin{array}{c}{\mathcal{L}}_{M,u}({\theta }_M,{\theta }_u):=\hfill \\ \hfill \underset{x,x^{\ast },u^{\ast }\sim \mathtt{Unif}}{\mathbb{E}}\left[L_{NSD}(\dot{M}+\mathtt{sym}(M(A+BK))+2\lambda M)\right],\end{array}$$ where $L_{NSD}:{\mathbb{R}}^{n\times n}\mapsto {\mathbb{R}}_{\ge }$ and $L_{NSD}(A)=0$ iff. matrix $A$ is negative semi-definite.

Obviously, by assuming the LHS of $(\ast )$ is continuous, $${\mathcal{L}}_{M,u}=0⟺(\ast )\text{ holds }\mathrm{\forall }x,x^{\ast },u^{\ast }\in \mathcal{X}\times \mathcal{X}\times \mathcal{U}.$$

Experimental results

• 

• 

The above figures show the tracking error of the proposed method and several others. The proposed method outperforms all the others. It is worth mentioning that $\mathtt{\text{Quadrotor}}$ is a $9$-dimensional system, and part of the dynamics of $\mathtt{\text{Neural Lander}}$ is represented as an NN.

This blog is a summary of the first part of the course ECE543@UIUC. More materials can be found here.

Problem setup

In this blog, we will focus on the binary classification problem, where the input is $X\in {\mathbb{R}}^D$, and the label is $Y\in \{0,1\}$. A set of i.i.d. training samples $S=\{(X_1,Y_1),\dots ,(X_n,Y_n)\}$ are drawn from a joint distribution $P$ defined over ${\mathbb{R}}^D\times \{0,1\}$. Sometimes, we may also denote $Z=(X,Y)$ and $Z_i=(X_i,Y_i)$. A hypothesis is a mapping $h:{\mathbb{R}}^D\mapsto \{0,1\}$. Moreover, $\mathcal{H}$ denotes the hypotheses class, which consists of all the possible hypotheses that our model (e.g. a neural network) can represent. The learning algorithm is denoted by $\mathcal{A}$, which maps a dataset $S$ to a hypothesis $h_S\in \mathcal{H}$.

Given a hypothesis $h$, we define its true risk as $$L_P(h)={\mathbb{E}}_{(X,Y)\sim P}{\mathbb{I}}_{h(X)\ne Y},$$ and the empirical risk on $S$ as $$L_S(h)=\frac{1}{n}\sum _{i=1}^n{\mathbb{I}}_{h(X_i)\ne Y_i}.$$

PAC-learnability

After applying the learning algorithm $\mathcal{A}$ to the dataset $S$, we get a hypothesis $h_S$ which depends on $S$ and minimizes the empirical risk $L_S(h)$. We care about the difference between the true risk of $h_S$ and that of $h^{\ast }$. Here, $h^{\ast }$ is the best hypothesis in the sense of minimizing the true risk, i.e. $h^{\ast }=\text{arg}\underset{h\in \mathcal{H}}{min}{L}_P(h)$. In other words, we want to get some guarantees on $L_P(h_S)-L_P(h^{\ast })$.

However, $L_P(h_S)-L_P(h^{\ast })$ is a random variable since $h_S$ depends on $S$ which is random. Therefore, it is not reasonable to look for a uniform upper bound on $L_P(h_S)-L_P(h^{\ast })$. In the PAC (Probably Approximately Correct) learning framework, instead of a uniform upper bound, we care about guarantees of the form $$Pr(L_P(h_S)-L_P(h^{\ast })\ge ϵ)\le \delta .$$ Here, “Probably” is characterized by $\delta$, and “Approximately” is characterized by $ϵ$. Next, we give the definition of PAC-learnability of a hypothesis class.

Definition 1 (PAC-learnability): A hypothesis class $\mathcal{H}$ is PAC-learnable if there exists an algorithm $\mathcal{A}$ such that for all data distribution $P_{X,Y}$ and all $ϵ,\delta \in {\mathbb{R}}^{+}$, $\mathrm{\exists }n=n(ϵ,\delta )$ such that given any training set $S$ which contains at least $n$ samples, $h_S=\mathcal{A}(S)$ satisfies $$Pr(L_P(h_S)-L_P(h^{\ast })\ge ϵ)\le \delta .$$

Theorem 1 (No free lunch): This theorem shows that we need some restrictions on the hypothesis class. We cannot learn an arbitrary set of hypotheses: there is no free lunch. Please see these lecture notes 1 and 2 for details.

A trick

Using a small trick, $L_P(h_S)–L_P(h^{\ast })$ can be bounded as follows. By doing this, $h_S$ and $h^{\ast }$ are eliminated.

$$\begin{array}{c}{L}_P(h_S)–L_P(h^{\ast })=[L_P(h_S)–L_S(h_S)]+[L_S(h^{\ast })–L_P(h^{\ast })]\hfill \\ +[L_S(h_S)–L_S(h^{\ast }){]}_{(\text{this term}\le 0)}\\ \le [L_P(h_S)–L_S(h_S)]+[L_S(h^{\ast })–L_P(h^{\ast })]\\ \hfill \le 2\underset{h\in \mathcal{H}}{sup}|L_P(h)-L_S(h)|=2\mathcal{V},\end{array}$$ where $\underset{h\in \mathcal{H}}{sup}|L_P(h)-L_S(h)|$ is denoted by $\mathcal{V}$.

Thus, $$Pr(L_P(h_S)-L_P(h^{\ast })\ge ϵ)\le Pr(\mathcal{V}\ge \frac{ϵ}{2}).$$

Theorem 2: Finite hypothesis classes are PAC-learnable.

Proof: Since $|\mathcal{H}|<\mathrm{\infty }$, we can first bound $Pr(|L_S(h)-L_P(h)|\ge \frac{ϵ}{2})$ for each $h$ and then apply the union bound. For all $ϵ>0$ and all sets $S$ with $n$ samples, We have that $$\begin{array}{rl}& Pr(L_P(h_S)-L_P(h^{\ast })\ge ϵ)\\ \le & Pr(\underset{h\in \mathcal{H}}{max}|L_S(h)-L_P(h)|\ge \frac{ϵ}{2})\\ =& Pr\left({\cup }_{h\in \mathcal{H}}\{|L_S(h)-L_P(h)|\ge \frac{ϵ}{2}\}\right)\\ \le & \sum _{h\in \mathcal{H}}Pr(|L_S(h)–L_P(h)|\ge \frac{ϵ}{2})\\ =& \sum _{h\in \mathcal{H}}Pr(|\frac{1}{n}\sum _{i=1}^n{\mathbb{I}}_{h(x_i)\ne y_i}–L_P(h)|\ge \frac{ϵ}{2})\\ \le & \sum _{h\in \mathcal{H}}\exp (-\frac{2n{ϵ}^2}{4})=|\mathcal{H}|\exp (-\frac{n{ϵ}^2}{2})=\delta ,\end{array}$$ where in the last step we use the Hoeffding’s inequality. Thus, $n(ϵ,\delta )=\frac{2}{{ϵ}^2}\log (\frac{|\mathcal{H}|}{\delta })$.

Theorem 1 is not very useful since almost all hypothesis classes we care about contain infinite hypotheses.

McDiarmid’s inequality

In order to derive PAC bounds for infinite hypothesis classes, we need some more sophisticated concentration inequalities.

Theorem 3 (McDiarmid’s inequality): Let $X_1,\dots ,X_n$ be i.i.d. random variables. Let $f$ be a function of $n$ variables. If $\mathrm{\forall }{x}_i,x_i^{\prime }$, $$|f(x_1,\dots ,x_i,\dots ,x_n)–f(x_1,\dots ,x_i^{\prime },\dots ,x_n)|\le c_i,$$ then $\mathrm{\forall }ϵ>0$, $$Pr(f(X_1,\dots ,X_n)-\mathbb{E}[f(X_1,\dots ,X_n)]\ge ϵ)\le \exp \left(\frac{-2{ϵ}^2}{\sum _{i=1}^n{c}_i}\right).$$ Such a function $f$ is said to have bounded differences.

Proof: TODO.

It can be shown that $\mathcal{V}$ has bounded differences, and thus McDiarmid’s inequality can be applied. Next, we have to derive an upper bound for $\mathbb{E}\left[\mathcal{V}\right]$.

Rademacher complexity

Definition 2 (Rademacher complexity of a set): Let $A\subseteq {\mathbb{R}}^n$, the Rademacher complexity $R(A)$ of set $A$ is defined as follows. $$R(A)={\mathbb{E}}_{\sigma }\left[\underset{a\in A}{sup}\left|\frac{1}{n}\sum _{i=1}^n{\sigma }_i{a}_i\right|\right],$$ where ${\sigma }_i$’s are i.i.d. random variables and $\mathrm{\forall }i$, $Pr({\sigma }_i=1)=Pr({\sigma }_i=-1)=0.5$.

Intuitively, Rademacher complexity characterizes the diversity of a set. If for every direction vector $\sigma =[{\sigma }_1,\cdots ,{\sigma }_n]$, we can always find an element $a\in A$ such that the inner product of $\sigma$ and $a$ is large, then $R(A)$ would be large.

Theorem 4: The expectation of $\mathcal{V}$ can be bounded as follows. $${\mathbb{E}}_S\left[\mathcal{V}\right]\le 2{\mathbb{E}}_S[R(\mathcal{F}(S))],$$ where $\mathcal{F}(S)=\{({\mathbb{I}}_{h(x_1)\ne y_1},\cdots ,{\mathbb{I}}_{h(x_n)\ne y_n}),h\in \mathcal{H}\}.$

Proof: To simplify the notation, the loss term ${\mathbb{I}}_{h(x_i)\ne y_i}$ is denoted by $f(z_i)$. Moreover, the set of all $f$’s is denoted by $\mathcal{F}$. The training set $S=\{Z_i{\}}_{i=1}^n$ is the source of randomness. Thus, $$\begin{array}{rl}& {\mathbb{E}}_S\left[\mathcal{V}\right]\\ =& {\mathbb{E}}_S\left[\underset{f\in \mathcal{F}}{sup}|\frac{1}{n}\sum _{i=1}^{n}f(Z_i)–{\mathbb{E}}_Z[f(Z)]|\right]\\ =& {\mathbb{E}}_S\left[\underset{f\in \mathcal{F}}{sup}|\frac{1}{n}\sum _{i=1}^{n}f(Z_i)–\frac{1}{n}\sum _{i=1}^n{\mathbb{E}}_{Z_i^{\prime }}[f(Z_i^{\prime })]|\right],\end{array}$$ where we introduce a virtual validation set or a set of ghost samples $S^{\prime }:=\{Z_i^{\prime }{\}}_{i=1}^n$, which is independent of $S$. This is known as the symmertrization trick. Thus, $$\begin{array}{rl}& {\mathbb{E}}_S\left[\mathcal{V}\right]\\ =& {\mathbb{E}}_S\left[\underset{f\in \mathcal{F}}{sup}\left|{\mathbb{E}}_{S^{\prime }}\left[\frac{1}{n}\sum _{i=1}^n(f(Z_i)–f(Z_i^{\prime }))\right]\right|\right]\\ \underset{\text{Jensen’s}}{\le }& {\mathbb{E}}_S\left[\underset{f\in \mathcal{F}}{sup}{\mathbb{E}}_{S^{\prime }}\left[\left|\frac{1}{n}\sum _{i=1}^n(f(Z_i)–f(Z_i^{\prime }))\right|\right]\right]\\ \le & {\mathbb{E}}_{S,S^{\prime }}\left[\underset{f\in \mathcal{F}}{sup}\left|\frac{1}{n}\sum _{i=1}^n(f(Z_i)–f(Z_i^{\prime }))\right|\right].\end{array}$$ Since $\mathrm{\forall }i$, $Z_i$ and $Z_i^{\prime }$ are i.i.d., we have that the following three random variables have the same distribution, $$f(Z_i)-f(Z_i^{\prime })\stackrel{\text{d}}{=}f(Z_i^{\prime })-f(Z_i)\stackrel{\text{d}}{=}{\sigma }_i(f(Z_i)-f(Z_i^{\prime })).$$ Thus, $$\begin{array}{rl}& {\mathbb{E}}_S\left[\mathcal{V}\right]\\ \le & {\mathbb{E}}_{S,S^{\prime },\sigma }\left[\underset{f\in \mathcal{F}}{sup}\left|\frac{1}{n}\sum _{i=1}^n{\sigma }_i(f(Z_i)–f(Z_i^{\prime }))\right|\right]\\ \le & 2{\mathbb{E}}_{S,\sigma }\left[\underset{f\in \mathcal{F}}{sup}|\frac{1}{n}\sum _{i=1}^n{\sigma }_{i}f(Z_i)|\right]=2{\mathbb{E}}_S[R(\mathcal{F}(S)].\end{array}$$

Some properties of Rademacher complexity

Rademacher calculus:

The following theorem is useful when dealing with the composition of a function and a set.

Theorem 5 (contraction principle): Let $A\subseteq {\mathbb{R}}^n$, $\varphi :\mathbb{R}\mapsto \mathbb{R}$, $\varphi (0)=0$, and $\varphi (\cdot )$ be $M$-Lipschitz continuous. Applying $\varphi$ to the set $A$ leads to a new set $\varphi \circ A=\{(\varphi (a_1),\cdots ,\varphi (a_n)),a\in A\}$. Then, the Rademacher complexity of $\varphi \circ A$ is bounded as follows. $$R(\varphi \circ A)\le 2MR(A).$$

VC-dimension

Theorem 6 (finite class lemma): Suppose $A=\{a^{(1)},\dots ,a^{(N)}\}$ is a finite subset of ${\mathbb{R}}^n$ for $N>2$ and $||a^{(i)}||\le L,\mathrm{\forall }i$, then the Radmacher complexity of $A$ is bounded as follows, $$R_n(A)\le \frac{2L\sqrt{\log N}}{n}.$$

• finite class lemma
• definition of VC-dimension
• VC’s lemma
• relationship of Rademacher complexity and VC-dimension

Others

• surrogate loss function
• contraction principle

Some examples

Now, we consider the separators on ${\mathbb{R}}^d$. Given $\mathrm{\Gamma }\subseteq {\mathbb{R}}^d$ and a data distribution $\mathcal{D}$ over $\mathrm{\Gamma }$. A set of i.i.d. samples $S=\{Z_1,\dots ,Z_n\}$ is sampled from $\mathrm{\Gamma }$ conforming the distribution $\mathcal{D}$. Denoting $\mathcal{H}$ as the hypothesis class, the learning alorithm maps $S$ to a hypothesis $h_S\in \mathcal{H}$. Given a hypothesis $h$, define its true risk as $$L_P(h)={\mathbb{E}}_{Z\sim \mathcal{D}}{\mathbb{I}}_{h(Z)\ne 1},$$ and the empirical risk on $S$ as $$L_S(h)=\frac{1}{n}\sum _{i=1}^n{\mathbb{I}}_{h(Z_i)\ne 1}.$$

Then using the VC-theory, we can derive a PAC bound for this learning problem. Here, we assume this case is realizable, i.e. $L_P(h^{\ast })=0$.

$\begin{array}{c}{L}_P(h_S)–L_P(h^{\ast })=[L_P(h_S)–L_S(h_S)]+[L_S(h^{\ast })–L_P(h^{\ast })]\hfill \\ +[L_S(h_S)–L_S(h^{\ast }){]}_{\le 0}\\ \le [L_P(h_S)–L_S(h_S)]+[L_S(h^{\ast })–L_P(h^{\ast })]\\ \hfill \le 2\underset{h\in \mathcal{H}}{sup}|L_P(h)-L_S(h)|=2\mathcal{V}\end{array}$

Using the Radmacher average to bound $\mathbb{E}[\mathcal{V}]$, $$\mathbb{E}[\mathcal{V}]\le 2\mathbb{E}[R(\mathcal{H}(Z^n))].$$

Then, we use the finite class lemma to bound the Radmacher average. Let $S_n(\mathcal{H})=\underset{z^n}{sup}|\mathcal{H}(z^n)|$, then $$\mathbb{E}[R(\mathcal{H}(Z^n))]\le \mathbb{E}\left[2\sqrt{\frac{\log S_n(\mathcal{H})}{n}}\right]=2\sqrt{\frac{\log S_n(\mathcal{H})}{n}}.$$

Next, we use the VC-dimension and the Sauer–Shelah lemma to bound $S_n(\mathcal{H})$. The Sauer-Shelah lemma, $$S_n(\mathcal{H})\le \sum _{i=1}^{VC(\mathcal{H})}(\genfrac{}{}{0ex}{}{n}{i})\le {\left(\frac{ne}{d}\right)}^{VC(\mathcal{H})}.$$ Thus, we finally have $$\mathbb{E}[L_P(h_S)]=\mathbb{E}[L_P(h_S)–L_P(h^{\ast })]\le 8\sqrt{\frac{VC(\mathcal{H})(1+\log \frac{n}{d})}{n}}.$$

Finally we use the McDiarmid’s inequality to derive a concentration property. We have $$Pr(L_P(h_S)–\mathbb{E}[L_P(h_S)]\le \frac{1}{2n}\sqrt{\log \frac{1}{\delta }})\ge 1-\delta$$ which with the above results implies that with probability higher than $1-\delta$, $$L_P(h_S)\le 8\sqrt{\frac{VC(\mathcal{H})(1+\log \frac{n}{d})}{n}}+\frac{1}{2n}\sqrt{\log \frac{1}{\delta }}.$$

With Dudley’s theorem, we can construct the so-called Dudley classes whose VC-dimension is known. Specifically, we can choose a basis of $n$ linearly independent functions to construct a $n$-dimensional Hilbert space of which the VC-dimension is $n$. For example, $\{1,x,\dots ,x^n\}$ is a valid basis.

https://image-matching-workshop.github.io/leaderboard/