Motion Planning of Multi-Limbed Robots Subject to Equilibrium Constraints: The Free-Climbing Robot Problem

Abstract

This paper addresses the problem of planning the motion of a multilimbed robot in order to “free-climb” vertical rock surfaces. Freeclimbing only relies on frictional contact with the surfaces rather than on special fixtures or tools like pitons. It requires strength, but more importantly it requires deliberate reasoning: not only must the robot decide how to adjust its posture to reach the next feature without falling, it must plan an entire sequence of steps, where each one might have future consequences. In this paper, this process of reasoning is broken into manageable pieces by decomposing a freeclimbing robot's configuration space into manifolds associated with each state of contact between the robot and its environment. A multistep planning framework is presented that decides which manifolds to explore by generating a candidate sequence of hand and foot placements first. A one-step planning algorithm is then described that explores individual manifolds quickly. This algorithm extends the probabilistic roadmap approach to better handle the interaction between static equilibrium and the topology of closed kinematic chains. It is assumed throughout this paper that a set of potential contact points has been presurveyed. Validation with real hardware was done with a four-limbed robot called LEMUR (developed by the Mechanical and Robotic Technologies Group at NASA–JPL). Using the planner presented in this paper, LEMUR free-climbed an indoor, near-vertical surface covered with artificial rock features.

Get full access to this article

View all access options for this article.

References

Abderrahim, M., Balaguer, C., Giménez, A., Pastor, J., and V. Padrón. 1999. ROMA: A climbing robot for inspection operations . IEEE International Conference on Robotics and Automation, Detroit, MI, pp. 2303–2308 .

Alami, R., Laumond, J.-P., and Siméon, T. 1995. Two manipulation planning algorithms. K. Goldberg, D. Halperin, J.-C. Latombe, and R. Wilson (Eds.), Algorithmic Foundations of Robotics, Wellesley, MA, A K Peters , pp. 109–125.

Almonacid, M., Saltarén, R., Aracil, R., and Reinoso, O. 2003. Motion planning of a climbing parallel robot . IEEE Transactions on Robotics and Automation, 19(3): 485–489 .

Bevly, D., Farritor, S., and Dubowsky, S. 2000. Action module planning and its application to an experimental climbing robot. IEEE International Conference on Robotics and Automation, pp. 4009–4014,

Bicchi, A., and Kumar, V. 2000. Robotic grasping and contact: A review. IEEE International Conference on Robotics and Automation, San Francisco, pp. 348–353.

Boissonnat, J.-D., Devillers, O., and Lazard, S. 2000. Motion planning of legged robots . SIAM Journal of Computing 30(1): 218–246 ,

Boor, V., Overmars, M., and van der Stappen, A. 1999. The gaussian sampling strategy for probabilistic roadmap planners. In IEEE International Conference on Robotics and Automation, pp. 1018–1023.

Bretl, T. 2005. Multi-Step Motion Planning: Application to Free-Climbing Robots. Ph.D. thesis, Stanford University.

Bretl, T., and Lall, S. 2006. A fast and adaptive test of static equilibrium for legged robots . IEEE International Conference on Robotics and Automation, Orlando, FL.

10.

Bretl, T., Lall, S., Latombe, J.-C., and Rock, S. 2004. Multistep motion planning for free-climbing robots . Proceedings of the International Workshop on Algorithmic Foundations of Robotics (WAFR), Zeist, Netherlands.

11.

Bretl, T., Latombe, J.-C., and Rock, S. 2003. Toward autonomous free-climbing robots . International Symposium on Robotics Research, Siena, Italy.

12.

Bretl, T., Rock, S., Latombe, J.-C., Kennedy, B., and Aghazarian, H. 2004. Free-climbing with a multi-use robot . International Symposium on Experimental Robotics, Singapore.

13.

Bullo, F., and Zefran, M. 2002. Modeling and controllability for a class of hybrid mechanical systems . IEEE Transactions on Robotics and Automation 18(4): 563–573 .

14.

Chen, I.-M., and Yeo, S. H. 2003. Locomotion of a twodimensional walking-climbing robot using a closed-loop mechanism: From gait generation to navigation . International-Journal of Robotics Research 22(1): 21–40 .

15.

Choset, H., Lynch, K., Hutchinson, S., Kanto, G., Burgard, W., Kavraki, L., and Thrun, S. 2005. Principles of Robot Motion: Theory, Algorithms, and Implementations. Cambridge, MA, MIT Press .

16.

Cortés, J., Siméon, T., and Laumond, J.-P. 2002. A random loop generator for planning the motions of closed kinematic chains using PRM methods . IEEE International Conference on Robotics and Automation, Washington, DC, pp. 2141–2146 .

17.

Dulimarta, H., and Tummala, R. L. 2002. Design and control of miniature climbing robots with nonholonomic constraints. WCICA, Shanghai, People's Republic of China .

18.

Eldershaw, C., and Yim, M. 2001. Motion planning of legged vehicles in an unstructured environment . IEEE International Conference on Robotics and Automation, Seoul, South Korea.

19.

Goodwine, B., and Burdick, J. 2002. Motion planning for kinematic stratified systems with application to quasi-static legged locomotion and finger gaiting . IEEE Transactions on Automatic Control 18(2): 209–222 .

20.

Grieco, J. C., Prieto, M., Armada, M., and de Santos, P. G. 1998. Asix-legged climbing robot for high payloads . IEEE International Conference on Control and Applications, Trieste, Italy,

21.

Han, L., and Amato, N. M. 2000. A kinematics-based probabilistic roadmap method for closed chain systems . Proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 233–246 .

22.

Hauser, K., Bretl, T., and Latombe, J.-C. 2005a. Learningassisted multi-step planning . IEEE International Conference on Robotics and Automation, Barcelona, Spain.

23.

Hauser, K., Bretl, T., and Latombe, J.-C. 2005b. Non-gaited humanoid locomotion planning. Humanoids, Tsukuba, Japan.

24.

Hsu, D., Kavraki, L. E., Latombe, J.-C., Motwani, R., and Sorkin, S. 1998. On finding narrow passages with probabilistic roadmap planners . Proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR), Natick, MA, pp. 141–153 .

25.

Hsu, D., Latombe, J.-C., and Motwani, R. 1997. Path planning in expansive configuration spaces . IEEE International Conference on Robotics and Automation, pp. 2219–2226 .

26.

Kavraki, L. E., Svetska, P., Latombe, J.-C., and Overmars, M. 1996. Probabilistic roadmaps for path planning in highdimensional configuration spaces . IEEE Transactions on Robotics and Automation 12(4): 566–580 .

27.

Koga, Y., and Latombe, J.-C. 1994. On multi-arm manipulation planning . IEEE International Conference on Robotics and Automation, San Diego, CA, pp. 945–952 .

28.

Kuffner, J. 1999. Autonomous Agents for Real-Time Animation. Ph.D. thesis, Stanford University.

29.

Kuffner, Jr., J. J., Nishiwaki, K., Kagami, S., Inaba, M., and Inoue, H. 2003. Motion planning for humanoid robots . International Symposium on Robotics Research, Siena, Italy.

30.

Latombe, J.-C. 1991. Robot Motion Planning. Boston, MA, Kluwer .

31.

LaValle, S. M., Yakey, J. H., and Kavraki, L. E. 1999. A probabilistic roadmap approach for systems with closed kinematic chains . IEEE International Conference on Robotics and Automation, Detroit, MI, pp. 1671–1676 .

32.

Leven, P., and Hutchinson, S. 2003. Using manipulability to bias sampling during the construction of probabilistic roadmaps . IEEE Transactions on Robotics and Automation 19(6): 1020–1026 .

33.

Long, J. 2000. How to Rock Climb! How to Rock Climb Series. Evergreen, CO, Chockstone Press .

34.

Madhani,A., and Dubowsky, S. 1992. Motion planning of mobile multi-limb robotic systems subject to force and friction constraints . IEEE International Conference on Robotics and Automation, pp. 233–239 .

35.

Nagakubo, A., and Hirose, S. 1994. Walking and running of the quadruped wall-climbing robot . IEEE International Conference on Robotics and Automation, pp. 1005–1012 .

36.

Neubauer, W. 1994. A spider-like robot that climbs vertically in ducts or pipes . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1178–1185 . Munich, Germany,

37.

Nielsen, C. L., and Kavraki, L. E. 2000. Atwo level fuzzy prm for manipulation planning . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Takamatsu, Japan, pp. 1716–1721 .

38.

Okamura, A., Smaby, N., and Cutkosky, M. 2000. An overview of dexterous manipulation . IEEE International Conference on Robotics and Automation, Symposium on Dexterous Manipulation, pp. 255–262 .

39.

Pettré, J., Laumond, J.-P., and Siméon, T. 2003. A 2-stages locomotion planner for digital actors . Eurographics/SIGGRAPH Symposium on Computer Animation, pp. 258–264 .

40.

Roßmann, T., and Pfeiffer, F. 1997. Control of an eight legged pipe crawling robot . International Symposium on Experimental Robotics, pp. 353–346 .

41.

Sahbani, A., Cortés, J., and Siméon, T. 2002. A probabilistic algorithm for manipulation planning under continuous grasps and placements . IEEE/RSJ International Conference on Intelligent Robotic Systems, Lausanne, Switzerland, pp. 1560–1565 .

42.

Sánchez, G., and Latombe, J.-C. 2002. On delaying collision checking in PRMplanning:Application to multi-robot coordination . International Journal of Robotics Research 21(1): 5–26 .

43.

Shapiro, A., and Rimon, E. 2003. PCG: A foothold selection algorithm for spider robot locomotion in 2D tunnels . Proceedings of the IEEE International Conference on Robotics and Automation, Taipei, Taiwan, pp. 2966–2972 .

44.

Sitti, M., and Fearing, R. 2003. Synthetic gecko foot-hair micro/nano-structures for future wall-climbing robots . Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 1, pp. 1164–1170 .

45.

Trinkle, J., and Milgram, R. 2002. Complete path planning for closed kinematic chains with spherical joints . International Journal of Robotics Research 21(9): 773–789 .

46.

Yim, M., Homans, S., and Roufas, K. 2001. Climbing with snake-robots . IFAC Workshop on Mobile Robot Technology, Jejudo, Korea, pp. 7–12 .

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB