Monotone Causality in Opportunistically Stochastic Shortest Path Problems

References

• [1] Ahmed KI (1999) Modeling drivers’ acceleration and lane changing behavior. PhD thesis, Massachusetts Institute of Technology, Cambridge.Google Scholar
• [2] Ahuja R, Magnanti T, Orlin J (1993) Network Flows (Prentice Hall, Inc., Upper Saddle River, NJ).Google Scholar
• [3] Alton K, Mitchell IM (2009) Fast marching methods for stationary Hamilton-Jacobi equations with axis-aligned anisotropy. SIAM J. Numer. Anal. 47(1):363–385.Crossref, Google Scholar
• [4] Alton K, Mitchell IM (2012) An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi Equations. J. Sci. Comput. 51(2):313–348.Crossref, Google Scholar
• [5] Bak S, McLaughlin J, Renzi D (2010) Some improvements for the fast sweeping method. SIAM J. Sci. Comput. 32(5):2853–2874.Crossref, Google Scholar
• [6] Bardi M, Capuzzo-Dolcetta I (1997) Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Modern Birkhäuser Classics, vol. 12 (Springer, New York).Crossref, Google Scholar
• [7] Bardi M, Maldonado López JP (2016) A Dijkstra-type algorithm for dynamic games. Dynam. Games Appl. 6(3):263–276.Crossref, Google Scholar
• [8] Bellman R (1957) Dynamic Programming (Princeton University Press, Princeton, NJ).Google Scholar
• [9] Bertsekas DP (1993) A simple and fast label correcting algorithm for shortest paths. Networks 23(8):703–709.Crossref, Google Scholar
• [10] Bertsekas DP (2001) Dynamic Programming and Optimal Control, 3rd ed., vol. I and II (Athena Scientific, Boston).Google Scholar
• [11] Bertsekas DP (2019) Robust shortest path planning and semicontractive dynamic programming. Naval Res. Logist. 66(1):15–37.Crossref, Google Scholar
• [12] Bertsekas DP, Tsitsiklis JN (1991) An analysis of stochastic shortest path problems. Math. Oper. Res. 16(3):580–595.Link, Google Scholar
• [13] Bertsekas DP, Guerriero F, Musmanno R (1996) Parallel asynchronous label-correcting methods for shortest paths. J. Optim. Theory Appl. 88(2):297–320.Crossref, Google Scholar
• [14] Bornemann F, Rasch C (2006) Finite-element discretization of static Hamilton-Jacobi equations based on a local variational principle. Comput. Visualization Sci. 9:57–69.Crossref, Google Scholar
• [15] Boué M, Dupuis P (1999) Markov chain approximations for deterministic control problems with affine dynamics and quadratic cost in the control. SIAM J. Numer. Anal. 36(3):667–695.Crossref, Google Scholar
• [16] Cameron M (2012) Finding the quasipotential for nongradient SDEs. Physica D Nonlinear Phenomena 241(18):1532–1550.Crossref, Google Scholar
• [17] Chacon A, Vladimirsky A (2012) Fast two-scale methods for Eikonal equations. SIAM J. Sci. Comput. 34(2):A547–A578.Crossref, Google Scholar
• [18] Chacon A, Vladimirsky A (2015) A parallel two-scale method for Eikonal equations. SIAM J. Sci. Comput. 37(1):A156–A180.Crossref, Google Scholar
• [19] Chen Y, Zhao Q, Krishnamurthy V, Djonin D (2007) Transmission scheduling for optimizing sensor network lifetime: A stochastic shortest path approach. IEEE Trans. Signal Processing 55(5):2294–2309.Crossref, Google Scholar
• [20] Clawson Z, Chacon A, Vladimirsky A (2014) Causal domain restriction for Eikonal equations. SIAM J. Sci. Comput. 36(5):A2478–A2505.Crossref, Google Scholar
• [21] Dai P, Goldsmith J (2007) Topological value iteration algorithm for Markov decision processes. Proc. 20th Internat. Joint Conf. Artificial Intelligence IJCAI’07 (Morgan Kaufmann Publishers Inc., San Francisco), 1860–1865.Google Scholar
• [22] Dai P, Mausam, Weld D (2009) Focused topological value iteration. Proc. 19th Internat. Conf. Automated Planning Scheduling (AAAI Press, Palo Alto, CA), 82–89.Google Scholar
• [23] Desquilbet F, Cao J, Cupillard P, Métivier L, Mirebeau JM (2021) Single pass computation of first seismic wave travel time in three dimensional heterogeneous media with general anisotropy. J. Sci. Comput. 89(1):23.Crossref, Google Scholar
• [24] Dial RB (1969) Algorithm 360: Shortest-path forest with topological ordering [H]. Commun. ACM 12(11):632–633.Crossref, Google Scholar
• [25] Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer. Math. 1(1):269–271.Crossref, Google Scholar
• [26] Fainberg EA (1976) On controlled finite state Markov processes with compact control sets. Theory Probab. Appl. 20(4):856–862.Crossref, Google Scholar
• [27] Falcone M, Ferretti R (2014) Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations, Other Titles in Applied Mathematics, vol. 133 (SIAM, Philadelphia).Google Scholar
• [28] Feinberg EA (1992) A Markov decision model of a search process. Contemp. Math. 125:87–96.Crossref, Google Scholar
• [29] Fitch GM, Lee SE, Klauer S, Hankey J, Sudweeks J, Dingus T (2009) Analysis of lane-change crashes and near-crashes. Report, National Highway Traffic Safety Administration, U.S. Department of Transportation, Washington, DC.Google Scholar
• [30] Gipps PG (1986) A model for the structure of lane-changing decisions. Transportation Res. Part B Methodological 20(5):403–414.Crossref, Google Scholar
• [31] Glover F, Glover R, Klingman D (1986) The threshold shortest path algorithm. Networks 14(1):12–37.Google Scholar
• [32] Gonzalez R, Rofman E (1985) On deterministic control problems: An approximation procedure for the optimal cost I. The stationary problem. SIAM J. Control Optim. 23(2):242–266.Crossref, Google Scholar
• [33] Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Sci. Cybernetics 4(2):100–107.Crossref, Google Scholar
• [34] Hong S, Lee SU, Huang X, Khonji M, Alyassi R, Williams BC (2021) An anytime algorithm for chance constrained stochastic shortest path problems and its application to aircraft routing. 2021 IEEE Internat. Conf. Robotics Automation ICRA (IEEE, Piscataway, NJ), 475–481.Google Scholar
• [35] Howard RA (1960) Dynamic Programming and Markov Processes (John Wiley, Hoboken, NJ).Google Scholar
• [36] Jones M, Haas-Heger M, van den Berg J (2022) Lane-level route planning for autonomous vehicles. Algorithmic Foundations Robotics XV Proc. Fifteenth Workshop Algorithmic Foundations Robotics (Springer, Cham, Switzerland), 312–327.Google Scholar
• [37] Jones M, Haas-Heger M, van den Berg J (2024) Lane-level route planning for autonomous vehicles. Internat. J. Robotics Res. 43(9):1425–1440.Crossref, Google Scholar
• [38] Kim S (2001) An O(N) level set method for Eikonal equations. SIAM J. Sci. Comput. 22:2178–2193.Crossref, Google Scholar
• [39] Kimmel R (1998) Fast marching methods on triangulated domains. Proc. Natl. Acad. Sci. USA 95:8431–8435.Crossref, Google Scholar
• [40] Kushner HJ, Dupuis PG (1992) Numerical Methods for Stochastic Control Problems in Continuous Time (Academic Press, New York).Crossref, Google Scholar
• [41] Michon JA (1985) A critical view of driver behavior models: What do we know, what should we do? Evans L, Schwing RC, eds. Human Behavior and Traffic Safety (Springer, Boston), 485–524.Crossref, Google Scholar
• [42] Mirebeau JM (2014) Anisotropic fast-marching on Cartesian grids using lattice basis reduction. SIAM J. Numer. Anal. 52(4):1573–1599.Crossref, Google Scholar
• [43] Mirebeau JM (2014) Efficient fast marching with Finsler metrics. Numer. Math. 126(3):515–557.Crossref, Google Scholar
• [44] Osher S, Fedkiw RP (2001) Level set methods: An overview and some recent results. J. Comput. Phys. 169(2):463–502.Crossref, Google Scholar
• [45] Pape U (1974) Implementation and efficiency of Moore-algorithms for the shortest route problem. Math. Programming 7:212–222.Crossref, Google Scholar
• [46] Patek SD, Bertsekas DP (1999) Stochastic shortest path games. SIAM J. Control Optim. 37(3):804–824.Crossref, Google Scholar
• [47] Piegl L, Tiller W (1996) The NURBS Book (Springer Science & Business Media, Heidelberg, Germany).Google Scholar
• [48] Polymenakos LC, Bertsekas DP, Tsitsiklis JN (1998) Implementation of efficient algorithms for globally optimal trajectories. IEEE Trans. Automatic Control 43(2):278–283.Crossref, Google Scholar
• [49] Sethian JA (1996) A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. USA 93(4):1591–1595.Crossref, Google Scholar
• [50] Sethian JA (1996) Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision and Materials Sciences (Cambridge University Press, Cambridge, UK).Google Scholar
• [51] Sethian JA (1999) Fast marching methods. SIAM Rev. 41(2):199–235.Crossref, Google Scholar
• [52] Sethian JA, Vladimirsky A (2000) Fast methods for the Eikonal and related Hamilton–Jacobi equations on unstructured meshes. Proc. Natl. Acad. Sci. USA 97(11):5699–5703.Crossref, Google Scholar
• [53] Sethian JA, Vladimirsky A (2001) Ordered upwind methods for static Hamilton-Jacobi equations. Proc. Natl. Acad. Sci. USA 98(20):11069–11074.Crossref, Google Scholar
• [54] Sethian JA, Vladimirsky A (2003) Ordered upwind methods for static Hamilton–Jacobi equations: Theory and algorithms. SIAM J. Numer. Anal. 41(1):325–363.Crossref, Google Scholar
• [55] Tsitsiklis J (1994) Efficient algorithms for globally optimal trajectories. Proc. 1994 33rd IEEE Conf. Decision Control, vol. 2 (IEEE, Piscataway, NJ), 1368–1373.Google Scholar
• [56] Tsitsiklis JN (1995) Efficient algorithms for globally optimal trajectories. IEEE Trans. Automatic Control 40(9):1528–1538.Crossref, Google Scholar
• [57] van Nunen JAEE (1976) A set of successive approximation methods for discounted Markovian decision problems. Zeitschrift Fuer Oper. Res. 20:203–208.Google Scholar
• [58] Vladimirsky A (2008) Label-setting methods for multimode stochastic shortest path problems on graphs. Math. Oper. Res. 33(4):821–838.Link, Google Scholar