Stochastic Ensemble Simulation motion planning in stochastic dynamic environments

Motion planning in stochastic dynamic environments is difficult due to the need for constant plan adjustment caused by the uncertainty of the environment. There are many motion planning problems, including flight coordination and autonomous vehicles, that require an algorithm to predict obstacle motion and plan safely. In this paper, we propose Stochastic Ensemble Simulation (SES)-based planning, a novel framework to efficiently predict and produce safe trajectories in the presence of stochastic obstacles. The stochastic obstacles can be introduced in several ways including stochastic motion or position/speed uncertainty. SES-based planning works by first predicting an obstacle's future position offline through an ensemble of Monte Carlo simulations. These runs simulate the stochastic obstacle dynamics and store the simulation results in temporal snapshots of predicted positions. An online planner then uses this output to identify a predicted collision-free direct path to the goal. If the direct path is not expected to be collision-free, a more expensive tree-based planner is used. Our experiments show SES-based planning outperforms other methods that have high planning success in environments with 900 stochastically moving obstacles. Furthermore, our method plans trajectories with an 80% success rate for a 7 DOF robot in an environment with 250 stochastic moving obstacles and 50 obstacles with speed/position uncertainty. This complex problem is currently beyond the capability of several comparison methods.

I. Introduction

Motion planning in dynamic environments is critical in several applications such as flight coordination [1], autonomous vehicles and human interacting robots [2]. Typical approaches assume knowledge of nearby obstacle position/geometry and dynamically adjustment plans to account for moving obstacles [3]. Performing plan adjustments often proves computationally expensive. In addition, several methods incur an increased computational expense due to the complexity of the robot shape and/or degrees of freedom (DOF) [4] [5].