Parallel O(log N) Algorithm for Dynamics Simulation of Humanoid Robots

This paper presents a new formulation the forward dynamics algorithm called assembly-disassembly algorithm (ADA) developed by the authors. The algorithm has the complexity of O(N) for serial computation and O(log N) for parallel computation on O(N) processors, which is comparable to the current fastet algorithms such as articulated-body algorithm (ABA) and divide-and-conquer algorithm (DCA), both proposed by Featherstone. However, it was difficult to figure out the essential differences of ADA and other two algorithms because they are based on different concepts. We reformulated ADA by applying the concept of articulated-body inertia (ABI) which is used in both ABA and DCA. The new formulation enables more rigorous comparison of the three algorithms and clarifies the difference of the underlying equations and efficiency. We also provide some implementation results including computation time, accuracy, and a simulation example