Path Planning using RRT

Overview

RRT in 2D and 3D

Rapidly-exploring Random Tree (RRT) is an algorithm commonly used in robotics and path planning to efficiently explore high-dimensional spaces. Its primary goal is to find a feasible path from a start point to a goal point while avoiding obstacles. In this project, I programmed RRT in 2d and 3D with collision detection.

How it Works

RRT incrementally builds a tree by randomly sampling points in the search space and connecting them to the nearest point in the tree, ensuring that the expansion is biased towards unexplored areas. As the dimensions increase, RRT becomes mopre computationally expensive, making it difficult to efficiently plan paths in higher dimensions.

Collision detection

Detecting collision with circles and lines

The collision detection in this RRT implementation checks if a proposed tree segment between two points intersects any circular obstacles. For each obstacle, it calculates the distances from the segment’s endpoints to the obstacle's center and determines the closest point on the segment to the center using a parameter u.

u = (c_x - a_x)(b_x - a_x) + (c_y - a_y)(b_y - a_y)] / [(b_x - a_x)² + (b_y - a_y)²

If u is within [0, 1], the closest point lies on the segment; otherwise, it is outside the segment. The method then checks if the distance from the closest point to the obstacle's center is less than the obstacle’s radius, indicating a collision. Additionally, it verifies if either endpoint is inside the obstacle. If a collision is detected, the method stops and returns True; otherwise, it continues checking other obstacles. This logic ensures that no segment intersects any obstacle or the goal without detection.

Shortest Path

If the new node reaches or enters the goal's radius without collisions, the algorithm traces the path back from the goal to the start node using the parent-child relationship stored in a dictionary. The result is a sequence of connected nodes forming a feasible path, approximating the shortest route within the constraints of the step size and random sampling. The algorithm visualizes the tree and path dynamically as it progresses.

RRT in 3 dimensions

The 3D RRT implementation differs from earlier 2D versions by extending the RRT algorithm into a three-dimensional space, where nodes, obstacles, and goals are represented in (x, y, z) coordinates instead of (x, y). This requires changes to several functions: distance calculations now use 3D Euclidean formulas, obstacles are modeled as spheres instead of circles, and collision detection accounts for the shortest distance between a line segment and the center of a sphere.