Carnegie Mellon University
A Data-Driven Approach to High Level Planning

Matthew Zucker
tech. report CMU-RI-TR-09-42, Robotics Institute, Carnegie Mellon University, January, 2009

  • Adobe portable document format (pdf) (5MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Motion planning for complex systems such as legged robots and mobile manipulators has proven to be a difficult task for a variety of reasons: not only must planning software con- sider a high-dimensional configuration space, but it must reason dynamically about how to apply forces to the real world. Accomplishing such planning in real-time is harder still. One promising strategy is to take a high-level approach to planning by reasoning about sequences of discrete behavior primitives. For many plaforms this has proven far more tractable than global search from start to goal in the full configuration space of the robot. A successful example from the field of legged robots is footstep planning, which reasons over sequences of footsteps. High-level planning, however, introduces significant tradeoffs. Although the space of dis- crete behavior primitives is frequently more efficient to search, the planner depends on an underlying controller or policy to faithfully and effectively execute the primitives the planner has selected. Hence, the planner must have some model of the capabilities of the controller. Encoding such capability models can be a tedious and error-prone task: if the capability model is too conservative, the high-level planner may fail to find solutions for difficult problems; if the model is too liberal, the robot may fail to execute the selected behavior. The situation is compounded if the planner must reason about heterogeneous behaviors—imagine adding hop- ping and sliding behavior primitives to an existing footstep planner. It may not be clear how to translate estimates of the risk and cost of diverse actions into a common currency. This thesis aims to develop a general system for quickly and effectively selecting among heterogeneous behaviors for high-dimensional robotic navigation and manipulation. The cen- tral idea of the system is to store pre-planned and/or previously executed actions in a behavior library, which is then analyzed and queried via machine learning techniques. This data-driven approach can aid high-level planning in a number of ways. First and foremost, planning is accelerated by re-using the results of previous computation. In addition, the high-level planner can adapt its capability model as well as heuristic cost-to-go estimates over time in order to better reflect the capabilities of the system. The proposed high-level planning system will be demonstrated and evaluated on the Boston Dynamics Inc. LittleDog quadruped robot, as well as on another high-dimensional robotic platform.

Associated Center(s) / Consortia: Center for the Foundations of Robotics
Associated Lab(s) / Group(s): Planning and Autonomy Lab
Associated Project(s): Learning Locomotion

Text Reference
Matthew Zucker, "A Data-Driven Approach to High Level Planning," tech. report CMU-RI-TR-09-42, Robotics Institute, Carnegie Mellon University, January, 2009

BibTeX Reference
   author = "Matthew Zucker",
   title = "A Data-Driven Approach to High Level Planning",
   booktitle = "",
   institution = "Robotics Institute",
   month = "January",
   year = "2009",
   number= "CMU-RI-TR-09-42",
   address= "Pittsburgh, PA",