RRT Connect

RRT Connect is very similar to RRT, just that the trees emanate from both the start points and end points, unlike RRT where only the start point acts as a root.

First let's look at bool RRT<T>:: plan() of include/RRTConnect_implementation.hpp. The function has a loop with three conditions as described below, with a bottom up approach.

Planning

• Under else, a point is generated randomly anywhere in the region under domain (restricted domain may be used by adjusting the internals of generatePoint() function). Next, the closest node to this point is determined and it is considered to be the parent. The child node is determined by taking a point at the stepLength distance from the closest (parent) node along the line joining the parent node and the randomly determined point. Thus, the tree to which the child is attached is the same as the tree to which the parent node is attached.

• Under else if, a point is generated biased towards the start or the end point alternately everytime the condition is satisfied. This is done by choosing a point closest to the destination (start ot end point) and generating a node at stepLength towards the destination, considering the originally chosen node to be the parent.

• Initially, at the beginning of every iteration, the minimum distance between both the trees are determined. If it is less than the stepLength, the tree is assumed to be complete (it means that if both the trees are merged, we should be able to get a node at the vicinity of another node atleast at a distance of stepLength). If this is true, the iteration is stopped and the path is generated.

Path generation

The nodes where the two trees merge (distance between them <= stepLength) is recovered. From the node attached to the tree towards the end point, the parent of every node is obtained till the end point is reached. Each and every node obtained in the process is pushed to a deque. A similar process is done for the other node. We keep obtaining the parent node and each node is pushed to the front of the deque till the start point is reached. The deque contains the nodes from the start point to the end point of the tree.