Event Location: GHC 6501

Abstract: In order to assist humans with dangerous or menial tasks, autonomous robots will need to act under significant time and energy constraints. At task time, the amount of effort a robot spends planning directly detracts from its total performance. Manipulation tasks, however, present challenges to efficient motion planning. They are often tightly coupled — while moving an object can be decomposed into steps (reach, grasp, transfer, release), each step requires choices (e.g. which grasp), and committing to a bad choice can render subsequent steps difficult; this encourages longer planning horizons. However, an articulated robot situated within a geometrically complex and dynamic environment induces a high-dimensional configuration space in which it is expensive to test for valid paths. And since multi-step plans require paths in changing valid subsets of configuration space, it is difficult to reuse computation across steps or maintain caches between tasks.

We focus on a motion planning approach for coupled multi-step manipulation problems that is efficient over the entire task (including both planning and execution). We contend that the problem’s cost structure favors explicit handling of both graph representation and task effort optimization, and propose a graph search algorithm which captures these insights given a model of planning effort. We offer methods for roadmap construction which seek to balance completeness with efficiency at task time. We then unify previous work examining configuration space structure of related problems (e.g. multi-step manipulation) into a general set-theoretic formulation which suggests a planning effort model to be exploited by our roadmap search algorithm, yielding a motion planner which efficiently reuses computation between queries. We also present a task planner that maps a task decomposition into queries to our motion planner. Our insights yield complementary components which, taken together, constitute an efficient approach to planning manipulation tasks.

This thesis proposes a heavy emphasis on experimental evaluation of the individual constituent algorithms and the approach as a whole. We will compare against state-of-the-art task and motion planners on multiple robotic platforms, in applications from home table clearing to remote disaster response. We also provide open-source implementations of our algorithms.

Committee:Siddhartha Srinivasa, Chair

Anthony Stentz

Maxim Likhachev

Lydia Kavraki, Rice University