Computation of forward stochastic reach sets: Application to stochastic, dynamic obstacle avoidance

We propose a method to efficiently compute the forward stochastic reach (FSR) set and its probability measure. We consider nonlinear systems with an affine disturbance input, that is stochastic and bounded. This model includes uncontrolled systems and systems with an a priori known controller, and often arises in problems in obstacle avoidance in mobile robotics. When used as a constraint in finite horizon controller synthesis, the FSR set and its probability measure facilitate probabilistic collision avoidance. This is in contrast to the traditional game-theoretic approaches which presume the obstacles are adversaries, generating hard constraints that cannot be violated. We tailor our approach to accommodate the geometry of the rigid body obstacles, and show convexity is assured when the rigid body shape of each obstacle is convex. We extend existing methods for multi-obstacle avoidance through mixed integer programming (with linear robot and obstacle dynamics) to accommodate chance constraints derived using the FSR analysis. We use our method to synthesize a receding horizon controller that drives a robot to a desired goal while avoiding several rigid-body obstacle with stochastic dynamics. Our approach can provide solutions when approaches that presume a worst-case action from the obstacle fail.