Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

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

View Current Project Information

Ron Alterovitz, Thierry Simeon and Ken Goldberg

We introduce a new motion planning framework that explicitly considers uncertainty in robot motion to maximize the probability of avoiding collisions and successfully reaching a goal.

In many motion planning applications ranging from maneuvering vehicles over unfamiliar terrain to steering flexible medical needles through human tissue, the response of a robot to commanded actions cannot be precisely predicted. We propose to build a roadmap by sampling collision-free states in the configuration space and then locally sampling motions at each state to estimate state transition probabilities for each possible action.

Given a query specifying initial and goal configurations, we use the roadmap to formulate a Markov Decision Process (MDP), which we solve using dynamic programming to compute stochastically optimal plans. The Stochastic Motion Roadmap (SMR) thus combines a sampling-based roadmap representation of the configuration space, as in PRMs, with the well-established theory of MDPs.

Generating both states and transition probabilities by sampling is far more flexible than previous Markov motion planning approaches based on problem-specific or grid-based discretizations.

We demonstrate the SMR framework by applying it to non-holonomic steerable needles, a new class of medical needles that follow curved paths through soft tissue, and confirm that SMRs generate motion plans with significantly higher probabilities of success compared to traditional shortest-path plans. We are currently extending the method to consider the 3D motion of steerable needles in tissue volumes with polyhedral obstacles.

Figure 1
Figure 1: Different paths

R. Alterovitz, T. Siméon, and K. Goldberg, "The Stochastic Motion Roadmap: A Sampling Framework for Planning with Markov Motion Uncertainty," Proc. Robotics: Science and Systems, June 2007.
R. Alterovitz, M. Branicky, and K. Goldberg, "Constant-Curvature Motion Planning under Uncertainty with Applications in Image-Guided Medical Needle Steering," Proc. Workshop on the Algorithmic Foundations of Robotics, July 2006.
R. Alterovitz, A. Lim, K. Goldberg, G. S. Chirikjian, and A. M. Okamura, "Steering Flexible Needles Under Markov Motion Uncertainty," Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), August 2005, pp. 120-125.