Consider the problem of finding a unit speed trajectory x(t) that minimizes the integral of a cost function g(x(t)). The numerical solution of this problem involves the solution of the discretization of the eikonal equation, a nonlinear partial differential equation, which is a special case of the Hamilton-Jacobi equation.
Besides the optimal control context, the eikonal equation arises in many other application domains such as computer vision, and semiconductor fabrication. For example, industrial simulations of etching and deposition processes in semiconductor manufacturing require a fast numerical solution of the eikonal equation.
Traditionally, Hamilton-Jacobi equations are solved numerically by iterative methods, which can be time consuming.
The paper
develops a one-pass, non-iterative, algorithm for the numerical solution of the eikonal equation. The algorithm exploits the optimal control interpretation, and emulates Dijkstra's shortest path algorithm. For a domain which is discretized using n grid points, the algorithm provides a solution in time O(n logn).
The same algorithm was later derived by Helmsen, and by Sethian (who introduced the name "fast marching"), using a different approach, based on the the Rouy-Tourin discretization of the eikonal equation.
The Dijkstra algorithm for the shortest path problem is sometimes outperformed in practice by certain label-correcting methods. The paper
suggests that this may be true for trajectory optimization as well.