Efficient parallel algorithm for robot inverse dynamics computation

Abstract

This paper shows that the time lower bound of computing the inverse dynamics of an n-link robot manipulator parallelly using p processors is O(k <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> [n/p] + k <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> [log <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> p]), where k <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> and k <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> are constants. A novel parallel algorithm for computing the inverse dynamics using the Newton-Euler equations of motion was developed to be implemented on an SIMD computer with p processors to achieve the time lower bound. When p = n, the proposed parallel algorithm achieves the Minsky's time lower bound O([log <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> n]) [22], which is the conjecture of parallel evaluation. The proposed p-fold parallel algorithm can be best described as consisting of p-parallel blocks with pipelined elements within each parallel block. The results from the computations in the p blocks form a new homogeneous linear recurrence of size p, which can be computed using the recursive doubling algorithm. A modified inverse perfect shuffle interconnection scheme was suggested to interconnect the p processors. Furthermore, the proposed parallel algorithm is susceptible to a systolic pipelined architecture, requiring three floating-point operations (Flops) per complete set of joint torques.