Finding the shortest path by evolving junctions on obstacle boundaries (E-JOB): An initial value ODEʼs approach

We propose a new fast algorithm (E-JOB) for finding a global shortest path connecting two points while avoiding obstacles in a region by solving an initial value problem of ordinary differential equations under random perturbations. The idea is based on the fact that every 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 set is a union of sets of finite dimensional compact manifolds. Then, we use a gradient flow, based on an intermittent diffusion method in conjunction with the level set framework, to obtain global shortest paths by solving a system of randomly perturbed ordinary differential equations with initial conditions. Compared to the existing methods, such as combinatorial methods or partial differential equation 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.