The mixed approach for motion planning: learning global strategies from a local planner

Abstract

In this paper, we propose a mixed approach for motion planning that decomposes the problem into two levels. At the global level, we build a graph whose nodes represent relatively large cells of the Configuration Space of the robotic system. Adjacent cells are connected by edges weighted by the probability for the local planner to succeed in computing a trajectory from a point in one cell to a goal in the other. These probabilities are used by a minimum cost path finding algorithm to generate subgoals for the local planner. They are updated using a Bayesian rule from the results of the execution of planned trajectories at the local level. At the global level, no geometric information is stored, thus eliminating the expensive transformation of obstacles into the Configuration Space needed by usual global methods. We take advantage of the ability of our local planner to move close to obstacles so that only a crude discretization of the Configuration Space is needed. This makes it possible to apply this technique to robotic systems with a large number of degrees of freedom. In mobile robot applications, sensors being used by the local planner, this method achieves the learning of planning strategies in an unknown environment without building a complete geometric model of the world. 1.