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

详细信息    查看全文

• 作者：Shui-Nee Chow ^{chow@math.gatech.edu} ; Jun Lu ; ^{jlu39@math.gatech.edu} ; Hao-Min Zhou ^{hmzhou@math.gatech.edu}
• 关键词：Shortest path ; Obstacles ; Intermittent diffusion ; Global optimization ; Level set method ; Stochastic differential equations
• 刊名：Applied and Computational Harmonic Analysis
• 出版年：2013
• 出版时间：July, 2013
• 年：2013
• 卷：35
• 期：1
• 页码：165-176
• 全文大小：663 K

文摘

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.