Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

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

[1]
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.
[2]
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.
[3]
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.