Inverse Kinematic Solutions for Articulated Characters using Massively Parallel Architectures and Differential Evolutionary Algorithms

Abstract

This paper presents a Differential Evolutionary (DE) algorithm for solving multi-objective kinematic problems (e.g., end-effector locations, centre-of-mass and comfort factors). Inverse kinematic problems in the context of character animation systems are one of the most challenging and important conundrums. The problems depend upon multiple geometric factors in addition to cosmetic and physical aspects. Further complications stem from the fact that there may be non or an infinite number of solutions to the problem (especially for highly redundant manipulator structures, such as, articulated characters). What is more, the problem is global and tightly coupled so small changes to individual link's impacts the overall solution. Our method focuses on generating approximate solutions for a range of inverse kinematic problems (for instance, positions, orientations and physical factors, like overall centre-of-mass location) using a Differential Evolutionary algorithm. The algorithm is flexible enough that it can be applied to a range of open ended problems including highly non-linear discontinuous systems with prioritisation. Importantly, evolutionary algorithms are typically renowned for taking considerable time to find a solution. We help reduce this burden by modifying the algorithm to run on a massively parallel architecture (like the GPU) using a CUDA-based framework. The computational model is evaluated using a variety of test cases to demonstrate the techniques viability (speed and ability to solve multi-objective problems). The modified parallel evolutionary solution helps reduce execution times compared to the serial DE, while also obtaining a solution within a specified margin of error (<1%).