Probabilistic Roadmaps
Return to the Robotics Research webpage
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.
Working on this project
- Lydia Kavraki - kavraki/AT/cs.rice.edu
Software Available
An implementation of our planner is distributed to be used for research purposes. If you wish to recieve a copy please write to Lydia Kavraki.Maintenance by Kostas Bekris (bekris/AT/cs.rice.edu).