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

  • ©Marco da Silva, Frédo Durand, and Jovan Popović

Conference:


Type:


Title:

    Linear Bellman combination for control of character animation

Presenter(s)/Author(s):



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. 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


ACM Digital Library Publication:



Overview Page: