LC2 Seminar – Alexander Vladimirsky (Cornell)

Stochastic Shortest Path (SPP) problems are Markov Decision Processes that have many applications in discrete settings but can also be used to produce discretizations of stationary Hamilton-Jacobi-Bellman PDEs describing the cost of optimal controls in indefinite-horizon problems (where the process terminates upon reaching a prescribed target).  For deterministic shortest path problems on graphs, the solution is easy to find via non-iterative label-setting algorithms such as Dijkstra’s classical method.  Unfortunately, label-setting algorithms are inapplicable to general SSPs, but there are well-known non-trivial examples of SSPs for which they produce the right answer.  This observation led to development of (non-iterative) Dijkstra-like methods for Eikonal PDEs describing isotropic optimal control problems.  Much subsequent work has focused on extending such non-iterative techniques to more general (anisotropic) problems.

We will present a broad subclass of SSPs called Opportunistically-Stochastic Shortest Path (OSSP) problems, for which the applicability of label-setting algorithms is easy to guarantee a priori.  We use OSSPs in two very different applications:  (1) finding a simple geometric characterization of anisotropic min-time control problems in 2D and 3D, for which label-setting methods are applicable; and (2) introducing a new stochastic model of optimal lane-switching by autonomous vehicles and showing that it can be solved by a Dijkstra-like method.  Both of these are joint work with Ph.D. student Mallory Gaspard.

Alex Vladimirsky is an applied mathematician at Cornell University, whose research interests include numerical analysis, nonlinear PDEs, dynamical systems, optimal control & differential games, mathematical biology, and algorithms on graphs. His past and current projects include numerical methods for (& homogenization of) Hamilton-Jacobi PDEs, multiobjective & randomly-terminated optimal control, uncertainty quantification in randomly-switching systems, multipopulation mean-field games, surveillance-evasion games under uncertainty, inverse problems in geophysical explorations, dimensional reduction in turbulent combustion, approximation of invariant manifolds, macro-scale models of pedestrian interactions, optimization of drug therapies for cancer patients, models of microbial competition, sailboat navigation under wind-pattern uncertainty, behavioral ecology, immunology, and traffic engineering. Vladimirsky’s research has been partially funded by the US National Science Foundation, the Air Force Office of Scientific, and the Simons Foundation. He looks forward to spending the 2025-26 sabbatical year as a Royal Society Wolfson Visiting Fellow at Imperial College London.