Methods and Applications of Analysis

Volume 20 (2013)

Number 4

Special issue dedicated to the 70th birthday of Stanley Osher: Part I

Guest Editor: Chi-Wang Shu, Brown University

Fast numerical methods based on SDES for several problems related to the shortest path

Pages: 353 – 364

DOI: https://dx.doi.org/10.4310/MAA.2013.v20.n4.a3

Authors

Shui-Nee Chow (School of Mathematics, Georgia Institute of Technology, Atlanta, Ga., U.S.A.)

Jun Lu (School of Mathematics, Georgia Institute of Technology, Atlanta, Ga., U.S.A.)

Hao-Min Zhou (School of Mathematics, Georgia Institute of Technology, Atlanta, Ga., U.S.A.)

Abstract

In this paper, we apply the Evolving Junctions on Obstacle Boundaries (E-JOB) method for the shortest path problem developed in [3] and [4] to three related problems: 1) find the shortest path to move a disk, instead of a point, from one position to another one; 2) calculate the Euclidean distance between two sets in $\mathbb{R}^n$; and 3) compute the shortest path in an environment with obstacles appearing or disappearing at arbitrary times. The methods are based on solving finite dimensional stochastic differential equations with given initial values. And they are robust, efficient and easy to implement. We illustrate the methods by some numerical examples.

Keywords

path planning, shortest path, stochastic differential equations, global optimization, robotics

2010 Mathematics Subject Classification

65C30, 65D18, 65K10

Full Text (PDF format)

Published 16 April 2014