In this paper we study the quasi-static motion of large legged robots that have many degrees of freedom. While gaited walking may suffice on easy ground, rough and steep terrain requires unique sequences of footsteps and postural adjustments specifically adapted to the terrain's local geometric and physical properties. In this paper we present a planner that computes these motions by combining graph searching to generate a sequence of candidate footfalls with probabilistic sample-based planning to generate continuous motions that reach these footfalls. To improve motion quality, the probabilistic planner derives its sampling strategy from a small set of motion primitives that have been generated offline. The viability of this approach is demonstrated in simulation for the six-legged Lunar vehicle ATHLETE and the humanoid HRP-2 on several example terrains, including one that requires both hand and foot contacts and another that requires rappelling.
Akinc, M., Bekris, K.E., Chen, B.Y., Ladd, A.M., Plaku, E. and Kavraki, L.E. (2003). Probabilistic roadmaps of trees for parallel computation of multiple query roadmaps. Proceedings of the International Symposium on Robotics Research, Siena, Italy.
2.
Alami, R., Laumond, J.-P. and Siméon, T. (1995). Two manipulation planning algorithms. Algorithmic Foundations of Robotics, Goldberg, K., Halperin, D., Latombe, J.-C. and Wilson, R. (eds). Wellesley, MA, A.K. Peters, pp. 109- 125.
3.
Arun, K., Huang, T. and Blostein, S. (1987). Least-squares fitting of two 3-D point sets. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(5): 698-700.
4.
Bares, J.E. and Wettergreen, D.S. (1999). Dante II: technical description, results and lessons learned. The International Journal of Robotics Research, 18(7): 621-649.
5.
Bevly, D., Farritor, S. and Dubowsky, S. (2000). Action module planning and its application to an experimental climbing robot. Proceedings IEEE International Conference on Robotics and Automation, pp. 4009-4014.
6.
Bicchi, A. and Kumar, V. (2000). Robotic grasping and contact: a review. Proceedings IEEE International Conference on Robotics and Automation , San Francisco, CA, pp. 348- 353.
7.
Bobrow, J., Martin, B., Sohl, G., Wang, E., Park, F. and Kim, J. (2001). Optimal robot motions for physical criteria. Journal of Robotic Systems, 18(12): 785-795.
8.
Boissonnat, J.-D., Devillers, O. and Lazard, S. (2000). Motion planning of legged robots. SIAM Journal of Computing, 30(1): 218-246.
9.
Boyd, S. and Vandenberghe, L. (2004). Convex Optimization. Cambridge, Cambridge University Press.
10.
Bretl, T. (2006). Motion planning of multi-limbed robots subject to equilibrium constraints: the free-climbing robot problem. The International Journal of Robotics Research, 25(4): 317-342.
11.
Bretl, T. and Lall, S. (2006). A fast and adaptive test of static equilibrium for legged robots. Proceedings IEEE International Conference on Robotics and Automation, Orlando, FL.
12.
Bretl, T. and Lall, S. (2008). Testing static equilibrium for legged robots. IEEE Transactions on Robotics, to appear.
13.
Bretl, T., Latombe, J.-C. and Rock, S.Toward autonomous free-climbing robots. Proceedings of the International Symposium on Robotics Research, Siena , Italy.
14.
Burridge, R., Rizzi, A. and Koditschek, D. (1999). Sequential composition of dynamically dexterous robot behaviors. The International Journal of Robotics Research , 18(6): 534- 555.
15.
Byrd, R.H., Gould, N.I.M., Nocedal, J. and Waltz, R.A. (2002). An active-set algorithm for nonlinear programming using linear programming and equality constrained subproblems. Technical Report OTC 2002/4, Optimization Technology Center, Northwestern University, Evanston, IL.
16.
Chestnutt, J., Kuffner, J., Nishiwaki, K. and Kagami, S. (2003). Planning biped navigation strategies in complex environments. Proceedings IEEE International Conference on Humanoid Robots, Munich, Germany.
17.
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.
18.
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. Proceedings IEEE International Conference on Robotics and Automation, Washington, DC.
19.
Eldershaw, C. and Yim, M.Motion planning of legged vehicles in an unstructured environment. Proceedings IEEE International Conference on Robotics and Automation , Seoul, South Korea.
20.
Estier, T., Crausaz, Y., Merminod, B., Lauria, M., Pguet, R. and Siegwart, R. (2000). An innovative space rover with extended climbing abilities. Proceedings of Space and Robotics, Albuquerque, NM.
21.
Frazzoli, E., Dahleh, M.A. and Feron, E. (2002a). Real-time motion planning for agile autonomous vehicles. AIAA Journal of Guidance, Control, and Dynamics , 25(1): 116- 129.
22.
Frazzoli, E., Dahleh, M.A. and Feron, E. (2002b). Maneuver-based motion planning for nonlinear systems with symmetries. IEEE Transactions on Robotics, 25(1): 116-129.
23.
Gavrilets, V., Frazzoli, E., Mettler, B., Peidmonte, M. and Feron, E. (2001). Aggressive maneuvering of small autonomous helicopters: a human-centered approach. The International Journal of Robotics Research, 20(10): 795- 807.
24.
Geraerts, R. and Overmars, M. (2004). Clearance based path optimization for motion planning . Proceedings IEEE International Conference on Robotics and Automation, New Orleans, LA.
25.
Gleicher, M. (1998). Retargetting motion to new characters. Proceedings of ACM SIGGRAPH'98, pp. 33-42.
26.
Gottschalk, S., Lin, M. and Manocha, D. (1996). OBB-tree: a hierarchical structure for rapid interference detection. Computer Graphics, 30: 171-180.
27.
Greenfield, A., Saranli, U. and Rizzi, A.A. (2005). Solving models of controlled dynamic planar rigid-body systems with frictional contact. The International Journal of Robotics Research, 24(11): 911-931.
28.
Grochow, K., Martin, S.L., Hertzmann, A. and Popović, Z. (2004). Style-based inverse kinematics . ACM Transactions on Graphics, 23(3): 522-531.
29.
Harada, K., Kajita, S., Saito, H., Kanehiro, F. and Hirukawa, H. (2004). Integration of manipulation and locomotion by a humanoid robot. Proceedings of the International Symposium on Experimental Robotics, Singapore.
30.
Harada, K., Hauser, K., Bretl, T. and Latombe, J.-C. (2006). National motion generation for humanoid robots . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Beijing, China.
31.
Hauser, K., Bretl, T. and Latombe, J.-C. (2005). Non-gaited humanoid locomotion planning. Proceedings of Humanoids, Tsukuba, Japan.
32.
Heiken, G.H., Vaniman, D.T. and French, B.M. (1991). Lunar Sourcebook: A User's Guide to the Moon. Cambridge, Cambridge University Press.
33.
Hirose, S. and Kunieda, O.Generalized standard foot trajectory for a quadruped walking vehicle. The International Journal of Robotics Research, 10(1): 3-12.
34.
Hirose, S., Yoneda, K. and Tsukagoshi, H. Titan VII: quadruped walking and manipulating robot on a steep slope. Proceedings IEEE International Conference on Robotics and Automation, Albuquerque, NM , pp. 494-500.
35.
Hsu, D., Latombe, J.-C. and Kurniawati, H. (2005). On the probabilistic foundations of probabilistic roadmap planning. Proceedings of the International Symposium on Robotics Research, San Francisco, CA.
36.
Iagnemma, K., Genot, F. and Dubowsky, S. (1999). Rapid physics-based rough-terrain rover planning with sensor and control uncertainty. Proceedings IEEE International Conference on Robotics and Automation, Detroit, MI.
37.
Kaneko, K., Kanehiro, F., Kajita, S., Hirukawa, H., Kawasaki, T., Hirata, M., Akachi, K. and Isozumi, T. (2004). Humanoid robot HRP-2. Proceedings IEEE International Conference on Robotics and Automation, New Orleans, LA, pp. 1083-1090.
38.
Kavraki, L.E., Svetska, P., Latombe, J.-C. and Overmars, M. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation , 12(4): 566-580.
39.
Koga, Y. and Latombe, J.-C. (1994). On multi-arm manipulation planning. Proceedings IEEE International Conference on Robotics and Automation , San Diego, CA, pp. 945-952.
40.
Kovar, L., Gleicher, M. and Pighin, F. (2002). Motion graphs. Proceedings of ACM SIGGRAPH'02, San Antonio, TX, pp. 473-482.
41.
Kron, T. and Shin, S.Y. (2005). Motion modeling for on-line locomotion synthesis . Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Computer Animation, Los Angeles, CA, pp. 29-38.
42.
Krotkov, E. and Simmons, R. (1996). Perception, planning, and control for autonomous walking with the ambler planetary rover. The International Journal of Robotics Research, 15: 155-180.
43.
Kuffner, J.J. Jr (1999) Autonomous agents for real-time animation. Ph.D. Thesis, Stanford University.
44.
Kuffner, J.J. Jr, Nishiwaki, K., Kagami, S., Inaba, M. and Inoue, H. (2003). Motion planning for humanoid robots. Proceedings of the International Symposium on Robotics Research , Siena, Italy.
45.
Laumond, J.-P. (1987). Finding collision-free smooth trajectories for a non-holonomic mobile robot. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 1120-1123.
46.
Laumond, J.-P., Jacobs, P., Taix, M. and Murray, R. (1994). A motion planner for nonholonomic mobile robots . IEEE Transactions on Robotics and Automation, 10(5): 577-593.
47.
Lauria, M., Piguet, Y. and Siegwart, R. (2002). Octopus: an autonomous wheeled climbing robot . Proceedings of CLAWAR.
48.
Lawrence, C., Zhou, J. and Tits, A. (1997). User's guide for CFSQP version 2.5: a C code for solving (large scale) constrained nonlinear (minimax) optimization problems, generating iterates satisfying all inequality constraints. Technical Report TR-94-16r1, Institute for Systems Research, University of Maryland, College Park, MD.
49.
Lee, H., Shen, Y., Yu, C.-H., Singh, G. and Ng, A.Y. (2006). Quadruped robot obstacle negotiation via reinforcement learning. Proceedings IEEE International Conference on Robotics and Automation.
50.
Liao, L., Fox, D. and Kautz, H. (2005). Location-based activity recognition. Advances in Neural Information Processing Systems, http://www.cs.washington.edu/ai/Mobile_Robotics/postscripts/places-nips-05.pdf .
51.
Liu, C.K., Hertzmann, A. and Popović, Z. (2005). Learning physics-based motion style with nonlinear inverse optimization. ACM Transactions on Graphics, 24(3): 1071- 1081.
52.
Meredith, M. and Maddock, S. (2005). Adapting motion capture data using weighted real-time inverse kinematics. Computer Entertainment, 3(1): 5.
53.
Miller, T., Bretl, T. and Rock, S. (2006). Control of a climbing robot using real-time convex optimization. Proceedings of the IFAC Symposium on Mechanical Systems, Heidelberg, Germany.
54.
Missiuro, P.E. and Roy, N. (2006). Adapting probabilistic roadmaps to handle uncertain maps. Proceedings IEEE International Conference on Robotics and Automation.
55.
Mumm, E., Farritor, S., Pirjanian, P., Leger, C. and Schenker, P. (2004). Planetary cliff descent using cooperative robots . Autonomous Robots, 16: 259-272.
56.
Ng, A.Y., Kim, H.J., Jordan, M. and Sastry, S. (2004). Autonomous helicopter flight via reinforcement learning. Neural Information Processing Systems16.
57.
Nielsen, C.L. and Kavraki, L.E. (2000). A two level fuzzy prm for manipulation planning . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Takamatsu, Japan, pp. 1716-1721.
58.
Okamura, A., Smaby, N. and Cutkosky, M. (2000). An overview of dexterous manipulation. Proceedings IEEE International Conference on Robotics and Automation , pp. 255-262.
Pang, J.-S. and Trinkle, J. (2000). Stability characterizations of rigid body contact problems with coulomb friction. Zeitschrift für Angewandte Mathematik und Mechanik, 80(10): 643-663.
61.
Pettré, J., Laumond, J.-P. and Siméon, T. (2003). A 2-stages locomotion planner for digital actors . Proceedings of the Eurographics/SIGGRAPH Symposium on Computer Animation.
62.
Popovic, M.B., Goswami, A. and Herr, H. (2005). Ground reference points in legged locomotion: Definitions, biological trajectories and control implications. The International Journal of Robotics Research, 24(12): 1013-1032.
63.
Popović, Z. and Witkin, A. (1999). Physically based motion transformation. Proceedings of ACM SIGGRAPH'99, pp. 11-20.
64.
Ren, L., Patrick, A., Efros, A.A., Hodgins, J.K. and Rehg, J.M. (2005). A data-driven approach to quantifying natural human motion. ACM Transactions on Graphics, 24(3): 1090-1097.
65.
Rimon, E., Burdick, J.W. and Omata, T. (2006). A polyhedral bound on the indeterminate contact forces in planar quasi-rigid fixturing and grasping arrangements. IEEE Transactions on Robotics, 22(2): 240-255. DOI: 10.1109/TRO.2005.862478.
66.
Sahbani, A., Cortés, J. and Siméon, T. (2002). A probabilistic algorithm for manipulation planning under continuous grasps and placements. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems , Lausanne, Switzerland, pp. 1560-1565.
67.
Sánchez, G. and Latombe, J.-C. (2002). On delaying collision checking in PRM planning: application to multi-robot coordination. The International Journal of Robotics Research, 21(1): 5-26.
68.
Schwarzer, F., Saha, M. and Latombe, J.-C. (2002). Exact collision checking of robot paths. Proceedings of WAFR, Nice, France.
69.
Sentis, L. and Khatib, O.Synthesis of whole-body behaviors through hierarchical control of behavioral primitives. International Journal of Humanoid Robotics, 2(4): 505-518.
70.
Shapiro, A. and Rimon, E. (2003). PCG: A foothold selection algorithm for spider robot locomotion in 2D tunnels. Proceedings IEEE International Conference on Robotics and Automation, Taipei , Taiwan, pp. 2966-2972.
71.
Shin, H.J., Lee, J., Shin, S.Y. and Gleicher, M. (2001). Computer puppetry: an importance-based approach . ACM Transactions on Graphics, 20(2): 67-94.
72.
Song, G., Miller, S. and Amato, N.M. (2001). Customizing PRM roadmaps at query time. Proceedings IEEE International Conference on Robotics and Automation , Seoul, Korea, pp. 1500-1505.
73.
Song, S.-M. and Waldron, K.J. (1989). Machines that Walk: the Adaptive Suspension Vehicle . Cambridge, MA, MIT Press.
74.
Stilman, M. and Kuffner, J.J.Planning among movable obstacles with artificial constraints. Proceedings of WAFR, New York, NY.
75.
Vougioukas, S.G. (2005) Optimization of robot paths computed by randomized planners. Proceedings IEEE International Conference on Robotics and Automation, Barcelona, Spain.
76.
Wang, L. and Chen, C. (1991). A combined optimization method for solving the inverse kinematics problem of mechanical manipulators. IEEE Transactions on Robotics and Automation, 7(4): 489-499.
77.
Wettergreen, D., Thorpe, C. and Whittaker, W. (1993). Exploring Mount Erebus by walking robot. Robotics and Autonomous Systems, 11: 171-185.
78.
Wilcox, B.H., Litwin, T., Biesiadecki, J., Matthews, J., Heverly, M., Morrison, J., Townsend, J., Ahmad, N., Sirota, A. and Cooper, B. (2007). ATHLETE: a cargo handling and manipulation robot for the Moon. Journal of Field Robotics, 24(5): 421-434.
79.
Witkin, A. and Popović, Z. (1995). Motion warping. Proceedings of ACM SIGGRAPH'95, Los Angeles, CA, pp. 105- 108.
80.
Yakey, J.H., LaValle, S.M. and Kavraki, L.E. (2001). Randomized path planning for linkages with closed kinematic chains. IEEE Transactions on Robotics and Automation , 17(6): 951-958.
81.
Yamane, K., Kuffner, J.J. and Hodgins, J.K. (2004). Synthesizing animations of human manipulation tasks. ACM Transactions on Graphics, 23(3): 532-539.
82.
Yoneda, K., Ito, F., Ota, Y. and Hirose, S. (1999). Steep slope locomotion and manipulation mechanism with minimum degrees of freedom. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1897-1901.
83.
Zheng, Y.F. and Shen, J. (1990). Gait synthesis for the SD-2 biped robot to climb sloping surface. IEEE Transactions on Robotics and Automation , 6(1): 86-96.
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.
