Synthesis of constrained walking skills

ABSTRACT

Simulated characters in simulated worlds require simulated skills. We develop control strategies that enable physically-simulated characters to dynamically navigate environments with significant stepping constraints, such as sequences of gaps. We present a synthesis-analysis-synthesis framework for this type of problem. First, an offline optimization method is applied in order to compute example control solutions for randomly-generated example problems from the given task domain. Second, the example motions and their underlying control patterns are analyzed to build a low-dimensional step-to-step model of the dynamics. Third, this model is exploited by a planner to solve new instances of the task at interactive rates. We demonstrate real-time navigation across constrained terrain for physics-based simulations of 2D and 3D characters. Because the framework sythesizes its own example data, it can be applied to bipedal characters for which no motion data is available.

REFERENCES

• 1: Byl, K., and Tedrake, R. 2008. Approximate optimal control of the compass gait on rough terrain. In Proc. Int'l Conf. on Robotics and Automation (ICRA).
• 2: Chestnutt, J., and Kuffner, J. 2004. A tiered planning strategy for biped navigation. In Proceedings of the IEEE - RAS / RSJ Conference on Humanoid Robots.
• 3: Chestnutt, J., Lau, M., Cheung, K. M., Kuffner, J., Hodgins, J. K., and Kanade, T. 2005. Footstep planning for the honda asimo humanoid. In Proc. IEEE Int'l Conf. on Robotics and Automation.
• 4: Min Gyu Choi , Jehee Lee , Sung Yong Shin, Planning biped locomotion using motion capture data and probabilistic roadmaps, ACM Transactions on Graphics (TOG), v.22 n.2, p.182-203, April 2003 [doi>10.1145/636886.636889]
• 5: Marco da Silva , Yeuhi Abe , Jovan Popović, Interactive simulation of stylized human locomotion, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 6: 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.
• 7: Jessica K. Hodgins , Nancy S. Pollard, Adapting simulated behaviors for new characters, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.153-162, August 1997 [doi>10.1145/258734.258822]
• 8: Hodgins, J. K., and Raibert, M. N. 1991. Adjusting step length for rough terrain locomotion. IEEE Trans. on Robotics and Automation 7, 3.
• 9: Andreas G. Hofmann , Brian C. Williams , Steven G. Massaquoi, Robust execution of bipedal walking tasks from biomechanical principles, Massachusetts Institute of Technology, Cambridge, MA, 2006
• 10: Pedro S. Huang , Michiel van de Panne, A planning algorithm for dynamic motions, Proceedings of the Eurographics workshop on Computer animation and simulation '96, p.169-182, December 1996, Poitiers, France
• 11: Kuffner, J., Nishiwaki, K., Kagami, S., Kuniyoshi, Y., and Inoue, H. 2003. Online footstep planning for humanoid robots. In Proc. IEEE Int'l Conf. on Robotics and Automation.
• 12: Taesoo Kwon , Sung Yong Shin, Motion modeling for on-line locomotion synthesis, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073373]
• 13: Joseph Laszlo , Michiel van de Panne , Eugene Fiume, Limit cycle control and its application to the animation of balancing and walking, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.155-162, August 1996 [doi>10.1145/237170.237231]
• 14: C. Karen Liu , Aaron Hertzmann , Zoran Popović, Learning physics-based motion style with nonlinear inverse optimization, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 15: Tomohiko Mukai , Shigeru Kuriyama, Geostatistical motion interpolation, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 16: Zoran Popović , Andrew Witkin, Physically based motion transformation, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.11-20, July 1999 [doi>10.1145/311535.311536]
• 17: Marc H. Raibert , Jessica K. Hodgins, Animation of dynamic legged locomotion, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.349-358, July 1991
• 18: Paul S. A. Reitsma , Nancy S. Pollard, Evaluating motion graphs for character animation, ACM Transactions on Graphics (TOG), v.26 n.4, p.18-es, October 2007 [doi>10.1145/1289603.1289609]
• 19: Alla Safonova , Jessica K. Hodgins, Construction and optimal search of interpolated motion graphs, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 20: Alla Safonova , Jessica K. Hodgins , Nancy S. Pollard, Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 21: Sharon, D., and van de Panne, M. 2005. Synthesis of controllers for stylized planar bipedal walking. In Proc. Int'l Conf. on Robotics and Automation (ICRA).
• 22: Kwang Won Sok , Manmyung Kim , Jehee Lee, Simulating biped behaviors from human motion data, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 23: van de Panne, M. 1997. From footprints to animation. Computer Graphics Forum 16, 4 (October), 211--223.
• 24: Wang, J. M., Fleet, D. J., and Hertzmann, A. 2005. Gaussian process dynamical models. In Proc. Neural Information Processing Systems Conf., 1441--1448.
• 25: KangKang Yin , Kevin Loken , Michiel van de Panne, SIMBICON: simple biped locomotion control, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 26: KangKang Yin , Stelian Coros , Philippe Beaudoin , Michiel van de Panne, Continuation methods for adapting simulated skills, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 27: Zeglin, G., and Brown, B. 1998. Control of a bow leg hopping robot. In Proc. IEEE Intl Conf. on Robotics and Automation, 793--798.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Design, Performance