Linear Bellman combination for control of character animation

ABSTRACT

Controllers are necessary for physically-based synthesis of character animation. However, creating controllers requires either manual tuning or expensive computer optimization. We introduce linear Bellman combination as a method for reusing existing controllers. Given a set of controllers for related tasks, this combination creates a controller that performs a new task. It naturally weights the contribution of each component controller by its relevance to the current state and goal of the system. We demonstrate that linear Bellman combination outperforms naive combination often succeeding where naive combination fails. Furthermore, this combination is provably optimal for a new task if the component controllers are also optimal for related tasks. We demonstrate the applicability of linear Bellman combination to interactive character control of stepping motions and acrobatic maneuvers.

REFERENCES

• 1: Pieter Abbeel , Andrew Y. Ng, Apprenticeship learning via inverse reinforcement learning, Proceedings of the twenty-first international conference on Machine learning, p.1, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015430]
• 2: Atkeson, C. G., and Morimoto, J. 2002. Nonparametric representation of policies and value functions: A trajectory-based approach. In Advances in Neural Information Processing Systems (NIPS), vol. 15, 1611--1618.
• 3: Atkeson, C. G. 1994. Using local trajectory optimizers to speed up global optimization in dynamic programming. In Advances in Neural Information Processing Systems (NIPS), vol. 6, 663--670.
• 4: Jernej Barbič , Jovan Popović, Real-time control of physically based simulations using gentle forces, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008
• 5: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 6: Miklós Bergou , Saurabh Mathur , Max Wardetzky , Eitan Grinspun, TRACKS: toward directable thin shells, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 7: Dimitri P. Bertsekas, Dynamic Programming and Optimal Control, Vol. II, Athena Scientific, 2007
• 8: Lynne Shapiro Brotman , Arun N. Netravali, Motion interpolation by optimal control, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.309-315, June 1988
• 9: Burridge, R. R., Rizzi, A. A., and Koditschek, D. E. 1999. Sequential composition of dynamically desterous robot behaviours. International Journal of Robotics Research 18, 6, 534--555.
• 10: Stelian Coros , Philippe Beaudoin , Kang Kang Yin , Michiel van de Pann, Synthesis of constrained walking skills, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008
• 11: da Silva, M., Abe, Y., and Popović, J. 2008. Simulation of human motion data using short-horizon model-predictive control. Computer Graphics Forum 27, 2, 371--380.
• 12: Marco da Silva , Yeuhi Abe , Jovan Popović, Interactive simulation of stylized human locomotion, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 13: Erez, T., and Smart, W. 2007. Bipedal walking on rough terrain using manifold control. International Conference on Intelligent Robots and Systems (IROS), 1539--1544.
• 14: Petros Faloutsos , Michiel van de Panne , Demetri Terzopoulos, Composable controllers for physics-based character animation, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.251-260, August 2001 [doi>10.1145/383259.383287]
• 15: Raanan Fattal , Dani Lischinski, Target-driven smoke animation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 16: Fleming, W. H. 1978. Exit probabilities and optimal stochastic control. Applied Mathematics and Optimization 4, 329--346.
• 17: Jessica K. Hodgins , Nancy S. Pollard, Adapting simulated behaviors for new characters, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.153-162, August 1997 [doi>10.1145/258734.258822]
• 18: Jessica K. Hodgins , Wayne L. Wooten , David C. Brogan , James F. O'Brien, Animating human athletics, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.71-78, September 1995 [doi>10.1145/218380.218414]
• 19: Holland, C. 1977. A new energy characterization of the smallest eigenvalue fo the schrödinger equation. Communications on Pure and Applied Mathematics 30, 755--765.
• 20: Jacobson, D., and Mayne, D. 1970. Differential Dynamic Programming, 1st ed. Elsevier, New York.
• 21: Kappen, H. J. 2005. Linear theory for control of nonlinear stochastic systems. Physical Review Letters 95, 20, 200--204.
• 22: Joseph Laszlo , Michiel van de Panne , Eugene Fiume, Limit cycle control and its application to the animation of balancing and walking, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.155-162, August 1996 [doi>10.1145/237170.237231]
• 23: C. Karen Liu , Aaron Hertzmann , Zoran Popović, Learning physics-based motion style with nonlinear inverse optimization, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 24: James McCann , Nancy Pollard, Responsive characters from motion fragments, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 25: Antoine McNamara , Adrien Treuille , Zoran Popović , Jos Stam, Fluid control using the adjoint method, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 26: Milam, M. B. 2003. Real-Time Optimal Trajectory Generation for Constrained Dynamical Systems. PhD thesis, Caltech.
• 27: J. Thomas Ngo , Joe Marks, Spacetime constraints revisited, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.343-350, August 02-06, 1993, Anaheim, CA [doi>10.1145/166117.166160]
• 28: Bernt Oksendal, Stochastic differential equations (3rd ed.): an introduction with applications, Springer-Verlag New York, Inc., New York, NY, 1992
• 29: Pollard, N. S., and Behmaram-Mosavat, F. 2000. Force-based motion editing for locomotion tasks. In In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 663--669.
• 30: Zoran Popović , Andrew Witkin, Physically based motion transformation, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.11-20, July 1999 [doi>10.1145/311535.311536]
• 31: Alla Safonova , Jessica K. Hodgins , Nancy S. Pollard, Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 32: Kwang Won Sok , Manmyung Kim , Jehee Lee, Simulating biped behaviors from human motion data, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 33: Adnan Sulejmanpašić , Jovan Popović, Adaptation of performed ballistic motion, ACM Transactions on Graphics (TOG), v.24 n.1, p.165-179, January 2005 [doi>10.1145/1037957.1037966]
• 34: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 35: Tassa, Y., Erez, T., and Smart, W. 2008. Receding horizon differential dynamic programming. In Advances in Neural Information Processing Systems (NIPS), vol. 20, 1465--1472.
• 36: Todorov, E. 2006. Bayesian Brain: Probabilistic Approaches to Neural Coding. MIT Press, Cambridge, MA, ch. 12, 269--298.
• 37: Todorov, E. 2006. Linearly-solvable markov decision problems. Advances in Neural Information Processing Systems (NIPS) 19, 1369--1376.
• 38: Todorov, E. 2008. Efficient computation of optimal actions. http://www.cogsci.ucsd.edu/~todorov/papers/framework.pdf. Unpublished manuscript, March.
• 39: Todorov, E. 2009. Compositionality of optimal control laws. http://www.cogsci.ucsd.edu/~todorov/papers/primitives.pdf. Unpublished manuscript, January 15.
• 40: Adrien Treuille , Yongjoon Lee , Zoran Popović, Near-optimal character animation with continuous control, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 41: van de Panne, M., Kim, R., and Fiume, E. 1994. Synthesizing parameterized motions. In Eurographics Workshop on Simulation and Animation.
• 42: Andrew Witkin , Michael Kass, Spacetime constraints, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.159-168, June 1988
• 43: Wooten, W. L., and Hodgins, J. K. 2000. Simulating leaping, tumbling, landing and balancing humans. International Conference on Robotics and Automation (ICRA), 656--662.
• 44: KangKang Yin , Kevin Loken , Michiel van de Panne, SIMBICON: simple biped locomotion control, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 45: KangKang Yin , Stelian Coros , Philippe Beaudoin , Michiel van de Panne, Continuation methods for adapting simulated skills, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 46: Victor Brian Zordan , Jessica K. Hodgins, Motion capture-driven simulations that hit and react, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545276]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Control theory

Keywords:
optimal control, physically based animation