NUMERICAL POTENTIAL-FIELD TECHNIQUES FOR ROBOT PATH PLANNING

A new approach is proposed 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. 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. On the other hand, 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. These techniques 1) construct "good" potential fields and 2) efficiently escape their local minima (i.e., efficiently build the local-minima graph). 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. It has solved a variety of problems, some of which are far beyond the capabilities of previously developed planners.