The linear programming approach to reach-avoid problems for Markov decision processes
From MaRDI portal
Abstract: One of the most fundamental problems in Markov decision processes is analysis and control synthesis for safety and reachability specifications. We consider the stochastic reach-avoid problem, in which the objective is to synthesize a control policy to maximize the probability of reaching a target set at a given time, while staying in a safe set at all prior times. We characterize the solution to this problem through an infinite dimensional linear program. We then develop a tractable approximation to the infinite dimensional linear program through finite dimensional approximations of the decision space and constraints. For a large class of Markov decision processes modeled by Gaussian mixtures kernels we show that through a proper selection of the finite dimensional space, one can further reduce the computational complexity of the resulting linear program. We validate the proposed method and analyze its potential with a series of numerical case studies.
Recommendations
- Verification of discrete time stochastic hybrid systems: a stochastic reach-avoid decision problem
- A stochastic reach-avoid problem with random obstacles
- Safety of stochastic systems: an analytic and computational approach
- Reachability and safety objectives in Markov decision processes on long but finite horizons
- Stochastic system controller synthesis for reachability specifications encoded by random sets
Cited in
(21)- Separable Markovian decision problems. The linear programming method in the multichain case
- Linear programming formulation for non-stationary, finite-horizon Markov decision process models
- Lagrangian approximations for stochastic reachability of a target tube
- Safety of stochastic systems: an analytic and computational approach
- Automated verification and synthesis of stochastic hybrid systems: a survey
- State-based confidence bounds for data-driven stochastic reachability using Hilbert space embeddings
- Similarity quantification for linear stochastic systems: a coupling compensator approach
- Detection-averse optimal and receding-horizon control for Markov decision processes
- Stochastic system controller synthesis for reachability specifications encoded by random sets
- Stochastic reachability of a target tube: theory and computation
- Viability, viscosity, and storage functions in model-predictive control with terminal constraints
- On the computational complexity and generalization properties of multi-stage and stage-wise coupled scenario programs
- Linear programming formulation of MDPs in countable state space: The multichain case
- A Linearly Relaxed Approximate Linear Program for Markov Decision Processes
- Cooperative strategies for two-evader-one-pursuer reach-avoid differential games
- Control synthesis for stochastic systems given automata specifications defined by stochastic sets
- The Reach-Avoid Problem for Constant-Rate Multi-mode Systems
- A linear programming based approach for composite-action Markov decision processes
- Elliptical Slice Sampling for Probabilistic Verification of Stochastic Systems with Signal Temporal Logic Specifications
- Symbolic control for stochastic systems via finite parity games
- Unsafe probabilities and risk contours for stochastic processes using convex optimization
This page was built for publication: The linear programming approach to reach-avoid problems for Markov decision processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5371013)
