“Online motion synthesis using sequential Monte Carlo” by Hämäläinen, Eriksson, Tanskanen, Kyrki and Lehtinen

  • ©Perttu Hämäläinen, Sebastian Eriksson, Esa Tanskanen, Ville Kyrki, and Jaakko Lehtinen



Session Title:

    Controlling Character


    Online motion synthesis using sequential Monte Carlo




    We present a Model-Predictive Control (MPC) system for online synthesis of interactive and physically valid character motion. Our system enables a complex (36-DOF) 3D human character model to balance in a given pose, dodge projectiles, and improvise a get up strategy if forced to lose balance, all in a dynamic and unpredictable environment. Such contact-rich, predictive and reactive motions have previously only been generated offline or using a handcrafted state machine or a dataset of reference motions, which our system does not require.For each animation frame, our system generates trajectories of character control parameters for the near future — a few seconds — using Sequential Monte Carlo sampling. Our main technical contribution is a multimodal, tree-based sampler that simultaneously explores multiple different near-term control strategies represented as parameter splines. The strategies represented by each sample are evaluated in parallel using a causal physics engine. The best strategy, as determined by an objective function measuring goal achievement, fluidity of motion, etc., is used as the control signal for the current frame, but maintaining multiple hypotheses is crucial for adapting to dynamically changing environments.


    1. Al Borno, M., de Lasa, M., and Hertzmann, A. 2013. Trajectory optimization for full-body movements with complex contacts. IEEE Transactions on Visualization and Computer Graphics 19, 8, 1405–1414. Google ScholarDigital Library
    2. Arulampalam, M., Maskell, S., Gordon, N., and Clapp, T. 2002. A tutorial on particle filters for online nonlinear/non-gaussian bayesian tracking. IEEE Transactions on Signal Processing 50, 2, 174–188. Google ScholarDigital Library
    3. Cohen, M. F. 1992. Interactive spacetime control for animation. In Proc. SIGGRAPH ’92, ACM, New York, NY, USA, 293–302. Google ScholarDigital Library
    4. 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
    5. da Silva, M., Durand, F., and Popović, J. 2009. Linear bellman combination for control of character animation. In Proc. SIGGRAPH 2009, ACM, New York, NY, USA, 82:1–82:10. Google ScholarDigital Library
    6. de Villiers, J. P., Godsill, S. J., and Singh, S. S. 2011. Particle predictive control. Journal of Statistical Planning and Inference 141, 5 (May), 1753–1763.Google ScholarCross Ref
    7. Deutscher, J., Blake, A., and Reid, I. 2000. Articulated body motion capture by annealed particle filtering. In IEEE Conference on Computer Vision and Pattern Recognition, 2000. Proceedings, vol. 2, 126–133 vol. 2.Google Scholar
    8. Doucet, A., and Johansen, A. M. 2009. A tutorial on particle filtering and smoothing: Fifteen years later. Handbook of Nonlinear Filtering 12, 656–704.Google Scholar
    9. Erez, T., Lowrey, K., Tassa, Y., Kumar, V., Kolev, S., and Todorov, E. 2013. An integrated system for real-time model-predictive control of humanoid robots. In Proc. IEEE/RAS International Conference on Humanoid Robots (HUMANOIDS), HUMANOIDS.Google Scholar
    10. Fang, A. C., and Pollard, N. S. 2003. Efficient synthesis of physically valid human motion. ACM Trans. Graph. 22, 3, 417–426. Google ScholarDigital Library
    11. Geijtenbeek, T., Pronost, N., Egges, A., and Overmars, M. H. 2011. Interactive character animation using simulated physics. Eurographics-State of the Art Reports 2.Google Scholar
    12. Geijtenbeek, T., van de Panne, M., and van der Stappen, A. F. 2013. Flexible muscle-based locomotion for bipedal creatures. ACM Trans. Graph. 32, 6 (Nov.), 206:1–206:11. Google ScholarDigital Library
    13. Heck, R., and Gleicher, M. 2007. Parametric motion graphs. In Proceedings of the 2007 symposium on Interactive 3D graphics and games, ACM, New York, NY, USA, I3D ’07, 129–136. Google ScholarDigital Library
    14. Hämäläinen, P., Aila, T., Takala, T., and Alander, J. 2006. Mutated kd-tree importance sampling. In Proc. SCAI 2006, 39–45.Google Scholar
    15. Ihler, A. T., Sudderth, E. B., Freeman, W. T., and Willsky, A. S. 2003. Efficient multiscale sampling from products of gaussian mixtures. Advances in Neural Information Processing Systems 16, 1–8.Google Scholar
    16. Jain, S., Ye, Y., and Liu, C. K. 2009. Optimization-based interactive motion synthesis. ACM Trans. Graph. 28, 1 (Feb.), 10:1–10:12. Google ScholarDigital Library
    17. Kajiya, J. T. 1986. The rendering equation. In Proc. SIGGRAPH ’86, ACM, New York, NY, USA, 143–150. Google ScholarDigital Library
    18. Kantas, N., Maciejowski, J. M., and Lecchini-Visintini, A. 2009. Sequential monte carlo for model predictive control. In Nonlinear Model Predictive Control, L. Magni, D. M. Raimondo, and F. Allgöwer, Eds., no. 384 in Lecture Notes in Control and Information Sciences. Springer Berlin Heidelberg, Jan., 263–273.Google Scholar
    19. Lasseter, J. 1987. Principles of traditional animation applied to 3D computer animation. In Proc. SIGGRAPH ’87, ACM, New York, NY, USA, 35–44. Google ScholarDigital Library
    20. Liu, L., Yin, K., van de Panne, M., Shao, T., and Xu, W. 2010. Sampling-based contact-rich motion control. ACM Trans. Graph. 29, 4, 128:1–128:10. Google ScholarDigital Library
    21. Mordatch, I., Todorov, E., and Popović, Z. 2012. Discovery of complex behaviors through contact-invariant optimization. ACM Trans. Graph. 31, 4 (July), 43:1–43:8. Google ScholarDigital Library
    22. Muico, U., Lee, Y., Popović, J., and Popović, Z. 2009. Contact-aware nonlinear control of dynamic characters. ACM Trans. Graph. 28, 3, 81:1–81:9. Google ScholarDigital Library
    23. Muja, M., and Lowe, D. G. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. In Proc. VISAPP (1), 331–340.Google Scholar
    24. Ngo, J. T., and Marks, J. 1993. Spacetime constraints revisited. In Proc. SIGGRAPH ’93, ACM, New York, NY, USA, 343–350. Google ScholarDigital Library
    25. Pejsa, T., and Pandzic, I. 2010. State of the art in example-based motion synthesis for virtual characters in interactive applications. Computer Graphics Forum 29, 1, 202–226.Google ScholarCross Ref
    26. Reil, T., and Husbands, P. 2002. Evolution of central pattern generators for bipedal walking in a real-time physics environment. IEEE Transactions on Evolutionary Computation 6, 2, 159–168. Google ScholarDigital Library
    27. Rudoy, D., and Wolfe, P. 2006. Monte carlo methods for multimodal distributions. In Proc. Fortieth Asilomar Conference on Signals, Systems and Computers, 2006. ACSSC ’06, 2019–2023.Google Scholar
    28. Safonova, A., Hodgins, J. K., and Pollard, N. S. 2004. Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces. ACM Trans. Graph. 23, 3, 514–521. Google ScholarDigital Library
    29. Schmidt, J., Fritsch, J., and Kwolek, B. 2006. Kernel particle filter for real-time 3D body tracking in monocular color images. In Proc. 7th International Conference on Automatic Face and Gesture Recognition, 2006. FGR 2006, 567–572. Google ScholarDigital Library
    30. Sims, K. 1994. Evolving virtual creatures. In Proc. SIGGRAPH ’94, ACM, New York, NY, USA, 15–22. Google ScholarDigital Library
    31. Stahl, D., and Hauth, J. 2011. PF-MPC: particle filter-model predictive control. Syst Control Lett 60, 8, 632–643.Google ScholarCross Ref
    32. Tassa, Y., Erez, T., and Todorov, E. 2012. Synthesis and stabilization of complex behaviors through online trajectory optimization. In Proc. 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE, IROS’12, 4906–4913.Google Scholar
    33. Thrun, S., Fox, D., and Burgard, W. 2000. Monte carlo localization with mixture proposal distribution. In Proc. AAAI/IAAI, 859–865. Google ScholarDigital Library
    34. Van Welbergen, H., Van Basten, B. J. H., Egges, A., Ruttkay, Z. M., and Overmars, M. H. 2010. Real time animation of virtual humans: A trade-off between naturalness and control. Computer Graphics Forum 29, 8, 2530–2554.Google ScholarCross Ref
    35. Wampler, K., and Popović, Z. 2009. Optimal gait and form for animal locomotion. In ACM Trans. Graph., vol. 28, 60. Google ScholarDigital Library
    36. Witkin, A., and Kass, M. 1988. Spacetime constraints. In Proc. SIGGRAPH ’88, ACM, New York, NY, USA, 159–168. Google ScholarDigital Library

ACM Digital Library Publication: