Parking cars with Laplacians

 In this note, I explain how one can use the Laplacian operator to test controllability properties of a nonlinear control system without drift. For example, your car. Unlike their fully actuated dynamical system cousins, every control engineer thinks of only one question when they see a car:  How does one generate three degree of motion with two degrees of control? Can it be parallel parked?

The difficulty of this problem exponentially sky rockets if you are trying to park in LA especially if you have Sir 405 honking behind you. But that is not a problem I propose to solve.

Let us first introduce the classical Laplacian operator. Some (just me) call it the Thor's hammer of the applied math world. But you do not need to be Thor (or Laplace) to wield it. So what is the Laplacian? 

It takes a function $h$ and maps it to it's sum of second order derivatives,
\[ h \mapsto \Delta h := \sum_{i =1}^m \frac{\partial^2 h }{\partial x^2_i} \]The problem that we are interested in is connectivity properties about the domain $\Omega \subseteq \mathbb{R}^d$, and how this relates to properties of the operator $\Delta$.

Let's consider the function constant on $\Omega$
\[ \Psi_{\Omega}(x) = 1 ~ \forall x \in \Omega \] We can see that $\Delta \Psi_{\Omega} = 0$, when the computation is restricted to the domain $\Omega$.

 Now, suppose that the set $\Omega$ is disconnected. That is there exists two sets $\Omega_1$ and $\Omega_2$ such that $\Omega = \Omega_1 \cup \Omega_2$, and there exists no path $x:[0,1] \rightarrow \Omega$ such that
$x (0) \in \Omega_1$ and $x(1) \in \Omega_2$.  Lets define the functions.
\begin{align}\psi_{\Omega_1}(x) = 1 ~ \forall x \in \Omega_1~~~~ \text{and $0$ otherwise} \nonumber \\ \psi_{\Omega_2}(x) = 1 ~ \forall x \in \Omega_2~~~~ \text{and $0$ otherwise} \end{align}
Let $e_i \in \mathbb{R}^d$ be the coordinate vector with $1$ in the $i^{th}$ coordinate, and $0$ otherwise.
We can compute to make the following observation,
\begin{align} \frac{\partial}{ \partial x_i} \psi_{\Omega_1} = \lim_{t \rightarrow 0} \frac{\psi_{\Omega_1}(x +te_i)}{t} = 0 \nonumber \\ \frac{\partial}{ \partial x_i} \psi_{\Omega_2} = \lim_{t \rightarrow 0} \frac{\psi_{\Omega_2}(x +te_i)}{t} = 0 \end{align}for all $x \in \Omega$.
Therefore if you consider the function
\[v = \frac{1}{\int_{\Omega_1} \Psi_{\Omega_1}} \psi_{\Omega_1}- \frac{1}{\int_{\Omega_2} \Psi_{\Omega_2}} \psi_{\Omega_2} \]
we find that $\Delta_H v = 0$. Moreover,
\[ \langle v, \psi_{\Omega} \rangle_2 = \int_{\Omega} v(x)  \psi_{\Omega}(x) dx= \int_{\Omega} v(x)dx = 0\]
Therefore, $v$ is another eigenfunction corresponding to $0$, and is orthogonal to the eigenfunction $\Psi_{\Omega}$.

 

Claim: If the set $\Omega$ is disconnected then the Laplacian has two linearly independent eigenfunctions corresponding to the eigenvalue $0$.

Now, we want to apply the same idea to controllability. Suppose $\{g_1,...g_m \}$ are smooth vector fields. Recall, that a nonlinear control system
\[\dot{x} = \sum_{i=1}^mg_i(x)u_i(t)\]
is said to be controllable if for any two points $x_0, x_1 \in \Omega$, there exists $u(t):= [u_1(t),...,u_m(t)]$ such that
$x(0) = x_0$ and $x(1) = x_1$.

There are many classical ways to test controllability of this system. For example, the Chow-Rashevsky condition, which is the nonlinear analogue of the Kalman rank condition. Here we take a different approach.

Corresponding to this control system, we want to construct an corresponding Laplacian operator. Toward this end,


\begin{align}
X_i h &= \sum\limits_{j=1}^d g_{i}^{j}(x) \ \frac{\partial}{\partial x_j}h ,   \nonumber
\end{align}
and its formal adjoint
\[X_i^*h = \sum_{j=1}^d -\frac{\partial}{\partial x_j} (g_i^j(x) h). ~~~\]
Given these two operators, we can introduce the sub-Laplacian operator,
\begin{equation}
\label{eq:nonlap}
\Delta_H h = -\sum_{i=1}^{m}X_i^*X_ih,  
\end{equation}
Note we arrive at the usual Laplacian if $g_i(x) = e_i$ are just the coordinate directions and $m=d$.
 

Claim: If the system is not controllable from some set $\Omega_1$ to $\Omega_2$, then the operator $\Delta_H$ has at least two linear independent eigenfunctions corresponding to the eigenvalue $0$.

The idea behind this construction is very similar to what we did for Laplacian operator $\Delta$.
The differential operators $X_i$ have another alternative characterization.
If $\phi_i:\mathbb{R} \times \mathbb{R}^d \rightarrow \mathbb{R}^d$ is the flow map of the differential equation
\[\dot{x}(t) = g_i(x(t))~~~x(0)= x_0 \]
given by $\phi(t,x_0) = x(t)$ for all $t \in \mathbb{R}$ and $x_0 \in \mathbb{R}^d$

Then the differential operator $X_i$ can be alternatively be characterized as the Lie Derivative of the function $f$ along the flow of $g_i$,
\[ X_ih(x) = \lim_{t \rightarrow 0} \frac{h(\phi_i(t,x))- h(x)}{t}\]
Now, $\Omega_1$ is not controllable to $\Omega_2$, then there can occur no control that takes the system from $\Omega_1$ to $\Omega_2$.

This implies that
\begin{align}\Psi_{\Omega_1}(\phi_i(t,x)) = constant \nonumber \\\Psi_{\Omega_2}(\phi_i(t,x)) = constant \end{align}with respect to $t$.

Hence, \begin{align}
X_i\Psi_{\Omega_1}(x)  = 0 \\
X_i\Psi_{\Omega_2}(x)  = 0
\end{align} for each $i = 1,...,m$.
This implies once again that, $\Delta_H v =\sum_{i=1}^{m}X_i^*X_iv = 0$.

For example, consider the control system\begin{equation}\dot{x}_1 = u(t) ~~~\dot{x}_2  = 0 \end{equation}In this case, the Laplacian is given by

\[\Delta_H = \frac{\partial^2 h}{\partial x^2_1}\]

Therefore, one derivative is missing in operator in the direction  $x_2$. Clearly this system is not controllable. In this case one can construct the sets $\Omega_1$ and $\Omega_2$ in an arbitrary way by drawing a horizontal line splitting the domain into two.

Next, consider the example of a simple car model.

\begin{equation}\dot{x}_1 = u_1(t) sin(x_3)~~~\dot{x}_2  =  u_2(t) cos(x_3) ~~~\dot{x}_3  =  u_2(t) \end{equation}

The controls are the forward and backward thrust $u_1(t)$, and turning radius $u_2(t)$. In this case the operators are given by \begin{equation}X_1 = sin(x_3)\frac{\partial }{\partial x_1} +cos(x_3)\frac{\partial }{\partial x_2} ~~~~X_2 = \frac{\partial }{\partial x_3} \end{equation} For this system, it is known that it is controllable. Suppose there exists a bad eigenfunction $v$ that is orthogonal to $\Psi_\Omega$. Then it must be that $X_i v =0$ for all $i \in \{ 1,...,m\}$. Let us now define $\Omega_1$ to be the set of points such that $v$ is positive, and $\Omega_2$ to be the set of points such that $v$ is negative. Since the system is controllable we can find a control $u(t)$ such that $x(0) \in \Omega_1$ and $x(1) \in \Omega_2$. Now we can compute \begin{equation} \frac{d}{dt}v(x(t)) = \dot{x} \cdot v(x(t)) = \sum_{i=1}^m u_i(t)g_i(x(t)) \cdot v(x(t)).\end{equation} Integrating both sides, this implies  \begin{equation}v(x(1))  - v(x(0))= \int_0^1 \sum_{i=1}^m u_i(t)g_i(x(t))v(x(t))dt = \int_0^1 \sum_{i=1}^m u_i(t)X_i v(x(t))dt =0, \end{equation} since $X_i v =0$. But v(x(1)) is positive and $v(x(0))$ is negative. Hence, this can't be possible. Therefore, $X_i v \neq 0$, for $i =1,...,m$, and the operator $\Delta_H$ has only one eigenvector corresponding to the eigenvalue $0$.

 

A car on a budget

Why the operator $\Delta_H$? 

You might wonder why we didn't instead work with the operator $\sum_{i=1}^mX_i$ since it is also the case that $\sum_{i=1}^mX_i v = 0$.

One reason for this is that the operator $\Delta_H$ is a self-adjoint operator if you consider the inner product on functions \begin{equation}\langle h, g \rangle_2 = \int_{\Omega} h(x)g(x)dx\end{equation}

Then using Green's theorem the operator satisfies, assuming the functions are zero at the boundary \begin{equation}\langle \Delta_Hh, g \rangle_2 =  \langle h, \Delta_hg \rangle_2 \end{equation} Everybody knows symmetric operators are the best operators. Even if you don't believe that, one can potentially use convex optimization methods to find the second eigenvalue of the operator $\Delta_H$ and thus potentially infer controllability or non-controllability. Notice that I used the word "potentially" a lot. This is because this would result in a infinite dimensional optimizatization problem. Hence, one will have to face some curse of dimensionality when trying to implement this. But maybe if we throw a new weird machine learning architecture at it we can pretend the curse doesn't exist.

Another reason is that it is possible that $\sum_{i=1}^mX_i v = 0$ even with $X_i v \neq 0$. On the othe hand, $\Delta_H v = 0$ only if the energy function \[h \mapsto E(h) = \langle \Delta_H h,h\rangle_2 = \sum_{i=1}^m|X_i h(x)|^2dx \] takes $0$ value at $v$.

Now, all of this above was a hot mess (well, we are talking about Laplacians..wink wink), partly not accounting for the fact that one has to take derivatives carefully. But this can be made rigorous. Additionally, while this discussion only included test for controllability, the idea can also be used to design controllers based on inverting the Laplacian operator (in theory). 

Some important works connecting second order differential operators to controllability.

1. L Hörmander - Hypoelliptic second order differential equations. 1967
2. LP Rothschild, EM Stein - Hypoelliptic differential operators and nilpotent groups. 1976
   

One can also associate with each second order differential operator a stochastic process. Therefore, there is also a parallel stochastic perspective on this theory.

1. P Malliavin - Stochastic calculus of variation and hypoelliptic operators. 1976
2. DW Stroock, SRS Varadhan - On the support of diffusion processes with applications to the strong maximum principle. 1972