A probabilistic learning approach to motion planning

Abstract

In this paper a new paradigm for robot motion planning is proposed. We split the motion planning process into two phases: the learning phase and the query phase. In the learning phase we construct a probabilistic roadmap in configuration space. This roadmap is a graph where nodes correspond to randomly chosen configurations in free space and edges correspond to simple collision-free motions between the nodes. These simple motions are computed using a fast local method. The longer we learn, the denser the roadmap becomes and the better it is for motion planning. In the query phase we can use this roadmap to find paths between different pairs of configurations. If a possible path is not found one can always extend the roadmap by learning further. This gives a very flexible scheme in which learning time and success for queries can be balanced. We will demonstrate the power of the paradigm by applying it to various instances of motion planning : free flying planar robots, plan...