Accession Number : ADA326999

Title :   Numerical Potential Field Techniques for Robot Path Planning.

Descriptive Note : Research rept.,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Barraquand, Jerome ; Langlois, Bruno ; Latombe, Jean-Claude

PDF Url : ADA326999

Report Date : OCT 1989

Pagination or Media Count : 40

Abstract : We propose a new approach to robot path planning which consists of incrementally building a graph connecting the local minima of a potential function 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. We describe a collection of specific techniques that allow to engineer various implementations of our path planning approach. The purpose of these techniques is to (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, in relation to other efficient numerical techniques. We have implemented these techniques in a path planner, which turns out to be both very fast and capable of handling many degrees of freedom. The planner has solved a variety of problems. Some of them are far beyond the capabilities of previously existing planners.

Descriptors :   *GRAPHS, *ROBOTS, *PATHS, *NUMERICAL METHODS AND PROCEDURES, GLOBAL, DISTRIBUTION, EFFICIENCY, DEGREES OF FREEDOM, PLANNING, CONFIGURATIONS, SPACE(ROOM), COLLECTING METHODS.

Subject Categories : Numerical Mathematics
      Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE