0.7 Robotic path planning and protein modeling  (Page 2/3)

In the above figures, the configuration space is two dimensional because the robot has two degrees of freedom. If the heading of the robot mattered (i.e., if the robot were not circular), then a configuration would consist of a position and an orientation. The configuration space would therefore be three dimensional. If the robot had a rotatable joint, this would add another degree of freedom and another dimension to the C-space.

The path planning problem

The robotic path planning problem is, given a robot, a work space, and starting and goal configurations for the robot in the work space, find a collision-free path for the robot from the starting configuration to the goal, if one exists. Otherwise determine that no such path exists. An extensive introduction to the path planning problem and existing solutions may be found in .

Early approaches to path planning included:

• Construction of visibility graphs between the vertices of C-space obstacles.
• Decomposition of the C-space, effectively into subproblems.
• Potential field methods, in which the goal exerts an attractive force on the robot, and the obstacles exert repulsive forces.

Sampling-based path planning

One solution to the scalability problem was to find methods whose run time does not depend on the dimensionality of the C-space, but on some other factor. This led to sampling-based path planning. Rather than making some explicit analysis of the whole C-space, sampling based planners built their representation of C-space by sampling random configurations and using a fast collision checker to determine whether they are in collision.

The basis of many modern sampling-based planners is the Probabilistic Roadmap Method (PRM) . Although the implementation details can become complicated, the basic algorithmic framework is quite straightforward and easy to understand.

The prm algorithmic framework:

• Randomly sample a large number of points in C-space, keeping any that are not in collision. This creates a point set in C-space.
• Using a local planner , attempt to connect pairs of samples that are relatively close to each other by thoroughly sampling and collision checking configurations between them. This creates a graph data structure called a roadmap.
• To query the roadmap, first attempt to connect the start and goal configurations to the existing graph. If that is successful, search the graph for a path from start to goal using any standard graph search method (often A*).