“Multi-Contact Locomotion Using a Contact Graph with Feasibility Predictors”

  • ©Jessica K. Hodgins and Taesoo Kwon




    Multi-Contact Locomotion Using a Contact Graph with Feasibility Predictors

Session/Category Title: Human Motion




    Multi-contact locomotion that uses both the hands and feet in a complex environment remains a challenging problem in computer animation. To address this problem, we present a contact graph, which is a motion graph augmented by learned feasibility predictors, namely contact spaces and an occupancy estimator, for a motion clip in each graph node. By estimating the feasibilities of candidate contact points that can be reached by modifying a motion clip, the predictors allow us to find contact points that are likely to be valid and natural before attempting to generate the actual motion for the contact points. The contact graph thus enables the efficient generation of multi-contact motion in two steps: planning contact points to the goal and then generating the whole-body motion. We demonstrate the effectiveness of our method by creating several climbing motions in complex and cluttered environments by using only a small number of motion samples.


    1. Karim Bouyarmane and Abderrahmane Kheddar. 2011. Using a multi-objective controller to synthesize simulated humanoid robot motion with changing contact configurations. In IEEE/RSJ Int’l Conf. Intelligent Robots and Systems (IROS). 4414–4419. Google ScholarCross Ref
    2. Myung Geol Choi, Manmyung Kim, Kyung Lyul Hyun, and Jehee Lee. 2011. Deformable motion: Squeezing into cluttered environments. Comput. Graph. Forum 30, 2 (Nov. 2011), 445–453. Google ScholarCross Ref
    3. Min Gyu Choi, Jehee Lee, and Sung Yong Shin. 2003. Planning biped locomotion using motion capture data and probabilistic roadmaps. ACM Trans. Graph. 22, 2 (Apr. 2003), 182–203. Google ScholarDigital Library
    4. Howie Choset, Kevin M. Lynch, Seth Hutchinson, George A. Kantor, Wolfram Burgard, Lydia E. Kavraki, and Sebastian Thrun. 2005. Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press.Google Scholar
    5. Adrien Escande, Abderrahmane Kheddar, and Sylvain Miossec. 2013. Planning contact points for humanoid robots. Robot. Auton. Syst. 61, 5 (2013), 428–442. Google ScholarDigital Library
    6. Kris Hauser, Timothy Bretl, Jean-Claude Latombe, Kensuke Harada, and Brian Wilcox. 2008. Motion planning for legged robots on varied terrain. Int. J. Robot. Res. 27, 11–12 (2008), 1325–1349.Google ScholarCross Ref
    7. Edmond S. L. Ho, Taku Komura, and Chiew-Lan Tai. 2010. Spatial relationship preserving character motion adaptation. ACM Trans. Graph. 29, 4 (July 2010), 33:1–33:8.Google ScholarDigital Library
    8. Sumit Jain, Yuting Ye, and C Karen Liu. 2009. Optimization-based interactive motion synthesis. ACM Transactions on Graphics (TOG) 28, 1 (2009), 10.Google ScholarDigital Library
    9. Changgu Kang and Sung-Hee Lee. 2014. Environment-adaptive contact poses for virtual characters. Comput. Graph. Forum 33, 7 (2014), 1–10. Google ScholarDigital Library
    10. Mubbasir Kapadia, Xu Xianghao, Maurizio Nitti, Marcelo Kallmann, Stelian Coros, Robert W. Sumner, and Markus Gross. 2016. Precision: Precomputing environment semantics for contact-rich character animation. In Proceedings of the 20th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. ACM, 29–37.Google ScholarDigital Library
    11. Manmyung Kim, Kyunglyul Hyun, Jongmin Kim, and Jehee Lee. 2009. Synchronized multi-character motion editing. ACM Trans. Graph. 28, 3 (Jul. 2009), Article 79, 9 pages.Google ScholarDigital Library
    12. Yoshihito Koga, Koichi Kondo, James Kuffner, and Jean-Claude Latombe. 1994. Planning motions with intentions. In SIGGRAPH’94. 395–408. Google ScholarDigital Library
    13. Lucas Kovar and Michael Gleicher. 2004. Automated extraction and parameterization of motions in large data sets. ACM Trans. Graph. 23, 3 (Aug. 2004), 559–568. Google ScholarDigital Library
    14. Lucas Kovar, Michael Gleicher, and Frédéric Pighin. 2002. Motion graphs. In ACM Transactions on Graphics (TOG), Vol. 21. ACM, 473–482. Google ScholarDigital Library
    15. J.-C. Latombe. 1991. Robot Motion Planning. Kluwer Academic Publishers. Google ScholarCross Ref
    16. Manfred Lau and James J. Kuffner. 2005. Behavior planning for character animation. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’05). ACM, New York, NY, 271–280. Google ScholarDigital Library
    17. Jehee Lee, Jinxiang Chai, Paul Reitsma, Jessica Hodgins, and Nancy Pollard. 2002. Interactive control of avatars animated with human motion data. ACM Trans. Graph. 21, 3 (July 2002), 491–500. Google ScholarDigital Library
    18. Kang Hoon Lee, Myung Geol Choi, and Jehee Lee. 2006. Motion patches: Building blocks for virtual environments annotated with motion data. ACM Trans. Graph. 25, 3 (July 2006), 898–906. Google ScholarDigital Library
    19. Sbastien Lengagne, Joris Vaillant, Eiichi Yoshida, and Abderrahmane Kheddar. 2014. Motion planning with sequential convex optimization and convex collision checking. Int. J. Robot. Res. 33 (2014), 1251–1270. Google ScholarDigital Library
    20. Sergey Levine, Yongjoon Lee, Vladlen Koltun, and Zoran Popović. 2011. Space-time planning with parameterized locomotion controllers. ACM Trans. Graph. 30, 3 (May 2011), Article 23, 11 pages.Google ScholarDigital Library
    21. Y. Lipman, O. Sorkine, D. Cohen-Or, D. Levin, C. Rossi, and H.-P. Seidel. 2004. Differential coordinates for interactive mesh editing. In Proceedings of the Shape Modeling Applications, 2004. 181–190. Google ScholarCross Ref
    22. Libin Liu, KangKang Yin, Michiel van de Panne, Tianjia Shao, and Weiwei Xu. 2010. Sampling-based contact-rich motion control. ACM Trans. Graph. 29, 4 (July 2010), Article 128, 10 pages.Google ScholarDigital Library
    23. Mentar Mahmudi and Marcelo Kallmann. 2015. Multi-modal data-driven motion planning and synthesis. In Proceedings of the 8th ACM SIGGRAPH Conference on Motion in Games. ACM, 119–124. Google ScholarDigital Library
    24. Igor Mordatch, Emanuel Todorov, and Zoran Popović. 2012. Discovery of complex behaviors through contact-invariant optimization. ACM Trans. Graph. 31, 4 (July 2012), Article 43, 8 pages.Google ScholarDigital Library
    25. Carl Edward Rasmussen. 2004. Gaussian processes in machine learning. In Advanced Lectures on Machine Learning. Springer, 63–71. Google ScholarCross Ref
    26. Stuart Jonathan Russell, Peter Norvig, John F. Canny, Jitendra M. Malik, and Douglas D. Edwards. 2003. Artificial Intelligence: A Modern Approach. Vol. 2. Prentice Hall, Upper Saddle River, NJ.Google Scholar
    27. Alla Safonova and Jessica K. Hodgins. 2007. Construction and optimal search of interpolated motion graphs. ACM Trans. Graph. 26, 3 (July 2007), Article 106. Google ScholarDigital Library
    28. Ari Shapiro, Marcelo Kallmann, and Petros Faloutsos. 2007. Interactive motion correction and object manipulation. In Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games (I3D’07). ACM, New York, NY, 137–144. Google ScholarDigital Library
    29. Hyun Joon Shin and Hyun Seok Oh. 2006. Fat graphs: Constructing an interactive character with continuous controls. In Proceedings of the 2006 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Eurographics Association, 291–298.Google Scholar
    30. Steve Tonneau, Rami Ali Al-Ashqar, Julien Pettré, Taku Komura, and Nicolas Mansard. 2016. Character contact re-positioning under large environment deformation. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 127–138. Google ScholarDigital Library
    31. Douglas J. Wiley and James K. Hahn. 1997. Interpolation synthesis of articulated figure motion. IEEE Comput. Graph. Appl. 17, 6 (Nov. 1997), 39–45. Google ScholarDigital Library
    32. Katsu Yamane, James J. Kuffner, and Jessica K. Hodgins. 2004. Synthesizing animations of human manipulation tasks. ACM Trans. Graph. 23, 3 (Aug. 2004), 532–539. Google ScholarDigital Library
    33. Yuting Ye and C. Karen Liu. 2012. Synthesis of detailed hand manipulations using contact sampling. ACM Trans. Graph. 31, 4 (July 2012), Article 41, 10 pages.Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: