Finding the Shortest Path by Evolving Junctions on Obstacle Boundaries

Friday, December 7, 2012 - 10:15am - 11:05am
Keller 3-180
Shui-Nee Chow (Georgia Institute of Technology)
We propose a new fast algorithm for finding a global shortest path connecting
two points while avoiding obstacles in a region by solving a finite set of initial value problems for ordinary differential equations under random (white noise) perturbations. The idea is based on the fact that every shortest path possesses a simple and the same geometric structure. This enables us to restrict our search to a set of feasible paths that share a common structure. Each of the search set is based on a union of finite dimensional compact manifolds representing the obstacle boundaries. Comparing to the existing methods, such as combinatorial methods or partial differential equations methods, our algorithm seems to be faster and easier to implement. We can also handle cases in which obstacle shapes are arbitrary and/or the dimension of the base space is three or higher. In addition, we can also consider similar problems with obstacles that are not necessary stationary.

This is joint work with Jun Lu and Haomin Zhou.