×

zbMATH — the first resource for mathematics

An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations. (English) Zbl 1256.65099
The authors present three simple criteria for the \(\delta\)-causality of the discretization of a static convex Hamilton-Jacobi partial differential equation (HJ PDE). They show that with respect to a node, \(\delta\)-anisotropy-angle-boundedness of a simplex \(\delta\)-negative-gradient-acuteness of the simplex, which in turn implies \(\delta\)-causality of the equation for the node value update from the simplex. A monotone acceptance ordered upwind method (MAOUM), that first determines a consistent, \(\delta \)-causal stencil for each grid node and then solves the discrete equation in a single-pass through the nodes, is developed. MAOUM is suited to solving HJ PDEs efficiently on highly-nonuniform grids, since the stencil size adjusts to the level of grid refinement. This strength of MAOUM is demonstrated in a problem with a homogeneous rectangular speed profile and in a robot navigation problem involving wind and obstacles. MAOUM is a Dijkstra-like algorithm that computes the solution in increasing the value order by using a heap to sort proposed node values.

MSC:
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
35F21 Hamilton-Jacobi equations
49L25 Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
Software:
Algorithm 360
PDF BibTeX Cite
Full Text: DOI
References:
[1] Alton, K.: Dijkstra-like ordered upwind methods for solving static Hamilton-Jacobi equations. PhD thesis, University of British Columbia (2010)
[2] 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)
[3] 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) · Zbl 1191.35098
[4] Bak, S., McLaughlin, J., Renzi, D.: Some improvements for the fast sweeping method. SIAM J. Sci. Comput. (2010). doi: 10.1137/090749645 · Zbl 1219.65124
[5] Barles, G., Souganidis, P.E.: Convergence of approximation schemes for fully nonlinear second order equations. Asymptot. Anal. 4, 271–283 (1991) · Zbl 0729.65077
[6] 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) · Zbl 05075074
[7] 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) · Zbl 0933.65073
[8] 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) · Zbl 1089.65084
[9] 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) · Zbl 0755.35015
[10] Cristiani, E.: A fast marching method for Hamilton-Jacobi equations modeling monotone front propagations. J. Sci. Comput. 39(2), 189–205 (2009) · Zbl 1203.65220
[11] Danielsson, P.-E.: Euclidean distance mapping. Comput. Graph. Image Process. 14(3), 227–248 (1980)
[12] Dial, R.B.: Algorithm 360: shortest-path forest with topological ordering. Commun. ACM 12, 632–633 (1969)
[13] Dijkstra, E.W.: A note on two problems in connection with graphs. Numer. Math. 1, 269–271 (1959) · Zbl 0092.16002
[14] 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) · Zbl 1090.35016
[15] Kiefer, J.: Sequential minimax search for a maximum. Proc. Am. Math. Soc. 4, 502–506 (1953) · Zbl 0050.35702
[16] Kimmel, R., Sethian, J.A.: Fast marching methods on triangulated domains. Proc. Natl. Acad. Sci. USA 95, 8341–8435 (1998) · Zbl 0908.65049
[17] Konolige, K.: Saphira robot control system (2011). http://www.ai.sri.com/konolige/saphira/
[18] Maubach, J.M.: Local bisection refinement for n-simplicial grids generated by reflection. J. Sci. Comput. 16(1), 210–227 (1995) · Zbl 0816.65090
[19] Osher, S., Fedkiw, R.P.: Level set methods: An overview and some recent results. J. Comput. Phys. 169(2), 463–502 (2001) · Zbl 0988.65093
[20] 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) · Zbl 1032.49037
[21] Qian, J., Zhang, Y., Zhao, H.: Fast sweeping methods for Eikonal equations on triangulated meshes. SIAM J. Numer. Anal. 45, 83–107 (2007) · Zbl 1149.65087
[22] 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) · Zbl 1115.70005
[23] Sethian, J.A.: A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. USA 93, 1591–1595 (1996) · Zbl 0852.65055
[24] Sethian, J.A.: Fast marching methods. SIAM Rev. 41(2), 199–235 (1999) · Zbl 0926.65106
[25] 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) · Zbl 0963.65076
[26] Sethian, J.A., Vladimirsky, A.: Ordered upwind methods for static Hamilton-Jacobi equations. Proc. Natl. Acad. Sci. USA 98(20), 11069–11074 (2001) · Zbl 1002.65112
[27] 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) · Zbl 1040.65088
[28] 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) · Zbl 1049.35020
[29] Tsitsiklis, J.N.: Efficient algorithms for globally optimal trajectories. In: Proceedings of the 33rd Conference on Decision and Control, pp. 1368–1373 (1994)
[30] Tsitsiklis, J.N.: Efficient algorithms for globally optimal trajectories. IEEE Trans. Autom. Control 40(9), 1528–1538 (1995) · Zbl 0831.93028
[31] Vladimirsky, A.: Label-setting methods for multimode stochastic shortest path problems on graphs. Math. Oper. Res. 33(4), 821–838 (2008) · Zbl 1218.90205
[32] Zhao, H.: A fast sweeping method for Eikonal equations. Math. Comput. 74(250), 603–627 (2004) · Zbl 1070.65113
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.