“Non-Smooth Newton Methods for Deformable Multi-Body Dynamics” by Macklin, Erleben, Müller-Fischer, Chentanez, Jeschke, et al. …

  • ©Miles Macklin, Kenny Erleben, Matthias Müller-Fischer, Nuttapong Chentanez, Stefan Jeschke, and Viktor Makoviychuk

Conference:


Type:


Title:

    Non-Smooth Newton Methods for Deformable Multi-Body Dynamics

Session/Category Title: Motion is in Control

Presenter(s)/Author(s):


Abstract:


    We present a framework for the simulation of rigid and deformable bodies in the presence of contact and friction. Our method is based on a non-smooth Newton iteration that solves the underlying nonlinear complementarity problems (NCPs) directly. This approach allows us to support nonlinear dynamics models, including hyperelastic deformable bodies and articulated rigid mechanisms, coupled through a smooth isotropic friction model. The fixed-point nature of our method means it requires only the solution of a symmetric linear system as a building block. We propose a new complementarity preconditioner for NCP functions that improves convergence, and we develop an efficient GPU-based solver based on the conjugate residual (CR) method that is suitable for interactive simulations. We show how to improve robustness using a new geometric stiffness approximation and evaluate our method’s performance on a number of robotics simulation scenarios, including dexterous manipulation and training using reinforcement learning.

References:


    1. Vincent Acary and Bernard Brogliato. 2008. Numerical Methods for Nonsmooth Dynamical Systems: Applications in Mechanics and Electronics. Springer Science 8 Business Media.
    2. Pierre Alart. 1997. Méthode de Newton généralisée en mécanique du contact. J. Afric. Math. Appl. 76 (1997), 83–108.
    3. Pierre Alart and Alain Curnier. 1991. A mixed formulation for frictional contact problems prone to Newton like solution methods. Comput. Methods Appl. Mech. Eng. 92, 3 (1991), 353–375.
    4. Sheldon Andrews, Marek Teichmann, and Paul G. Kry. 2017. Geometric stiffness for real-time constrained multibody dynamics. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 235–246.
    5. Mihai Anitescu and Gary D. Hart. 2004. A constraint-stabilized time-stepping approach for rigid multibody dynamics with joints, contact and friction. Internat. J. Numer. Methods Engrg. 60, 14 (2004), 2335–2371.
    6. Uri M. Ascher, Hongsheng Chin, Linda R. Petzold, and Sebastian Reich. 1995. Stabilization of constrained mechanical systems with DAEs and invariant manifolds. J. Struct. Mech. 23, 2 (1995), 135–157.
    7. Jan Bender, Matthias Müller, Miguel A. Otaduy, Matthias Teschner, and Miles Macklin. 2014. A survey on position-based simulation methods in computer graphics. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 228–251.
    8. Michele Benzi, Gene H. Golub, and Jörg Liesen. 2005. Numerical solution of saddle point problems. Acta Numerica 14 (2005), 1–137.
    9. Florence Bertails-Descoubes, Florent Cadoux, Gilles Daviet, and Vincent Acary. 2011. A nonsmooth Newton solver for capturing exact Coulomb friction in fiber assemblies. ACM Trans. Graph. 30, 1 (2011), 6.
    10. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective dynamics: Fusing constraint projections for fast simulation. ACM Trans. Graph. 33, 4 (2014), 154.
    11. Stephen P. Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press.
    12. Charles G. Broyden. 1965. A class of methods for solving nonlinear simultaneous equations. Math. Comput. 19, 92 (1965), 577–593.
    13. Frank H. Clarke. 1990. Optimization and Nonsmooth Analysis. Vol. 5. Siam.
    14. Michael B. Cline and Dinesh K. Pai. 2003. Post-stabilization for rigid body simulation with contact and constraints. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’03), Vol. 3. IEEE, 3744–3751.
    15. Richard W. Cottle. 2008. Linear complementarity problem. In Encyclopedia of Optimization. Springer, 1873–1878.
    16. Erwin Coumans. 2015. Bullet physics simulation. In Proceedings of the ACM SIGGRAPH 2015 Courses (SIGGRAPH’15). ACM, New York, NY, Article 7.
    17. Alain Curnier and Pierre Alart. 1988. A generalized Newton method for contact problems with friction. Journal de mécanique théorique et appliquée 7, suppl. 1 (1988), 67–82. http://infoscience.epfl.ch/record/54198.
    18. Gilles Daviet, Florence Bertails-Descoubes, and Laurence Boissieux. 2011. A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics. In ACM Transactions on Graphics, Vol. 30. ACM, 139.
    19. Steven P. Dirkse and Michael C. Ferris. 1995. The path solver: A nommonotone stabilization scheme for mixed complementarity problems. Optimiz. Methods Softw. 5, 2 (1995), 123–156.
    20. Christian Duriez. 2013. Control of elastic soft robots based on real-time finite element method. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’13). IEEE, 3982–3987.
    21. Kenny Erleben. 2013. Numerical methods for linear complementarity problems in physics-based animation. In Proceedings of the ACM SIGGRAPH 2013 Courses. ACM, 8.
    22. Kenny Erleben. 2017. Rigid body contact problems using proximal operators. In Proceedings of the ACM Symposium on Computer Animation. 13.
    23. Michael C. Ferris and Todd S. Munson. 2000. Complementarity Problems in GAMS and the PATH Solver1. J. Econ. Dynam. Control 24, 2 (2000), 165–188.
    24. Andreas Fischer. 1992. A special Newton-type optimization method. Optimization 24, 3–4 (1992), 269–284.
    25. David Chin-Lung Fong and Michael Saunders. 2012. CG versus MINRES: An empirical comparison. Sultan Qaboos Univ. J. Sci. 17, 1 (2012), 44–62.
    26. Mihai Frâncu and Florica Moldoveanu. 2015. Virtual try on systems for clothes: Issues and solutions. UPB Sci. Bull., Ser. C 77, 4 (2015), 31–44.
    27. Masao Fukushima, Zhi-Quan Luo, and Paul Tseng. 2002. Smoothing functions for second-order-cone complementarity problems. SIAM J. Optimiz. 12, 2 (2002), 436–460.
    28. Nicolas Heess, Srinivasan Sriram, Jay Lemmon, Josh Merel, Greg Wayne, Yuval Tassa, Tom Erez, Ziyu Wang, Ali Eslami, Martin Riedmiller, et al. 2017. Emergence of locomotion behaviours in rich environments. arXiv:1707.02286.
    29. Magnus Rudolph Hestenes and Eduard Stiefel. 1952. Methods of Conjugate Gradients for Solving Linear Systems. Vol. 49. NBS Washington, DC.
    30. Michael Hintermüller. 2010. Semismooth Newton methods and applications. (2010).
    31. Filip Ilievski, Aaron D. Mazzeo, Robert F. Shepherd, Xin Chen, and George M. Whitesides. 2011. Soft robotics for chemists. Angewandte Chemie 123, 8 (2011), 1930–1935.
    32. Michel Jean. 1999. The non-smooth contact dynamics method. Comput. Methods Appl. Mech. Eng. 177, 3–4 (1999), 235–257.
    33. Michel Jean and Jean Jacques Moreau. 1992. Unilaterality and dry friction in the dynamics of rigid body collections. 1st Contact Mechanics International Symposium. 31–48. https://hal.archives-ouvertes.fr/hal-01863710.
    34. Franck Jourdan, Pierre Alart, and Michel Jean. 1998. A Gauss-Seidel like algorithm to solve frictional contact problems. Comput. Methods Appl. Mech. Eng. 155, 1–2 (1998), 31–47.
    35. Danny M. Kaufman, Shinjiro Sueda, Doug L. James, and Dinesh K. Pai. 2008. Staggered projections for frictional contact in multibody systems. In ACM Transactions on Graphics (TOG), Vol. 27. ACM, 164.
    36. Danny M. Kaufman, Rasmus Tamstorf, Breannan Smith, Jean-Marie Aubry, and Eitan Grinspun. 2014. Adaptive nonlinearity for collisions in complex rod assemblies. ACM Trans. Graph. 33, 4 (2014), 123.
    37. Cornelius Lanczos. 1970. The Variational Principles of Mechanics. Vol. 4. Courier Corporation.
    38. Sergey Levine, Peter Pastor, Alex Krizhevsky, Julian Ibarz, and Deirdre Quillen. 2018. Learning hand-eye coordination for robotic grasping with deep learning and large-scale data collection. Int. J. Robot. Res. 37, 4–5 (2018), 421–436.
    39. Yanmei Li and Imin Kao. 2001. A review of modeling of soft-contact fingers and stiffness control for dextrous manipulation in robotics. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’01), Vol. 3. IEEE, 3055–3060.
    40. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2016. Towards real-time simulation of hyperelastic materials. arXiv preprint arXiv:1604.07378.
    41. Miles Macklin, Matthias Müller, and Nuttapong Chentanez. 2016. XPBD: Position-based simulation of compliant constrained dynamics. In Proceedings of the 9th International Conference on Motion in Games. ACM, 49–54.
    42. Jeffrey Mahler, Jacky Liang, Sherdil Niyaz, Michael Laskey, Richard Doan, Xinyu Liu, Juan Aparicio Ojea, and Ken Goldberg. 2017. Dex-Net 2.0: Deep learning to plan robust grasps with synthetic point clouds and analytic grasp metrics. CoRR abs/1703.09312. http://arxiv.org/abs/1703.09312.
    43. Nicholas Maratos. 1978. Exact Penalty Function Algorithms for Finite Dimensional and Control Optimization Problems. Ph.D. Dissertation. Imperial College London (University of London).
    44. Hammad Mazhar, Toby Heyn, Dan Negrut, and Alessandro Tasora. 2015. Using Nesterov’s method to accelerate multibody dynamics with friction and contact. ACM Trans. Graph. 34, 3 (2015), 32.
    45. T. S. Munson, F. Facchinei, M. C. Ferris, A. Fischer, and C. Kanzow. 2001. The semismooth algorithm for large scale complementarity problems. INFORMS J. Comput. 13 (2001), 294–311.
    46. Sarah Niebe and Kenny Erleben. 2015. Numerical methods for linear complementarity problems in physics-based animation. Synth. Lect. Comput. Graph. Animat. 7, 1 (2015), 1–159.
    47. Jorge Nocedal. 1980. Updating quasi-Newton matrices with limited storage. Math. Comput. 35, 151 (1980), 773–782.
    48. Jorge Nocedal and Stephen Wright. 2006. Numerical Optimization. Springer Science 8 Business Media.
    49. OpenAI. 2017. Roboschool. Retrieevd from https://github.com/openai/roboschool.
    50. Miguel A. Otaduy, Rasmus Tamstorf, Denis Steinemann, and Markus Gross. 2009. Implicit contact handling for deformable objects. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 559–568.
    51. Jong-Shi Pang. 1990. Newton’s method for B-differentiable equations. Math. Operat. Res. 15, 2 (1990), 311–341.
    52. Alvaro G. Perez, Gabriel Cirio, Fernando Hernandez, Carlos Garre, and Miguel A. Otaduy. 2013. Strain limiting for soft finger contact simulation. In Proceedings of the World Haptics Conference (WHC’13). IEEE, 79–84.
    53. Liqun Qi and Jie Sun. 1993. A nonsmooth version of Newton’s method. Math. Program. 58, 1–3 (1993), 353–367.
    54. Yousef Saad. 2003. Iterative Methods for Sparse Linear Systems. Vol. 82. SIAM.
    55. Fereshteh Sadeghi, Alexander Toshev, Eric Jang, and Sergey Levine. 2017. Sim2real view invariant visual servoing by recurrent control. arXiv:1712.07642.
    56. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347.
    57. Martin Servin, Claude Lacoursiere, and Niklas Melin. 2006. Interactive simulation of elastic deformable materials. In Proceedings of the SIGRAD Conference. 22–32.
    58. Tamar Shinar, Craig Schroeder, and Ronald Fedkiw. 2008. Two-way coupling of rigid and deformable bodies. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Eurographics Association, 95–103.
    59. Morten Silcowitz, Sarah Niebe, and Kenny Erleben. 2009. Nonsmooth newton method for fischer function reformulation of contact force problems for interactive rigid body simulation. In Proceedings of 6th Workshop on Virtual Reality Interaction and Physical Simulation (VRIPHYS’09). 105–114.
    60. Morten Silcowitz-Hansen, Sarah Niebe, and Kenny Erleben. 2010. A nonsmooth nonlinear conjugate gradient method for interactive contact force problems. Visual Comput. 26, 6–8 (2010), 893–901.
    61. Breannan Smith, Fernando De Goes, and Theodore Kim. 2018. Stable Neo-Hookean flesh simulation. ACM Trans. Graph. 37, 2 (2018), 12.
    62. Breannan Smith, Danny M. Kaufman, Etienne Vouga, Rasmus Tamstorf, and Eitan Grinspun. 2012. Reflections on simultaneous impact. ACM Trans. Graph. 31, 4 (2012), 106.
    63. David Stewart and Jeffrey C. Trinkle. 2000. An implicit time-stepping scheme for rigid body dynamics with coulomb friction. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’00), Vol. 1. IEEE, 162–169.
    64. David E. Stewart. 2000. Rigid-body dynamics with friction and impact. SIAM Rev. 42, 1 (2000), 3–39.
    65. David E. Stewart and Jeffrey C. Trinkle. 1996. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction. Int. J. Numer. Methods Eng. 39, 15 (1996), 2673–2691.
    66. Jie Tan, Tingnan Zhang, Erwin Coumans, Atil Iscen, Yunfei Bai, Danijar Hafner, Steven Bohez, and Vincent Vanhoucke. 2018. Sim-to-Real: Learning agile locomotion for quadruped robots. arXiv preprint arXiv:1804.10332.
    67. Joseph Teran, Eftychios Sifakis, Geoffrey Irving, and Ronald Fedkiw. 2005. Robust quasistatic finite elements and flesh simulation. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. ACM, 181–190.
    68. Françoise Tisseur. 2001. Newton’s method in floating point arithmetic and iterative refinement of generalized eigenvalue problems. SIAM J. Matrix Anal. Appl. 22, 4 (2001), 1038–1057.
    69. Emanuel Todorov. 2010. Implicit nonlinear complementarity: A new approach to contact dynamics. In IEEE International Conference on Robotics and Automation (ICRA’10). IEEE, 2322–2329.
    70. Richard Tonge, Feodor Benevolenski, and Andrey Voroshilov. 2012. Mass splitting for jitter-free parallel rigid body simulation. ACM Trans. Graph. 31, 4 (July 2012).
    71. Maxime Tournier, Matthieu Nesme, Benjamin Gilles, and François Faure. 2015. Stable constrained dynamics. ACM Trans. Graph. 34, 4 (2015), 132.
    72. Ernst Hairer and Gerhard Wanner. 2010. Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, Vol. 14. Springer.
    73. Jedediyah Williams, Ying Lu, and J. C. Trinkle. 2017. A geometrically exact contact model for polytopes in multirigid-body simulation. J. Comput. Nonlin. Dynam. 12, 2 (2017), 021001.
    74. Changxi Zheng and Doug L. James. 2011. Toward high-quality modal contact sound. ACM Trans. Graph. 30, 4 (Aug. 2011).

ACM Digital Library Publication:


Overview Page: