  This article presents a novel approach, named MCMP (Monte Carlo Motion
Planning), to the problem of motion planning under uncertainty, i.e., to the
problem of computing a low-cost path that fulfills probabilistic collision
avoidance constraints. MCMP estimates the collision probability (CP) of a given
path by sampling via Monte Carlo the execution of a reference tracking
controller (in this paper we consider LQG). The key algorithmic contribution of
this paper is the design of statistical variance-reduction techniques, namely
control variates and importance sampling, to make such a sampling procedure
amenable to real-time implementation. MCMP applies this CP estimation procedure
to motion planning by iteratively (i) computing an (approximately) optimal path
for the deterministic version of the problem (here, using the FMT* algorithm),
(ii) computing the CP of this path, and (iii) inflating or deflating the
obstacles by a common factor depending on whether the CP is higher or lower
than a target value. The advantages of MCMP are threefold: (i) asymptotic
correctness of CP estimation, as opposed to most current approximations, which,
as shown in this paper, can be off by large multiples and hinder the
computation of feasible plans; (ii) speed and parallelizability, and (iii)
generality, i.e., the approach is applicable to virtually any planning problem
provided that a path tracking controller and a notion of distance to obstacles
in the configuration space are available. Numerical results illustrate the
correctness (in terms of feasibility), efficiency (in terms of path cost), and
computational speed of MCMP.
