“Discovering and synthesizing humanoid climbing movements” by Naderi, Rajamäki and Hämäläinen
Conference:
Type(s):
Title:
- Discovering and synthesizing humanoid climbing movements
Session/Category Title: Learning to Move
Presenter(s)/Author(s):
Moderator(s):
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarCross Ref
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.Google ScholarCross Ref
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. Google ScholarDigital Library
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. Google ScholarCross Ref
7. David Eppstein. 1998. Finding the k Shortest Paths. SIAM Journal on Computing 28, 2 (1998), 652–673. Google ScholarDigital Library
8. David Eppstein and others. 2016. k-Best Enumeration. Springer. (2016). Google ScholarCross Ref
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. Google ScholarCross Ref
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. Google ScholarCross Ref
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.Google ScholarDigital Library
12. Nikolaus Hansen. 2006. The CMA Evolution Strategy: A Comparing Review. In Towards a New Evolutionary Computation. Springer, 75–102. Google ScholarCross Ref
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. Google ScholarCross Ref
14. 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
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. Google ScholarDigital Library
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.Google Scholar
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.Google ScholarCross Ref
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.1853Google Scholar
19. Steven M LaValle and James J Kuffner. 2001. Randomized Kinodynamic Planning. The International Journal of Robotics Research 20, 5 (2001), 378–400.Google ScholarCross Ref
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. Google ScholarCross Ref
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.Google Scholar
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.Google Scholar
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. Google ScholarDigital Library
24. Giacomo Nannicini and Leo Liberti. 2008. Shortest Paths on Dynamic Graphs. International Transactions in Operational Research 15, 5 (2008), 551–563. Google ScholarCross Ref
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/Google Scholar
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.Google Scholar
27. Liam Roditty and Uri Zwick. 2004. On Dynamic Shortest Paths Problems. In European Symposium on Algorithms. Springer, 580–591. Google ScholarCross Ref
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. Google ScholarCross Ref
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. Google ScholarCross Ref
30. Yuval Tassa, Nicolas Mansard, and Emo Todorov. 2014. Control-Limited Differential Dynamic Programming. In Proc. ICRA 2014. IEEE, 1168–1175. Google ScholarCross Ref
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.2619652Google ScholarDigital Library
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. Google ScholarCross Ref
