Complexity of control affine systems
1. Definitions of complexities
A control system takes the form
where some manifold and a set of admissible controls. A cost function is given.
- Find a path that minimizes . In general, it is not admissible.
- Approximate it by admissible trajectories.
Complexity of a path is a function of the precision of approximation,
The set of approximating controls can be defined via interpolation,
Then is the suitable rate.
If the cost depends on the parametrization, one may want to replace with time interpolation,
Tubular interpolation complexity arises from
The parametrized version of this is
Each class defines a corresponding complexity. Parametrized ones tend to 0 when tends to 0, unparametrized ones tend to infinity when tends to 0.
2.1. Sub-Riemannian geometry
Sub-Riemannian geometry deals with which is linear in ,
Let be the distribution spanned by the vector-fields . Let the distribution generated by brackets of sections of , and so on. We assume that Hörmander’s condition is satisfied, as well as equiregularity: ranks of are constant.
Theorem 1 Let be a path in such that . Then
The time interpolation complexity has the same behaviour,
2.2. Control affine systems
Control affine systems are of the form
Again, cost is
We assume the strong Hörmander condition, i.e. alone satisfy Hörmander condition. consists of all controls on sub-intervals of .
Theorem 2 Assume that , . Let be a path in such that . Then, for small enough,
For time interpolation, assume further that mod . Then
When is large enough, certain curves can be approximated more easily, and our results break down. Extreme case : drift is a recurrent vector field. Then minimum cost is zero.
Both theorems require variants of the ball-box theorem. Assumptions can probably be weakened.
For application to mechanics, i.e. second order
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 norm is replaced with norm, approximability may depend on the number of brackets needed to fill in space.