Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2008 Research Summary

The Stochastic Motion Roadmap: A Sampling Framework for Planning with Markov 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 PRM's, with the well-established theory of MDP's. 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 SMR's generate motion plans with significantly higher probabilities of success compared to traditional shortest-path plans.

Figure 1
Figure 1: The expected results of two plans to steer a needle from an initial configuration (solid square) to a goal (open circle). The needle tip follows arcs of constant curvature in the plane, but its motion is subject to uncertainty that may result in deflections in the path. Evaluation of the probability of success demonstrates that following a traditional minimum length path under motion uncertainty (a) is substantially less likely to succeed than executing actions from an SMR plan that explicitly considers motion uncertainty during the planning stage (b).

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 International Conference on Intelligent Robots and Systems (IROS), August 2005, pp. 120-125.