Reach-avoid semi-Markov decision processes with time-varying obstacles

2025/05/05 by Li, Yanyun, Guo, Xianping
#FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2505.02479

Abstract

We consider the maximal reach-avoid probability to a target in finite horizon for semi-Markov decision processes with time-varying obstacles. Since the variance of the obstacle set, the model \eqrefModel is non-homogeneous. To overcome such difficulty, we construct a related two-dimensional model \eqrefnewModel, and then prove the equivalence between such reach-avoid probability of the original model and that of the related two-dimensional one. For the related two-dimensional model, we analyze some special characteristics of the equivalent reach-avoid probability. On this basis, we provide a special improved value-type algorithm to obtain the equivalent maximal reach-avoid probability and its ε-optimal policy. Then, at the last step of the algorithm, by the equivalence between these two models, we obtain the original maximal reach-avoid probability and its ε-optimal policy for the original model.

Citations

• The minimal hitting probability of continuous-time controlled Markov systems with countable states
• On reachability of Markov decision processes: a novel state-classification-based PI approach
• Improved results on reachable set estimation of singular systems
• Hamilton-Jacobi formulation for reach-avoid differential games

Related

• The Linear Programming Approach to Reach-Avoid Problems for Markov\n Decision Processes
• Reachability and safety objectives in Markov decision processes on long\n but finite horizons
• Upper bounds for the reach-avoid probability via robust optimization
• A learning-based approach to stochastic optimal control under reach-avoid constraint
• Sampling-based Approximations with Quantitative Performance for the Probabilistic Reach-Avoid Problem over General Markov Processes