Description Basic Problem
Find a collision-free path from the initial configuration to the goal configuration in the C-space. The Hard part of path planning is to represent the obstacle in the C-space.
Probabilistic RoadMap (PRM) Planning
The method proceeds in two phases: a learning phase and a query phase.
In the learning phase, a probabilistic roadmap is constructed. First generate free configurations by uniform random sampling. Then connect these configurations using some simple, but very fast motion planner, which is local planner. Thus the roadmap is stored as an undirected graph in free C-space.
Local palnner: A simple and intuitive method is to do subdivision in a straight line path. Decompose the motion into the straight line in C-space. Split the line in half, and check for collision. If not, recurse until the distance is small.
In the query phase, the task is to seek a path from the initial configuration to the goal configuration. The approach first finds a path from the start and goal configurations to two nodes of the roadmap (adding the initial and goal configuration to the graph). Then just find a sequence of edges connecting these nodes by graph search algorithm.