The Stochastic Motion Roadmap: A Sampling-Based Framework for Planning with Motion Uncertainty

In many applications of motion planning, the motion of the robot in response to commanded actions cannot be precisely predicted. Whether maneuvering a vehicle over unfamiliar terrain, steering a flexible needle through human tissue to deliver medical treatment, guiding a micro-scale swimming robot through turbulent water, or displaying a folding pathway of a protein polypeptide chain, the underlying motions cannot be predicted with certainty. But in many of these cases, a probabilistic distribution of feasible outcomes in response to commanded actions can be experimentally measured. This stochastic information is fundamentally different from a deterministic motion model. Though planning shortest feasible paths to the goal may be appropriate for problems with deterministic motion, shortest paths may be highly sensitive to uncertainties: the robot may deviate from its expected trajectory when moving through narrow passageways in the configuration space, resulting in collisions.

In this chapter, we develop a new motion planning framework that explicitly considers uncertainty in robot motion at the planning stage. Because future configurations cannot be predicted with certainty, we define a plan by actions that are a function of the robot’s current configuration. A plan execution is successful if the robot does not collide with any obstacles and reaches the goal. The idea is to compute plans that maximize the probability of success.