Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces

Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces

August 1994 | L. Kavraki, P. Svestka, J.-C. Latombe, and M. Overmars
The paper presents a new motion planning method for robots in static workspaces, focusing on robots with many degrees of freedom (dof). The method consists of two phases: a learning phase and a query phase. In the learning phase, a probabilistic roadmap is constructed by generating random configurations and connecting them using a simple local planner. The roadmap is stored as an undirected graph where nodes represent collision-free configurations and edges represent feasible paths. In the query phase, the method connects the start and goal configurations to nodes in the roadmap and searches for a path between them. The method is general and easy to implement, suitable for various types of holonomic robots. Parameters such as the duration of the learning phase can be adjusted based on the specific scene, and efficiency can be improved by tailoring components like the local planner to the robot. Experimental results show that the method can plan paths for planar articulated robots with many dofs in a fraction of a second, making it suitable for tasks like maintenance of cooling pipes in nuclear plants or point-to-point welding in car assembly. The paper also discusses the relation to previous work and provides details on the general method, including the construction and expansion steps of the learning phase and the query phase.The paper presents a new motion planning method for robots in static workspaces, focusing on robots with many degrees of freedom (dof). The method consists of two phases: a learning phase and a query phase. In the learning phase, a probabilistic roadmap is constructed by generating random configurations and connecting them using a simple local planner. The roadmap is stored as an undirected graph where nodes represent collision-free configurations and edges represent feasible paths. In the query phase, the method connects the start and goal configurations to nodes in the roadmap and searches for a path between them. The method is general and easy to implement, suitable for various types of holonomic robots. Parameters such as the duration of the learning phase can be adjusted based on the specific scene, and efficiency can be improved by tailoring components like the local planner to the robot. Experimental results show that the method can plan paths for planar articulated robots with many dofs in a fraction of a second, making it suitable for tasks like maintenance of cooling pipes in nuclear plants or point-to-point welding in car assembly. The paper also discusses the relation to previous work and provides details on the general method, including the construction and expansion steps of the learning phase and the query phase.
Reach us at info@study.space
[slides and audio] Probabilistic roadmaps for path planning in high-dimensional configuration spaces