A multilevel fast-marching method

International audienceWe introduce a new numerical method to approximate the solutions of a class of static Hamilton-Jacobi-Bellman equations arising from minimum time optimal control problems. We rely on several grid approximations, and look for the optimal trajectories by using the coarse grid approximations to reduce the search space for the optimal trajectories in fine grids. This may be thought of as an infinite dimensional version, for PDE, of the "highway hierarchy" method which has been developed to solve discrete shortest path problems. We obtain, for each level, an approximate value function on a sub-domain of the state space. We show that the sequence obtained in this way does converge to the viscosity solution of the HJB equation. Moreover, the number of arithmetic operations that we need to obtain an error of O(ε) is bounded by Õ(1/ε^(2d/(1+β)), to be compared with Õ(1/ε^(2d)) for ordinary grid-based methods. Here β ∈ (0, 1] depends on the "stiffness" of the value function around optimal trajectories, and the notation Õ ignores logarithmic factors. Under a regularity condition on the dynamics, we obtain a bound of Õ(1/ε^((1−β)d)) operations, for β < 1, and this bound becomes O(|log ε|) for β = 1. This allowed us to solve HJB PDE of eikonal type up to dimension 7