Rapidly Exploring Random Tree (+ Intro to Randomized algorithm)

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, high-dimensional spaces by randomly building a space-filling tree.

Table of contents:

  1. Introduction to Randomized algorithm
  2. 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 Las-Vegas algorithms.

Following pseudo code can give idea about how las-vegas and probabilistic/randomized algorithms works:

1.Las Vegas algorithm:

findingA_LV(array A, n)

  1. begin
  2. repeat
  3. Randomly select one element out of n elements. Until 'a' is found
  4. 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/ 2i) 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)

  1. begin
  2. i=0
  3. repeat
  4. Randomly select one element out of n elements.
  5. i = i + 1
  6. until i=k or 'a' is found
  7. 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 data-structure design for a broad class of path planning problems.

A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree.

  1. Start with a source.

  2. Randomly select a position in a given region.

  3. 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 step-size distance from current node.

  4. 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.

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

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

  7. Loop runs for some already defined number of iterations

  8. Step-size is set to some minimum value

  9. 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 nearest-node from random position, from list of seen-nodes

qnear ← NEAREST_VERTEX(qrand, G)

If no nearest-node found, create new-node @ Δq distance from current-node

qnew ← NEW_CONF(qnear, qrand, Δq)

Add new-node to current-node’s children list and list of seen-nodes.
This list is traversed to find nodes nearest to a random position.

Select new-node as current-node

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 current-node/ nearest-node(from seen-node list).

With this article at OpenGenus, you must have a strong idea of Rapidly Exploring Random Tree along with the introduction to Randomized algorithms.