We present a novel approach to legged locomotion over rough terrain that is thoroughly rooted in optimization. This approach relies on a hierarchy of fast, anytime algorithms to plan a set of footholds, along with the dynamic body motions required to execute them. Components within the planning framework coordinate to exchange plans, cost-to-go estimates, and ‘certificates’ that ensure the output of an abstract high-level planner can be realized by lower layers of the hierarchy. The burden of careful engineering of cost functions to achieve desired performance is substantially mitigated by a simple inverse optimal control technique. Robustness is achieved by real-time re-planning of the full trajectory, augmented by reflexes and feedback control. We demonstrate the successful application of our approach in guiding the LittleDog quadruped robot over a variety of types of rough terrain. Other novel aspects of our past research efforts include a variety of pioneering inverse optimal control techniques as well as a system for planning using arbitrary pre-recorded robot behavior.
Bobrow JE, Martin B., Sohl G., Wang EC, Park FC and Kim J. ( 2001) Optimal robot motions for physical criteria. Journal of Robotic Systems18: 785-795.
2.
Brock O. and Khatib O. ( 2002) Elastic strips: a framework for motion generation in human environments. The International Journal of Robotics Research21: 1031.
3.
Buchli J., Kalakrishnan M., Mistry M., Pastor P. and Schaal S. ( 2009) Compliant quadruped locomotion over rough terrain. In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems.
4.
Buehler M., Playter R. and Raibert M. ( 2005) Robots step outside. In Proceedings International Symposium on Adaptive Motion in Animals and Machines.
5.
Chestnutt J. ( 2007) Navigation Planning for Legged Robots. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
6.
Chestnutt J., Lau M., Cheung KM, Kuffner J., Hodgins J. and Kanade T. ( 2005) Footstep Planning for the Honda ASIMO Humanoid. In Proceedings IEEE International Conference on Robotics and Automation.
7.
Dubins LE ( 1957) On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents . American Journal of Mathematics79: 497-516.
8.
Felzenszwalb P. and Huttenlocher D. ( 2004) Distance Transforms of Sampled Functions. Technical Report TR2004-1963, Cornell University.
9.
Geraerts R. and Overmars M. ( 2006) Creating high-quality roadmaps for motion planning in virtual environments. In IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4355-4361.
10.
Hauser K., Bretl T. and Latombe JC ( 2005) Learning-assisted multi-step planning. In Proceedings IEEE International Conference on Robotics and Automation .
11.
Hazan E., Agarwal A. and Kale S. ( 2006) Logarithmic regret algorithms for online convex optimization . In Proceedings of COLT, pp. 499-513.
12.
Herbrich R., Graepel T. and Obermayer K. ( 1999) Support vector learning for ordinal regression. In 9th International Conference on Artificial Neural Networks, ICANN 99 (Conf. Publ. No. 470), 1.
Kajita S., Kanehiro F., Kaneko K., Fujiwara K., Harada K., Yokoi K. and Hirukawa H. ( 2003) Biped walking pattern generation by using preview control of zero-moment point. In IEEE International Conference on Robotics and Automation.
15.
Kalakrishnan M. ( 2009) Personal communication, November.
16.
Kalakrishnan M., Buchli J., Pastor P. and Schaal S. ( 2009) Learning locomotion over rough terrain using terrain templates . In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems.
17.
Khatib O. ( 1987) A unified approach for motion and force control of robot manipulators: the operational space formulation. IEEE Journal of Robotics and Automation3: 43-53.
18.
Kivinen J., Smola AJ and Williamson RC ( 2004) Online learning with kernels. IEEE Transactions on Signal Processing52: 2165-2176.
19.
Koenig S. and Likhachev M. ( 2002) D^* Lite. In Proceedings of the National Conference on Artificial Intelligence. Cambridge, MA: MIT Press, pp. 476-483.
20.
Kolter JZ and Ng AY ( 2007) Learning omnidirectional path following using dimensionality reduction. In Proceedings Robots, Science and Systems.
21.
Kolter JZ and Ng AY ( 2009) Task-space trajectories via cubic spline optimization . In Proceedings IEEE International Conference on Robotics and Automation.
22.
Kolter JZ, Abbeel P. and Ng AY ( 2008a) Hierarchical apprenticeship learning, with application to quadruped locomotion. In Advances in Neural Information Processing Systems, Vol. 20. Cambridge, MA: MIT Press.
23.
Kolter JZ, Rodgers MP and Ng AY ( 2008b) A control architecture for quadruped locomotion over rough terrain. In Proceedings IEEE International Conference on Robotics and Automation, pp. 811-18.
24.
Likhachev M., Gordon G. and Thrun S. ( 2004) ARA*: Anytime A* with provable bounds on sub-optimality . In Advances in Neural Information Processing Systems, Vol. 16. Cambridge, MA: MIT Press.
25.
Likhachev M., Ferguson D., Gordon G., Stentz A. and Thrun S. ( 2005) Anytime dynamic A*: An anytime, re-planning algorithm . In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp. 262-71.
26.
Pearl J. ( 1984) Heuristics: Intelligent Search Strategies for Computer Problem Solving. Reading, MA: Addison-Wesley .
27.
Raibert M. ( 1986) Legged Robots that Balance. Cambridge, MA: MIT Press.
28.
Ratliff N. ( 2009) Learning to Search: Structured Prediction Techniques for Imitation Learning. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
29.
Ratliff N., Bagnell JA and Zinkevich M. ( 2006) Maximum margin planning. In 22nd International Conference on Machine Learning (ICML06).
30.
Ratliff N., Bagnell JA and Zinkevich M. ( 2007a) (Online) Sub-gradient methods for structured prediction . In Artificial Intelligence and Statistics, San Juan, Puerto Rico.
31.
Ratliff N., Bagnell JA and Srinivasa S. ( 2007b) Imitation learning for locomotion and manipulation. In IEEE-RAS International Conference on Humanoid Robots .
32.
Ratliff N., Bradley D., Bagnell JA and Chestnutt J. ( 2007c) Boosting structured prediction for imitation learning . In Scholkopf B, Platt JC and Hofmann T (Eds), Advances in Neural Information Processing Systems, Vol. 19. Cambridge, MA: MIT Press.
33.
Ratliff N., Silver D and Bagnell JA (2009a) Learning to search: functional gradient techniques for imitation learning. Autonomous Robots27: 25-53.
34.
Ratliff N., Zucker M., Bagnell JA and Srinivasa S. ( 2009b) CHOMP: gradient optimization techniques for efficient motion planning. In Proceedings IEEE International Conference on Robotics and Automation.
35.
Rebula JR, Neuhaus PD, Bonnlander BV, Johnson MJ and Pratt JE ( 2007) A controller for the LittleDog quadruped walking on rough terrain. In Proceedings IEEE International Conference on Robotics and Automation, pp. 1467-73.
36.
Safonova A. and Hodgins J. ( 2007) Construction and optimal search of interpolated motion graphs. ACM Transactions on Graphics (SIGGRAPH 2007)26: 106.
37.
Saranli J., Buehler M. and Koditschek DE ( 2001) RHex: A simple and highly mobile hexapod robot. The International Journal of Robotics Research20: 616.
38.
Stentz A. ( 1995) The focussed D* algorithm for real-time re-planning. In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1652-1659.
39.
Stolle M. ( 2008) Finding and Transferring Policies Using Stored behavior . PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
40.
Willow Garage ( 2009) CHOMP Motion Planner. Willow Garage Blog , September. http://www.willowgarage.com/blog/2009/09/02/chomp-motion-planner . Retrieved in November.
41.
Zucker M. ( 2009) A Data-driven Approach to High Level Planning. Technical Report CMU-RI-TR-09-42, Robotics Institute, Carnegie Mellon University.
42.
Zucker M., Kuffner J. and Bagnell JA ( 2008) Adaptive workspace biasing for sampling based planners . In Proceedings IEEE International Conference on Robotics and Automation.
