Label-setting methods for multimode stochastic shortest path problems on graphs

DOI10.1287/MOOR.1080.0321MaRDI QIDQ3168996zbMATH OpenOpenAlexFDO

Authors Alexander Vladimirsky

Publication date 27 April 2011

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0707.0335

zbMATH Keywords

dial's methodDijkstra's methoddynamic programmingfast marching methodHamilton-Jacobi PDEslabel-settingoptimal controlstochastic shortest path

Mathematics Subject Classification ID

PDEs in connection with control and optimization (35Q93) Dynamic programming in optimal control and differential games (49L20) Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games (49L25) Numerical mathematical programming methods (65K05) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40) Optimal stochastic control (93E20)

Abstract: Stochastic shortest path (SSP) problems arise in a variety of discrete stochastic control contexts. An optimal solutions to such a problem is typically computed using the value function, which can be found by solving the corresponding dynamic programming equations. In the deterministic case, these equations can be often solved by the highly efficient label-setting methods (such as Dijkstra's and Dial's algorithms). In this paper we define and study a class of Multimode Stochastic Shortest Path problems and develop sufficient conditions for the applicability of label-setting methods. We illustrate our approach on a number of discrete stochastic control examples. We also discuss the relationship of SSPs with discretizations of static Hamilton-Jacobi equations and provide an alternative derivation for several fast (non-iterative) numerical methods for these PDEs.

Recommendations

• scientific article; zbMATH DE number 1300391
• An Analysis of Stochastic Shortest Path Problems
• Stochastic shortest path problems with recourse
• Stochastic shortest path problems with associative accumulative criteria
• A Relaxation-Based Pruning Technique for a Class of Stochastic Shortest Path Problems

Cited in

(10)

• A survey and comparison of discrete and continuous multi-label optimization approaches for the Potts model
• An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations
• Efficient fast marching with Finsler metrics
• Minimal stencils for discretizations of anisotropic PDEs preserving causality or the maximum principle
• Robust shortest path planning and semicontractive dynamic programming
• A Dijkstra-type algorithm for dynamic games
• A Relaxation-Based Pruning Technique for a Class of Stochastic Shortest Path Problems
• Riemannian fast-marching on cartesian grids, using Voronoi's first reduction of quadratic forms
• Optimal control with budget constraints and resets
• Numerical analysis for geometric and nonlinear PDEs. Abstracts from the workshop held February 1--6, 2026

Describes a project that uses

Uses Software

• Algorithm 360

This page was built for publication: Label-setting methods for multimode stochastic shortest path problems on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3168996)