Rapidly-exploring Random Tree
Brief overview
A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. RRTs were developed by Steven M. LaValle and James J. Kuffner Jr. They easily handle problems with obstacles and differential constraints (nonholonomic and kinodynamic) and have been widely used in autonomous robotic motion planning.
Results
- RRT with no obstacles (100 & 1000 iterations)
- RRT with circular obstacles
Algorithm descriptions
- pseudocode for the basic algorithm with no obstacles:
- CHECK_POINT_COLLISION Checks if the point collides with the obstacles
- CHECK_EDGE_COLLISION Checks if the edge collides with the obstacles
- CHECK_COLLISION_FREE_PATH Check if there is a collision-free path to the goal position