  We consider finite horizon reach-avoid problems for discrete time stochastic
systems. Our goal is to construct upper bound functions for the reach-avoid
probability by means of tractable convex optimization problems. We achieve this
by restricting attention to the span of Gaussian radial basis functions and
imposing structural assumptions on the transition kernel of the stochastic
processes as well as the target and safe sets of the reach-avoid problem. In
particular, we require the kernel to be written as a Gaussian mixture density
with each mean of the distribution being affine in the current state and input
and the target and safe sets to be written as intersections of quadratic
inequalities. Taking advantage of these structural assumptions, we formulate a
recursion of semidefinite programs where each step provides an upper bound to
the value function of the reach- avoid problem. The upper bounds provide a
performance metric to which any suboptimal control policy can be compared, and
can themselves be used to construct suboptimal control policies. We illustrate
via numerical examples that even if the resulting bounds are conservative, the
associated control policies achieve higher reach-avoid probabilities than
heuristic controllers for problems of large state-input space dimensions (more
than 20). The results presented in this paper, far exceed the limits of current
approximation methods for reach-avoid problems in the specific class of
stochastic systems considered.
