The purpose of this page is provide an overview of an implementation of a sampling based path planning algorithm using rapidly exploring random trees (RRT). The path planning algorithm was implemented on the OMAPL138/F28335 based robots built by the U of I Control Systems Laboratory for use in GE423 - Mechatronics and research projects. Path planning using a rapidly exploring random tree is only one example of a sampling based planning algorithm. Additionally, many other strategies exist for motion and path planning that are not based on sampling within a configuration space. Students of GE423 are encouraged to explore implementation of a path planning algorithm for their final project competition.
From the video, it is clear that this type of path planning does not provide an optimal path to the goal. However, if a path exists, as the number of samples taken approaches infinity, the probability of finding a path approaches one.
Sampling and Building the Tree
The robot in this implementation is assumed to be constrained to a 12' x 16' space. In the following screenshots, the thick black lines represent walls which the robot may not pass through. Obstacles in the area were assumed to be 2' sections of plywood located on the 1' grid. These obstacles were represented in code by multiple tiles of small circles. For each path planning cycle, the robot's position and the goal position are represented by a green and red circle, respectively.
The path is planned by building a tree starting from the position of the robot. When a point in the space is randomly sampled, it is checked if that point collides with an obstacle in the space. If the sampled point has no collisions, it is then checked if the straight line path between the sampled point and the nearest existing point in the tree has any collisions. If this straight line path has no collisions, the sampled point is added to the tree with the nearest point as its parent node. If there is a collision, this point is thrown out. Examples of these three outcomes can be seen below.
Each time after a node is added to the tree and than node is less than some threshold distance from the goal position, it is checked if the goal can be reach in a straight line path from the added node. If the goal position is reachable, the goal position is added to the tree with the recently added node as its parent. At this point, the path planning is complete. If the goal position is still unreachable, additional points are sampled. An example of a completed path is shown below. Additionally, the expansion of the tree in this course is shown for multiple iterations as well.
After a path is found, path smoothing can be applied to make a smoother, more direct route to the goal. This can be done iteratively by sampling points between nodes on the overall path and then checking if two points could be connected to reduce the overall path length.
To run the Matlab code, download both of the files below. With the files in the same directory, run the RRTpathplan.m script. Add breakpoints to better understand how the algorithm is working.
Precision. Accuracy. Speed.
Control Systems Instructional Laboratory
University of Illinois
1406 W Green
Urbana, IL 61801-2307