E-Graphs: Bootstrapping Planning with Experience Graphs

July 2012

E-Graphs: Bootstrapping Planning with Experience Graphs

Authors:

Mike Phillips, Benjamin Cohen, Sachin Chitta, and Maxim Likhachev

Abstract:

Human environments possess a significant amount of underlying structure that is under-utilized in motion planning and mobile manipulation. In domestic environments for example, walls and shelves are static, large objects such as furniture and kitchen appliances most of the time do not move and do not change, and objects are typically placed on a limited number of support surfaces such as tables, countertops or shelves. Motion planning for robots operating in such environments should be able to exploit this structure to improve its performance with each execution of a task. In this paper, we develop an online motion planning approach which learns from its planning episodes (experiences) a graph, an Experience Graph. This graph represents the underlying connectivity of the space required for the execution of the mundane tasks performed by the robot. The planner uses the Experience graph to accelerate its planning efforts whenever possible. On the theoretical side, we show that planning with Experience graphs is complete and provides bounds on sub-optimality with respect to the graph that represents the original planning problem. On the experimental side, we show in simulations and on a physical robot that our approach is particularly suitable for higher-dimensional motion planning tasks such as planning for single-arm manipulation and two armed mobile manipulation. The approach provides significant speedups over planning from scratch and generates predictable motion plans: motions planned from start positions that are close to each other to goal positions that are also close to each other tend to be similar. In addition, we show how the Experience graphs can incorporate solutions from other approaches such as human demonstrations, providing an easy way of bootstrapping motion planning for complex tasks.
@conference{Phillips-2012-109554,
author = {Mike Phillips And Benjamin Cohen And Sachin Chitta And Maxim Likhachev},
title = {E-Graphs: Bootstrapping Planning with Experience Graphs},
booktitle = {Proceedings of Robotics: Science and Systems (RSS '12)},
year = {2012},
month = {July},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.