Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T12:57:53.503Z 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  and
Tomasz Popiel
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: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 classical criteria are extended to curves in Riemannian manifolds, including several recent mathematical results that have not yet found their way into the literature.

Keywords

Path planningInterpolationLie groupLie quadraticAsymptotic estimateRigid body
Type
Article
Information
Robotica , Volume 25 , Issue 6 , November 2007 , pp. 691 - 701
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 on SE(3),” In: Nonlinear Control in Year 2000 Lecture Notes in Control and Information Sciences (Isidori, A., Lamnabhi-Lagarrigue, F. and Respondek, W., eds.) 258, (Springer, Berlin Germany, 2000) pp. 23–34.CrossRefGoogle Scholar
2.Barr, A., Currin, B., Gabriel, S. and Hughes, J., “Smooth Interpolation of Orientations with Angular Velocity Constraints using Quaternions,” SIGGRAPH Comput. Graph. 26, 313–320 (1992).CrossRefGoogle Scholar
3.Belta, C. and Kumar, V., “On the computation of rigid body motion,” Electron. J. Computat. Kinematics 2 (2002).Google Scholar
4.Belta, C. and Kumar, V., “Euclidean metrics for motion generation on SE(3),” J. Mech. Eng. Sci. Part C 216, 47–60, (2002).CrossRefGoogle Scholar
5.Bloch, A. M., Baillieul, J., Crouch, P. and Marsden, J., Nonholonomic Mechanics and Control Interdisciplinary Applied Mathematics) 24 (Springer, Berlin, Germany, 2003).Google Scholar
6.Brunnett, G. and Crouch, P., “Elastic curves on the sphere,” Adv. Comput. Math. 2, 23–40, (1994).CrossRefGoogle Scholar
7.Brunnett, G., Crouch, P. and Silva-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. and Fillmore, 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. and Crouch, P., “On the geometry of Riemannian cubic polynomials,” Differential Geom. Appl. 15 (2), 107–135 (2001).CrossRefGoogle Scholar
12.Camarinha, M., Silva Leite, F. and Crouch, P., “Splines of class Ck 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. IMA 10, 134–149, (1972).Google Scholar
14.Crouch, P. and Silva-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. and Silva 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. and Silva 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. and Crouch, 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. Theory 6, 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. and Jüttler, B., “An algebraic approach to curves and surfaces on the sphere and other quadrics,” Comput. Aided Geometric Design 10, 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. and Kajiya, 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. and Ravani, B., “Geometric Construction of Bézier Motions,” Trans. ASME J. Mech. Des. 116, 749–755, (1994).CrossRefGoogle Scholar
26.Giambo, R., Giannoni, F. and Piccione, P., “An analytical theory for Riemannian cubic polynomials,” IMA J. Math. Control Inf. 19, 445–460, (2002).CrossRefGoogle Scholar
27.Giambo, R., Giannoni, F. and Piccione, P., “Optimal control on Riemannian manifolds by interpolation,” Math. Control, Signals Syst. 16, 278–296, (2004).CrossRefGoogle Scholar
28.Hofer, M. and Pottmann, H., “Energy-minimising splines in manifolds,” ACM Trans. Graph. 23, 284–293, (2004).CrossRefGoogle Scholar
29.Hüper, K. and Silva-Leite, F., “On the geometry of rolling and interpolation curves on Sn, SOn and Grassmann manifolds,” J. Dynam. Control Syst. (2007) to be published.CrossRefGoogle Scholar
30.Jost, J., Riemannian Geometry and Geometric Analysis Universitext) (Springer, Berlin, Germany, 1995).CrossRefGoogle Scholar
31.Jurdjevic, V., “Non-Euclidean elastica,” Amer. J. Math 117, 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. and Novak, J., Space Kinematics and Lie Groups (Gordon and Breach, New York, 1985.Google Scholar
34.Kim, M.-J., Kim, M.-S. and Shin, S., “A C2 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 Inference Ph.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. and Wagner, M., “Computer-aided design with spatial rational B-spline motions,” Trans. ASME J. Mech. Des. 118, 193–201, (1996).CrossRefGoogle Scholar
38.Lane, J. and Riesenfeld, 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. and Ratiu, T. S., Introduction to Mechanics and Symmetry (Texts in Applied Mathematics) 17 (Springer, Berlin, Germany, 1994).Google Scholar
40.Milnor, J., Morse Theory Annals 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. and Heiland, 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. and Schumaker, 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. and Paden, 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. and Popiel, T., “Null Riemannian cubics in tension in SO(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 in E 3,” SIAM J on Appl. Dyn. Sys. in-press 2007.CrossRefGoogle Scholar
55.Park, F. and Ravani, 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. and Ravani, 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. and Crouch, 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. and Crouch, P., “Elastic curves as solutions of sub-Riemannian control problems,” Math. Control, Signals Syst. 13, 140–155, (2000).CrossRefGoogle Scholar
60.Popiel, T. and Noakes, L., “C 2 spherical Bézier splines,” Comput. Aided Geom. Des. 23, 261–275, (2006).CrossRefGoogle Scholar
61.Popiel, T. and Noakes, L., “Bézier curves and C 2 interpolation in Riemannian manifolds,” J. Approx. Theory (Oct. 2006) to be published.Google Scholar
62.Popiel, T. and Noakes, L., “Elastica in SO(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. and Ravani, 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. and Dyn, N., “Convergence and C 1 Analysis of Subdivision Schemes on Manifolds by Proximity,” Comput. Aided Geom. Des. 22, 593–622, (2005).CrossRefGoogle Scholar
69.Zefran, M., Kumar, V. and Croke, 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. and Kumar, 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. and Kumar, 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. and Kumar, V., “Interpolation schemes for rigid body motions,” Comput. Aided Des. 30 (3), 179–189 (1998).CrossRefGoogle Scholar
73.Zefran, M., Kumar, V. and Croke, C., “On the generation of smooth three-dimensional body motions,” IEEE Trans. Robot. Autom. 14, 576–589, (1998).CrossRefGoogle Scholar