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.


The Linear Programming Approach to Reach-Avoid Problems for Markov Decision Processes


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

Journal of Artificial Intelligence Research, vol. 60, no. 284, pp. 263, published [OC:09578,03751]

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 numerical case studies.


Type of Publication:


File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@Article { KarEtal:2017:IFA_5348,
    author={N. Kariotoglou and M. Kamgarpour and T.H. Summers and J. Lygeros},
    title={{The Linear Programming Approach to Reach-Avoid Problems for
	  Markov Decision Processes}},
    journal={Journal of Artificial Intelligence Research},
Permanent link