Abstract
In this paper we present a generalization of the Fast Marching method introduced by J.A. Sethian in 1996 to solve numerically the eikonal equation. The new method, named Buffered Fast Marching (BFM), is based on a semi-Lagrangian discretization and is suitable for Hamilton-Jacobi equations modeling monotonically advancing fronts, including Hamilton-Jacobi-Bellman and Hamilton-Jacobi-Isaacs equations which arise in the framework of optimal control problems and differential games. We also show the convergence of the algorithm to the viscosity solution. Finally we present several numerical tests comparing the BFM method with other existing methods.
Similar content being viewed by others
References
Bardi, M., Capuzzo Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Birkhäuser, Boston (1997)
Bardi, M., Falcone, M.: An approximation scheme for the minimum time function. SIAM J. Control Optim. 28, 950–965 (1990)
Bokanowski, O., Cristiani, E., Zidani, H.: An efficient data structure to solve front propagation problems. J. Sci. Comput. (2008, submitted)
Carlini, E., Cristiani, E., Forcadel, N.: A non-monotone Fast Marching scheme for a Hamilton-Jacobi equation modelling dislocation dynamics. In: Bermúdez de Castro, A., Gómez, D., Quintela, P., Salgado, P. (eds.) Proceedings of ENUMATH 2005 (Santiago de Compostela, Spain, July 2005). Numerical Mathematics and Advanced Applications, pp. 723–731. Springer, Berlin (2006)
Carlini, E., Falcone, M., Forcadel, N., Monneau, R.: Convergence of a Generalized Fast Marching Method for an eikonal equation with a velocity changing sign. SIAM J. Numer. Anal. 46, 2920–2952 (2008)
Cristiani, E.: Fast marching and semi-Lagrangian methods for Hamilton-Jacobi equations with applications. Ph.D. thesis, Dipartimento di Metodi e Modelli Matematici per le Scienze Applicate, SAPIENZA—Università di Roma, Rome, Italy (2007)
Cristiani, E., Falcone, M.: Fast semi-Lagrangian schemes for the Eikonal equation and applications. SIAM J. Numer. Anal. 45, 1979–2011 (2007)
Cristiani, E., Falcone, M.: Numerical solution of the Isaacs equation for differential games with state constraints. In: Proceedings of 17th IFAC World Congress (Seoul, Korea, July 6–11, 2008) (2008)
Cristiani, E., Falcone, M.: A characteristics driven Fast Marching method for the Eikonal equation. In: Kunisch, K. Of, G., Steinbach, O. (eds.) ENUMATH 2007, Graz, Austria, September 10–14, 2007. Numerical Mathematics and Advanced Applications, pp. 695–702. Springer, Berlin (2008)
Cristiani, E., Falcone, M.: Fully-discrete schemes for the value function of Pursuit-Evasion games with state constraints. Ann. Int. Soc. Dyn. Games 10, 177–206 (2008, to appear)
Falcone, M.: The minimum time problem and its applications to front propagation. In: Visintin, A., Buttazzo, G. (eds.) Motion by Mean Curvature and Related Topics, pp. 70–88. de Gruyter, Berlin (1994)
Falcone, M.: Numerical methods for differential games based on partial differential equations. Int. Game Theory Rev. 8, 231–272 (2006)
Gremaud, P.A., Kuster, C.M.: Computational study of fast methods for the eikonal equation. SIAM J. Sci. Comput. 27, 1803–1816 (2006)
Hysing, S.-R., Turek, S.: The eikonal equation: numerical efficiency vs. algorithmic complexity on quadrilateral grids. In: Proceedings of ALGORITMY 2005, pp. 22–31 (2005)
Kim, S.: An \(\mathcal{O}(N)\) level set method for eikonal equations. SIAM J. Sci. Comput. 22, 2178–2193 (2001)
Kimmel, R., Sethian, J.A.: Computing geodesic paths on manifold. Proc. Natl. Acad. Sci. USA 95, 8431–8435 (1998)
Kimmel, R., Sethian, J.A.: Optimal algorithm for shape from shading and path planning. J. Math. Imaging Vis. 14, 237–244 (2001)
Prados, E., Soatto, S.: Fast marching method for generic shape from shading. In: Paragios, N., Faugeras, O., Chan, T., Schnoerr, C. (eds.) Proceedings of VLSM 2005 (Third International Workshop on Variational, Geometric and Level Set Methods in Computer Vision), October 2005. Lecture Notes in Computer Science, vol. 3752, pp. 320–331. Springer, Berlin (2005). http://perception.inrialpes.fr/Publications/2005/PS05
Qian, J., Zhang, Y.-T., Zhao, H.-K.: A fast sweeping method for static convex Hamilton-Jacobi equations. J. Sci. Comput. 31, 237–271 (2007)
Sethian, J.A.: A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. USA 93, 1591–1595 (1996)
Sethian, J.A.: Level Set Methods and Fast Marching Methods. Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press, Cambridge (1999)
Sethian, J.A., Vladimirsky, A.: Ordered upwind methods for static Hamilton–Jacobi equations: Theory and algorithms. SIAM J. Numer. Anal. 41, 325–363 (2003)
Spira, A., Kimmel, R.: An efficient solution to the eikonal equation on parametric manifolds. Interfaces Free Bound. 6, 315–327 (2004)
Tsai, Y.-H.R., Cheng, L.-T., Osher, S., Zhao, H.-K.: Fast sweeping algorithms for a class of Hamilton–Jacobi equations. SIAM J. Numer. Anal. 41, 673–694 (2003)
Tsitsiklis, J.N.: Efficient algorithms for globally optimal trajectories. IEEE Trans. Automat. Control 40, 1528–1538 (1995)
Vladimirsky, A.: Static PDEs for time-dependent control problems. Interfaces Free Bound. 8, 281–300 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partially supported by the MIUR Project 2006 “Modellistica Numerica per il Calcolo Scientifico ed Applicazioni Avanzate” and by INRIA–Futurs and ENSTA, Paris, France.
Rights and permissions
About this article
Cite this article
Cristiani, E. A Fast Marching Method for Hamilton-Jacobi Equations Modeling Monotone Front Propagations. J Sci Comput 39, 189–205 (2009). https://doi.org/10.1007/s10915-008-9257-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-008-9257-x