Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


A numerical approach to the reach-avoid problem for Markov decision processes


N. Kariotoglou, M. Kamgarpour, T.H. Summers, J. Lygeros

Engineering Applications of Artificial Intelligence, submitted

An important problem in stochastic control is the so-called reach-avoid problem where one maximizes the probability of reaching a target set while avoiding unsafe subsets of the state-space. We develop a computational method for the finite horizon reach-avoid problem for discrete-time Markov decision processes. Our approach is based on deriving an infinite dimensional linear program whose solution is equivalent to the value function of the reach-avoid problem. We then propose a tractable approximation to the infinite linear program by projecting the value function onto the span of a finite number of basis functions and using randomized sampling to relax the infinite constraints. We illustrate the applicability of the method on a large class of Markov decision processes modeled by Gaussian mixtures and develop benchmark control and robotic problems to explore the computational tractability and accuracy of the proposed approach. To the best of our knowledge, this is the first time that problems up to six state variables and two inputs have been addressed using the reach-avoid formulation. Our results demonstrate that the approximation scheme has considerable computational advantages compared to standard space gridding-based methods.


Type of Publication:


No Files for download available.
% Autogenerated BibTeX entry
@Article { KarEtal:2016:IFA_5348,
    author={N. Kariotoglou and M. Kamgarpour and T.H. Summers and J. Lygeros},
    title={{A numerical approach to the reach-avoid problem for Markov
	  decision processes}},
    journal={Engineering Applications of Artificial Intelligence},
Permanent link