Abstract
We define a δ-causal discretization of static convex Hamilton-Jacobi Partial Differential Equations (HJ PDEs) such that the solution value at a grid node is dependent only on solution values that are smaller by at least δ. We develop a Monotone Acceptance Ordered Upwind Method (MAOUM) that first determines a consistent, δ-causal stencil for each grid node and then solves the discrete equation in a single-pass through the nodes. MAOUM is suited to solving HJ PDEs efficiently on highly-nonuniform grids, since the stencil size adjusts to the level of grid refinement. MAOUM is a Dijkstra-like algorithm that computes the solution in increasing value order by using a heap to sort proposed node values. If δ>0, MAOUM can be converted to a Dial-like algorithm that sorts and accepts values using buckets of width δ. We present three hierarchical criteria for δ-causality of a node value update from a simplex of nodes in the stencil.
The asymptotic complexity of MAOUM is found to be \(\mathcal {O}((\hat{\Psi}\rho )^{d} N \log N)\), where d is the dimension, \(\hat{\Psi}\) is a measure of anisotropy in the equation, and ρ is a measure of the degree of nonuniformity in the grid. This complexity is a constant factor \((\hat{\Psi}\rho)^{d}\) greater than that of the Dijkstra-like Fast Marching Method, but MAOUM solves a much more general class of static HJ PDEs. Although ρ factors into the asymptotic complexity, experiments demonstrate that grid nonuniformity does not have a large effect on the computational cost of MAOUM in practice. Our experiments indicate that, due to the stencil initialization overhead, MAOUM performs similarly or slightly worse than the comparable Ordered Upwind Method presented in (Sethian and Vladimirsky, SIAM J. Numer. Anal. 41:323, 2003) for two examples on uniform meshes, but considerably better for an example with rectangular speed profile and significant grid refinement around nonsmooth parts of the solution. We test MAOUM on a diverse set of examples, including seismic wavefront propagation and robotic navigation with wind and obstacles.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alton, K.: Dijkstra-like ordered upwind methods for solving static Hamilton-Jacobi equations. PhD thesis, University of British Columbia (2010)
Alton, K., Mitchell, I.: Optimal path planning under different norms in continuous state spaces. In: Proceedings of the International Conference on Robotics and Automation, pp. 866–872 (2006)
Alton, K., Mitchell, I.M.: Fast marching methods for stationary Hamilton-Jacobi equations with axis-aligned anisotropy. SIAM J. Numer. Anal. 43, 363–385 (2008)
Bak, S., McLaughlin, J., Renzi, D.: Some improvements for the fast sweeping method. SIAM J. Sci. Comput. (2010). doi:10.1137/090749645
Barles, G., Souganidis, P.E.: Convergence of approximation schemes for fully nonlinear second order equations. Asymptot. Anal. 4, 271–283 (1991)
Bornemann, F., Rasch, C.: Finite-element discretization of static Hamilton-Jacobi equations based on a local variational principle. Comput. Vis. Sci. 9, 57–69 (2006)
Boue, M., Dupuis, P.: Markov chain approximations for deterministic control problems with affine dynamics and quadratic cost in the control. SIAM J. Numer. Anal. 36(3), 667–695 (1999)
Cecil, T.C., Osher, S.J., Qian, J.: Simplex free adaptive tree fast sweeping and evolution methods for solving level set equations in arbitrary dimension. J. Comput. Phys. 213, 458–473 (2006)
Crandall, M.G., Ishii, H., Lions, P.: User’s guide to viscosity solutions of second order partial differential equations. Bull. Am. Math. Soc. 27(1), 1–67 (1992)
Cristiani, E.: A fast marching method for Hamilton-Jacobi equations modeling monotone front propagations. J. Sci. Comput. 39(2), 189–205 (2009)
Danielsson, P.-E.: Euclidean distance mapping. Comput. Graph. Image Process. 14(3), 227–248 (1980)
Dial, R.B.: Algorithm 360: shortest-path forest with topological ordering. Commun. ACM 12, 632–633 (1969)
Dijkstra, E.W.: A note on two problems in connection with graphs. Numer. Math. 1, 269–271 (1959)
Kao, C.Y., Osher, S., Tsai, Y.: Fast sweeping methods for static Hamilton-Jacobi equations. SIAM J. Numer. Anal. 42(6), 2612–2632 (2004–2005)
Kiefer, J.: Sequential minimax search for a maximum. Proc. Am. Math. Soc. 4, 502–506 (1953)
Kimmel, R., Sethian, J.A.: Fast marching methods on triangulated domains. Proc. Natl. Acad. Sci. USA 95, 8341–8435 (1998)
Konolige, K.: Saphira robot control system (2011). http://www.ai.sri.com/konolige/saphira/
Maubach, J.M.: Local bisection refinement for n-simplicial grids generated by reflection. J. Sci. Comput. 16(1), 210–227 (1995)
Osher, S., Fedkiw, R.P.: Level set methods: An overview and some recent results. J. Comput. Phys. 169(2), 463–502 (2001)
Polymenakos, L.C., Bertsekas, D.P., Tsitsiklis, J.N.: Implementation of efficient algorithms for globally optimal trajectories. IEEE Trans. Autom. Control 43, 278–283 (1998)
Qian, J., Zhang, Y., Zhao, H.: Fast sweeping methods for Eikonal equations on triangulated meshes. SIAM J. Numer. Anal. 45, 83–107 (2007)
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.: Fast marching methods. SIAM Rev. 41(2), 199–235 (1999)
Sethian, J.A., Vladimirsky, A.: Fast methods for Eikonal and related Hamilton-Jacobi equations on unstructured meshes. Proc. Natl. Acad. Sci. USA 97(11), 5699–5703 (2000)
Sethian, J.A., Vladimirsky, A.: Ordered upwind methods for static Hamilton-Jacobi equations. Proc. Natl. Acad. Sci. USA 98(20), 11069–11074 (2001)
Sethian, J.A., Vladimirsky, A.: Ordered upwind methods for static Hamilton-Jacobi equations: Theory and algorithms. SIAM J. Numer. Anal. 41(1), 323–363 (2003)
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(2), 673–694 (2003)
Tsitsiklis, J.N.: Efficient algorithms for globally optimal trajectories. In: Proceedings of the 33rd Conference on Decision and Control, pp. 1368–1373 (1994)
Tsitsiklis, J.N.: Efficient algorithms for globally optimal trajectories. IEEE Trans. Autom. Control 40(9), 1528–1538 (1995)
Vladimirsky, A.: Label-setting methods for multimode stochastic shortest path problems on graphs. Math. Oper. Res. 33(4), 821–838 (2008)
Zhao, H.: A fast sweeping method for Eikonal equations. Math. Comput. 74(250), 603–627 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by a grant from the National Science and Engineering Research Council of Canada.
Rights and permissions
About this article
Cite this article
Alton, K., Mitchell, I.M. An Ordered Upwind Method with Precomputed Stencil and Monotone Node Acceptance for Solving Static Convex Hamilton-Jacobi Equations. J Sci Comput 51, 313–348 (2012). https://doi.org/10.1007/s10915-011-9512-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-011-9512-4