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) [link]. Although the implementation details can become complicated, the basic algorithmic framework is quite straightforward and easy to understand.
- 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*).
PRM implementations vary in terms of how the points are sampled--remember that random does not mean uniformly at random--as well as in how the local planner attempts to connect nearby configurations.
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.
Single-query planners come in three basic types, each of which has been subject to numerous variations and enhancements since its original development:
- 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.
