  Robust motion planning entails computing a global motion plan that is safe
under all possible uncertainty realizations, be it in the system dynamics, the
robot's initial position, or with respect to external disturbances. Current
approaches for robust motion planning either lack theoretical guarantees, or
make restrictive assumptions on the system dynamics and uncertainty
distributions. In this paper, we address these limitations by proposing the
robust rapidly-exploring random-tree (Robust-RRT) algorithm, which integrates
forward reachability analysis directly into sampling-based control trajectory
synthesis. We prove that Robust-RRT is probabilistically complete (PC) for
nonlinear Lipschitz continuous dynamical systems with bounded uncertainty. In
other words, Robust-RRT eventually finds a robust motion plan that is feasible
under all possible uncertainty realizations assuming such a plan exists. Our
analysis applies even to unstable systems that admit only short-horizon
feasible plans; this is because we explicitly consider the time evolution of
reachable sets along control trajectories. Thanks to the explicit consideration
of time dependency in our analysis, PC applies to unstabilizable systems. To
the best of our knowledge, this is the most general PC proof for robust
sampling-based motion planning, in terms of the types of uncertainties and
dynamical systems it can handle. Considering that an exact computation of
reachable sets can be computationally expensive for some dynamical systems, we
incorporate sampling-based reachability analysis into Robust-RRT and
demonstrate our robust planner on nonlinear, underactuated, and hybrid systems.
