Using Nesterov's Method to Accelerate Multibody Dynamics with Friction and Contact

Abstract

We present a solution method that, compared to the traditional Gauss-Seidel approach, reduces the time required to simulate the dynamics of large systems of rigid bodies interacting through frictional contact by one to two orders of magnitude. Unlike Gauss-Seidel, it can be easily parallelized, which allows for the physics-based simulation of systems with millions of bodies. The proposed accelerated projected gradient descent (APGD) method relies on an approach by Nesterov in which a quadratic optimization problem with conic constraints is solved at each simulation time step to recover the normal and friction forces present in the system. The APGD method is validated against experimental data, compared in terms of speed of convergence and solution time with the Gauss-Seidel and Jacobi methods, and demonstrated in conjunction with snow modeling, bulldozer dynamics, and several benchmark tests that highlight the interplay between the friction and cohesion forces.

References

1. V. Acary, F. Cadoux, C. Lemarechal, and J. Malick. 2011. A formulation of the linear discrete Coulomb friction problem via convex optimization. ZAMM- J. Appl. Math. Mechan./Zeitschrift fur Angewandte Mathematik und Mechanik 91, 2, 155--175.
2. M. A. Ambroso, C. R. Santore, A. R. Abate, and D. J. Durian. 2005. Penetration depth for shallow impact cratering. Phys. Rev. E71, 051305.
3. E. Andersen and K. Andersen. 2000. The mosek interior point optimizer for linear programming: An implementation of the homogeneous algorithm. In High Performance Optimization, H. Frenk, K. Roos, T. Terlaky, and S. Zhang, Eds., Springer, 197--232.
4. E. Andersen, C. Roos, and T. Terlaky. 2003. On implementing a primal-dual interior-point method for conic quadratic optimization. Math. Program. 95, 2, 249--277.
5. M. Anitescu. 2006. Optimization-based simulation of nonsmooth rigid multibody dynamics. Math. Program. 105, 1, 113--143.
6. M. Anitescu, J. F. Cremer, and F. A. Potra. 1996. Formulating 3D contact dynamics problems. Mechan. Struct. Mach. 24, 4, 405--437.
7. M. Anitescu and G. D. Hart. 2004. A constraint-stabilized time-stepping approach for rigid multibody dynamics with joints, contact and friction. Int. J. Numer. Meth. Engin. 60, 14, 2335--2371.
8. M. Anitescu and A. Tasora. 2010. An iterative approach for cone complementarity problems for nonsmooth dynamics. Comput. Optim. Appl. 47, 2, 207--235.
9. A. Beck and M. Teboulle. 2009. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2, 1, 183--202.
10. S. R. Becker, E. J. Candes, and M. C. Grant. 2011. Templates for convex cone problems with applications to sparse signal recovery. Math. Program. Comput. 3, 3, 165--218.
11. F. Bertails-Descoubes, F. Cadoux, G. Daviet, and V. Acary. 2011. A nonsmooth Newton solver for capturing exact Coulomb friction in fiber assemblies. ACM Trans. Graph. 30, 1, 6.
12. D. Bertsekas. 1976. On the Goldstein-Levitin-Polyak gradient projection method. IEEE Trans. Autom. Control 21, 2, 174--184.
13. K. Bodin, C. Lacoursiere, and M. Servin. 2012. Constraint fluids. IEEE Trans. Visual. Comput. Graph. 18, 3, 516--526.
14. O. Bonnefon and G. Daviet. 2011. Quartic formulation of Coulomb 3D frictional contact. Tech. rep. Rapport Technique RT-0400, INRIA.
15. R. Bridson, R. Fedkiw, and J. Anderson. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3, 594--603.
16. N. V. Brilliantov, F. Spahn, J.-M. Hertzsch, and T. Poschel. 1996. Model for collisions in granular gases. Phys. Rev. E53, 5, 5382.
17. F. Cadoux. 2009. An optimization-based algorithm for Coulomb's frictional contact. ESAIM: Proc. 27, 54--69.
18. Cauchy, A. 1847. Methode generale pour la resolution des systemes d'equations simultanees. Comput. Rend. Sci. Paris 25, 1847, 536--538.
19. R. W. Cottle, J.-S. Pang, and R. E. Stone. 2009. The Linear Complementarity Problem. Academic Press, New York.
20. P. Cundall. 1971. A computer model for simulating progressive large-scale movements in block rock mechanics. In Proceedings of the International Symposium on Rock Mechanics.
21. P. Cundall. 1988. Formulation of a three-dimensional distinct element model-Part I. A scheme to detect and represent contacts in a system composed of many polyhedral blocks. Int. J. Rock Mechan. Mining Sci. Geomechan. Abstr. 25, 3, 107--116.
22. P. Cundall and O. Strack. 1979. A discrete element model for granular assemblies. Geotechniq. 29, 47--65.
23. G. Daviet, F. Bertails-Descoubes, and L. Boissieux. 2011. A hybrid iterative solver for robustly capturing Coulomb friction in hair dynamics. ACM Trans. Graph. 30, 139.
24. G. De Saxce and Z.-Q. Feng. 1998. The bipotential method: A constructive approach to design the complete contact law with friction and improved numerical algorithms. Math. Comput. Model. 28, 4, 225--245.
25. R. Delannay, M. Louge, P. Richard, N. Taberlet, and A. Valance. 2007. Towards a theoretical picture of dense granular flows down inclines. Nature Mater. 6, 2, 99--108.
26. J. W. Demmel. 2011. SuperLu users' guide. http://crd.lbl.gov/∼xiaoye/SuperLU/superlu_ug.pdf.
27. S. P. Dirkse and M. C. Ferris. 1995. The PATH solver: A nonmonotone stabilization scheme for mixed complementarity problems. Optim. Meth. Softw. 5, 2, 123--156.
28. K. Erleben. 2007. Velocity-based shock propagation for multibody dynamics animation. ACM Trans. Graph. 26, 2, 12.
29. A. Filippov. 1967. Classical solutions of differential equations with multi-valued right-hand side. SIAM J. Control 5, 4, 609--621.
30. D. M. Flickinger, J. Williams, and J. Trinkle. 2013. What's wrong with collision detection in multibody dynamic simulation? In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA'13). 959--964.
31. C. Glocker and F. Pfeiffer. 2006. An LCP-approach for multibody systems with planar friction. In Proceedings of the International Symposium on Contact Mechanics (CMIS'06). 13--20.
32. E. Guendelman, R. Bridson, and R. Fedkiw. 2003. Nonconvex rigid bodies with stacking. ACM Trans. Graph. 22, 871--878.
33. E. J. Haug. 1989. Computer-Aided Kinematics and Dynamics of Mechanical Systems, Vol. 1. Prentice-Hall, Englewood Cliffs, NJ.
34. T. Heyn. 2013. On the modeling, simulation, and visualization of many-body dynamics problems with friction and contact. Ph.D. thesis. Department of Mechanical Engineering, University of Wisconsin-Madison.
35. T. Heyn, M. Anitescu, A. Tasora, and D. Negrut. 2013. Using Krylov subspace and spectral methods for solving complementarity problems in many-body contact dynamics simulation. Int. J. Numer. Meth. Engin. 95, 7, 541--561.
36. Intel. 2013. The Intel math kernel library sparse matrix vector multiply format prototype package. http://software.intel.com/en-us/article/the-intel-math-kernel-library-sparse-matrix-vector-multiply-format-prot otype-package.
37. H. M. Jaeger, S. R. Nagel, and R. P. Behringer. 1996. Granular solids, liquids, and gases. Rev. Mod. Phys. 68, 1259--1273.
38. K. L. Johnson. 1987. Contact Mechanics. Cambridge University Press.
39. C. Kane, E. Repetto, M. Ortiz, and J. Marsden. 1999. Finite element analysis of nonsmooth contact. Comput. Meth. Appl. Mechan. Engin. 180, 1, 1--26.
40. D. M. Kaufman and D. K. Pai. 2012. Geometric numerical integration of inequality constrained, nonsmooth Hamiltonian systems. SIAM J. Sci. Comput. 34, 5, A2650--A2703.
41. A. Li, R. Serban, and D. Negrut. 2013. A SPIKE-based approach for the parallel solution of sparse linear systems on GPU cards. Tech. rep. TR-2013-05, University of Wisconsin-Madison. http://sbel.wisc.edu/documents/TR-2013-05.pdf.
42. S. Luding. 2005. Molecular dynamics simulations of granular materials. In The Physics of Granular Media, H. Hinrichsen and D. E. Wolf, Eds., Wiley-VCH, Weinheim, Germany. 299--324.
43. H. Mazhar, J. Bollman, E. Forti, A. Praeger, T. Osswald, and D. Negrut, 2013a. Studying the effect of powder geometry of the selective laser sintering process. Tech. rep. TR-2013-03, Simulation-Based Engineering Laboratory, University of Wisconsin-Madison. http://sbel.wisc.edu/documents/TR-2013-03.pdf.
44. H. Mazhar, T. Heyn, A. Pazouki, D. Melanz, A. Seidl, A. Bartholomew, A. Tasora, and D. Negrut. 2013b. Chrono: A parallel multi-physics library for rigid-body, flexible-body, and fluid dynamics. Mechan. Sci. 4, 1, 49--64.
45. H. Mazhar, D. Melanz, M. Ferris, and D. Negrut. 2014a. An analysis of several methods for handling hard-sphere frictional contact in rigid multibody dynamics. Tech. rep. TR-2014-11, Simulation-Based Engineering Laboratory, University of Wisconsin-Madison. http://sbel.wisc.edu/documents/TR-2014-11.pdf.
46. H. Mazhar, J. Schneider, and D. Negrut. 2014b. Preliminary results for helical anchoring project. Tech. rep. TR-2014-10, Simulation-Based Engineering Laboratory. University of Wisconsin-Madison, http://sbel.wisc.edu/documents/TR-2014-10.pdf.
47. H. Mazhar, T. Heyn, and D. Negrut. 2011. A scalable parallel method for large collision detection problems. Multibody Syst. Dynam. 26, 37--55.
48. J. J. Moreau and M. Jean. 1996. Numerical treatment of contact and friction: The contact dynamics method. In Proceedings of the 3^rd Biennial Joint Conference on Engineering Systems and Analysis (ESDA'96). 201--208.
49. A. Nemirovsky and D. B. Yudin. 1983. Problem Complexity and Method Efficiency in Optimization. John Wiley and Sons.
50. Y. Nesterov. 2003. A method of solving a convex programming problem with convergence rate O (1/k²). Soviet Math. Doklady 27, 2, 372--376.
51. Y. Nesterov. 2003. Introductory Lectures on Convex Optimization: A Basic Course, Vol. 87. Springer.
52. B. O'Donoghue and E. Candes. 2012. Adaptive restart for accelerated gradient schemes. ArXiv e-prints.
53. T. Poschel and T. Schwager. 2005. Computational Granular Dynamics: Models and Algorithms. Springer.
54. T. M. Preclik, K. I. Iglberger, and U. Rude. 2009. Iterative rigid multi-body dynamics. In Proceedings of the Thematic Conference on Multibody Dynamics (ECCOMAS'09).
55. T. M. Preclik and U. Rude. 2011. Solution existence and non-uniqueness of Coulomb friction. Tech. rep. 4, Friedrich-Alexander University Erlangen-Nurnberg, Institut fur Informatik, Nurnberg, Germany.
56. O. Schenk and K. Gartner. 2004. Solving unsymmetric sparse systems of linear equations with Pardiso. Future Generat. Comput. Syst. 20, 3, 475--487.
57. Z. Shojaaee, M. R. Shaebani, L. Brendel, J. Toeroek, and D. E. Wolf. 2012. An adaptive hierarchical domain decomposition method for parallel contact dynamics simulations of granular materials. J. Comput. Phys. 231, 2, 612--628.
58. B. Smith, D. M. Kaufman, G. Vouga, R. Tamstorf, and E. Grinspun. 2012. Reflections on simultaneous impact. ACM Trans. Graph. 31, 4, 106:1--106:12.
59. D. E. Stewart. 2000. Rigid-body dynamics with friction and impact. SIAM Rev. 42, 1, 3--39.
60. D. E. Stewart and J. C. Trinkle. 1996. An implicit time-stepping scheme for rigid-body dynamics with inelastic collisions and Coulomb friction. Int. J. Numer. Meth. Engin. 39, 2673--2691.
61. B.-Y. Su and K. Keutzer. 2012. clSpMV: A cross-platform OpenCL SpMV framework on GPUs. In Proceedings of the 26^th ACM International Conference on Supercomputing (ICS'12). ACM Press, New York, 353--364.
62. A. Tasora and M. Anitescu. 2013. A complementarity-based rolling friction model for rigid contacts. Meccanica 48, 7, 1643--1659.
63. A. Tasora, M. Anitescu, S. Negrini, and D. Negrut. 2013. A compliant visco-plastic particle contact model based on differential variational inequalities. Int. J. Non-Linear Mechan. 53, SI, 2--12.
64. A. Tasora, D. Negrut, and M. Anitescu. 2008. Large-scale parallel multi-body dynamics with frictional contact on the graphical processing unit. J. Multi-Body Dynam. 222, 4, 315--326.
65. R. Tonge, F. Benevolenski, and A. Voroshilov. 2012. Mass splitting for jitter-free parallel rigid body simulation. ACM Trans. Graph. 31, 4, 105.
66. J. C. Trinkle. 2003. Formulation of multibody dynamics as complementarity problems. In Proceedings of the 19^th Biennial Conference on Mechanical Vibration and Noise, Parts A, B, and C (ASME'03). Vol. 5. ASME.
67. J. S. Uehara, M. A. Ambroso, R. P. Ojha, and D. J. Durian. 2003. Low-speed impact craters in loose granular media. Phys. Rev. Lett. 90, 194301.
68. L. Vu-Quoc, L. Lesburg, and X. Zhang. 2004. An accurate tangential force-displacement model for granular-flow simulations: Contacting spheres with plastic deformation, force-driven formulation. J. Comput. Phys. 196, 1, 298--326.
69. L. Vu-Quoc and X. Zhang. 1999. An elastoplastic contact force-displacement model in the normal direction: Displacement-driven version. Proc. Royal Soc. London Series A: Math. Phys. Engin. Sci. 455, 1991, 4013--4044.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Simulation types and techniques

      • Massively parallel and high-performance simulations

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Numerical differentiation

• Theory of computation

  • Design and analysis of algorithms