Probabilistic Roadmap Method (PRM)
The problem
Path planning for robots in known and static workspaces has been studied extensively over the last two decades. Recently there has been renewed interest in developing planners that can be applied to robots with many degrees of freedom (dof), e.g. 5 or more. Indeed, an increasing number of practical problems involve such robots, while very few effective motion planning methods are available to solve them. Besides its use in robotics, planning with many dof is becoming increasingly important in emerging applications, e.g., computer graphic animation, where motion planning can drastically reduce the amount of data input by human animators, and molecular biology, where motion planning can be used to compute motions of molecules (modeled as spatial linkages with many dof) docking against other molecules.
The Probabilistic Roadmap Planner
Among the most efficient methods today, the Probabilistic Roadmap Planner (PRM) is a planner that can compute collision-free paths for robots of virtually any type moving among stationary obstacles (static workspaces). However, PRM is particularly interesting for robots with many dof. The method proceeds in two phases: a learning phase and a query phase.Learning phase. A graph called a roadmap, the nodes of which are collision-free configurations and the edges collision-free paths is built by repeating the two following steps:
Pick a random configuration of the robot, test it for collision and repeat this step until the random configuration is collision-free.
Using a fast local planner, try to connect the former configuration to the roadmap.
Query phase. To find a path between an initial and goal configuration, this step attemps to connect these configurations to the roadmap and searches the roadmap for a sequence of local paths linking these nodes.
An illustration of a probabilistic network.
Notice that the learning and the query phases do not have to be executed sequentially. Instead, they can be interwoven to adapt the size of the roadmap to difficulties encountered during the query phase, thus increasing the learning flavor of our method.
The very small query times make PRM particularly suitable for many-dof robots performing several point-to-point motions in known static workspaces. Examples of tasks meeting these conditions include maintenance of cooling pipes in a nuclear plant, point-to-point welding in car assembly and cleaning of airplane fuselages. In such tasks, many dofs are needed to achieve successive desired configurations of the end-effector while avoiding collisions of the rest of the arm with the complicated workspace. Explicit programming of such robots is tedious and time consuming. An efficient and reliable planner would considerably reduce the programming burden.
A 6 dof rigid robot.
Work on PRM started while Lydia Kavraki was at Stanford University working under the supervision of Jean-Claude Latombe.
A movie (55k QuickTime) showing a 6 dof rigid robot in action.
Extensive description of the approach can be found in the book "Principles of Robot Motion: Theory, Algorithms and Implementations" by Choset, Lynch, Hutchinson, Kantor, Burgard, Kavraki and Thrun.
Analysis
The main objective of the theoretical analysis is to show how probabilistic completeness can be proved for a given choice of planning problem, local planner and configuration generator. A PRM planner is probabilistically complete if for any query, the probability of answering the query incorrectly after building a roadmap goes to zero as the number of milestones goes to infinity. For the purposes of the analysis, a simplified version of PRM is considered which tries all pairs of connections in the roadmap.
There are many avenues one could follow for the analysis:
- PRM operating in
: The simplest method considers a PRM operating in
, where the
local planner is the straight line and configurations are generated
from the uniform distribution. The proof is achieved by tiling the
path with a set of carefully chosen balls and showing that generating
a point in each ball ensures the path has been found. This is the approach followed
in the "Analysis of Probabilistic Roadmaps for Path Planning"
paper by Kavraki, Kolountzakis, Latombe. - Extension to other topologies:
Since most planning problems take place in more complex topologies than
, some generalization is required to address this. The path tiling can
be lifted into a metric space where the local planner tries to connect
points with geodesics and again the configuration generator choses
from a uniform distribution. This technique is useful for proving
probabilistic completeness for a variety of planners for the mover
problem, multiple mover problem and for kinematic chain problems. It
assumes that local planner uses geodesics which may not be desirable or
even possible in an actual implementation.
- General Measure-Theoretic Analysis The final approach takes a more abstract point of view and can show that probabilistic completeness for a query is equivalent to whether or not a random walk planner is probabilistically complete - a property which is more easily checkable. Then in order to show whether or not PRM is probabilistic complete, it is sufficient to show that it can produce a random walk that solves the query. In this generalization, natural extensions such as an asymmetric local planner or non-uniform distribution for configuration sampling are very natural. This is the approach followed in the "Measure Theoretic Analysis of Probabilistic Path Planning" paper by Ladd and Kavraki.
There are additional methods for analysis proposed in the literature, which are covered in the book "Principles of Robot Motion: Theory, Algorithms and Implementations" by Choset, Lynch, Hutchinson, Kantor, Burgard, Kavrak and Thrun. Furthermore, a detailed explanation of the various methods that study the theoretical properties of the PRM is provided in the Analysis of the PRM webpage, prepared by Andrew Ladd. <?php $_SESSION['biblio_filter'] = array(); ?>