“Linear Bellman combination for control of character animation” by da Silva, Durand and Popović

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.

1. Abbeel, P., and Ng, A. Y. 2004. Apprenticeship learning via inverse reinforcement learning. In International Conference on Machine learning (ICML), ACM, vol. 69, 1:1–1:8. Google ScholarDigital Library
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.Google Scholar
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.Google Scholar
4. Barbič, J., and Popović, J. 2008. Real-time control of physically based simulations using gentle forces. ACM Transactions on Graphics 27, 5, 163:1–163:10. Google ScholarDigital Library
5. Bellman, R. E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ. Google ScholarDigital Library
6. Bergou, M., Mathur, S., Wardetzky, M., and Grinspun, E. 2007. Tracks: toward directable thin shells. ACM Transactions on Graphics 26, 3, 50:1–50:10. Google ScholarDigital Library
7. Bertsekas, D. P. 2007. Dynamic Programming and Optimal Control, 3 ed., vol. I. Athena Scientific, Nashua, NH. Google ScholarDigital Library
8. Brotman, L. S., and Netravali, A. N. 1988. Motion interpolation by optimal control. In Computer Graphics (Proceedings of SIGGRAPH 88), 309–315. Google ScholarDigital Library
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.Google ScholarCross Ref
10. Coros, S., Beaudoin, P., Yin, K., and van de Panne, M. 2008. Synthesis of constrained walking skills. ACM Transactions on Graphics 27, 5, 113:1–113:9. Google ScholarDigital Library
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.Google ScholarCross Ref
12. da Silva, M., Abe, Y., and Popović, J. 2008. Interactive simulation of stylized human locomotion. ACM Transactions on Graphics 27, 3, 82:1–82:10. Google ScholarDigital Library
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.Google Scholar
14. Faloutsos, P., van de Panne, M., and Terzopoulos, D. 2001. Composable controllers for physics-based character animation. In Proceedings of ACM SIGGRAPH 2001, Annual Conference Series, 251–260. Google ScholarDigital Library
15. Fattal, R., and Lischinski, D. 2004. Target-driven smoke animation. ACM Transactions on Graphics 23, 3, 441–448. Google ScholarDigital Library
16. Fleming, W. H. 1978. Exit probabilities and optimal stochastic control. Applied Mathematics and Optimization 4, 329–346.Google ScholarDigital Library
17. Hodgins, J. K., and Pollard, N. S. 1997. Adapting simulated behaviors for new characters. In Proceedings of SIGGRAPH 97, Annual Conference Series, 153–162. Google ScholarDigital Library
18. Hodgins, J. K., Wooten, W. L., Brogan, D. C., and O’Brien, J. F. 1995. Animating human athletics. In Proceedings of ACM SIGGRAPH 95, Annual Conference Series, 71–78. Google ScholarDigital Library
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.Google ScholarCross Ref
20. Jacobson, D., and Mayne, D. 1970. Differential Dynamic Programming, 1st ed. Elsevier, New York.Google Scholar
21. Kappen, H. J. 2005. Linear theory for control of nonlinear stochastic systems. Physical Review Letters 95, 20, 200–204.Google ScholarCross Ref
22. Laszlo, J. F., van de Panne, M., and Fiume, E. L. 1996. Limit cycle control and its application to the animation of balancing and walking. In Proceedings of SIGGRAPH 96, Annual Conference Series, 155–162. Google ScholarDigital Library
23. Liu, C. K., Hertzmann, A., and Popović, Z. 2005. Learning physics-based motion style with nonlinear inverse optimization. ACM Transactions on Graphics 24, 3, 1071–1081. Google ScholarDigital Library
24. McCann, J., and Pollard, N. 2007. Responsive characters from motion fragments. ACM Transactions on Graphics 26, 3, 6:1–6:7. Google ScholarDigital Library
25. McNamara, A., Treuille, A., Popović, Z., and Stam, J. 2004. Fluid control using the adjoint method. ACM Transactions on Graphics 23, 3, 449–456. Google ScholarDigital Library
26. Milam, M. B. 2003. Real-Time Optimal Trajectory Generation for Constrained Dynamical Systems. PhD thesis, Caltech.Google Scholar
27. Ngo, J. T., and Marks, J. 1993. Spacetime constraints revisited. In Proceedings of ACM SIGGRAPH 2000, Annual Conference Series, 343–350. Google ScholarDigital Library
28. Oksendal, B. K. 2002. Stochastic Differential Equations: An Introduction with Applications. Springer, New York, NY. Google ScholarDigital Library
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.Google Scholar
30. Popović, Z., and Witkin, A. P. 1999. Physically based motion transformation. In Computer Graphics (Proceedings of SIGGRAPH 99), ACM SIGGRAPH, Annual Conference Series, 11–20. Google ScholarDigital Library
31. Safonova, A., Hodgins, J., and Pollard, N. 2004. Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces. ACM Transactions on Graphics 23, 3, 514–521. Google ScholarDigital Library
32. Sok, K. W., Kim, M., and Lee, J. 2007. Simulating biped behaviors from human motion data. ACM Transactions on Graphics 26, 3, 107:1–107:9. Google ScholarDigital Library
33. Sulejmanpasić, A., and Popović, J. 2005. Adaptation of performed ballistic motion. ACM Transactions on Graphics 24, 1, 165–179. Google ScholarDigital Library
34. Sutton, R. S., and Barto, A. G. 1998. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA. Google ScholarDigital Library
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.Google Scholar
36. Todorov, E. 2006. Bayesian Brain: Probabilistic Approaches to Neural Coding. MIT Press, Cambridge, MA, ch. 12, 269–298.Google Scholar
37. Todorov, E. 2006. Linearly-solvable markov decision problems. Advances in Neural Information Processing Systems (NIPS) 19, 1369–1376.Google Scholar
38. Todorov, E. 2008. Efficient computation of optimal actions. http://www.cogsci.ucsd.edu/~todorov/papers/framework.pdf. Unpublished manuscript, March.Google Scholar
39. Todorov, E. 2009. Compositionality of optimal control laws. http://www.cogsci.ucsd.edu/~todorov/papers/primitives.pdf. Unpublished manuscript, January 15.Google Scholar
40. Treuille, A., Lee, Y., and Popović, Z. 2007. Near-optimal character animation with continuous control. ACM Transactions on Graphics 26, 3, 7:1–7:7. Google ScholarDigital Library
41. van de Panne, M., Kim, R., and Fiume, E. 1994. Synthesizing parameterized motions. In Eurographics Workshop on Simulation and Animation.Google Scholar
42. Witkin, A., and Kass, M. 1988. Spacetime constraints. In Computer Graphics (Proceedings of SIGGRAPH 88), vol. 22, 159–168. Google ScholarDigital Library
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.Google Scholar
44. Yin, K., Loken, K., and van de Panne, M. 2007. SIMBICON: Simple biped locomotion control. ACM Transactions on Graphics 26, 3, 105:1–105:10. Google ScholarDigital Library
45. Yin, K., Coros, S., Beaudoin, P., and van de Panne, M. 2008. Continuation methods for adapting simulated skills. ACM Transactions on Graphics 27, 3, 81:1–81:7. Google ScholarDigital Library
46. Zordan, V. B., and Hodgins, J. K. 2002. Motion capture-driven simulations that hit and react. In Symposium on Computer Animation (SCA), 89–96. Google ScholarDigital Library