HISTORY OF THE METHODS/FLOW CHART
ABOUT THE AUTHOR/CV
Ordered Upwind Methods
MotivationFast Marching Methods are designed to track a propagating interface, and find the first arrival of the interface as it passes a point. They also are designed for problems in which the speed of propagation is isotropic: this means that standing at any point, you get to move in any direction with the same speed. That speed can change from point to point, but once you dropped in the domain, there's no preferred direction. This was the setting for the problem of robotic navigation, in which we found the optimal path through and around a set of obstacles.
In optimal control , how much it costs to move depends on both where you are standing and also on the direction in which you chose to move. A good example is sailing: the direction of the wind gives a preferred direction, and your speed depends on which direction you choose. There are many physical examples of this, including preferred directions in the etching of microchips and anisotropic propagation of waves in rock.
Fast Marching Methods have many desirable qualities.
Unfortunately, the Fast Marching Method won't work in this setting. The answer why has to do with how the method really works. In the Fast Marching Method, just like Dijkstra's method, one systematically updates the solution starting from known values, and works from known territory to unknown spots. At each step, one exploits the fact that the perpendicular (or gradient) back to the front is the direction from which information must come. Mathematically, this means that the characteristics are the same as the gradient.
And this isn't true when the speed is not isotropic. If the speed depends on the direction, then one cannot assume that information always arrives at the green spot along a trajectory perpendicular to the evolving front.
The Way Out: Ordered Upwind MethodsThe way out of this, that is, the way to keep the idea of Dijkstra's method and a one-pass algorithm is to keep track of the ratio between the fastest and slowest speed at each point. This anisotropy ratio reveals something important: although the information may not come along a trajectory perpendicular to the front, it can't come from very far away. In the figure below, the only trajectories on the front that can send information to the green spot are those that start no further than the anisotropy ratio times the distance to the closest point.
DetailsOrdered Upwind Methods are a class of Dijkstra-like schemes to approximate the solution of convex static Hamilton-Jacobi equations. They are of order N log N, where N is the number of points in the computational domain, and both semi-Lagrangian and fully Eulerian versions have been developed. Numerical solutions to these problems are typically obtained by solving a large system of coupled non-linear discretized equations. In contrast, Ordered Upwind Methods, use partial information about the characteristic directions, obtained by examining the anisotropy ratio between fastest and slowest speeds to de-couple the non-linear systems, producing one-pass algorithms of greatly reduced computational labor.