Lie group integrators for animation and control of vehicles

ABSTRACT

This article is concerned with the animation and control of vehicles with complex dynamics such as helicopters, boats, and cars. Motivated by recent developments in discrete geometric mechanics, we develop a general framework for integrating the dynamics of holonomic and nonholonomic vehicles by preserving their state-space geometry and motion invariants. We demonstrate that the resulting integration schemes are superior to standard methods in numerical robustness and efficiency, and can be applied to many types of vehicles. In addition, we show how to use this framework in an optimal control setting to automatically compute accurate and realistic motions for arbitrary user-specified constraints.

REFERENCES

• 1: Marc Alexa, Linear combination of transformations, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 2: Bloch, A. 2003. Nonholonomic Dynamical Systems. Springer.
• 3: Bloch, A. M., Krishnaprasad, P. S., Marsden, J. E., and Murray, R. 1996. Nonholonomic mechanical systems with symmetry. Arch. Rational Mech. Anal. 136, 21--99.
• 4: Nawaf Bou-Rabee , Jerrold E. Marsden, Hamilton–Pontryagin Integrators on Lie Groups Part I: Introduction and Structure-Preserving Properties, Foundations of Computational Mathematics, v.9 n.2, p.197-219, March 2009 [doi>10.1007/s10208-008-9030-4]
• 5: Bullo, F. and Lewis, A. 2004. Geometric Control of Mechanical Systems. Springer.
• 6: Celledoni, E. and Owren, B. 2003. Lie group methods for rigid body dynamics and time integration on manifolds. Comput. Meth. Appl. Mech. Eng. 19, 3--4, 421--438.
• 7: Cendra, H., Marsden, J., and Ratiu, T. 2001a. Geometric mechanics, Lagrangian reduction, and nonholonomic systems. In Mathematics Unlimited-2001 and Beyond, 221--273.
• 8: Cendra, H., Marsden, J. E., and Ratiu, T. S. 2001b. Lagrangian reduction by stages. Mem. Amer. Math. Soc. 152, 722, 108.
• 9: Cortés, J. 2002. Geometric, Control and Numerical Aspects of Nonholonomic Cystems. Springer.
• 10: Cortés, J. and Martínez, S. 2001. Non-Holonomic integrators. Nonlinearity 14, 5, 1365--1392.
• 11: Craft Animations. Craft Director Tools 4-wheeler (Autodesk Maya plugin).
• 12: de Leon, M., de Diego, D. M., and Santamaria-Merino, A. 2004. Geometric integrators and nonholonomic mechanics. J. Math. Phys. 45, 3, 1042--1062.
• 13: Dormand, J. 1996. Numerical Methods for Differential Equations. CRC Press.
• 14: Fedorov, Y. N. and Zenkov, D. V. 2005. Discrete nonholonomic LL systems on Lie groups. Nonlinearity 18, 2211--2241.
• 15: Philip E. Gill , Walter Murray , Michael A. Saunders, SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization, SIAM Journal on Optimization, v.12 n.4, p.979-1006, 2002 [doi>10.1137/S1052623499350013]
• 16: Radek Grzeszczuk , Demetri Terzopoulos , Geoffrey Hinton, NeuroAnimator: fast neural network emulation and control of physics-based models, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.9-20, July 1998 [doi>10.1145/280814.280816]
• 17: Hairer, E., Lubich, C., and Wanner, G. 2006. Geometric Numerical Integration. Springer Series in Computational Mathematics, no. 31. Springer-Verlag.
• 18: Iserles, A., Munthe-Kaas, H. Z., Nørsett, S. P., and Zanna, A. 2000. Lie group methods. Acta Numerica 9, 215--365.
• 19: Junge, O., Marsden, J., and Ober-Blöbaum, S. 2005. Discrete mechanics and optimal control. In Proccedings of IFAC.
• 20: Danny M. Kaufman , Timothy Edmunds , Dinesh K. Pai, Fast frictional dynamics for rigid bodies, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 21: Kelly, S. and Murray, R. 1995. Geometric phases and robotic locomotion. J. Robotic Syst. 12, 6, 417--431.
• 22: L. Kharevych , Weiwei Yang , Y. Tong , E. Kanso , J. E. Marsden , P. Schröder , M. Desbrun, Geometric, variational integrators for computer animation, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria
• 23: Kineo CAM. 2009. Kineo path planner (standalone automatic path planning software tool). http://www.kineocam.com/.
• 24: Kobilarov, M. 2007. Discrete geometric motion control of autonomous vehicles. Masters thesis, University of Southern California.
• 25: Wang-Sang Koon , Jerrold E. Marsden, Optimal Control for Holonomic and Nonholonomic Mechanical Systems with Symmetry and Lagrangian Reduction, SIAM Journal on Control and Optimization, v.35 n.3, p.901-929, May 1997 [doi>10.1137/S0363012995290367]
• 26: Krysl, P. and Endres, L. 2005. Explicit Newmark/Verlet algorithm for time integration of the rotational dynamics of rigid bodies. Int. J. Numer. Methods Eng. 62, 15, 2154--2177.
• 27: Lanczos, C. 1949. Variational Principles of Mechanics. University of Toronto Press.
• 28: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 29: Marsden, J. and West, M. 2001. Discrete mechanics and variational integrators. Acta Numerica 10, 357--514.
• 30: Marsden, J. E. and Ratiu, T. S. 1999. Introduction to Mechanics and Symmetry. Springer.
• 31: McLachlan, R. and Perlmutter, M. 2006. Integrators for nonholonomic mechanical systems. J. NonLinear Sci. 16, 283--328.
• 32: Richard M. Murray , S. Shankar Sastry , Li Zexiang, A Mathematical Introduction to Robotic Manipulation, CRC Press, Inc., Boca Raton, FL, 1994
• 33: Ostrowski, J. 1996. The mechanics and control of undulatory robotic locomotion. Ph.D. thesis, California Institute of Technology.
• 34: Jovan Popović , Steven M. Seitz , Michael Erdmann , Zoran Popović , Andrew Witkin, Interactive manipulation of rigid body simulations, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.209-217, July 2000 [doi>10.1145/344779.344880]
• 35: J. C. Simo , N. Tarnow , K. K. Wong, Exact energy-momentum conserving algorithms and symplectic schemes for nonlinear dynamics, Computer Methods in Applied Mechanics and Engineering, v.100 n.1, p.63-116, Oct. 1992 [doi>10.1016/0045-7825(92)90115-Z]
• 36: Ari Stern , Mathieu Desbrun, Discrete geometric mechanics for variational time integrators, ACM SIGGRAPH 2006 Courses, July 30-August 03, 2006, Boston, Massachusetts [doi>10.1145/1185657.1185669]
• 37: Yongning Zhu , Robert Bridson, Animating sand as a fluid, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation

General Terms:
Algorithms

Keywords:
Lie group integrators, Physically-based animation, holomonic and nonholonomic constraints, vehicle simulation