A comparative study of search and optimization algorithms for the automatic control of physically realistic 2-D animated figures

Abstract

In the Spacetime Constraints paradigm of animation, the animator specifies what a character should do, and the details of the motion are generated automatically by the computer. Ngo and Marks [11, 12] recently proposed a technique of automatic motion synthesis that uses a massively parallel genetic algorithm to search a space of motion controllers that generate physically realistic motions for 2D articulated figures. In this paper, we describe an empirical study of evolutionary computation algorithms and standard function optimization algorithms that were implemented in lieu of the massively parallel GA in order to find a substantially more efficient search algorithm that would be viable on serial workstations. We discovered that simple search algorithms based on the evolutionary programming paradigm were most efficient in searching the space of motion controllers.