Building and Nevigating a Network of Local Minima

Date of Submission: 
October 16, 1998
Report Number: 
We present a novel method that constructs and navigates a network of local minima of potential fields defined over the multi-dimensional spaces. Such methods has a wide variety of applications such as motion planning. Our method finds local minima and then connects them to form a graph, which we call a roadmap. We use a gradient search scheme to find the local minima very efficiently and accurately. To find a path between the start and goal positions, it is then a simple matter to connect given the start and goal points 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 with very little communication. We present extensive simulation results.