Discovering and synthesizing humanoid climbing movements

Abstract

This paper addresses the problem of offline path and movement planning for wall climbing humanoid agents. We focus on simulating bouldering, i.e. climbing short routes with diverse moves, although we also demonstrate our system on a longer wall. Our approach combines a graph-based high-level path planner with low-level sampling-based optimization of climbing moves. Although the planning problem is complex, our system produces plausible solutions to bouldering problems (short climbing routes) in less than a minute. We further utilize a k-shortest paths approach, which enables the system to discover alternative paths - in climbing, alternative strategies often exist, and what might be optimal for one climber could be impossible for others due to individual differences in strength, flexibility, and reach. We envision our system could be used, e.g. in learning a climbing strategy, or as a test and evaluation tool for climbing route designers. To the best of our knowledge, this is the first paper to solve and simulate rich humanoid wall climbing, where more than one limb can move at the same time, and limbs can also hang free for balance or use wall friction in addition to predefined holds.

References

1. Rami Aladdin and Paul Kry. 2012. Static Pose Reconstruction with an Instrumented Bouldering Wall. In Proceedings of the 18th ACM Symposium on Virtual Reality Software and Technology (VRST '12). ACM, New York, NY, USA, 177--184.
2. Timothy Bretl. 2006. Motion Planning of Multi-Limbed Robots Subject to Equilibrium Constraints: The Free-Climbing Robot Problem. The International Journal of Robotics Research 25, 4 (2006), 317--342.
3. Oliver Brock and Oussama Khatib. 2002. Elastic Strips: A Framework for Motion Generation in Human Environments. The International Journal of Robotics Research 21, 12 (2002), 1031--1052.
4. Myung Geol Choi, Manmyung Kim, Kyung Lyul Hyun, and Jehee Lee. 2011. Deformable Motion: Squeezing into Cluttered Environments. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 445--453.
5. Min Gyu Choi, Jehee Lee, and Sung Yong Shin. 2003. Planning Biped Locomotion Using Motion Capture Data and Probabilistic Roadmaps. ACM Transactions on Graphics (TOG) 22, 2 (2003), 182--203.
6. Nguyen Anh Dung and Akira Shimada. 2014. A Path-Planning Algorithm for Humanoid Climbing Robot Using Kinect Sensor. In SICE Annual Conference (SICE) in Sapporo. IEEE, 1549--1554.
7. David Eppstein. 1998. Finding the k Shortest Paths. SIAM Journal on Computing 28, 2 (1998), 652--673.
8. David Eppstein and others. 2016. k-Best Enumeration. Springer. (2016).
9. Ian Garcia and Jonathan P How. 2005. Improving the Efficiency of Rapidly-Exploring Random Trees Using a Potential Function Planner. In Proceedings of the 44th IEEE Conference on Decision and Control. IEEE, 7965--7970.
10. Jürgen Guldner, Vadim I Utkin, and Hideki Hashimoto. 1997. Robot Obstacle Avoidance in n-Dimensional Space Using Planar Harmonic Artificial Potential Fields. Journal of Dynamic Systems, Measurement, and Control 119, 2 (1997), 160--166.
11. Perttu Hämäläinen, Joose Rajamäki, and C Karen Liu. 2015. Online Control of Simulated Humanoids Using Particle Belief Propagation. ACM Transactions on Graphics (TOG) 34, 4 (2015), 81.
12. Nikolaus Hansen. 2006. The CMA Evolution Strategy: A Comparing Review. In Towards a New Evolutionary Computation. Springer, 75--102.
13. Michael Hoy, Alexey S Matveev, and Andrey V Savkin. 2015. Algorithms for Collision-Free Navigation of Mobile Robots in Complex Cluttered Environments: A Survey. Robotica 33, 03 (2015), 463--497.
14. Sumit Jain, Yuting Ye, and C Karen Liu. 2009. Optimization-Based Interactive Motion Synthesis. ACM Transactions on Graphics (TOG) 28, 1 (2009), 10.
15. Raine Kajastila, Leo Holsti, and Perttu Hämäläinen. 2016. The Augmented Climbing Wall: High-Exertion Proximity Interaction on a Wall-Sized Interactive Surface. In Proceedings of the 2016 CHI Conference on Human Factors in Computing Systems (CHI '16). ACM, New York, NY, USA, 758--769.
16. Lydia E Kavraki, Petr Svestka, J-C Latombe, and Mark H Overmars. 1996. Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces. IEEE transactions on Robotics and Automation 12, 4 (1996), 566--580.
17. James J Kuffner and Steven M LaValle. 2000. RRT-Connect: An Efficient Approach to Single-Query Path Planning. In Robotics and Automation, 2000. Proceedings. ICRA'00. IEEE International Conference on, Vol. 2. IEEE, 995--1001.
18. Steven M. Lavalle. 1998. Rapidly-Exploring Random Trees: A New Tool for Path Planning. Technical Report. TR 98-11, Computer Science Dept., Iowa State Univ. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.1853
19. Steven M LaValle and James J Kuffner. 2001. Randomized Kinodynamic Planning. The International Journal of Robotics Research 20, 5 (2001), 378--400.
20. Benoît Libeau, Alain Micaelli, and Olivier Sigaud. 2009. Transfer of Knowledge for a Climbing Virtual Human: A Reinforcement Learning Approach. In Robotics and Automation, 2009. ICRA'09. IEEE International Conference on. IEEE, 2119--2124.
21. Maxim Likhachev, David I Ferguson, Geoffrey J Gordon, Anthony Stentz, and Sebastian Thrun. 2005. Anytime Dynamic A*: An Anytime, Replanning Algorithm. In ICAPS. 262--271.
22. Gang Liu and KG Ramakrishnan. 2001. A* Prune: An Algorithm for Finding K Shortest Paths Subject to Multiple Constraints. In INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, Vol. 2. IEEE, 743--749.
23. Igor Mordatch, Emanuel Todorov, and Zoran Popović. 2012. Discovery of Complex Behaviors through Contact-Invariant Optimization. ACM Transactions on Graphics (TOG) 31, 4 (2012), 43.
24. Giacomo Nannicini and Leo Liberti. 2008. Shortest Paths on Dynamic Graphs. International Transactions in Operational Research 15, 5 (2008), 551--563.
25. Tim Olsen, Sheldon Andrews, and Paul Kry. 2014. Computational Climbing for Physics-Based Characters. Technical Report. The ACM SIGGRAPH / Eurographics Symposium on Computer Animation (SCA posters). http://cs.mcgill.ca/~sandre17/climbing/
26. Mohammad Naim Rastgoo, Bahareh Nakisa, Mohammad Faidzul Nasrudin, Ahmad Nazri, and Mohd Zakree. 2014. A Critical Evaluation of Literature on Robot Path Planning in Dynamic Environment. Journal Of Theoretical And Applied Information Technology 10th 70, 1 (December 2014), 175--185.
27. Liam Roditty and Uri Zwick. 2004. On Dynamic Shortest Paths Problems. In European Symposium on Algorithms. Springer, 580--591.
28. F. Sibella, I. Frosio, F. Schena, and N.A. Borghese. 2007. 3D Analysis of the Body Center of Mass in Rock Climbing. Human Movement Science 26, 6 (2007), 841 -- 852.
29. Herbert G Tanner and Amit Kumar. 2005. Towards Decentralization of Multi-Robot Navigation Functions. In Proceedings of the 2005 IEEE International Conference on Robotics and Automation. IEEE, 4132--4137.
30. Yuval Tassa, Nicolas Mansard, and Emo Todorov. 2014. Control-Limited Differential Dynamic Programming. In Proc. ICRA 2014. IEEE, 1168--1175.
31. Steve Tonneau, Julien Pettré, and Franck Multon. 2014. Task Efficient Contact Configurations for Arbitrary Virtual Creatures. In Proceedings of Graphics Interface 2014 (GI '14). Canadian Information Processing Society, Toronto, Ont., Canada, Canada, 9--16. http://dl.acm.org/citation.cfm?id=2619648.2619652
32. Dustin J Webb and Jur van den Berg. 2013. Kinodynamic RRT*: Asymptotically Optimal Motion Planning for Robots with Linear Dynamics. In Robotics and Automation (ICRA), 2013 IEEE International Conference on. IEEE, 5054--5061.

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

      • Physical simulation