Hostname: page-component-5cf477f64f-tgq86 Total loading time: 0 Render date: 2025-04-08T06:40:27.444Z Has data issue: false hasContentIssue false
  • English
  • Français

Geometry for robot path planning

Published online by Cambridge University Press: 01 November 2007

Lyle Noakes*
Affiliation:
School of Mathematics and Statistics, University of Western Australia, Nedlands, WA 6009 Perth, Australia.
Tomasz Popiel
Affiliation:
School of Mathematics and Statistics, University of Western Australia, Nedlands, WA 6009 Perth, Australia.
*
*Corresponding author. E-mail:lyle@maths.uwa.edu.au

Summary

There have been many interesting recent results in the area of geometrical methods for path planning in robotics. So it seems very timely to attempt a description of mathematical developments surrounding very elementary engineering tasks. Even with such limited scope, there is too much to cover in detail. Inevitably, our knowledge and personal preferences have a lot to do with what is emphasised, included, or left out.

Part I is introductory, elementary in tone, and important for understanding the need for geometrical methods in path planning. Part II describes the results on geometrical constructions that imitate well-known constructions from classical approximation theory. Part III reviews a class of methods where classicalcriteria are extended to curves in Riemannian manifolds, including several recent mathematical results that have not yet found their way into the literature.

Type
Article
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Altafini,C., “The de Castlejau Algorithm onSE(3),”In:Nonlinear Control in Year 2000 Lecture Notes in Control and Information Sciences (Isidori,A.,Lamnabhi-Lagarrigue,F. andRespondek,W., eds.)258, (Springer,Berlin Germany,2000) pp.23–34.CrossRefGoogle Scholar
2.Barr,A.,Currin,B.,Gabriel,S. andHughes,J., “Smooth Interpolation of Orientations with Angular Velocity Constraints using Quaternions,”SIGGRAPH Comput. Graph.26,313–320 (1992).CrossRefGoogle Scholar
3.Belta,C. andKumar,V., “On the computation of rigid body motion,”Electron. J. Computat. Kinematics2 (2002).Google Scholar
4.Belta,C. andKumar,V., “Euclidean metrics for motion generation on SE(3),”J. Mech. Eng. Sci. Part C216,47–60, (2002).CrossRefGoogle Scholar
5.Bloch,A. M.,Baillieul,J.,Crouch,P. andMarsden,J., Nonholonomic Mechanics and ControlInterdisciplinary Applied Mathematics)24 (Springer,Berlin, Germany,2003).Google Scholar
6.Brunnett,G. andCrouch,P., “Elastic curves on the sphere,”Adv. Comput. Math.2,23–40, (1994).CrossRefGoogle Scholar
7.Brunnett,G.,Crouch,P. andSilva-Leite,F., “Spline Elements on Spheres,”In:Mathematical Methods for Curves and Surfaces (Vanderbilt University Press,Nashville, TN,1995) pp.49–54.Google Scholar
8.Buss,S. andFillmore,J., “Spherical averages and applications to spherical splines and interpolation,”ACM Trans. Graph.20,95–126, (2001).CrossRefGoogle Scholar
9.Buss,S., “Accurate and efficient simulations of rigid body rotations,”J. Comput. Phys.164,377–406, (2000).CrossRefGoogle Scholar
10.Camarinha,M., The Geometry of Cubic Polynomials on Riemannian Manifolds,Ph.D. Thesis (Coimbra, Portugal: University of Coimbra,1996).Google Scholar
11.Camarinha,M.,Silva Leite,F. andCrouch,P., “On the geometry of Riemannian cubic polynomials,”Differential Geom. Appl.15(2),107–135 (2001).CrossRefGoogle Scholar
12.Camarinha,M.,Silva Leite,F. andCrouch,P., “Splines of classCk on non-Euclidean spaces,”IMA J. Math. Control Inf.12(4),399–410 (1995).CrossRefGoogle Scholar
13.Cox,M., “The numerical evaluation of B-splines,”J. IMA10,134–149, (1972).Google Scholar
14.Crouch,P. andSilva-Leite,F., “Geometry and the Dynamic Interpolation Problem,”Proceedings of the American Control Conference, Boston, U.K. (1991) pp.1131–1136.Google Scholar
15.Crouch,P. andSilva Leite,F., “The dynamic interpolation problem: On Riemannian manifolds, Lie groups, and symmetric spaces,”J. Dynam. Control Syst.1(2),177–202 (1995).CrossRefGoogle Scholar
16.Crouch,P.,Kun,G. andSilva Leite,F., “The de Castlejau algorithm on Lie groups and spheres,”J. Dynam. Control Syst.5(3),397–429 (1999).CrossRefGoogle Scholar
17.Silva Leite,F.,Camarinha,M. andCrouch,P., “Elastic curves as solutions of Riemannian and sub-Riemannian control problems,”Math. Control Signals Syst.13(2),140–155 (2000).CrossRefGoogle Scholar
18.Boor,C. de, “On calculating with B-Splines,”J. Approx. Theory6,50–62, (1972).CrossRefGoogle Scholar
19.Boor,C. de,A Practical Guide to Splines (Springer,Berlin, Germany,2001).Google Scholar
20.Dietz,R.,Hoschek,J. andJüttler,B., “An algebraic approach to curves and surfaces on the sphere and other quadrics,”Comput. Aided Geometric Design10,211–229, (1993).CrossRefGoogle Scholar
21.Ding,R., “Drawing ruled surfaces using the Dual de Boor algorithm,”Electron. Notes Theoretical Comput. Sci.61,178–190, (2002).CrossRefGoogle Scholar
22.Duff,T., “Quaternion Splines for Animating Orientation,”Proceedings of the USENIX Association 2nd Computer Graphics Workshop, Monterey, CA (1985) pp. 54–62.Google Scholar
23.Duff,T., “Splines in Animation and Modelling,”In:State of the Art in Image Synthesis, SIGGRAPH '86 Course Notes (ACM Press,New York,1986).Google Scholar
24.Gabriel,S. andKajiya,J., “Spline Interpolation in Curved Space,”In:State of the Art in Image Synthesis, SIGGRAPH '85 Course Notes (ACM Press,New York,1985), pp.1–14.Google Scholar
25.Ge,Q. andRavani,B., “Geometric Construction of Bézier Motions,”Trans. ASME J. Mech. Des.116,749–755, (1994).CrossRefGoogle Scholar
26.Giambo,R.,Giannoni,F. andPiccione,P., “An analytical theory for Riemannian cubic polynomials,”IMA J. Math. Control Inf.19,445–460, (2002).CrossRefGoogle Scholar
27.Giambo,R.,Giannoni,F. andPiccione,P., “Optimal control on Riemannian manifolds by interpolation,”Math. Control, Signals Syst.16,278–296, (2004).CrossRefGoogle Scholar
28.Hofer,M. andPottmann,H., “Energy-minimising splines in manifolds,”ACM Trans. Graph.23,284–293, (2004).CrossRefGoogle Scholar
29.Hüper,K. andSilva-Leite,F., “On the geometry of rolling and interpolation curves onSn, SOn and Grassmann manifolds,”J. Dynam. Control Syst. (2007) to be published.CrossRefGoogle Scholar
30.Jost,J.,Riemannian Geometry and Geometric AnalysisUniversitext) (Springer,Berlin, Germany,1995).CrossRefGoogle Scholar
31.Jurdjevic,V., “Non-Euclidean elastica,”Amer. J. Math117,93–124, (1995).CrossRefGoogle Scholar
32.Jurdjevic,V.,Geometric Control Theory (Cambridge Studies in Advanced Mathematics)51 (Cambridge University Press, Cambridge,U. K,1997).Google Scholar
33.Karger,A. andNovak,J.,Space Kinematics and Lie Groups (Gordon and Breach,New York,1985.Google Scholar
34.Kim,M.-J.,Kim,M.-S. andShin,S., “AC2 Continuous B-Spline Quaternion Curve Interpolating a Given Sequence of Solid Orientations,”Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques (1995) pp. 369–376.Google Scholar
35.Krakowski,K., Geometrical Methods of InferencePh.D. Thesis (Perth, Australia: University of Western Australia,2002).Google Scholar
36.Krakowski,K., “Envelopes of splines in the projective plane,”IMA J. Math. Control Inf.22,171–180, (2005).CrossRefGoogle Scholar
37.Jüttler,B. andWagner,M., “Computer-aided design with spatial rational B-spline motions,”Trans. ASME J. Mech. Des.118,193–201, (1996).CrossRefGoogle Scholar
38.Lane,J. andRiesenfeld,R., “A theoretical development for the computer generation and display of piecewise polynomial surfaces,”IEEE Trans. Pattern Anal. Mach. Intel.2,35–46, (1980).CrossRefGoogle ScholarPubMed
39.Marsden,J. E. andRatiu,T. S., Introduction to Mechanics and Symmetry(Texts in Applied Mathematics)17 (Springer,Berlin, Germany,1994).Google Scholar
40.Milnor,J., Morse TheoryAnnals of Mathematical Studies)51 (Princeton University Press,NJ,1963).Google Scholar
41.Nielson,G., “Smooth Interpolation of Orientation,”Proceedings of Computer Animation '93: Models and Techniques in Computer Animation (1993) pp. 75–93.Google Scholar
42.Nielson,G. andHeiland,R., “Animated Rotations using Quaternions and Splines on a 4D Sphere,”Programm. Comput. Softw.18,145, 154 (1992).Google Scholar
43.Noakes,L., “Spherical Splines,”In:Geometric Properties for Incomplete Data (Klette,R.,Kozera,R.,Noakes,L.,Weickert,J. eds.) (Computational Imaging and Vision)31 (Springer,Berlin, Germany,2006) pp.77–101.CrossRefGoogle Scholar
44.Noakes,L., “Riemannian quadratics,”In:Curves and Surfaces with Applications in CAGD (Méhauté,A. Le,Rabut,C. andSchumaker,L. eds.) (Vanderbilt University Press,Nashville, TN,1997) pp.319–328.Google Scholar
45.Noakes,L., “Nonlinear corner-cutting,”Adv. Comput. Math.8,165–177, (1998).CrossRefGoogle Scholar
46.Noakes,L., “Accelerations of Riemannian Quadratics,”Proceedings of the American Mathematical Society 127 (1999) pp. 1827–1836.Google Scholar
47.Noakes,L., “Quadratic interpolation in spheres,”Adv. Comput. Math.17,385–395, (2002).CrossRefGoogle Scholar
48.Noakes,L.,Heinzinger,G. andPaden,B., “Cubic splines on curved spaces,”IMA J. Math. Control Inf.6,465–473, (1989).CrossRefGoogle Scholar
49.Noakes,L., “Null cubics and Lie quadratics,”J. Math. Phys.44(3),1436–1448 (Mar.2003).CrossRefGoogle Scholar
50.Noakes,L., “Non-null Lie quadratics in E3,”J. Math Phys.45(11),4334–4351 (2004).CrossRefGoogle Scholar
51.Noakes,L. andPopiel,T., “Null Riemannian cubics in tension inSO(3),”IMA J. Math. Control Inf.22,477–488, (2005).CrossRefGoogle Scholar
52.Noakes,L., “Duality and Riemannian cubics,”Adv. Comput. Math.25,195–209, (2006).CrossRefGoogle Scholar
53.Noakes,L., “Lax constraints in semisimple Lie groups,”Q. J. Math.57,527–538 (2006).CrossRefGoogle Scholar
54.Noakes,L., “Asymptotics of null Lie quadratics inE3,”SIAM J on Appl. Dyn. Sys. in-press2007.CrossRefGoogle Scholar
55.Park,F. andRavani,B., “Bézier curves on Riemannian manifolds and Lie groups with kinematic applications,”Trans. ASME J. Mech. Des.117,36–40, (1995).CrossRefGoogle Scholar
56.Park,F. andRavani,B., “Smooth invariant interpolations of rotations,”ACM Trans. Graph.16,277–295 (1997).CrossRefGoogle Scholar
57.Pletinckx,D., “Quaternion calculus as a basic tool in computer graphics,”Vis. Comput.5,2–13, (1989).CrossRefGoogle Scholar
58.Silva-Leite,F.,Camarainha,M. andCrouch,P., “Two Higher Order Variational Problems on Riemannian manifolds and the Interpolation Problem,”Proceedings of the 3rd European Control Conf. (1995) pp. 3269–3274.Google Scholar
59.Silva-Leite,F.,Camarainha,M. andCrouch,P., “Elastic curves as solutions of sub-Riemannian control problems,”Math. Control, Signals Syst.13,140–155, (2000).CrossRefGoogle Scholar
60.Popiel,T. andNoakes,L., “C2 spherical Bézier splines,”Comput. Aided Geom. Des.23,261–275, (2006).CrossRefGoogle Scholar
61.Popiel,T. andNoakes,L., “Bézier curves andC2 interpolation in Riemannian manifolds,”J. Approx. Theory (Oct.2006) to be published.Google Scholar
62.Popiel,T. andNoakes,L., “Elastica inSO(3),”J. Aust. Math. Soc. (2006) to be published.CrossRefGoogle Scholar
63.Popiel,T., “On Parametric Smoothness of Generalised B-Spline Curves,”Comput. Aided Geom. Des.23,655–668, (2006).CrossRefGoogle Scholar
64.Popiel,T., Geometrically Defined Curves in Riemannian Manifolds Ph.D. Thesis (Perth, Australia: University of Western Australia,2007).Google Scholar
65.Shoemake,K., “Animating rotations with quaternion curves,”SIGGRAPH Comput. Graph.19,245–254, (1985).CrossRefGoogle Scholar
66.Sprott,K. andRavani,B., “Ruled surfaces, Lie groups and mesh generation,”Proceedinds of the ASME Design Engineering Technology Conference (1997) No. DETC97/DAC-3966.Google Scholar
67.Wallner,J., “Smoothness analysis of subdivision schemes by proximity,”Constr. Approx.24,289–318, (2006).CrossRefGoogle Scholar
68.Wallner,J. andDyn,N., “Convergence andC1 Analysis of Subdivision Schemes on Manifolds by Proximity,”Comput. Aided Geom. Des.22,593–622, (2005).CrossRefGoogle Scholar
69.Zefran,M.,Kumar,V. andCroke,C., “Choice of Riemannian metrics for rigid body dynamics,”Proceedings of the ASME Design Engineering Technical Conference and Computers in Engineering Conf., Irvine, CA (Aug. 18–22,1996) pp. 1–11.Google Scholar
70.Zefran,M. andKumar,V., “Planning of Smooth Motions on SE(3),”Proceedings of the IEEE International Conf. on Robotics and Automation, Minneapolis, MN (1996).Google Scholar
71.Zefran,M. andKumar,V., “Two Methods for Interpolating Rigid Body Motions,”Proceedings of the IEEE International Conf. on Robotics and Automation, Leuven, Belgium (1996).Google Scholar
72.Zefran,M. andKumar,V., “Interpolation schemes for rigid body motions,”Comput. Aided Des.30(3),179–189 (1998).CrossRefGoogle Scholar
73.Zefran,M.,Kumar,V. andCroke,C., “On the generation of smooth three-dimensional body motions,”IEEE Trans. Robot. Autom.14,576–589, (1998).CrossRefGoogle Scholar