Multiple Rapidly-exploring Random Tree (RRT)
% See Usage section in RrtPlanner.m file. This is a basic example of usage:
treesMax = 28; %How many multiple trees (must be at least 2, 1 for source and 1 for destination
seedsPerAxis = 3; %Number of seeds allowed on each axis (discretely placed seeds which idealy helps the RRT expansion)
wallCount = 5; %Number of mock walls to be placed in the environment
rrt = RrtPlanner(treesMax,seedsPerAxis,wallCount)
rrt.SetStart([0 -0.9 0]);
rrt.SetGoal([0 +0.9 0]);
rrt.Run()
plot3(rrt.smoothedPath(:,1),rrt.smoothedPath(:,2),rrt.smoothedPath(:,3),'k*');
delete(rrt);
obstacleFilename = 'obstacles.txt';
seedsPerAxis = 7;
treesMax = seedsPerAxis^3*3+2;
rrt = RrtPlanner(treesMax,seedsPerAxis,obstacleFilename);
rrt.drawingSkipsPerDrawing = 30;
rrt = RrtPlanner(treesMax,seedsPerAxis,obstacleFilename);
rrt.Run()
plot3(rrt.path(:,1),rrt.path(:,2),rrt.path(:,3),'k*');
% To generate an obstacle: create them by specifying rectangular planes as a set of 4 points around the bounds of a rectangle
A-------- B
| |
| |
| |
D---------C
% If this is flat on the z plane at 0.5 then the file would look something like this (with the x,y,z of A, B, C, D on separate lines)
0 0 0.5
1 0 0.5
1 1 0.5
0 1 0.5
A YouTube video of a simple case of this planner can be found here:
http://youtu.be/LodUn86QAfg
About RRTs:
RRTs first published in [1] are randomised planners especially adept at solving difficult,high-dimensional path planning problems. However, environments with low-connectivity due to the presence of obstacles can severely affect convergence. Multiple RRTs have been proposed as a means of addressing this issue, however, this approach can adversely affect computational efficiency.
This paper [2] published by the authors of this Matlab code is the implementation of multiple Rapidly-exploring Random Tree (RRT) algorithm work. This paper introduces a new and simple method which takes advantage of the benefits of multiple trees, whilst ensuring the computational burden of maintaining them is minimised. Results indicate that multiple RRTs are able to reduce the logarithmic complexity of the search, most notably in environments with high obstacle densities.
[1] LaValle, S. M., ‘Rapidly-Exploring Random Trees: A New Tool for Path Planning’, TR 98-11, Computer Science Department, Iowa State University, Oct. 1998.
[2] Matthew Clifton, Gavin Paul, Ngai Kwok, Dikai Liu, Da-Long Wang, "Evaluating Performance of Multiple RRTs", IEEE conference on Mechatronic and Embedded Systems and Application, 2008
Cite As
Gavin (2024). Multiple Rapidly-exploring Random Tree (RRT) (https://www.mathworks.com/matlabcentral/fileexchange/21443-multiple-rapidly-exploring-random-tree-rrt), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxCategories
- AI, Data Science, and Statistics > Statistics and Machine Learning Toolbox > Cluster Analysis and Anomaly Detection > Nearest Neighbors >
Tags
Communities
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.
Version | Published | Release Notes | |
---|---|---|---|
1.4.0.0 | There was a bug in the Connect method that was sometimes creating incorrect connections. Thanks to David for the bug fix. |
||
1.3.0.0 | This is now in Matlab OO (i.e. it is a class).
|
||
1.0.0.0 |