Rapidly Exploring Random Trees
Rapidly-exploring Random Tree (RRT) is a sampling-based motion planning algorithm for robots and autonomous systems. It is used to find a path between a start configuration and a goal configuration in high-dimensional configuration spaces.
For single-query methods, Rapidly-exploring Random Trees (RRT) is the most prevalent algorithm. Unlike PRM, RRT can be applied to nonholonomic and kinodynamic planning. Starting from an initial configuration, RRT constructs a tree using random sampling. The tree expands until a predefined time period expires or a fixed number of iterations are executed.
Invented by Steven M. Lavalle.
Resources
- https://arxiv.org/pdf/1105.1186.pdf
- F1TENTH slides for Sampling-Based Motion Planning
- Short 10min YT Intro video
Add start node to tree Repeat n times Generate a random configuration, x If x is in freespace using the CollisionCheck function Find y, the closest node in the tree to the random configuration x If (Dist(x,y)) > delta
F1TENTH
Implementing RRT on the car so it can dynamically avoid obstacles (and other cars?). I think this will take me around 5-6 hours? Good learning experience.
TODO: make self.L a function of the car’s velocity, it does run into the wall from time to time, which is kind of annoying.
Some things:
- Message Throttling the RRT to 10hz
It uses the occupancy grid to figure out what obstacles on in the way, and tries to plan a path around it by expanding a tree from the current position to the target position, which is some fixed point ahead on the racing line.
it’s very popular in the robotics world, and tries to connect a initial point to our goal point, which is our racing line, without colliding into anything on the occupancy grid.
in a random configuration space by expanding the tree. insert the video of RRT
In our case, our initial point is our current position, and our goal point is a point on the racing line that is in front of us.
Issues
Naive RRT creates these jagged path.
RRT* can resolve this, by computing a more efficient path.
Collision checks are done by drawing a straight line between points, and checking if they intersect with any black cells in the occupancy grid.
Okay fiouf, that was lot to take in, now is this going to actually work in the real world?? I have no idea… let’s go test it out on the track!
because all it does is randomly sample points to create this tree structure, until it can connect the start to end point.
But when there is obstacle, we want to plan a path around it and get back on the racing line as soon as possible.