Monotone Causality in Opportunistically Stochastic Shortest Path Problems

When traveling through a graph with an accessible deterministic path to a target, is it ever preferable to resort to stochastic node-to-node transitions instead? And, if so, what are the conditions guaranteeing that such a stochastic optimal routing policy can be computed efficiently? We aim to answer these questions here by defining a class of Opportunistically Stochastic Shortest Path (OSSP) problems and deriving sufficient conditions for applicability of noniterative label-setting methods. The usefulness of this framework is demonstrated in two very different contexts: numerical analysis and autonomous vehicle routing. We use OSSPs to derive causality conditions for semi-Lagrangian discretizations of anisotropic Hamilton-Jacobi equations. We also use a Dijkstra-like method to solve OSSPs, optimizing the timing and urgency of lane change maneuvers for an autonomous vehicle navigating road networks with a heterogeneous traffic load.

Funding: Financial support from the Air Force Office of Scientific Research [Grant FA9550-22-1-0528], the Division of Mathematical Sciences [Grants 1645643 and 2111522], and a National Defense Science and Engineering Graduate Fellowship is gratefully acknowledged.