  In this paper, we consider a class of continuous-time, continuous-space
stochastic optimal control problems. Building upon recent advances in Markov
chain approximation methods and sampling-based algorithms for deterministic
path planning, we propose a novel algorithm called the incremental Markov
Decision Process (iMDP) to compute incrementally control policies that
approximate arbitrarily well an optimal policy in terms of the expected cost.
The main idea behind the algorithm is to generate a sequence of finite
discretizations of the original problem through random sampling of the state
space. At each iteration, the discretized problem is a Markov Decision Process
that serves as an incrementally refined model of the original problem. We show
that with probability one, (i) the sequence of the optimal value functions for
each of the discretized problems converges uniformly to the optimal value
function of the original stochastic optimal control problem, and (ii) the
original optimal value function can be computed efficiently in an incremental
manner using asynchronous value iterations. Thus, the proposed algorithm
provides an anytime approach to the computation of optimal control policies of
the continuous problem. The effectiveness of the proposed approach is
demonstrated on motion planning and control problems in cluttered environments
in the presence of process noise.
