Georgia Institute of Technology College of Sciences

We propose a new fast algorithm for finding the global shortest path connecting two points while avoiding obstacles in a region by solving an initial value problem of ordinary differential equations (ODE's). The idea is based on the factthat the global shortest path possesses a simple geometric structure. This enables us to restrict the search in a set of feasible paths that share the same structure. The resulting search space is reduced to a finite dimensional set. We use a gradient descent strategy based on the intermittent diffusion (ID) in conjunction with the level set framework to obtain the global shortest path by solving a randomly perturbed ODE's with initial conditions.Compared to the existing methods, such as the combinatorial methods or partial differential equation(PDE) methods, our algorithm is faster and easier to implement. We can also handle cases in which obstacles shape are arbitrary and/or the dimension of the base space is three or higher.