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

Citations Over TimeTop 10% of 2007 papers

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 (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 nonholonomic 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.

Related Papers

• → Computing multiple guiding paths for sampling-based motion planning(2019)7 cited
• → A hierarchical and dynamic method to compute harmonic functions for constrained motion planning(2003)22 cited
• → An intelligent configuration-sampling based local motion planner for robotic manipulators(2013)8 cited
• → A novel approach for motion planning(2002)1 cited
• → Path Planning in the Configuration Space of Manipulator Using Potential Field with Information of Pseudo-distance.(1995)1 cited