Framework for planning feedback motion strategies based on a random neighborhood graph

Randomized techniques have led to the development of many successful algorithms for path planning in high-dimensional configuration spaces. This paper presents a randomized framework for computing feedback motion strategies, by defining a global navigation function over a collection of spherical balls in the configuration space. If the goal is changed, an updated navigation function can be quickly computed, offering benefits similar to the fast multiple queries permitted by the probabilistic roadmap approach to path planning. Our choice of balls is motivated in part by recent tools from computational geometry which compute point locations and arrangements efficiently without significant dependence on dimension. We present a construction algorithm that includes a Bayesian termination condition based on the probability that a specified fraction of the free space is covered. A basic implementation illustrates the framework for rigid and articulated bodies with up to five-dimensional configuration spaces.