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

By Ron Alterovitz, Thierry Siméon, Ken Goldberg. 2007

256 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Control and Systems Engineering, Robotics & Control

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Control and Systems Engineering

In Robotics & Control

Citations in the corpus

Learning Trajectory Preferences for Manipulators via Iterative Improvement (2013, neutral): “Previously both approaches [3, 4, 6, 36] have been studied.”
The Belief Roadmap: Efficient Planning in Belief Space by Factoring the Covariance (2009, background): “MDP-based planning through a Probabilistic Roadmap optimizes over a stochastic action space (Alterovitz et al., 2006, 2007), but still assumes perfect knowledge of the state.”
Integrated task and motion planning in belief space (2013, background): “A number of recent papers (Alterovitz et al., 2007; Levihn et al., 2012) tackle motion planning problems with substantial future-state uncertainty.”
LQG-MP: Optimized path planning for robots with motion uncertainty and imperfect state information (2010, background): “MDPs, for instance, can be used with motion uncertainty to optimize probability of success [1], [30].”
PRM-RL: Long-range Robotic Navigation Tasks by Combining Reinforcement Learning and Sampling-Based Planning (2017, background): “PRMs have also been modified to work with moving obstacles [14], [32], noisy sensors [23], and localization errors [2], [4].”
Motion planning with sequential convex optimization and convex collision checking (2014, background): “Planning constant curvature trajectories for such needles in a plane has also been explored (Alterovitz et al., 2007; Bernardes et al., 2013).”
Learning preferences for manipulation tasks from online coactive feedback (2015, background): “Two effective ways of solving the former problem are either discretizing the state space [3, 7, 59] or directly sampling trajectories from the continuous space [6, 12].”