Event Location: NSH 1305

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 for reasonable amounts of time. For instance, much 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. In these tasks, while the pick up location and drop off location is slightly different each time, the overall motion is mostly the same. Another set of scenarios where repetition occurs is when manipulating objects with constraints such as opening doors, cabinets, and drawers. In this thesis we study how to exploit the fact that many tasks have some repetition to them in order to improve planning by learning from past experience or human demonstrations. This includes accelerating motion planning and using demonstrations to learn the representation of the task being solved.

At a high level, the proposed planning framework takes a set of previous plans. They 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 E-Graph. 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. We’ve shown that in repetitive tasks, using Experience Graphs to guide the search to reuse parts of previous paths can lead to a large speedup in planning times. This is done in a way that can provide guarantees on the quality of the solutions produced, even when the prior experiences have arbitrary quality (e.g. a human demonstration). Planning with Experience Graphs can be anytime, meaning solution quality can be improved when there is additional time. We also show how E-Graphs provide a natural framework for efficient replanning when conditions change (as opposed to planning from scratch). Additionally, Experience Graphs provide a way for user demonstrations to be integrated into the planning process and we show how demonstrations can also be leveraged to automatically instantiate relevant degrees of freedom during planning.

Experimentally, we have applied E-Graphs to high dimensional pick and place tasks such as single-arm manipulation and dual-arm mobile manipulation. We’ve also applied it to mobile manipulation tasks with constraints, such as approaching, grasping, and opening a cabinet or drawer. To round out the experiments, we applied it to navigation domains. Most of these experiments have been duplicated in simulation and on a real PR2 robot. Our results show that E-Graphs provide significant speedups over planning from scratch and that the generated paths are consistent: motions planned from similar start and goal states tend to 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.

For the remaining work of my thesis, we propose to generalize Experience Graphs along several dimensions. One of these is parameterization of experiences. Currently, paths in an Experience Graphs can only be reused by guiding the search toward the exact states contained in a prior path. However, often motions can be modified to fit a new scenario. For instance, the robot may have been shown by demonstration how to open a very wide door and a very narrow door. Now, the robot is presented with a medium-width door. The door width is the parameter here and we would like to adapt previous demonstrations to solve the new scenario. Another direction is extending to symbolic planning domains, which is useful for planning high-level tasks. So far, E-Graphs have only been applied to motion planning. Our last research direction is mitigating the effect of misleading experiences on our algorithms. Finally, we will investigate the application of Experience Graphs to assembly tasks. This is a challenging task as it has a large number of discrete variables (the state of the assembly) in addition to the continuous ones typical of motion planning. We believe this task can benefit greatly from using prior experience.

Committee:Maxim Likhachev, Chair

Siddhartha Srinivasa

Manuela Veloso

Sachin Chitta, SRI International

Sven Koenig, University of Southern California