Skip to Main content Skip to Navigation
Conference papers

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

Abstract : We present 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 Infinite Horizon Dynamic Programming in polynomial time to compute stochastically optimal plans. The Stochastic Motion Roadmap (SMRM) 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. In this paper, we formulate SMRM and demonstrate it by generating non-holonomic plans for steerable needles, a new class of medical needles that follow curved paths through soft tissue and can be modeled as a variant of a Dubins car. Using randomized simulations, we show that SMRM is computationally faster than a previously reported MDP method and confirm that SMRM generates motion plans with a significantly higher probability of success compared to shortest-path plans.
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download
Contributor : Thierry Simeon <>
Submitted on : Monday, January 21, 2019 - 10:50:08 AM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM


Files produced by the author(s)


  • HAL Id : hal-01987480, version 1


Ron Alterovitz, Thierry Simeon, Ken Goldberg. The Stochastic Motion Roadmap: A Sampling Framework for Planning with Markov Motion Uncertainty. Robotics: Science and Systems, 2007, Atlanta, United States. ⟨hal-01987480⟩



Record views


Files downloads