1996, 1999, 2006
J.A. Sethian

Applications to Robotics and Path Navigation
You are currently in the
topic outlined in red.
Overview of and references for papers on theory Overview of and references for papers on link to 
hyperbolic equations Overview of and references for level_set methods Overview of and references for on stationary 
formulation Overview of and references for Narrow Band formulation Overview of and references for papers on Fast Marching Methods Work on unstructured mesh versions of level set and fast marching methods Coupling interface methods to complex physics Adaptive mesh refinement Applications to semiconductor modeling Applications to geometry Applications to medical imaging Applications to constructing geodesics on surfaces Applications to seismology and travel times Applications to combustion Applications to fluid mechanics Applications to materials sciences Applications to robotics Applications to computer graphics Applications to CAD/CAM Applications to mesh generation

Click on navigable flow chart to go to new topic

click on any text
to go to a new topic.

Fast Marching Methods can be used to solve problems in path planning and robotic navigation. The goal is to move an obstacle in a domain from a specified starting point to end point in the shortest amount of time, taking care to not collide with given obstacles in the field. This can be transformed into an Eikonal equation
| nabla T| = F(x,y,theta)

where T is the arrival time and F(x,y,theta) is the speed at a point (x,y,theta) taken as zero if the object cannot enter that point. This is similar to the application of computing shortest geodesic paths on manifold in that one uses the Fast Marching Method to find the arrival time solution and then traces backwards along the gradient to produce the shortest path. The resulting algorithm is O(N log N), where N is the number of points in the computational domain, making it a highly efficient technique.

Reference 1 below shows how these techniques may be applied to problems in path planning. The interested reader is referred to
a collection of Movies and interactive java applets on path planning and robotic navigation. .

(51K) (71K)
Click on images above for movies of moving a piano in a San Francisco apartment
(see Reference 1 below)

Design your own obstacle course and robot

New Book and Resource on Level Set and Fast Marching Methods


  1. Application of Fast Marching Methods to Path Planning : Kimmel, R., and Sethian, J.A., Center for Pure and Applied Mathematics Report, Univ. of California, Berkeley, May 1996.

    We present a consistent, accurate, and efficient numerical scheme for solving problems in path planning. Our approach is based on Sethian's Fast Marching Method, which is a fast algorithm for solving static Hamilton-Jacobi equations, and is based on entropy-satisfying upwind schemes and fast sorting techniques. The computational complexity of this algorithm is $O(N \log N)$, where $N$ is the total number of points in configuration space. The Fast Marching Method is comparable to graph-search algorithms in complexity, however, because the scheme is stable and consistent. That is, the scheme is guaranteed to converge to the optimal path as the grid is refined. Once the Eikonal equation is solved, the optimal path is extracted using back propagation through the associated field of arrival times. We demonstrate the algorithm by accurately computing optimal paths for problems with 2 and 3 degrees of freedom. The scheme is applicable to path planning problems with a relatively small number of space dimension; in problems with a large number of degrees of freedom, memory limitations are substantial.

    Download publications