RRT/RRT* and Informed RRT* Motion Planning

Implementation of RRT based planning algorithms.

The Rapidly-Exploring Random Tree (RRT) and its enhanced versions, RRT* and Informed RRT*, are pivotal in robotic path planning, especially within complex, high-dimensional spaces. These algorithms facilitate the discovery of feasible and optimized paths for robots navigating through environments with obstacles.

Key Features and Contributions:

Rapidly-Exploring Random Tree (RRT):

  • Purpose: Efficiently explores large, high-dimensional spaces to find feasible paths from a start to a goal position.
  • Methodology: Incrementally builds a tree by randomly sampling points in the space and connecting them to the nearest existing tree node, ensuring rapid exploration.
  • Application: Particularly useful in environments with complex constraints and obstacles, providing a probabilistically complete solution.

RRT-Star

  • Enhancement: Introduces an optimization process that rewires the tree during construction to find not just feasible but optimal paths.
  • Advantages: Maintains the rapid exploration characteristic of RRT while ensuring asymptotic optimality, meaning the solution improves over time.

Informed RRT-Star;

  • mprovement: Focuses the sampling process within an ellipsoidal subset of the space that contains the optimal path, enhancing efficiency.
  • Collision Detection: Efficient algorithms are necessary to verify that nodes and edges are within the free space.
  • Benefits: Accelerates convergence to the optimal path by reducing unnecessary exploration, making it suitable for high-dimensional problems.
Outputs of RRT, RRT-Star, and Informed RRT-Star