RRT & RRT*

A Rapidly-exploring Random Tree (RRT) is a data structure and algorithm that randomly searches the state space.

Consider, for example, a naive random tree that is constructed incrementally by selecting a vertex at random, an input at random, and then applying the input to generate a new vertex. Although one might intuitively expect the tree to ``randomly’’ explore the space, there is actually a very strong bias toward places already explored

An RRT works in the opposite manner by being biased toward places not yet visited. RRTs are particularly suited for path planning problems that involve obstacles.

RRT Pseudo Code

G (V, E) //Graph containing edges and vertices

For itr in range (0…N)
Xrand = Random_configuration ()
If Obstacle (Xrand) == True, try again
Xnear = Near (G (V, E), Xrand)

Xnew = New_configuration (Xnear,△q)

Parent (Xnew) = Xnear

Link = {Xnew, Xnear}

G += Xnew
G += Link
Return G

Explanation

First choose a random configuration, Xrand, from configuration space, C. Next select the vertex, Xnear, in the RRT, G, that is closest to Xrand. Finally select a new configuration, Xnew, by moving from Xnear an incremental distance, △q, in the direction of Xrand. This assumes that motion in any direction is possible.

Going as far as we can toward the goal state G, instead of moving a small distance △q is suitable for best case scenario with no obstacles. In the best scenario, the agent reaches the goal very quickly. But when obstacles are present, this can waste time filling out branches that will ultimately fail.

The benefit of the algorithm is its speed. Compared to other path planning algorithms, RRT is fairly quick. Further it does not get trapped in local minima. And works well in high-dimensional spaces. The costliest part of the algorithm is finding its closest neighbor as this process grows depending on the number of vertices that have been generated.

Issues with RRT

It can’t tell when no solution exists; only quits when it exceeds the iteration limit N. The main issue however is the kind of paths generated.

RRT isn’t guaranteed to produce optimal paths unfortunately. RRT*, a better version of RRT, that generates an optimal path eventually. Further RRT produces very cubic graphs. This is expected as nodes are attached to their nearest neighbor. The structural nature of these graphs hinders the probability of finding an optimal path. The cubic nature and irregular paths generated by RRT are addressed by RRT*.

RRT* Pseudo Code

Rad = r
G (V, E) //Graph containing edges and vertices
For itr in range (0…N)
Xrand = Random_configuration ()
If Obstacle (Xrand) == True, try again
Xnear = Nearest (G (V, E), Xrand)

Xnew = New_configuration (Xnear,

)
Xbest, Xneighbors = findNeighbors (G (V, E), Xnew,Radius)

Parent (Xnew) = min_Cost (Xbest, Xnear)

Cost (Xnew) = Distance (Xnew,Parent (Xnew))
For X’ in Xneighbors
If Cost (Xnew) + Distance (Xnew, X’) < Cost (X’)
Cost (X’) = Cost (Xnew) + Distance (Xnew, X’)
Parent (X’) = Xnew

Link = {Xnew, X’}

G += X’
G += Link
Return G

Explanation

RRT* records the distance each vertex has traveled relative to its parent vertex. This is referred to as the cost of the vertex. The RRT* starts with an empty tree and adds a single node corresponding to the initial state. It then builds and refines the tree through a set of N iterations. Like the RRT, the RRT* incrementally builds the tree by sampling a random state Xrand from the obstacle-free space and solving for a trajectory xnew that extends the closest node in the tree Xnear toward the sample. The standard RRT inserts the new node Xnew into the tree with Xnear as its parent and continues with the next iteration. It is here that the operation of the RRT* differs. Rather than choosing the nearest node as the parent, the RRT* considers all nodes in a neighborhood of vertices in a fixed radius from Xnew and evaluates whether Xnear or Xbest as the parent of Xnew. The node that yields the lowest cost becomes the parent as the new node is added to the tree

The second difference RRT* adds is the rewiring of the tree. It then checks each node X’ in the vicinity of Xnew to see whether being rewired to the newly added vertex i.e. Xnew would make their cost decrease. If the cost does indeed decrease, the neighbor is rewired to the newly added vertex, making Xnew its current parent. Thus, RRT* tries to eliminate the connections which have a larger cost by connection via Xnew. This feature makes the path smoother.

Because of the pruning and reconnecting, the tree turns to be more compact and dense which leads to incredibly straight paths. Consequently the overall minimal cost can be obtained. However, the whole time consumption increases.

Drawbacks of RRT*

RRT* suffers from a reduction in performance. Due to examining neighboring nodes and rewiring the graph.