Numerical potential field techniques for robot path planning

An approach to robot path planning that consists of incrementally building a graph connecting the local minima of a potential field defined in the robot's configuration space and concurrently searching this graph until a goal configuration is attained is proposed. Unlike the so-called global path planning methods, this approach does not require an expensive computation step before the search for a path can actually start, and it searches a graph that is usually much smaller than the graph searched by the so-called local methods. A collection of effective techniques to implement this approach is described. They are based on the use of multiscale pyramids of bitmap arrays for representing both the robot's workspace and configuration space. This distributed representation makes it possible to construct potential fields numerically, rather than analytically. A path planner based on these techniques has been implemented. Experiments with this planner show that it is both very fast and capable of handling many degrees of freedom.>