A continuation method for motion-planning problems

Yacine Chitour

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

  • Volume: 12, Issue: 1, page 139-168
  • ISSN: 1292-8119

Abstract

top
We apply the well-known homotopy continuation method to address the motion planning problem (MPP) for smooth driftless control-affine systems. The homotopy continuation method is a Newton-type procedure to effectively determine functions only defined implicitly. That approach requires first to characterize the singularities of a surjective map and next to prove global existence for the solution of an ordinary differential equation, the Wazewski equation. In the context of the MPP, the aforementioned singularities are the abnormal extremals associated to the dynamics of the control system and the Wazewski equation is an o.d.e. on the control space called the Path Lifting Equation (PLE). We first show elementary facts relative to the maximal solution of the PLE such as local existence and uniqueness. Then we prove two general results, a finite-dimensional reduction for the PLE on compact time intervals and a regularity preserving theorem. In a second part, if the Strong Bracket Generating Condition holds, we show, for several control spaces, the global existence of the solution of the PLE, extending a previous result of H.J. Sussmann.

How to cite

top

Chitour, Yacine. "A continuation method for motion-planning problems." ESAIM: Control, Optimisation and Calculus of Variations 12.1 (2006): 139-168. <http://eudml.org/doc/245708>.

@article{Chitour2006,
abstract = {We apply the well-known homotopy continuation method to address the motion planning problem (MPP) for smooth driftless control-affine systems. The homotopy continuation method is a Newton-type procedure to effectively determine functions only defined implicitly. That approach requires first to characterize the singularities of a surjective map and next to prove global existence for the solution of an ordinary differential equation, the Wazewski equation. In the context of the MPP, the aforementioned singularities are the abnormal extremals associated to the dynamics of the control system and the Wazewski equation is an o.d.e. on the control space called the Path Lifting Equation (PLE). We first show elementary facts relative to the maximal solution of the PLE such as local existence and uniqueness. Then we prove two general results, a finite-dimensional reduction for the PLE on compact time intervals and a regularity preserving theorem. In a second part, if the Strong Bracket Generating Condition holds, we show, for several control spaces, the global existence of the solution of the PLE, extending a previous result of H.J. Sussmann.},
author = {Chitour, Yacine},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
keywords = {homotopy continuation method; path following; Wazewski equation; sub-riemannian geometry; nonholonomic control systems; motion planning problem; sub-Riemannian geometry},
language = {eng},
number = {1},
pages = {139-168},
publisher = {EDP-Sciences},
title = {A continuation method for motion-planning problems},
url = {http://eudml.org/doc/245708},
volume = {12},
year = {2006},
}

TY - JOUR
AU - Chitour, Yacine
TI - A continuation method for motion-planning problems
JO - ESAIM: Control, Optimisation and Calculus of Variations
PY - 2006
PB - EDP-Sciences
VL - 12
IS - 1
SP - 139
EP - 168
AB - We apply the well-known homotopy continuation method to address the motion planning problem (MPP) for smooth driftless control-affine systems. The homotopy continuation method is a Newton-type procedure to effectively determine functions only defined implicitly. That approach requires first to characterize the singularities of a surjective map and next to prove global existence for the solution of an ordinary differential equation, the Wazewski equation. In the context of the MPP, the aforementioned singularities are the abnormal extremals associated to the dynamics of the control system and the Wazewski equation is an o.d.e. on the control space called the Path Lifting Equation (PLE). We first show elementary facts relative to the maximal solution of the PLE such as local existence and uniqueness. Then we prove two general results, a finite-dimensional reduction for the PLE on compact time intervals and a regularity preserving theorem. In a second part, if the Strong Bracket Generating Condition holds, we show, for several control spaces, the global existence of the solution of the PLE, extending a previous result of H.J. Sussmann.
LA - eng
KW - homotopy continuation method; path following; Wazewski equation; sub-riemannian geometry; nonholonomic control systems; motion planning problem; sub-Riemannian geometry
UR - http://eudml.org/doc/245708
ER -

References

top
  1. [1] R.A. Adams, Sobolev Spaces. Academic Press, New York (1975). Zbl0314.46030MR450957
  2. [2] E.L. Allgower and K. Georg, Continuation and Path Following. Acta Numerica (1992). Zbl0792.65034MR1224680
  3. [3] J.M. Bismuth, Large Deviations and the Malliavin Calculus. Birkhäuser (1984). Zbl0537.35003MR755001
  4. [4] L. Cesari, Functional analysis and Galerkin’s method. Mich. Math. J. 11 (1964) 385–418. Zbl0192.23702
  5. [5] A. Chelouah and Y. Chitour, On the controllability and trajectories generation of rolling surfaces. Forum Math. 15 (2003) 727–758. Zbl1044.93015
  6. [6] Y. Chitour, Applied and theoretical aspects of the controllability of nonholonomic systems. Ph.D. thesis, Rutgers University (1996). 
  7. [7] Y. Chitour, Path planning on compact Lie groups using a continuation method. Syst. Control Lett. 47 (2002) 383–391. Zbl1106.93320
  8. [8] Y. Chitour and H.J. Sussmann, Line-integral estimates and motion planning using a continuation method. Essays on Math. Robotics, J. Baillieul, S.S. Sastry and H.J. Sussmann Eds., IMA. Math. Appl. 104 (1998) 91–125. Zbl0946.70003
  9. [9] S.N. Chow and J.K. Hale, Methods of Bifurcation Theory. Springer, New York 251 (1982). Zbl0487.47039MR660633
  10. [10] A. Divelbiss and J.T. Wen, A Path Space Approach to Nonholonomic Motion Planning in the Presence of Obstacles. IEEE Trans. Robotics Automation 13 (1997) 443–451. 
  11. [11] Ge Zhong, Horizontal Path Spaces and Carnot-Carathéodory Metrics. Pacific J. Math. 161 (1993) 255–286. Zbl0797.49033
  12. [12] K.A. Grasse and H.J. Sussmann, Global controllability by nice controls, Nonlinear controllability and optimal control. Dekker, NY. Mono. Text. Pure Appl. Math. 133 (1990) 33–79. Zbl0703.93014
  13. [13] J.K. Hale, Applications of alternative problems. Lectures notes, Brown University (1971). 
  14. [14] M.W. Hirsch, Differential Topology. Springer, New York (1976). Zbl0356.57001MR448362
  15. [15] V. Jurdjevic, Geometric control theory. Cambridge Studies in Adv. Math., Cam. Univ. Press (1997). Zbl0940.93005MR1425878
  16. [16] G. Lafferriere, and H.J. Sussmann, Motion planning for controllable systems without drift, in Proc. Int. Conf. Robot. Auto. Sacramento, CA (1991) 1148–1153. 
  17. [17] E.B. Lee and L. Markus, Foundations of Optimal Control Theory. Wiley, New York (1967). Zbl0159.13201MR220537
  18. [18] J. Leray and J. Schauder, Topologie et équations fonctionelles. Ann. Sci. Ecole Norm. Sup. 51 (1934) 45–78. Zbl60.0322.02JFM60.0322.02
  19. [19] T.Y. Li, Numerical solution of multivariate polynomial systems by homotopy continuation methods. Acta Numerica (1997) 399–436. Zbl0886.65054
  20. [20] W. Liu, An approximation algorithm for nonholonomic systems. SIAM J. Control Optim. 35 (1997) 1328–1365. Zbl0887.34063
  21. [21] W. Liu and H.J. Sussmann, Shortest paths for sub-Riemannian metrics on rank 2 distributions. Memoirs of the AMS, # 564 118 (1995). Zbl0843.53038MR1303093
  22. [22] P. Martin, Contribution à l’étude des systèmes différentiellement plats. Ph.D. thesis, École des Mines de Paris, Paris, France (1992). 
  23. [23] R. Montgomery, Abnormal Optimal Controls and Open Problems in Nonholonomic Steering. J. Dyn. Cont. Sys. 1 Plenum Pub. Corp. (1995) 49–90. Zbl0941.53021
  24. [24] R.M. Murray and S.S. Sastry, Steering nonholonomic systems using sinusoids, in Proc. IEEE Conference on Decision and Control (1990). Zbl0788.70019
  25. [25] Cz. Olech, On the Wazewski equation, in Proc. of the conference, Topological methods in Differential Equations and Dynamical systems, Krakow (1996). Univ. Iagel. Acta Math. 36 (1998) 55–64. Zbl1002.58007
  26. [26] P. Pansu, Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un. Ann. Math. 129 (1989) 1–60. Zbl0678.53042
  27. [27] S.L. Richter and R.A. Decarlo, Continuation methods: Theory and Application. IEEE Trans. Circuits Syst. 30 (1983). MR713902
  28. [28] E.D. Sontag, Mathematical Control Theory. Texts Appl. Math. 6, Springer-Verlag, New York, 2nd edition (1998). Zbl0945.93001MR1640001
  29. [29] P. Souères and J.P. Laumond, Shortest paths synthesis for a car-like robot. IEEE Trans. Aut. Cont. 41 (1996) 672–688. Zbl0864.93076
  30. [30] R. Strichartz, Sub-Riemannian Geometry. J. Diff. Geom. 24 (1983) 221–263. Zbl0609.53021
  31. [31] H.J. Sussmann, A Continuation Method for Nonholonomic Path-finding Problems, in Proceedings of the 32nd IEEE CDC, San Antonio, TX (Dec. 1993). 
  32. [32] H.J. Sussmann, New Differential Geometric Methods in Nonholonomic Path Finding, in Systems, Models, and Feedback, A. Isidori and T.J. Tarn Eds. Birkhäuser, Boston (1992). Zbl0777.93014MR1169956
  33. [33] T. Wazewski, Sur l’évaluation du domaine d’existence des fonctions implicites réelles ou complexes. Ann. Soc. Polon. Math. 20 (1947). Zbl0032.05601

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.