In the probabilistic roadmap procedure, the basic idea was to construct a roadmap of the free space consisting of random samples and edges between them. Once that had been constructed, you could connect your desired start and endpoints to this graph and plan a path from one end to the other. Note that the first phase constructs a generic roadmap of the entire free space without considering any particular pair of start and end points. The advantage of this approach is that you can reuse the roadmap over and over again to answer multiple planning problems. There are times though, when you're only interested in answering one specific planning problem. And in those situations, it can be wasteful to construct roadmaps that span the entire free space. In these situations, it may be better to use procedures that explicitly consider the start and the goal locations in the sampling procedure. In this section, we will describe one such approach. The Rapidly Exploring Random Tree or RRT Method. Like the probabilistic roadmap technique, this approach works by generating random samples and connecting them together to form a graph, but the sampling scheme is a bit different. The RRT procedure proceeds by constructing a special kind of graph called a tree, where every node is connected to a single parent and the tree is rooted at a given starting location. The following animation shows how the algorithm evolves to construct a tree in a two-dimensional configuration space containing obstacles. Notice how the graph grows outward organically from the start or seed location at the center of the figure. The basic tree construction algorithm is outlined here in pseudocode. Just as in the PRM procedure, the basic algorithm proceeds by sampling points at random and connecting them to the current graph. The difference lies in the way the construction is carried out. On every iteration, the system generates a random point in the configurations base and checks if there's a free space. It then searches for the closest point in the existing tree and tries to generate a new node in the tree by moving in a straight line between the current vertex of the tree and new random vertex. The distance that it tries to move, delta is a parameter of the algorithm. Note that id the distance between the random configuration and the closest existing node in the tree is less than delta, the algorithm will try to directly connect these two locations. These sequence of figures shows the basic idea. The first slide shows the original tree. Here the red node depicts the new random configuration that the system generates, while y depicts the closest existing node in the tree. This next figure shows a new node z, which is generated by finding a configuration that is distance delta away from y along the line towards x. Finally, this slide shows the new state of the tree after adding the node z. If the procedure does not succeed in this process of stepping towards a random node, it's simply abandons a point and moves on to the next iteration where it will generate a new random sample and try again. Like the PRM algorithm, this procedure assumes that we have some kind of distance function that we can use to measure the effective displacement between two points in configuration space. We also use the same local planner procedure to decide whether two points in configuration space can be linked by a collision free trajectory. It turns out that this procedure for generating random samples is very effective at growing trees that explore and span the free space. Hence, the name, Rapidly Exploring Random Tree or RRT. In order to construct a path between the stark configuration and an end configuration, we actually construct two trees. One rooted at the start location and one at the goal. The procedure then tries to grow both trees until they meet. This animation shows the procedure in action on a two-dimensional configuration space with obstacles. Here, we have outlined this two-tree procedure in pseudocode. On every iteration of the algorithm, the system generates a random sample and tries to grow the current tree towards that random sample. If it succeeds in adding a new node to the tree, it tries to connect that new node to the other tree to form a bridge. Note that if you succeed in finding such a bridge, you can claim success since it means that you have now forged a path between the two trees. On every route of this procedure, it swaps the two trees. That way, both trees are growing towards each other at the same rate. Here's a depiction of a few rounds of this procedure. On the first round, we generate a random sample and grow the blue tree towards that sample as shown here. We then try to link the newly added node to the red tree by seeing if we can link the new node that we just added to the closest node in the red tree. In this case, this linking attempt does not succeed, because of an intervening obstacle. In the next round, we generate a new random sample and try to grow the red tree towards that point. Once we have done this, we turn around and try to connect that point to the blue tree. Here we succeed, so we can now forge her out between the start and the goal locations. Like the probabilistic roadmap procedure, the RRT algorithm is probabilisticly complete. So, there's a certain probability that the method will find the path from the start to the goal if one exists. In practice, the RRT Method is very effective at forging paths in high-dimensional configuration spaces. Another important feature of the RRT approach is it can be used on systems that have dynamic constraints, which limit how they can move. A simple example of this would be a car-like robot where limits on the turning radius imply that it can not translate sideways or turn in place around it's center.
