The commenter indicates that in the above-mentioned paper (see ibid., vol.5, no.5, p.569-82 (1989)) the proposed pipelined array architecture for the mixed-radix conversion problem is not as efficient and suitable for VLSI implementation as claimed. The commenter identifies the shortcomings of the design and then gives an efficient systolic/wavefront array that requires fewer hardware resources. The authors reply that this is another valid design for the mixed-radix conversion problem that avoids broadcasting; however, the triangular array of buffers is still required in the design for the data-format conversion, and this problem is not addressed. Since a semisystolic design was not given, the comparison between the original design and the semisystolic design in terms of buffers is premature.>

The authors present the design of a two-level macro-pipelined VLSI array architecture for the real-time computation of the exact solution of the manipulator pseudo-inverse Jacobian using the Decell algorithm in the residue arithmetic system. The first-level arrays are asynchronous data-driven, wave-front-like arrays and perform matrix multiplication, matrix diagonal addition, and trace computations in the Decel algorithm. A pool of the first-level arrays is then configured into a second-level macro-pipeline with outputs of one array acting as inputs to another array in the pipe. The pipelined time of the proposed two-level pipelined array architecture has a computational order of 0(n+2p-1), which is the same computational complexity order as that of the evaluation of a matrix product in an ordinary wavefront array. For a 12 degree-of-freedom redundant robot, a pipelined time of 6.975 mu s is achievable with current VLSI custom design technology.>

The use of residue arithmetic for the exact computation of the manipulator pseudoinverse Jacobian, to obviate the roundoff errors normally associated with the computations, is considered. A two-level macropipelined residue arithmetic array architecture implementing Decell's pseudoinverse algorithm has been developed to overcome the ill-conditioned problem of the pseudoinverse computation. The Decell algorithm is suitable for VLSI array implementation to achieve the real-time computation requirement. The first-level arrays are data-driven, wavefront-like arrays and perform the matrix multiplications, matrix diagonal additions, and trace computations. A pool of the first-level arrays are configured into a second-level macro-pipeline with outputs of one array acting as inputs to another array in the pipe. The proposed architecture can calculate the pseudoinverse Jacobian with a pipelined time in the same computational complexity order as evaluating a matrix product in a wavefront array.>

Two efficient parallel algorithms for computing the forward dynamics for real-time simulation were developed for implementation on a single-instruction multiple-data-stream (SIMD) computer with n processors, where n is the number of degrees of freedom of the manipulator. The first parallel algorithm, based on the composite rigid-body method, generates the inertia matrix using the parallel Newton-Euler algorithm, the parallel linear recurrence algorithm, and the modified row-sweep algorithm, and then inverts the inertia matrix to obtain the joint acceleration vector at time t. The time complexity of this parallel algorithm is of the order O(n/sup 2/) with O(n) processors. The second parallel algorithm, based on the conjugate gradient method, computes the joint acceleration with a time complexity of O(n) for multiplication operation and O(n log/sub 2/n) for addition operation. The interprocessor communication problem for the implementation of the proposed parallel algorithms on SIMD machines is also discussed and analyzed.>

Computing the robot forward dynamics is important for real-time computer simulation of robot arm motion. Two efficient parallel algorithms for computing the forward dynamics for robot arm simulation were developed to be implemented on an SIMD computer with n processors, where n is the number of degrees-of-freedom of the manipulator. The first parallel algorithm, based on the Composite Rigid-Body method, generates the inertia matrix using the parallel Newton-Euler algorithm, the parallel linear recurrence algorithm, and the row-sweep algorithm, and then inverts the inertia matrix to obtain the joint acceleration vector desired at time t. The second parallel algorithm, based on the conjugate gradient method, computes the joint accelerations with a time complexity of O(n) for multiplication operation and O(nlogn) for addition operation. The proposed parallel computation results are compared with the existing methods.

A cost-effective coordinate rotation digital computer (CORDIC) architecture is described for the computation of inverse kinematic position solution based on a functional decomposition of the closed-form joint equations. The functional decomposition shows a limited amount of parallelism with a large amount of sequentialism in the flow of computation and data dependencies and reveals the requirement for computing a large set of elementary operations: multiplications, additions, divisions, square roots, trigonometric functions and their inverse. However, these elementary operations, in general, cannot be efficiently computed in general-purpose uniprocessor computers. The CORDIC algorithms are the natural candidates for efficiently computing these elementary operations and the interconnection of these CORDIC processors to exploit the great potential of pipelining provides a better solution for computing the inverse kinematic position solution. The functional decomposition of the inverse kinematic position solution into a set of computational tasks can be represented as a directed task graph. The inclusion of input data modifies the task graph to an acyclic data dependency graph (ADDG). The nodes of the ADDG correspond to the computational modules, each of which can be realized by a CORDIC processor. The operands or data move along the edges, each of which connects a pair of nodes. Due to different paths and computation time for each CORDIC processor, operands may arrive at multi-input modules at different arrival time, causing a longer pipelined time. Delay buffers may be inserted at various paths to achieve a balanced ADDG. The optimal buffer assignment problem is reduced to an integer linear optimization problem which can be solved easily by computers. The realization of the balanced ADDG results in a maximum pipelined CORDIC architecture with a minimum number of delay buffer stages for the computation of inverse kinematic position solution.

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(k1[n/p] + k2[log2p]), where k1and k2are 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([log2n]) [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.

It is shown that the time lower bound of computing the inverse dynamics of an n-link robot manipulator parallelly using p processors is O(k1 [n/p] + k2 [log<2 p]), where k1 and k2 are constants. A novel parallel algorithm for computing the inverse dynamics using the Newton-Euler equations of motion was developed to be implemented on a single-instruction-stream multiple-data-stream 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([log2 n]), whidc 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 per complete set of joint torques.

A method is developed for planning the point-to-point path that the manipulator may adopt to minimize a specified performance index, under the realistic physical constraints on Joint torques, accelerations, velocities and position limits. The purpose of such path planning is either to provide the best input for the manipulator controller or to evaluate the arm performance for various designs. Because there is no analytic function available for describing the optimum path, cubic spline functions are proposed for an approximation. For a selected number of polynomial segments, the flexible polyhedron search is used to search for the optimum path arrangement. During the search period, it is often necessary to convert an infeasible arrangement into a feasible one. Methods for these required conversions have been studied. The number of concatenated polynomials is increased until there is no significant improvement on the approximation. Computer programs have been written to implement the algorithm.

Methods of joint trajectory generation for mechanical manipulators usingX-spline and quartic spline functions are presented. A sequence of Cartesian knots, i.e. positions and orientations of the hand, are selected from the desired Cartesian path. Joint values corresponding to these selected knots are solved from the kinematic equation. Approximate joint paths are constructed by interpolating these joint positions. At any instant, two or more future knots need to be known in advance in order to determine the current joint trajectories. Approximate errors for Cartesian paths are discussed. An illustrative example is used for comparing these trajectories to other existent polynomial-type trajectories.