Event Location: NSH 3305

Abstract: Motion planning is a central problem in robotics and is crucial to finding paths to navigate and manipulate safely and efficiently. Ideally, we want planners which find paths quickly and of good quality. Additionally, planners should generate predictable motions, which are safer when operating in the presence of humans. While the world is dynamic, there are large parts that are static much of the time. For instance, most of a kitchen is fixed and factory floors are largely static and structured. Further, there are many tasks in these environments that are highly repetitive. Some examples are moving boxes from a pallet to shelving in a warehouse, or in a kitchen when moving dirty dishes from a sink to dishwasher. This thesis studies how to exploit the repetition of these tasks to improve planning by learning from past experience or human demonstrations.

At a high level, the proposed planning framework takes a set of previous plans which may have been generated by the planner previously, found by some other planner, or provided from a human demonstration. These prior plans are put together to form an Experience Graph or EGraph. When solving a new problem, the planner is biased toward parts of the Experience Graph that look as though they will help find the goal faster. Our experiments show that in repetitive tasks, using E-Graphs can lead to large speedups in planning time. This is done in a way that can provide guarantees on completeness and the quality of the solutions produced, even when the prior experiences have arbitrary quality (for instance, when based on a human demonstration).

Experimentally, we have applied E-Graphs to high dimensional pick-and-place tasks such as single-arm manipulation and dual-arm mobile manipulation. One such experiment was an assembly task where the PR2 robot constructed real birdhouses out of wooden pieces and nails. We also applied E-Graphs to mobile manipulation tasks with constraints, such as approaching, grasping, and opening a cabinet or drawer. Most of these experiments have been duplicated in simulation and on a real PR2 robot. Our results show that under certain conditions, E-Graphs provide significant speedups over planning from scratch and that the generated paths are consistent: motions planned for similar start and goal states produce similar paths. Additionally, our experiments show E-Graphs can incorporate human demonstrations effectively, providing an easy way of bootstrapping motion planning for complex tasks.

Committee:Maxim Likhachev, Chair

Siddhartha Srinivasa

Manuela Veloso

Sachin Chitta, SRI International

Sven Koenig, University of Southern California