Entropy and complexity of a path in sub-riemannian geometry

Frédéric Jean

ESAIM: Control, Optimisation and Calculus of Variations (2003)

  • Volume: 9, page 485-508
  • ISSN: 1292-8119

Abstract

top
We characterize the geometry of a path in a sub-riemannian manifold using two metric invariants, the entropy and the complexity. The entropy of a subset A of a metric space is the minimum number of balls of a given radius ε needed to cover A . It allows one to compute the Hausdorff dimension in some cases and to bound it from above in general. We define the complexity of a path in a sub-riemannian manifold as the infimum of the lengths of all trajectories contained in an ε -neighborhood of the path, having the same extremities as the path. The concept of complexity for paths was first developed to model the algorithmic complexity of the nonholonomic motion planning problem in robotics. In this paper, our aim is to estimate the entropy, Hausdorff dimension and complexity for a path in a general sub-riemannian manifold. We construct first a norm ∥ · ∥ ε on the tangent space that depends on a parameter ε > 0 . Our main result states then that the entropy of a path is equivalent to the integral of this ε -norm along the path. As a corollary we obtain upper and lower bounds for the Hausdorff dimension of a path. Our second main result is that complexity and entropy are equivalent for generic paths. We give also a computable sufficient condition on the path for this equivalence to happen.

How to cite

top

Jean, Frédéric. "Entropy and complexity of a path in sub-riemannian geometry." ESAIM: Control, Optimisation and Calculus of Variations 9 (2003): 485-508. <http://eudml.org/doc/245107>.

@article{Jean2003,
abstract = {We characterize the geometry of a path in a sub-riemannian manifold using two metric invariants, the entropy and the complexity. The entropy of a subset $A$ of a metric space is the minimum number of balls of a given radius $\{\varepsilon \}$ needed to cover $A$. It allows one to compute the Hausdorff dimension in some cases and to bound it from above in general. We define the complexity of a path in a sub-riemannian manifold as the infimum of the lengths of all trajectories contained in an $\{\varepsilon \}$-neighborhood of the path, having the same extremities as the path. The concept of complexity for paths was first developed to model the algorithmic complexity of the nonholonomic motion planning problem in robotics. In this paper, our aim is to estimate the entropy, Hausdorff dimension and complexity for a path in a general sub-riemannian manifold. We construct first a norm $\Vert \cdot \Vert _\{\{\varepsilon \}\}$ on the tangent space that depends on a parameter $\{\varepsilon \}&gt;0$. Our main result states then that the entropy of a path is equivalent to the integral of this $\{\varepsilon \}$-norm along the path. As a corollary we obtain upper and lower bounds for the Hausdorff dimension of a path. Our second main result is that complexity and entropy are equivalent for generic paths. We give also a computable sufficient condition on the path for this equivalence to happen.},
author = {Jean, Frédéric},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
keywords = {complexity; Hausdorff dimension; metric entropy; non-linear control; nonholonomic systems; sub-riemannian geometry; Complexity; sub-Riemannian geometry},
language = {eng},
pages = {485-508},
publisher = {EDP-Sciences},
title = {Entropy and complexity of a path in sub-riemannian geometry},
url = {http://eudml.org/doc/245107},
volume = {9},
year = {2003},
}

TY - JOUR
AU - Jean, Frédéric
TI - Entropy and complexity of a path in sub-riemannian geometry
JO - ESAIM: Control, Optimisation and Calculus of Variations
PY - 2003
PB - EDP-Sciences
VL - 9
SP - 485
EP - 508
AB - We characterize the geometry of a path in a sub-riemannian manifold using two metric invariants, the entropy and the complexity. The entropy of a subset $A$ of a metric space is the minimum number of balls of a given radius ${\varepsilon }$ needed to cover $A$. It allows one to compute the Hausdorff dimension in some cases and to bound it from above in general. We define the complexity of a path in a sub-riemannian manifold as the infimum of the lengths of all trajectories contained in an ${\varepsilon }$-neighborhood of the path, having the same extremities as the path. The concept of complexity for paths was first developed to model the algorithmic complexity of the nonholonomic motion planning problem in robotics. In this paper, our aim is to estimate the entropy, Hausdorff dimension and complexity for a path in a general sub-riemannian manifold. We construct first a norm $\Vert \cdot \Vert _{{\varepsilon }}$ on the tangent space that depends on a parameter ${\varepsilon }&gt;0$. Our main result states then that the entropy of a path is equivalent to the integral of this ${\varepsilon }$-norm along the path. As a corollary we obtain upper and lower bounds for the Hausdorff dimension of a path. Our second main result is that complexity and entropy are equivalent for generic paths. We give also a computable sufficient condition on the path for this equivalence to happen.
LA - eng
KW - complexity; Hausdorff dimension; metric entropy; non-linear control; nonholonomic systems; sub-riemannian geometry; Complexity; sub-Riemannian geometry
UR - http://eudml.org/doc/245107
ER -

References

top
  1. [1] A. Bellaïche, The tangent space in sub-Riemannian geometry, edited by A. Bellaïche and J.-J. Risler, Sub-Riemannian Geometry. Birkhäuser, Progr. Math. (1996). Zbl0862.53031MR1421822
  2. [2] A. Bellaïche, F. Jean and J.-J. Risler, Geometry of nonholonomic systems, edited by J.-P. Laumond, Robot Motion Planning and Control. Springer, Lecture Notes Inform. Control Sci. 229 (1998). MR1603381
  3. [3] A. Bellaïche, J.-P. Laumond and J. Jacobs, Controllability of car-like robots and complexity of the motion planning problem, in International Symposium on Intelligent Robotics. Bangalore, India (1991) 322-337. 
  4. [4] J.F. Canny, The Complexity of Robot Motion Planning. MIT Press (1988). Zbl0668.14016MR952555
  5. [5] W.L. Chow, Über Systeme von linearen partiellen Differentialgleichungen erster Ordnung. Math. Ann. 117 (1940) 98-115. Zbl0022.02304JFM65.0398.01
  6. [6] G. Comte and Y. Yomdin, Tame geometry with applications in smooth analysis. Preprint of the IHP-RAAG Network (2002). MR2041428
  7. [7] M. Gromov, Carnot–Carathéodory spaces seen from within, edited by A. Bellaïche and J.-J. Risler, Sub-Riemannian Geometry. Birkhäuser, Progr. Math. (1996). Zbl0864.53025
  8. [8] W. Hurewicz and H. Wallman, Dimension Theory. Princeton University Press, Princeton (1948). Zbl0036.12501MR6493JFM67.1092.03
  9. [9] F. Jean, Paths in sub-Riemannian geometry, edited by A. Isidori, F. Lamnabhi–Lagarrigue and W. Respondek, Nonlinear Control in the Year 2000. Springer-Verlag (2000). 
  10. [10] F. Jean, Complexity of nonholonomic motion planning. Int. J. Control 74 (2001) 776-782. Zbl1017.68138MR1832948
  11. [11] F. Jean, Uniform estimation of sub-Riemannian balls. J. Dynam. Control Systems 7 (2001) 473-500. Zbl1029.53039MR1854033
  12. [12] A.N. Kolmogorov, On certain asymptotics characteristics of some completely bounded metric spaces. Soviet Math. Dokl. 108 (1956) 385-388. Zbl0070.11501MR80904
  13. [13] I. Kupka, Géométrie sous-riemannienne, in Séminaire N. Bourbaki, Vol. 817 (1996). MR1472545
  14. [14] J.-P. Laumond, Controllability of a multibody mobile robot. IEEE Trans. Robotics Automation 9 (1993) 755-763. 
  15. [15] J.-P. Laumond, S. Sekhavat and F. Lamiraux, Guidelines in nonholonomic motion planning for mobile robots, edited by J.-P. Laumond, Robot Motion Planning and Control. Springer, Lecture Notes Inform. Control Sci. 229 (1998). MR1603377
  16. [16] J. Mitchell, On Carnot–Carathéodory metrics. J. Differential Geom. 21 (1985) 35-45. Zbl0554.53023
  17. [17] T. Nagano, Linear differential systems with singularities and an application to transitive Lie algebras. J. Math. Soc. Japan 18 (1966) 398-404. Zbl0147.23502MR199865
  18. [18] J.T. Schwartz and M. Sharir, On the “piano movers” problem II: General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math. 4 (1983) 298-351. Zbl0554.51008
  19. [19] H.J. Sussmann, An extension of theorem of Nagano on transitive Lie algebras. Proc. Amer. Math. Soc. 45 (1974) 349-356. Zbl0301.58003MR356116
  20. [20] A.M. Vershik and V.Ya. Gershkovich, Nonholonomic dynamical systems, geometry of distributions and variational problems, edited by V.I. Arnold and S.P. Novikov, Dynamical Systems VII. Springer, Encyclopaedia Math. Sci. 16 (1994). Zbl0797.58007MR1256257

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.