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

Unlike some slower methods, there is no guarantee that PRM will find a path if one exists. A different kind of guarantee is possible, however. While not complete, PRM is probabilistically complete . As the number of samples increases, the probability of the planner finding a path if one exists approaches 1. For many real-world path-planning problems, the method is very fast and reliable in practice.

PRMS are not the only kind of robotic path planner. Building a roadmap is a time-consuming process. The advantage of doing so is that once the roadmap is built, and assuming that the obstacles are not allowed to move, it can be used to rapidly plan an arbitrary number of paths. If the goal is only to find a single path, however, much of the effort of building the roadmap is wasted. It would be preferable to use a method that is concerned with connecting the start and goal configurations rather than covering the configuration space.

Such a class of sampling-based planners exist, and they are called tree-based or single-query planners. All of these planners take the same overall approach: They begin with the start configuration for the path planning query, and build a tree data structure of samples growing away from it, with a bias toward the goal configuration.

Types of single-query planners

• Expansive Spaces Trees (ESTs) : At each step of building an EST, a node of the tree is selected for expansion. Nodes in more sparsely sampled parts of the configuration space are more likely to be chosen, and some bias may also be present for nodes closer to the goal. A number of samples are made in the vicinity of this node, and those that can be connected to it are added to the tree.
• Rapidly-exploring Random Trees (RRTs) : At each step of RRT-building, a random point is selected in the configuration space, with some bias toward the goal configuration. The nearest node in the tree is found, and a path is created from it toward the random point, either for a set distance or until an obstacle is encountered, whichever comes first. The final collision-free configuration on this path is added to the tree.
• Path-Directed Subdivision Trees (PDSTs) : PDSTs store edges and branch points as their primitive data rather than nodes. It also maintains a cell decomposition of the configuration space and assigns paths to cells. At each step of building the tree, an edge is deterministically selected based on an estimate of how well-sampled its surroundings are (using the cell decomposition), and a random point on the edge is selected for branching. The old edge is divided in two, a new edge is added at the branch point, and the cell decomposition is updated. Thus, the tree expands outward from its starting point, steered toward less well-sampled regions by the cell decomposition. PDSTs are well-suited for robotics problems with realistic and complex physics.

Sampling based planners for proteins

With adjustments, one can apply sampling-based robotic path planning to study protein motion. First and foremost, the configuration space, which sorts conveniently into occupied and free configurations, must be replaced by the more complicated molecular conformation space . Each conformation of a molecule has a free energy , which depends on chemical and physical interactions between its component atoms and those of any other molecules (such as solvent molecules) that may be nearby. This free energy is related to the probability of a protein being in a conformation. Thus, instead of dealing with the binary problem of colliding and free conformations, the conformation space is one of continuously varying probabilities. This problem may be simplified by the use of energy cutoffs, but it is difficult to decide, for any given problem, what energy is so high that a conformation is effectively in collision. Free energy and how it is incorporated into the study of molecular motion is discussed in more detail in Motion Planning for Proteins: Biophysics and Applications .

Recommended reading