Efficient parallel algorithms and VLSI architectures for manipulator Jacobian computation

The real-time computation of the Jacobian that relates the manipulator joint velocities to the linear and angular velocities of the manipulator end-effector is pursued. Since the Jacobian can be expressed in the form of a first-order linear recurrence, the time lower bound for computing the Jacobian can be proved to be of order O(N) on uniprocessor computers and of order O(log₂ N) on both single-instruction-stream-multiple-data-stream (SIMD) and VLSI pipelined parallel processors, where N is the number of links of the manipulator. To achieve the lower bound, the authors developed a generalized-k method for uniprocessor computers, a parallel forward and backward recursive doubling algorithm (PFABRD) for SIMD computers, and a parallel systolic architecture for VLSI pipelines. All the methods are capable of computing the Jacobian at any desired reference coordinate frame k from the base coordinate frame to the end-effector coordinate frame. The computational effort in terms of floating-point operations is minimal when k is in the range (4, N-3) for the generalized-k method, and k=(N+1)/2 for both the PFABRD algorithm and the parallel pipeline