A hybrid parallelizable low-order algorithm for dynamics of multi-rigid-body systems. I: Chain systems. (English) Zbl 1042.70500
Summary: This paper presents a new hybrid parallelizable \(O(n)\) algorithm for the modeling of the dynamic behavior of multi-rigid-body chain systems. The method is based on the cutting of certain system interbody joints so that largely independent multibody subchain systems are formed. These subchains in turn interact with one another through associated unknown constraint forces \(\underline{f_ c}\) at the cut joints. The underlying feature of this new hybrid low-order algorithm is the increased coarse grain parallelism obtained through cutting the joints and explicit determination of associated constraint loads combined with a sequential \(O(n)\) procedure. In other words, sequential \(O(n)\) procedures are performed to form and solve equations of motion within subchains, and parallel strategies are used to form and solve constraint equations between subchains in parallel. It is shown that the resulting algorithm is coarse grain parallelizable up to the total number of bodies in the system. Also, the algorithm can easily accommodate the available number of processors while maintaining high efficiency. An \(O[(n+m)/N_ p+m^ {(1+\gamma)}/N_ p+m^ \gamma\log_ 2N_ p]\) \((0<\gamma<1)\) performance will be achieved with \(N_ p\) processors for a chain system with \(n\) degrees of freedom and \(m\) constraints due to cutting of interbody joints.
MSC:
| 70-08 | Computational methods for problems pertaining to mechanics of particles and systems |
| 70E55 | Dynamics of multibody systems |
Software:
MEXXReferences:
| [1] | Armstrong, W. W., Recursive solution of the equations of motion of an \(N\)-link manipulator, (Proceedings of the Fifth World Congress on the Theory of Machines and Mechanisms Montreal, Canada, Vol. 2 (1979)), 1342-1346 |
| [2] | Hollerbach, J. M., A recursive Lagrangian formulation of manipulator dynamics and a comparative study of dynamics formulation complexity, IEEE Trans. Systems, Man, and Cybernetics, SMC-10, 11, 730-736 (November 1980) |
| [3] | Walker, M. W.; Orin, D. E., Efficient dynamic computer simulation of robotic mechanisms, Journal of Dynamic Systems, Measurements, and Control, 104, 205-211 (September 1982) · Zbl 0508.70003 |
| [4] | Featherstone, R., The calculation of robotic dynamics using articulated body inertias, International Journal of Robotics Research, 2, 1, 13-30 (Spring 1983) |
| [5] | Bae, D. S.; Haug, E. J., A recursive formation for constrained mechanical systems dynamics: Part I, Open loop systems, Mechanisms, Structures, and Machines, 15, 3, 359-382 (1987) |
| [6] | Bae, D. S.; Haug, E. J., A recursive formation for constrained mechanical systems dynamics: Part II, Closed loop systems, Mechanisms, Structures, and Machines, 15, 4, 481-506 (1987) |
| [7] | Nielan, P. E., Efficient computer simulation of motions of multibody system, (Ph.D. Dissertation (1986), Stanford University) |
| [8] | Anderson, K. S., Recursive derivation of explicit equations of motion for efficient dynamic/control simulation of large multibody systems, (Ph.D. Dissertation (1990), Stanford University) |
| [9] | Rosenthal, D. E., An order \(n\) formulation for robotic systems, Journal of Astronautical Sciences, 38, 4, 511-529 (December 1990) |
| [10] | Jones, R. E., Multi-flex body dynamics for control design, (Proceedings of the Workshop on Multibody Simulation. Proceedings of the Workshop on Multibody Simulation, JPL D-5190 (1988)), 543-549, Pasadena, CA |
| [11] | Schwertassek, R., Reduction of multibody simulation time by appropriate formulation of dynamical system equations, (Proc. of the NATO Advanced Study Institute on Computer-Aided Analysis of Rigid and Flexible Mechanical Systems. Proc. of the NATO Advanced Study Institute on Computer-Aided Analysis of Rigid and Flexible Mechanical Systems, Troia, Portugal (June 27-July 9, 1993)), 447-482 · Zbl 0877.70002 |
| [12] | de Jalon, J. Garcia; Bayo, E., Kinematic and Dynamic Simulation of Multibody Systems: The Real-Time Challenge (1994), Springer-Verlag: Springer-Verlag New York |
| [13] | Rosenthal, D. E.; Sherman, M. A., High performance multibody simulations via symbolic equation manipulation and Kane’s method, Journal of the Astronautical Sciences, 34, 3, 223-239 (July-September 1986) |
| [14] | Roberson, R. E.; Schwertassek, R., Dynamics of Multibody Systems (1988), Springer-Verlag: Springer-Verlag New York · Zbl 0556.70008 |
| [15] | Anderson, K. S., An order-N formulation for motion simulation of general constrained multi-rigid-body systems, Computers and Structures, 43, 3, 565-572 (1992) · Zbl 0792.70003 |
| [16] | Anderson, K. S., An efficient formulation for the modeling of general multi-flexible-body constrained systems, International Journal of Solids and Structures, 30, 7, 921-945 (1993) · Zbl 0785.73045 |
| [17] | Orlandea, N.; Chace, M. A.; Calahan, D. A., A sparsity-oriented approach to the dynamics analysis and design of mechanical systems—Parts 1 & 2, Journal of Engineering for Industry, 43, 773-784 (August 1977) |
| [18] | Chace, M. A., Method and experience in computer aided design of large-displacement mechanical systems, (Haug, E. J., Computer Aided Analysis and Optimizations of Mechanical System Dynamics (1984), Springer-Verlag: Springer-Verlag Berlin), 233-259 · Zbl 0557.70003 |
| [19] | Lubich, C.; Nowak, U.; Pohle, U.; Engstler, C., MEXX—Numerical software for the integration of constrained mechanical systems (1992), SC92-12, Berlin |
| [20] | Brenan, K. E.; Campbell, S. L.; Petzold, L. R., Numerical Solution of Initial-Value Problems in Differential-Algebraic Equations (1989), North-Holland: North-Holland New York · Zbl 0699.65057 |
| [21] | Petzold, L. R., Differential/algebraic equations are not ODE’s, SIAM Journal of Science, Statistics and Computation, 3, 3, 367-384 (September 1982) · Zbl 0482.65041 |
| [22] | Petzold, L. R.; Lotstedt, P., Numerical solution of nonlinear differential equations with algebraic constraints II: Practical implications, SIAM Journal of Science, Statistics and Computation, 7, 3, 720-733 (July 1986) · Zbl 0632.65086 |
| [23] | Banerjee, A. K., Block-diagonal equations for multibody elastrodynamics with geometric stiffness and constraints, Journal of Guidance, Control, and Dynamics, 16, 6, 1092-1100 (Nov.-Dec. 1993) · Zbl 0794.70004 |
| [24] | Fijany, A.; Bejczy, A. K., Parallel computation of forward dynamics of manipulators, JPL New Technology Report NPO-18706, NASA Technical Brief, Vol. 17, No. 12 (December 1993), Item #82 |
| [25] | Fijany, A.; Bejczy, A. K., Techniques for parallel computation of mechanical manipulator dynamics. Part II: Forward dynamics, (Leondes, C. T., Advances in Robotic Systems and Control. Advances in Robotic Systems and Control, Advances in Control and Dynamic Systems, Vol. 40 (March 1991), Academic Press), 357-410 · Zbl 0723.00051 |
| [26] | Anderson, K. A., Parallel \(O( log_2N)\) algorithm for the motion simulation of general multi-rigid-body mechanical systems, (Proceedings of DETC’97, 1997 ASME Design Engineering Technical Conference (September 14-17, 1997)), Sacramento, CA, CDROM Paper # DETC97/VIB-4226. |
| [27] | K.A. Anderson and S. Duan, Highly parallelizable low order algorithm for the dynamics of complex multi rigid body systems, Journal of Guidance, Control, and Dynamics; K.A. Anderson and S. Duan, Highly parallelizable low order algorithm for the dynamics of complex multi rigid body systems, Journal of Guidance, Control, and Dynamics · Zbl 1042.70500 |
| [28] | Kasshara, H.; Fujii, H.; Iwata, M., Parallel processing of robot motion simulation, (Proc. IFAC \(10^{th}\) World Conference. Proc. IFAC \(10^{th}\) World Conference, Munich, Germany (July, 1987)) |
| [29] | Bae, D. S.; Kuhl, J. G.; Haug, E. J., A recursive formation for constrained mechanical system dynamics: Part III, Parallel processing implementation, Mechanisms, Structures, and Machines, 16, 249-269 (1988) |
| [30] | Lee, C. S.G.; Chang, P. R., Efficient parallel algorithms for robot forward dynamics, IEEE Transactions on Systems, Man, and Cybernetics, 18, 2, 238-251 (1988) |
| [31] | Hwang, R. S.; Bae, D. S.; Kuhl, J. G.; Haug, E. J., Parallel processing for real-time dynamic system simulation, ASME Journal of Mechanical Design, 112, 4, 520-528 (1990) |
| [32] | Anderson, K. S., An efficient modeling of constrained multibody systems for application with parallel computing, Zeitschrift für Angewante Mathematic und Mechanik, 73, 6, 520-528 (1993) |
| [33] | Sharf, I.; D’Eleuterio, G. M.T., An iterative approach to multibody simulation dynamics suitable for parallel implementation, Journal of Dynamic Systems, Measurement and Control, 115, 730-735 (December 1993) |
| [34] | Eichberger, A., Transputer-based multibody system dynamic simulation, Part I: The residual algorithm—A modified inverse dynamic formulation, Mechanics of Structures and Machines, 22, 2, 211-237 (1994) |
| [35] | Eichberger, A., Transputer-based multibody system dynamic simulation, Part II: The residual algorithm—A modified inverse dynamic formulation, Mechanics of Structures and Machines, 22, 2, 239-261 (1994) |
| [36] | Fijany, A.; Sharf, I.; D’Eleuterio, G. M.T., Parallel \(O( log N)\) algorithms for computation of manipulator forward dynamics, IEEE Transactions on Robotics and Automation, 11, 3, 389-400 (June 1995) |
| [37] | S.S. Lee, Symbolic generation of equation of motion for dynamics/control simulation of large flexible multibody space systems, Ph.D. Dissertation, University of California, Los Angeles, CA.; S.S. Lee, Symbolic generation of equation of motion for dynamics/control simulation of large flexible multibody space systems, Ph.D. Dissertation, University of California, Los Angeles, CA. |
| [38] | Lathrop, L. H., Parallelism in manipulator dynamics, International Journal of Robotics Research, 4, 2, 80-102 (1985) |
| [39] | Lee, C. S.G.; Chang, P. R., Efficient parallel algorithms for robot inverse dynamics, IEEE Transactions on Systems, Man, and Cybernetics, 16, 4, 532-542 (1988) |
| [40] | Zeid, A. A.; Overholt, J. L.; Beck, R. R., Modeling of multibody systems for controls using general purpose simulation languages, (Simulation (January 1994)), 6-19 |
| [41] | Chung, S.; Haug, E. J., Real-time simulation of multibody dynamics on shared memory multiprocessors, ASME Journal of Dynamic Systems, Measurement, and Control, 115, 730-735 (December 1993) |
| [42] | Eichberger, A.; Fuhrer, C.; Schwertassek, R., The benefits of parallel multibody simulation, International Journal for Numerical Methods in Engineering, 37, 1557-1572 (1994) · Zbl 0800.70008 |
| [43] | Kane, T. R.; Levinson, D. A., Dynamics: Theory and Application (1985), McGraw Hill: McGraw Hill New York · Zbl 0546.70015 |
| [44] | Ider, S. K.; Amirouche, F. M.L., Coordinate reduction in the dynamics of constrained multibody systems—A new approach, Journal of Applied Mechanics, 55, 899-904 (December 1988) · Zbl 0676.70009 |
| [45] | Saad, Y., Iterative Methods for Sparse Linear Systems (1996), PWS: PWS Boston · Zbl 1002.65042 |
| [46] | Golub, G. H., Matrix Computations (1993), Johns Hopkins: Johns Hopkins Baltimore, MD |
| [47] | Quinn, M., Parallel Computing: Theory and Practice (1994), McGraw-Hill: McGraw-Hill New York |
| [48] | Pacheco, P. S., Parallel Programming with MPI (1997), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA · Zbl 0877.68013 |
| [49] | Foster, I., Designing and Building Parallel Programs (1995), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0844.68040 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
