by Roy Featherstone
A new algorithm has been developed by the author for efficient calculation of the dynamics of rigid-body systems on a parallel computer. It achieves the theoretical minimum complexity, and it is applicable to most rigid-body systems.
The equations that describe the motions of rigid-body systems have been known for centuries, but efficient algorithms for evaluating those equations are a relatively recent invention. In the 1970s and 1980s, researchers in the robotics community developed a number of highly-efficient recursive algorithms to calculate the dynamics of robot mechanisms, treating them as rigid-body systems. Although the initial aim was to calculate robot dynamics, the new algorithms were applicable to rigid-body systems in general, and quickly found applications outside the robotics community.
These algorithms were originally intended to be run on a serial computer, and they are still today the best available algorithms for serial computation of rigid-body dynamics. However, the intrinsically-serial nature of their recursive computations has made it difficult to devise comparably efficient algorithms for parallel computers. In particular, algorithm designers have sought for many years the ‘holy grail’ of an algorithm that would run in O(log(n)) time on a computer with O(n) processors, n being the number of bodies in the system. The problem was first solved in 1995 by Fijany et al. for a restricted class of rigid-body systems; but there is now a new algorithm, developed by the author, that is applicable to a much larger class of systems and achieves the theoretical minimum possible complexity. It is also the fastest algorithm in many situations.
This new algorithm uses a divide-and-conquer paradigm, and its operation is illustrated in figure 1. Starting with a collection of individual rigid bodies (rectangles), the equation of motion of each body is evaluated. As each body is independent of the others at this stage, all of the equations can be evaluated in parallel. The next step is to connect them together in pairs, typically using joints (small circles) but other types of kinematic constraint can also be accomodated. This creates a collection of two-body subsystems. A special formula is used to evaluate the equations of motion of these subsystems from the equations already evaluated at the previous stage. Since these subsystems are still independent of each other, the evaluations can all be done in parallel. This process repeats until a subsystem is obtained that contains all of the bodies in the original rigid-body system, plus all of the inter-body connections except for the connections to a fixed reference body. These connections are added last, and the computation is complete.
The algorithm can be thought of as assembling the desired rigid-body system from its component parts, and the order of assembly is the ‘assembly tree’ shown in the figure. Roughly speaking, the execution time on a parallel computer is proportional to the depth of the tree, and the total number of computations is proportional to the number of nodes in the tree.
The new algorithm is appropriate whenever it is desired to calculate the dynamics of a large system of rigid bodies on a parallel computer that supports fine-grained divide-and-conquer algorithms. It can handle any system with tree connectivity and most systems with closed loops. The main exceptions are closed-loop systems with area-filling or volume-filling regular grid patterns of connectivity. Potential applications include redundant and hyperredundant robot mechanisms, multi-rigid-body approximations to elastic systems, complex mechanical devices, and rigid-body approximations of protein and polymer molecules. It has been tested on large kinematic trees, like the 1024-body fractal tree shown below, but not yet on closed-loop systems.
Links:
http://www.aber.ac.uk/~ryf/
Please contact:
Roy Featherstone - University of Wales,
Department of Computer Science
Tel: +44 1970 621688
E-mail: ryf@aber.ac.uk