Analytical Potential Fields and Control Strategies for Motion Planning

Date of Submission: 
January 1, 1998
Report Number: 
98-002
Abstract: 
One of the skills that autonomous robots require is the ability to move itself to the goal while avoiding collisions with obstacles. Most previous workers used potential fields or a randomization process in the discretized space to guide robots. But none have combined both methods efficiently due to the inherent inaccuracy of the discretization. We present a novel method for robot motion planning that constructs a network of collision free paths using a randomized search over a piecewise smooth potential field in continuous space. Our method finds local minima and then connects them to form a graph, which we call a roadmap. To find the local minima very efficiently and accurately, we use an analytical gradient search scheme, with extra search steps to handle the points of non-smoothness. The heart of this thesis is the ability to comb out of a local minimum and find a collsion-free path to another local minimum. By this method, we are able to find narrow passageways in configuration space. To find a path between two configurations, it is then a simple matter to connect given start and goal configurations to the roadmap and to use a standard graph search algorithm to search the roadmap. The construction of the roadmap can be done in parallel effciently. It is shown that our method works very well on parallel computers with moderate number of processors.