Rapidly Exploring Random Tree (+ Intro to Randomized algorithm)
Get FREE domain for 1st year and build your brand new site
In this article, we have presented the idea of Randomized Algorithms and then, dived into Rapidly exploring random trees which is used to efficiently search nonconvex, highdimensional spaces by randomly building a spacefilling tree.
Table of contents:
 Introduction to Randomized algorithm
 Rapidly exploring random trees
Let us get started now.
Introduction to Randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits.
Randomized algorithms have the chances of producing incorrect results. For example, Monte Carlo algorithms whose output may be incorrect with certain probability. Whereas the answer returned by a deterministic algorithm is always expected to be correct, this is not the case for Monte Carlo algorithms. There are few randomized algorithms that always give the correct result or it informs about failure. For example, the LasVegas algorithms.
Following pseudo code can give idea about how lasvegas and probabilistic/randomized algorithms works:
1.Las Vegas algorithm:
findingA_LV(array A, n)
 begin
 repeat
 Randomly select one element out of n elements. Until 'a' is found
 end
These algorithms always end with probability 1. The number of iterations varies and can be arbitrarily large, but the expected number of iterations is
Sum of (i/ 2^{i}) where i tends to infinity from i = 1.
The sum equates to: 2
Since it is constant the expected run time over many calls is O(1).
2.Monte Carlo algorithm:
findingA_MC(array A, n, k)
 begin
 i=0
 repeat
 Randomly select one element out of n elements.
 i = i + 1
 until i=k or 'a' is found
 end
If an ‘a’ is found, the algorithm succeeds, else the algorithm fails. After k iterations, the probability of finding an ‘a’ is
This algorithm does not guarantee success, but the run time is bounded. The number of iterations is always less than or equal to k. Taking k to be constant the run time (expected and absolute) is O(1).
Rapidly exploring random trees
In this article at OpenGenus, we are studying the concept of Rapidly exploring random trees as a randomized datastructure design for a broad class of path planning problems.
A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, highdimensional spaces by randomly building a spacefilling tree.

Start with a source.

Randomly select a position in a given region.

From current position and randomly selected point, find nearest node if present select that node as current node. Else create a new node at predefined stepsize distance from current node.

If the distance of a newly created node is less than a certain threshold to the destination node, we can end our search for the destination. And traverse back from the last node to the source node.

Structure of each node stores its immediate parent and list of immediate childrens.

While travelling back from the destination we follow the parent node.

Loop runs for some already defined number of iterations

Stepsize is set to some minimum value

By controlling number of iteration more approximate path can be found, usually more the number of iterations more approximate ideal path would be.
Algorithm BuildRRT
Input: Initial configuration qinit, number of vertices in RRT K, incremental distance Δq)
Output: RRT graph G
G.init(qinit) for k = 1 to K do
Randomly select position
qrand ← RAND_CONF()
Look for nearestnode from random position, from list of seennodes
qnear ← NEAREST_VERTEX(qrand, G)
If no nearestnode found, create newnode @ Δq distance from currentnode
qnew ← NEW_CONF(qnear, qrand, Δq)
Add newnode to currentnode’s children list and list of seennodes.
This list is traversed to find nodes nearest to a random position.
Select newnode as currentnode
G.add_vertex(qnew) G.add_edge(qnear, qnew) return G
Properties of RRT:
 Expansion of RRT is heavily biased towards unexplored spaces
 An RRT always remain connected
 It is relatively simple and facilitates performance analysis
 The distribution of vertices in RRT reaches sampling distribution leading to consistent behaviour
 Step size delta used to create new node from currentnode/ nearestnode(from seennode list).
With this article at OpenGenus, you must have a strong idea of Rapidly Exploring Random Tree along with the introduction to Randomized algorithms.