An efficient, error-bounded approximation algorithm for simulating quasi-statics of complex linkages

ABSTRACT

Design and analysis of articulated mechanical structures, commonly referred to as linkages, is an integral part of any CAD/CAM system. The most common approaches formulate the problem as purely geometric in nature, though dynamics or quasi-statics of linkages should also be considered. Existing optimal algorithms that compute forward dynamics or quasi-statics of linkages have a linear runtime dependence on the number of joints in the linkage. When forces are applied to a linkage, these techniques need to compute the accelerations of all the joints and can become impractical for rapid prototyping of highly complex linkages with a large number of joints.We introduce a novel algorithm that enables adaptive refinement of the forward quasi-statics simulation of complex linkages. This algorithm can cull away joints whose contribution to the overall linkage motion is below a given user-defined threshold, thus limiting the computation of the joint accelerations and forces to those that contribute most to the overall motion. It also allows a natural trade-off between the precision of the resulting simulation and the time required to compute it. We have implemented our algorithm and tested its performance on complex benchmarks consisting of up to 50,000 joints. We demonstrate that in some cases our algorithm is able to achieve up to two orders of magnitude of performance improvement, while providing a high-precision, error-bounded approximation of the quasi-statics of the simulated linkage.

REFERENCES

• 1: Bae, D., and Hauge, E. 1987. A recursive formulation for constrained mechanical systems dynamics: Part i. open-loop systems. Mechanical Structures and Machines, Vol. 15, No. 3, pp. 359--382.
• 2: Brandl, H., Johanni, R., and Otter, M. 1986. A very efficient algorithm for the simulation of robots and similar multibody systems without inversion of the mass matrix. IFAC/IFIP/IMACS Symposium, pp. 95--100.
• 3: Featherstone, R., and Orin, D. E. 2000. Robot dynamics: Equations and algorithms. IEEE Int. Conf. Robotics and Automation, pp. 826--834.
• 4: Roy Featherstone , Kluwer Academic Publishers, Robot Dynamics Algorithm, Kluwer Academic Publishers, Norwell, MA, 1987
• 5: Featherstone, R. 1999. A divide-and-conquer articulated body algorithm for parallel o(log(n)) calculation of rigid body dynamics. part 1: Basic algorithm. International Journal of Robotics Research 18(9): 867--875.
• 6: Featherstone, R. 1999. A divide-and-conquer articulated body algorithm for parallel o(log(n)) calculation of rigid body dynamics. part 2: Trees, loops, and accuracy. International Journal of Robotics Research 18(9): 876--892.
• 7: Fijany, A., Sharf, I., and D'Eleuterio, G. 1995. Parallel o(log n) algorithms for computation of manipulator forward dynamics. IEEE Transactions on Robotics and Automation 11(3): 389400.
• 8: Hollerbach, J. 1980. A recursive lagrangian formulation of manipulator dynamics and a comparative study of dynamics formulation complexity. IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-10, No. 11.
• 9: Hooker, W., and Margulies, G. 1965. The dynamical attitude equations for an n-body satellite. Journal of Astronautical Sciences, Vol. 12.
• 10: Itay Lotan , Fabian Schwarzer , Dan Halperin , Jean-Claude Latombe, Efficient maintenance and self-collision testing for Kinematic Chains, Proceedings of the eighteenth annual symposium on Computational geometry, p.43-52, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513406]
• 11: McMillan, S., and Orin, D. E. 1995. Efficient computation of articulated-body inertias using successive axial screws. IEEE Trans. on Robotics and Automation, vol. 11, pp. 606--611.
• 12: Mueller, A., and Maisser, P. 2003. A lie-group formulation of kinematics and dynamics of constrained mbs and its application to analytical mechanics. Multibody System Dynamics, vol. 9, no. 4, pp. 311--352(42).
• 13: Redon, S., Galoppo, N., and Lin, M. C. 2005. Adaptive dynamics: Algorithms and analysis. UNC Chapel Hill Technical Report TR05--006.
• 14: G. Rodriguez , K. Kreutz-Delgado , A. Jain, A spatial operator algebra for manipulator modeling and control, International Journal of Robotics Research, v.10 n.4, p.371-381, Aug. 1991 [doi>10.1177/027836499101000406]

INDEX TERMS

Keywords:
design and analysis, simulation, virtual prototyping