Title :
Parallel O(log N) algorithms for the computation of manipulator forward dynamics
Author :
Fijany, Amir ; Sharf, Inna ; Eleuterio, Gabriele M T D
Author_Institution :
Jet Propulsion Lab., California Inst. of Technol., Pasadena, CA, USA
Abstract :
In this paper, two parallel O(log N) algorithms for the computation of manipulator forward dynamics are presented. They are based on a new O(N) algorithm for the problem which is developed from a new factorization of mass matrix M. Specifically, a factorization of the inverse M-1 in the form of a Schur complement is derived. The new O(N) algorithm is then developed as a recursive implementation of this factorization. It is shown that the resulting algorithm is strictly parallel, that is, it is less efficient than other algorithms for serial computation of the problem. However, to our knowledge, it is the only algorithm that can be parallelized to derive both a time-optimal O(logN) - and processor-optimal - O(N) - parallel algorithm for the problem. A more efficient parallel O(logN) algorithm based on a multilevel exploitation of parallelism is also briefly described. In addition to their theoretical significance, these parallel algorithms allow a practical implementation due to their simple architectural requirements
Keywords :
computational complexity; dynamics; force control; manipulators; parallel algorithms; position control; Schur complement; factorization; force decomposition; forward dynamics; manipulator; mass matrix; parallel algorithm; Aerodynamics; Algorithm design and analysis; Concurrent computing; Control systems; Force control; Iron; Manipulator dynamics; Motion control; Parallel algorithms; Parallel processing;
Conference_Titel :
Robotics and Automation, 1994. Proceedings., 1994 IEEE International Conference on
Conference_Location :
San Diego, CA
Print_ISBN :
0-8186-5330-2
DOI :
10.1109/ROBOT.1994.351368