August 1994 | L. Kavraki, P. Svestka, J.-C. Latombe, and M. Overmars
This paper presents a probabilistic roadmap (PRM) method for motion planning in high-dimensional configuration spaces. The method consists of two phases: a learning phase and a query phase. In the learning phase, a roadmap is constructed by generating random free configurations and connecting them using a local planner. The roadmap is stored as an undirected graph where nodes represent free configurations and edges represent feasible paths. The learning phase is followed by postprocessing to improve connectivity. In the query phase, any start and goal configurations are connected to nodes in the roadmap, and a path is found by searching the roadmap. The method is general and efficient, applicable to various holonomic robots. It requires selecting parameters that depend on the scene, but these values are relatively easy to choose. The method is applied to planar articulated robots with many degrees of freedom, and experimental results show that path planning can be done quickly after a short learning phase. The method is compared to other path planning approaches, including potential field methods and randomized path planners. The PRM method is shown to be effective for high-dimensional configuration spaces and can be adapted to different types of robots. The method is efficient, with query times in the fraction of a second, making it suitable for many-dof robots performing point-to-point motions in known static workspaces. The paper also discusses the application of the method to various types of robots, including car-like robots, and presents experimental results demonstrating its effectiveness.This paper presents a probabilistic roadmap (PRM) method for motion planning in high-dimensional configuration spaces. The method consists of two phases: a learning phase and a query phase. In the learning phase, a roadmap is constructed by generating random free configurations and connecting them using a local planner. The roadmap is stored as an undirected graph where nodes represent free configurations and edges represent feasible paths. The learning phase is followed by postprocessing to improve connectivity. In the query phase, any start and goal configurations are connected to nodes in the roadmap, and a path is found by searching the roadmap. The method is general and efficient, applicable to various holonomic robots. It requires selecting parameters that depend on the scene, but these values are relatively easy to choose. The method is applied to planar articulated robots with many degrees of freedom, and experimental results show that path planning can be done quickly after a short learning phase. The method is compared to other path planning approaches, including potential field methods and randomized path planners. The PRM method is shown to be effective for high-dimensional configuration spaces and can be adapted to different types of robots. The method is efficient, with query times in the fraction of a second, making it suitable for many-dof robots performing point-to-point motions in known static workspaces. The paper also discusses the application of the method to various types of robots, including car-like robots, and presents experimental results demonstrating its effectiveness.