Notes of dario Prandi’s lecture

Complexity of control affine systems

1. Definitions of complexities

A control system takes the form

$\displaystyle \begin{array}{rcl} \dot{q}=f(q,u), \end{array}$

where ${q\in M}$ some manifold and ${u\in \mathcal{U}}$ a set of admissible controls. A cost function ${J:\mathcal{U}\rightarrow[0,+\infty]}$ is given.

Problem.

1. Find a path that minimizes ${J}$. In general, it is not admissible.
2. Approximate it by admissible trajectories.

1.1. Definition

Complexity of a path ${\Gamma}$ is a function of the precision ${\epsilon}$ of approximation,

$\displaystyle \begin{array}{rcl} \sigma(\Gamma,\epsilon)=\phi(\epsilon)\inf_{u\in A_\epsilon}J(u). \end{array}$

The set of approximating controls can be defined via interpolation,

$\displaystyle \begin{array}{rcl} A_\epsilon=\{u\,;\,q_u(t_i)\in\Gamma,\,J(u_{|[t_i,t_{i+1}]})<\epsilon\}. \end{array}$

Then ${\phi(\epsilon)=\frac{1}{\epsilon}}$ is the suitable rate.

If the cost depends on the parametrization, one may want to replace ${A_\epsilon}$ with time interpolation,

$\displaystyle \begin{array}{rcl} A^t_\delta = \{u\,;\,q_u(t_i)=\gamma(t_i),\,|t_i-t_{i+1}|<\delta\}. \end{array}$

Tubular interpolation complexity arises from

$\displaystyle \begin{array}{rcl} A^a_\epsilon=\{u\,;\,q_u\subset \mathrm{Tube}(\Gamma,\epsilon)\}. \end{array}$

The parametrized version of this is

$\displaystyle \begin{array}{rcl} A^n_\delta = \{u\,;\,q_u(t)\in B(\gamma(t),\epsilon)\}. \end{array}$

Each class ${A^?_\epsilon}$ defines a corresponding complexity. Parametrized ones tend to 0 when ${\delta}$ tends to 0, unparametrized ones tend to infinity when ${\epsilon}$ tends to 0.

2. Results

2.1. Sub-Riemannian geometry

Sub-Riemannian geometry deals with ${f(q,u)}$ which is linear in ${u}$,

$\displaystyle \begin{array}{rcl} \dot{q}=\sum_{i=1}^m i f_i(q), \end{array}$

and cost

$\displaystyle \begin{array}{rcl} J(u)=\int\sqrt{\sum u_i^2}\,ds. \end{array}$

Let ${\Delta(q)}$ be the distribution spanned by the vector-fields ${f_i(q)}$. Let ${\Delta^2(q)}$ the distribution generated by brackets of sections of ${\Delta}$, and so on. We assume that Hörmander’s condition ${\Delta^r=TM}$ is satisfied, as well as equiregularity: ranks of ${\Delta^p}$ are constant.

Theorem 1 Let ${\Gamma}$ be a path in ${M}$ such that ${T\Gamma\subset \Delta^k \setminus \Delta^{k-1}}$. Then

$\displaystyle \begin{array}{rcl} \sigma_c(\Gamma,\epsilon)\sim\sigma_a(\Gamma,\epsilon)\sim \sigma_n(\Gamma,\epsilon)\sim\frac{1}{\epsilon^k}. \end{array}$

The time interpolation complexity has the same behaviour,

$\displaystyle \begin{array}{rcl} \sigma_t(\gamma,\delta)\sim\delta^{1/k}. \end{array}$

2.2. Control affine systems

Control affine systems are of the form

$\displaystyle \begin{array}{rcl} \dot{q}=f_0 (q)+\sum_{i=1}^m i f_i(q). \end{array}$

Again, cost is

$\displaystyle \begin{array}{rcl} J(u)=\int\sqrt{\sum u_i^2}\,ds. \end{array}$

We assume the strong Hörmander condition, i.e. ${f_1,\ldots,f_m}$ alone satisfy Hörmander condition. ${\mathcal{U}}$ consists of all ${L^1}$ controls on sub-intervals of ${[0,\tau]}$.

Theorem 2 Assume that ${f_0 \in \Delta^s \setminus \Delta^{s-1}}$, ${s>1}$. Let ${\Gamma}$ be a path in ${M}$ such that ${T\Gamma\subset \Delta^k \setminus \Delta^{k-1}}$. Then, for ${\tau}$ small enough,

$\displaystyle \begin{array}{rcl} \sigma_c(\Gamma,\epsilon)\sim\sigma_a(\Gamma,\epsilon)\sim \frac{1}{\epsilon^k}. \end{array}$

For time interpolation, assume further that ${\dot{\gamma}\not= f_0(\gamma)}$ mod ${\Delta^{s-1}}$. Then

$\displaystyle \begin{array}{rcl} \sigma_t(\gamma,\delta)\sim\delta^{1/\max\{k,s\}}, \quad \sigma_n(\gamma,\epsilon)\sim \frac{1}{\epsilon^{\max\{k,s\}}}. \end{array}$

When ${\tau}$ is large enough, certain curves can be approximated more easily, and our results break down. Extreme case : drift ${f_0}$ is a recurrent vector field. Then minimum cost is zero.

3. Proofs

Both theorems require variants of the ball-box theorem. Assumptions can probably be weakened.

For application to mechanics, i.e. second order

4. Questions

Agrachev: Beware that approximation may be impossible in general. The end point map may not have an open image, the minimum cost between two points may be discontinuous, depending on the cost function. If ${L^1}$ norm is replaced with ${L^p}$ norm, approximability may depend on the number of brackets needed to fill in space.