The Rapidly-exploring Random Tree (RRT) algorithm (La Valle, 1998) is a popular method for path planning in robotics and autonomous systems. RRT works by incrementally building a tree of feasible paths from a starting point to a goal point, exploring the space randomly.

The overview of the algorithm is as follows:

  1. Initialization: Start with a tree containing only the initial position (usually the robot itself).
  2. Sampling: Randomly sample a point in a defined space. In the demo, this is sampled uniformly, but other distributions can be used. It is also common to sample the goal point with a certain probability (goal bias). This helps to speed up the convergence of the algorithm towards the goal but could be detrimental in environments with many obstacles.
  3. Steering: Find the nearest node in the tree and steer towards the sampled point. If the new node is valid (i.e., not in collision with obstacles), add it to the tree. By steer, I mean we take a step in the direction of the sampled point, but only move a fixed step size. This helps to ensure that the tree grows incrementally and avoids large jumps that could lead to collisions.
  4. Goal Check: If the new node is close enough to the goal, connect it to the goal and terminate the algorithm.

RRT Planning Demo

I would recommend starting with the initial default values and no obstacles. Then, gradually make it more difficult by adding walls. I like how it gives a good intuition of how the algorithm works. You can see how the tree expands and explores the space, and how it eventually finds a path to the goal. It reminds of a lighting strike ⚡ every time I play with it.

Code

Below is the core logic of the RRT algorithm used in the demo above, I’ve added extra comments at key parts:

function rrtStep() {
  /* Randomly sample a point in the space or the goal point based on goal bias.
   * When we sample the sample the goal, we're effectively trying to take a step
   * towards it. */
  let randPoint = (Math.random() < goalBias) ? goal : { x: Math.random() * canvas.width, y: Math.random() * canvas.height };
  let nearestNode = findNearestNode(randPoint);
  let theta = Math.atan2(randPoint.y - nearestNode.y, randPoint.x - nearestNode.x);
  /* Create a new node in the direction of the sampled point, but only move a
   * fixed step size. This helps to ensure that the tree grows incrementally and
   * avoids large jumps that could lead to collisions. */
  let newNode = new Node(
    nearestNode.x + stepSize * Math.cos(theta),
    nearestNode.y + stepSize * Math.sin(theta),
    nearestNode
  );

  /* This is crucial to not let our robot go through walls. We check if the
   * path from the nearest node to the new node collides with any obstacles.
   * If there's no collision, we add the new node to the tree. */
  if (!isCollision(nearestNode, newNode)) {
    tree.push(newNode);

    // Live draw the new branch
    ctx.strokeStyle = themes[currentTheme].tree;
    ctx.lineWidth = 1.5;
    ctx.beginPath();
    ctx.moveTo(nearestNode.x, nearestNode.y);
    ctx.lineTo(newNode.x, newNode.y);
    ctx.stroke();

    if (distance(newNode, goal) <= stepSize && !isCollision(newNode, goal)) {
      let goalNode = new Node(goal.x, goal.y, newNode);
      tree.push(goalNode);
      reconstructPath(goalNode);
      statusEl.textContent = 'Path Found!';
      isRunning = false;
      startBtn.textContent = 'Start';
      draw(); // Final draw with path
      return;
    }
  }

  iterationCount++;
  iterationCountEl.textContent = iterationCount;
}