research-article

Online motion synthesis using sequential Monte Carlo

Authors:

Perttu Hämäläinen,

Sebastian Eriksson,

Jaakko LehtinenAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 33, Issue 4

Article No.: 51, Pages 1 - 12

https://doi.org/10.1145/2601097.2601218

Published: 27 July 2014 Publication History

Abstract

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.

Supplementary Material

ZIP File (a51-hamalainen.zip)

Supplemental material.

Download
99.94 MB

References

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

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

Digital Library

[3]

Cohen, M. F. 1992. Interactive spacetime control for animation. In Proc. SIGGRAPH '92, ACM, New York, NY, USA, 293--302.

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

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

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

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

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

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

[10]

Fang, A. C., and Pollard, N. S. 2003. Efficient synthesis of physically valid human motion. ACM Trans. Graph. 22, 3, 417--426.

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

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

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

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

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

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

Digital Library

[17]

Kajiya, J. T. 1986. The rendering equation. In Proc. SIGGRAPH '86, ACM, New York, NY, USA, 143--150.

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

[19]

Lasseter, J. 1987. Principles of traditional animation applied to 3D computer animation. In Proc. SIGGRAPH '87, ACM, New York, NY, USA, 35--44.

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

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

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

Digital Library

[23]

Muja, M., and Lowe, D. G. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. In Proc. VISAPP (1), 331--340.

[24]

Ngo, J. T., and Marks, J. 1993. Spacetime constraints revisited. In Proc. SIGGRAPH '93, ACM, New York, NY, USA, 343--350.

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

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

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

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

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

Digital Library

[30]

Sims, K. 1994. Evolving virtual creatures. In Proc. SIGGRAPH '94, ACM, New York, NY, USA, 15--22.

Digital Library

[31]

Stahl, D., and Hauth, J. 2011. PF-MPC: particle filter-model predictive control. Syst Control Lett 60, 8, 632--643.

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

[33]

Thrun, S., Fox, D., and Burgard, W. 2000. Monte carlo localization with mixture proposal distribution. In Proc. AAAI/IAAI, 859--865.

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

[35]

Wampler, K., and Popović, Z. 2009. Optimal gait and form for animal locomotion. In ACM Trans. Graph., vol. 28, 60.

Digital Library

[36]

Witkin, A., and Kass, M. 1988. Spacetime constraints. In Proc. SIGGRAPH '88, ACM, New York, NY, USA, 159--168.

Digital Library

Cited By

Kujanpää KBabadi AZhao YKannala JIlin APajarinen JDastani MSichman JAlechina NDignum V(2024)Continuous Monte Carlo Graph SearchProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662960(1047-1056)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662960
Khoshsiyar NGou RZhou TAndrews Svan de Panne M(2024)PartwiseMPC: Interactive Control of Contact‐Guided MotionsComputer Graphics Forum10.1111/cgf.15174Online publication date: 9-Oct-2024
https://doi.org/10.1111/cgf.15174
Hu BGuo HYang YTao XHe J(2024)Lightweight Physics-Based Character for Generating Sensible Postures in Dynamic EnvironmentsIEEE Access10.1109/ACCESS.2024.341722012(89660-89678)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3417220
Show More Cited By

Index Terms

Online motion synthesis using sequential Monte Carlo
1. Computing methodologies
  1. Computer graphics
    1. Animation

Recommendations

Motion capture assisted animation: texturing and synthesis
SIGGRAPH '02: Proceedings of the 29th annual conference on Computer graphics and interactive techniques

We discuss a method for creating animations that allows the animator to sketch an animation by setting a small number of keyframes on a fraction of the possible degrees of freedom. Motion capture data is then used to enhance the animation. Detail is ...
Motion synthesis from annotations

This paper describes a framework that allows a user to synthesize human motion while retaining control of its qualitative properties. The user paints a timeline with annotations --- like walk, run or jump --- from a vocabulary which is freely chosen by ...
Motion capture assisted animation: texturing and synthesis

We discuss a method for creating animations that allows the animator to sketch an animation by setting a small number of keyframes on a fraction of the possible degrees of freedom. Motion capture data is then used to enhance the animation. Detail is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 33, Issue 4

July 2014

1366 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2601097

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 July 2014

Published in TOG Volume 33, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
790
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kujanpää KBabadi AZhao YKannala JIlin APajarinen JDastani MSichman JAlechina NDignum V(2024)Continuous Monte Carlo Graph SearchProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662960(1047-1056)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662960
Khoshsiyar NGou RZhou TAndrews Svan de Panne M(2024)PartwiseMPC: Interactive Control of Contact‐Guided MotionsComputer Graphics Forum10.1111/cgf.15174Online publication date: 9-Oct-2024
https://doi.org/10.1111/cgf.15174
Hu BGuo HYang YTao XHe J(2024)Lightweight Physics-Based Character for Generating Sensible Postures in Dynamic EnvironmentsIEEE Access10.1109/ACCESS.2024.341722012(89660-89678)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3417220
Klar MFischer FFleig ABachinski MMüller J(2023)Simulating Interaction Movements via Model Predictive ControlACM Transactions on Computer-Human Interaction10.1145/357701630:3(1-50)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1145/3577016
Kim NKirjonen MHämäläinen P(2022)Learning High-Risk High-Precision Motion ControlProceedings of the 15th ACM SIGGRAPH Conference on Motion, Interaction and Games10.1145/3561975.3562943(1-10)Online publication date: 3-Nov-2022
https://dl.acm.org/doi/10.1145/3561975.3562943
Xie ZStarke SLing Hvan de Panne M(2022)Learning Soccer Juggling Skills with Layer-wise Mixture-of-ExpertsACM SIGGRAPH 2022 Conference Proceedings10.1145/3528233.3530735(1-9)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.1145/3528233.3530735
Tao TWilson MGou Rvan de Panne M(2022)Learning to Get UpACM SIGGRAPH 2022 Conference Proceedings10.1145/3528233.3530697(1-10)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.1145/3528233.3530697
Kwiatkowski AAlvarado EKalogeiton VLiu CPettré Jvan de Panne MCani M(2022)A Survey on Reinforcement Learning Methods in Character AnimationComputer Graphics Forum10.1111/cgf.1450441:2(613-639)Online publication date: 24-May-2022
https://doi.org/10.1111/cgf.14504
Babadi Avan de Panne MLiu CHamalainen P(2022)Learning Task-Agnostic Action Spaces for Movement OptimizationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.310009528:12(4700-4712)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TVCG.2021.3100095
Hamalainen PToikka JBabadi ALiu C(2022)Visualizing Movement Control Optimization LandscapesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2020.301818728:3(1648-1660)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TVCG.2020.3018187
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents