Robust shortest path planning and semicontractive dynamic programming
From MaRDI portal
Abstract: In this paper we consider shortest path problems in a directed graph where the transitions between nodes are subject to uncertainty. We use a minimax formulation, where the objective is to guarantee that a special destination state is reached with a minimum cost path under the worst possible instance of the uncertainty. Problems of this type arise, among others, in planning and pursuit-evasion contexts, and in model predictive control. Our analysis makes use of the recently developed theory of abstract semicontractive dynamic programming models. We investigate questions of existence and uniqueness of solution of the optimality equation, existence of optimal paths, and the validity of various algorithms patterned after the classical methods of value and policy iteration, as well as a Dijkstra-like algorithm for problems with nonnegative arc lengths.
Recommendations
- Robust shortest path problems
- Robust constrained shortest path problems under budgeted uncertainty
- On the robust shortest path problem.
- Reduction approaches for robust shortest path problems
- An enhanced exact procedure for the absolute robust shortest path problem
- Recoverable robust shortest path problems
- New models for the robust shortest path problem: complexity, resolution and generalization
- An approach to the distributionally robust shortest path problem
- Robust shortest path problems with two uncertain multiplicative cost coefficients
- Lagrangian relaxation for the multiple constrained robust shortest path problem
Cites work
- scientific article; zbMATH DE number 440580 (Why is no real title available?)
- scientific article; zbMATH DE number 3889341 (Why is no real title available?)
- scientific article; zbMATH DE number 3961334 (Why is no real title available?)
- scientific article; zbMATH DE number 3718885 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- scientific article; zbMATH DE number 53999 (Why is no real title available?)
- scientific article; zbMATH DE number 193993 (Why is no real title available?)
- scientific article; zbMATH DE number 3590298 (Why is no real title available?)
- scientific article; zbMATH DE number 3623330 (Why is no real title available?)
- scientific article; zbMATH DE number 1239298 (Why is no real title available?)
- scientific article; zbMATH DE number 1321699 (Why is no real title available?)
- scientific article; zbMATH DE number 1349965 (Why is no real title available?)
- scientific article; zbMATH DE number 665576 (Why is no real title available?)
- scientific article; zbMATH DE number 700091 (Why is no real title available?)
- scientific article; zbMATH DE number 1134975 (Why is no real title available?)
- scientific article; zbMATH DE number 836591 (Why is no real title available?)
- scientific article; zbMATH DE number 3249162 (Why is no real title available?)
- A mixed value and policy iteration method for stochastic control with universally measurable policies
- A numerical approach to the infinite horizon problem of deterministic control theory
- Abstract dynamic programming
- Affine Monotonic and Risk-Sensitive Models in Dynamic Programming
- Algorithms for Countable State Markov Decision Models with an Absorbing Set
- An Analysis of Stochastic Shortest Path Problems
- An Appraisal of Some Shortest-Path Algorithms
- An analysis of transient Markov decision processes
- An exact algorithm for the robust shortest path problem with interval data
- An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations
- Approximate dynamic programming. Solving the curses of dimensionality
- Causal domain restriction for eikonal equations
- Computational methods for risk-averse undiscounted transient Markov models
- Concurrent reachability games
- Constrained model predictive control: Stability and optimality
- Contraction Mappings in the Theory Underlying Dynamic Programming
- Deterministic control of randomly-terminated processes
- Distributed asynchronous computation of fixed points
- Distributed dynamic programming
- Dynamic programming and optimal control. Vol. 1.
- Dynamic programming and optimal control. Vol. 2
- Efficient algorithms for globally optimal trajectories
- Efficient fast marching with Finsler metrics
- Ellipsoidal calculus for estimation and control
- Fast Marching Methods
- Fast two-scale methods for eikonal equations
- Finite state Markovian decision processes
- Global optimal control of perturbed systems
- Implementation of efficient algorithms for globally optimal trajectories
- Label-setting methods for multimode stochastic shortest path problems on graphs
- Markov control process with the expected total cost criterion: Optimality, stability, and transient models
- Model predictive control. With a foreword by M. J. Grimble and M. A. Johnson
- Monotone Mappings with Application in Dynamic Programming
- Negative Dynamic Programming
- On Deterministic Control Problems: an Approximation Procedure for the Optimal Cost II. The Nonstationary Case
- On terminating Markov decision processes with a risk-averse objective function
- On the Speed of Convergence of Value Iteration on Stochastic Shortest-Path Problems
- On the robust shortest path problem.
- Parallel asynchronous label-correcting methods for shortest paths
- Planning Algorithms
- Predictive control with constraints
- Q-learning and enhanced policy iteration in discounted dynamic programming
- Q-learning and policy iteration algorithms for stochastic shortest path problems
- Reinforcement learning. An introduction
- Robust discrete optimization and network flows
- Robust optimization
- Set invariance in control
- Set-theoretic methods in control
- Stochastic Shortest Path Games
- Stochastic optimal control. The discrete time case
- Sufficiently informative functions and the minimax feedback control of uncertain dynamic systems
- The complexity of searching a graph
- Theory and applications of robust optimization
- \(H^ \infty\) - optimal control and related minimax design problems. A dynamic game approach
Cited in
(9)- Model-free optimal control of discrete-time systems with additive and multiplicative noises
- Stable Optimal Control and Semicontractive Dynamic Programming
- Regular policies in abstract dynamic programming
- Approximative policy iteration for exit time feedback control problems driven by stochastic differential equations using tensor train format
- A Dijkstra-type algorithm for dynamic games
- Robust constrained shortest path problems under budgeted uncertainty
- A type of biased consensus-based distributed neural network for path planning
- Robust and distributionally robust shortest path problems: a survey
- Deep reinforcement learning in finite-horizon to explore the most probable transition pathway
This page was built for publication: Robust shortest path planning and semicontractive dynamic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3120605)
