Bio IK: A Memetic Evolutionary Algorithm for Generic Multi-Objective Inverse Kinematics

Abstract

Inverse kinematics constitutes an essential task for control of motion, manipulation as well as interaction in robotics and animation. In this thesis, a novel efficient algorithm Bio IK is presented for solving complex kinematic body postures on generic and fully-constrained geometries with multiple joint chains and objectives. It is based on memetic evolution, combining biologically-inspired evolutionary and swarm optimisation with the gradient-based L-BFGS-B algorithm. This aims to combine the characteristic strengths of different optimisation methodologies. Accurate solutions both for position and orientation can be found in real-time while robustly avoiding suboptimal extrema as well as singularity issues, and scaling well even for greatly higher degree of freedom.

The algorithm provides high flexibility for the design of custom cost functions, which can be used for concrete specifications of desired body postures both in joint and Cartesian space. In particular, the ability to arbitrarily combine different objectives extends traditional inverse kinematics by handling multiple end effectors simultaneously while further allowing intermediate goals along the chains, such as an elbow position or wrist orientation while grasping. Additionally, task-specific objectives such as minimal displacement between solutions, prioritised joint values, functional joint dependencies, as well as real-time collision avoidance can directly be integrated into the optimisation. The algorithm represents a general method for bounded continuous optimisation, and only requires two parameters to be set for the population size and number of elite individuals. It adaptively handles varying dimensionality as well as dynamic exploitation and exploration. The beauty of this method lies in the ability to minimise the same objective function both by the evolutionary and local search.

Experiments were conducted on several industrial and humanoid robot models as well as virtual characters in order to demonstrate its applicability for different challenging tasks in robotics, human-robot interaction and character animation. Those include dexterous object manipulation with anthropomorphic robotic hands, full-body motion, modeling and teleoperation in virtual reality, collision-free trajectory generation, as well as animation post-processing for video games and films. The results show that the proposed algorithm can compete with popular state-of-the-art methods for inverse kinematics in terms of speed and robustness, and is further able to outperform them in flexibility and scalability. In particular, it has already gained popularity and active usage through dissemination of available implementations. The algorithm can contribute to solving more complex tasks and kinematic structures, which is of high interest for current research problems in robotics and animation.