Computer Science Department
School of Computer Science, Carnegie Mellon University


A Hierarchical Framework for
Configuration Space Task Planning

Evan Shapiro

July 2015

M.S. Thesis


Keywords: Robotics, Task Planning, Task Specification, Manipulation Planning, Motion Planning, Hierarchical Planning, Configuration Space, Monte Carlo Tree Search, Interleaved Planning and Execution

Robots are rapidly moving towards proficiency at useful tasks. In order for task planners to adapt to novel scenarios, new architectures and algorithms will be necessary. This work develops a framework and extensions to that framework in order to provide a system that can efficiently and robustly plan for a wide variety of tasks.

The framework dynamically restricts search space by exploiting highly interconnected hierarchically composed actions. The hierarchical action structure can be generated dynamically during planning, allowing geometric state to determine high level search space restrictions. This allows the framework to provide intermediate goals to efficiently plan through high dimensional spaces over long sequences of actions, and integrate with arbitrary existing task and motion planners.

We also develop framework enhancements to improve performance during both planning and during execution. The order in which intermediate steps are explored greatly affects planning time. We apply a variant of Monte Carlo Tree Search to determine the order to compute intermediate steps. Execution performance is improved by interleaving planning and execution. We consider tasks that are composed of reversible trajectories, and construct methods to traverse partially complete plans. We explore the affects of different variants of these enhancements on manipulation tasks.

65 pages

Thesis Committee:
Siddhartha Srinivasa (Chair)
Maxim Likhachev

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by