“Spacetime constraints revisited” by Ngo and Marks

The Spacetime Constraints (SC) paradigm, whereby the animator
specifies what an animated figure should do but not how to do it, is
a very appealing approach to animation. However, the algorithms
available for realizing the SC approach are limited. Current techniques are local in nature: they all use some kind of perturbational
analysis to refine an initial trajectory. We propose a global search
algorithm that is capable of generating multiple novel trajectories
for SC problems from scratch. The key elements of our search
strategy are a method for encoding trajectories as behaviors, and a
genetic search algorithm for choosing behavior parameters that is
currently implemented on a massively parallel computer. We describe the algorithm and show computed solutions to SC problems
for 2D articulated figures.

1. D. Baraff. Coping with friction for non-penetrating rigid body simulation. Computer Graphics, 25(4):31-40, July 1991.
2. L. S. Brotman and A. N. Netravali. Motion interpolation by optimal control. Computer Graphics, 22(4):309-315, August 1988.
3. M. F. Cohen. Interactive spacetime control for animation. Computer Graphics, 26(2):293-302, July 1992.
4. Y. Davidor. A genetic algorithm applied to robot trajectory generation. In L. Davis, editor, Handbook of Genetic Algorithms, chapter 12, pages 144-165. Van Nostrand Reinhold, New York, 1991.
5. L. Davis. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, 1991.
6. H. de Garis. Genetic programming: Building artificial nervous systems using genetically programmed neural network modules. In Proceedings of the Seventh International Conference on Machine Learning, pages 132-139, Austin, Texas, June 1990.
7. K. A. De Jong. An Analysis of the Behavior of a Class of Genetic Algorithms. PhD thesis, University of Michigan, 1975.
8. D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, Massachusetts, 1988.
9. J. K. Hahn. Realistic animation of rigid bodies. Computer Graphics, 22(4):299-308, August 1988.
10. J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.
11. J. Luh, M. Walker, and R. Paul. On-line computational scheme for mechanical manipulators. Trans. ASME, J. Dynamic Systems, Measurement, and Control, 102:69-76, 1980.
12. P. Maes and R. A. Brooks. Learning to coordinate behaviors. In Proceedings of the Eighth National Conference on Artificial Intelligence, pages 796-802, Menlo Park, California, 1990. American Association for Artificial Intelligence.
13. J. T. Ngo and J. Marks. Physically realistic trajectory planning in animation: A stimulus-response approach. Technical Report TR-21-92, Center for Research in Computing Technology, Harvard University, October 1992.
14. B. F. Skinner. The Behavior of Organisms; An Experimental Analysis. The Century Psychology Series. D. Appleton- Century, New York, London, 1938.
15. G. Syswerda. Uniform crossover in genetic algorithms. Proceedings of the Third International Conference on Genetic Algorithms, pages 2-9, 1989.
16. J. Wilhelms and R. Skinner. A “notion” for interactive behavioral animation control. IEEE Computer Graphics and Applications, 10(3):14-22, May 1990.
17. A. Witkin and M. Kass. Spacetime constraints. Computer Graphics, 22(4): 159-168, August 1988.