Experience Graphs: Leveraging Experience in Planning

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 presents a planning framework which can reuse parts of provided paths while generating new paths. In general, provided paths can be arbitrary. For domains where tasks are repetitive though, this framework enjoys dramatic speedups in planning times when provided with previously generated paths. At a high level, the proposed planning framework takes a set of paths which may have been generated by the planner previously, found by some other planner, provided by a human demonstration, or simply paths a person knows to be feasible. These given 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. 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 given 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.