  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.
