Monotone Causality in Opportunistically Stochastic Shortest Path Problems

Mallory Gaspard (Center for Applied Mathematics, Cornell University)

Opportunistically Stochastic Shortest Path Problems (OSSPs) are useful modeling tools when the decision-maker has a choice between making a deterministic transition or a stochastic transition to another node in the graph. While OSSPs are applicable to a variety of real-world applications, an important setting in which they arise are semi-Lagrangian (SL) discretizations of anisotropic Hamilton-Jacobi-Bellman (HJB) Equations. Numerically solving these HJB equations can be challenging due to the anisotropy present, and it is natural to seek methods which can produce quick yet correct results. In this talk, we present a sharp causality condition on the OSSPs’ transition cost function which guarantees the use of fast label-setting methods (e.g., Dijkstra’s Method or Dial’s Method) to solve general OSSPs. In the context of continuous optimal control with anisotropic dynamics whose corresponding HJB equation is discretized on a two-dimensional simplical mesh, we then present and prove a condition on the speed profile which guarantees that the transition cost function is causal and numerical methods built on label-setting algorithms to solve the discretized HJB equation are applicable. Joint work with Alex Vladimirsky.