A Basic Implementation of Rapidly Exploring Random Tree

Posted on Edited on Views: Word count in article: 212 Reading time ≈ 1 mins.

Introduction

The Rapidly Exploring Random Tree (RRT) is widely used in robot motion planning. The algorithm was developed by Steven M. LaValle and James J. Kuffner Jr.

For more information about RRT, please refer to the following papers:

The pseudocode of basic RRT is as follows:

Example

Taking the map above as an example, the red circle represents the starting point, the blue circle represents the end point, and the gray rectangles represent obstacles. We need to use the RRT algorithm to plan a path from the starting point to the ending point for the robot while avoiding collisions with obstacles.

Result

The path search results of the algorithm are as follows, where the green line represents the found feasible path.

  • Step size=0.2:
  • Step size=0.5:
  • Step size=1:

Code

The Python code of the basic RRT algorithm is here: PathPlan/RRT/Basic_RRT.py (github.com)