RRT, RRT* & Random Trees
Вставка
- Опубліковано 27 чер 2024
- Lecture 24 of Intro to Robotics @ University of Houston.
using demonstrations.wolfram.com/Rap... by Aaron Becker and Li Huang
A rapidly exploring random tree (RRT) grows a tree rooted at a start node. RRTs are designed to efficiently explore paths in a high-dimensional space. This lecture compares random trees (RTs), RRTs and RRT*. An RT selects a node at random from the tree and adds an edge in a random direction, but an RRT first selects a goal point, then tries to add an edge from the closest node in the tree toward the goal point. RRT* improves on this by rewiring the tree to form shortest paths.
We show a tree defined by red nodes with black edges. Obstacles are drawn in blue, and the goal position is indicated by a locator surrounded by a disc of radius goal radius. This is yellow before the goal is reached and turns green after success. A tree generated by random motion from a randomly selected tree node does not explore very far. A rapidly exploring random tree (RRT) first selects a goal point (drawn in green), then tries to add an edge from the closest node in the tree (blue) toward the goal point. This results in a tree that tends to quickly explore the space, because search is biased into the largest Voronoi regions of a graph defined by the tree. RRT* improves on this by rewiring the tree to form shortest paths. RRT* converges to the shortest path, at the cost of more computation. All three trees are probabilistically complete, meaning if a nonzero width path exists, the tree will eventually find the path.
In general, the path lengths for RRT* are shorter than RRT. The online Mathematica Demonstration lets you try changing the obstacle type, the tree type and the goal location.
RRTs were developed by S. M. LaValle and J. J. Kuffner Jr. in [1] and [2]. They are often used for robot motion planning, especially for high-dimensional problems with obstacles. The RRT* variant was introduced by S. Karaman and E. Frazolli [3].
References
[1] S. M. LaValle, Rapidly-Exploring Random Trees: A New Tool for Path Planning, Computer Science Department, Iowa State University (TR 98-11), 1998.
[2] S. M. LaValle and J. J. Kuffner, Jr., "Randomized Kinodynamic Planning," The International Journal of Robotics Research, 20(5), 2001 pp. 378\[Dash]400. doi:10.1177/02783640122067453.
[3] S. Karaman and E. Frazzoli, "Sampling-Based Algorithms for Optimal Motion Planning," The International Journal of Robotics Research, 30(7), 2011 pp. 846\[Dash]894. doi:10.1177/0278364911406761.
[4] Wikipedia. "Rapidly-Exploring Random Tree." (Jan 11, 2018) en.wikipedia.org/wiki/Rapidly-exploring_random_tree.
This work was supported by the National Science Foundation under Grant No. IIS-1646607 nsf.gov/awardsearch/showAward...
Full Playlist "Intro to Robotics": • Intro2Robotics Lecture... - Навчання та стиль
Thank you for the video, this helped me a lot in three different lectures at once!
Your style of explaining and presenting is great!
@Talon24 your words are kind! This semester due to COVID I'm teaching online, so will load all my Intro to Robotics lecture here. Hopefully it will be helpful!
The visualization and explanation are just great, thanks a lot for sharing!!
Its a great video for me to learn robot motion planning. Thanks a lot, only these kind of videos make youtube worth watching.
Great demo, high quality as usual, love your patience and tone when you speak prof❤
Great UI to demonstrate the algos
Thank you! Best explanation on the internet!
This is great. Please do more videos on motion planning.
Thank you!
Was looking for rrts, somehow found this, liked it
If there are other videos you'd like, let me know
Very Good Description of the Concept-Need to understand program structure
You can follow the link to see the code used for the video.
I searched youtube for "planting rows of trees vs random placement" referring to physical trees and was pleasantly surprised by this video.
Funny! Here in Texas the commercial pecan groves are in straight rows. I hope you find your desired video.
The UI makes the whole thing clear
Thanks Ethan -- feel free to try the code.
Hi, great video with magnificent visualization. I am wondering if the RRT* algorithm could be adapted to work with non-binary cells (i.e. instead of "obstacle"/"non obstacle", we would have some sort of cost function for each cell)?
@Vellyxenya, since each node in the RRT already has a 'cost' that represents the cost to get to the node, this would be a way that you could add in penalties for different regions of the workspace. My implementation sets this cost as the Euclidean distance along each edge, but it would be reasonable to augment this with a penalty for the node. However, since the robot moves between edges (doesn't jump from nodes to node) you need to think about cost as you move along that edge between the nodes. There are ways to do this, but they often require more computation.
@@AaronBecker Hi and thank you for the swift answer! Great idea I will try implementing that, maybe by interpolating the cost along the edges, or keep it at the nodes if the cost function is smooth enough, I guess I will try and see what performances/precision I get with both implementations :)
Hello there Aaron, I recently had an assignment to create an RRT algorithm in matlab. With some blood and sweat I finally managed to make something half-decent. But it was just terrible at navigating through the cluttered maze we were provided.
Something I noticed is that my non-biased RRT keeps validating new nodes very close to old ones, sometimes completely flooding an area while very slowly moving toward the goal location. But your RRT algorithm seems to always move away from previously generated nodes, how is that?
It is my understanding that there is nothing stopping the randomly generating nodes from being generated in already heavily explored places, and there is also nothing stopping the algorithm from attempting to find the closest node to it. But in your case the generated nodes seem to avoid heavily populated areas, super interesting!
You are right that "nothing stop[s] the randomly generating nodes from being generated in already heavily explored places", but if the nodes are randomly generated then they ought to be spread. I suggest three things: (1) generate 1000 random nodes, and check that they are actually well spread in your workspace. (2) make your step length (the distance your local planner can move toward a node) large, perhaps 3% of a workspace edge and make sure that new nodes can grow this distance. (3) visually check that the closest node is being expanded.
great!
Thank you for this lecture, it's really helpful !
I have a questions (i'm new to this): Are there any disadvantages of RRT* ? (it's limitations or maybe compare to other methods )
RRT* is slower to compute than RRT. Also RRT and RRT* are good for motion planning from a given state, but if you start in a different state, you have to replan from scratch. Other algorithms (for example, Probabilistic Roadmap Methods) are able to make a global planner that can start from any state.
nice
What algorithm was used to find the path from the start node to the end node? Dijkstra's?
@Vashini Kannan -- since the RRT is stored as a 'tree' data structure, there is no need to use Dijkstras. You simply start at the end node, and keep moving to the 'parent' of your current node until you reach the start node. In the data structure I made (see link above), verts[[n, 2]] is the parent of node n. (Each entry in verts: { the xy location, parent, IDnum, cost2go, childrenlist}). When I do PRM (demonstrations.wolfram.com/ProbabilisticRoadmapMethodForRobotArm/ ) there is no tree. To search the PRM graph I use an A* search, since it is faster than Dijkstras.
Got it. Thank you!
Hey Aron,
thank you for the video. I would like to ask a question. if I want to implement this in real time or real world scenario how can I do? like if I have a car controlled by Arduino or raspberry pi, how can I implement this logic? I created a png image with all obstacles and available spaces. can you tell me how can I implement RRT?
Cars are well-suited for RRT. The new versions of Matlab have planners just for this. However, there are better ways. You can also check out my video on "Reeds shepp car" for a relatively straightforward implementation of this.
nearest node to what? the wall? neareast node to previous node extented? if that were the case, why is it not one linear chain? how does it branch off?
Joe, a random configuration is generated (green dot), and the nearest node in the TREE is extended. This is the unique feature that makes the RRT branch off. There are many pretty images of RRTs growing at msl.cs.uiuc.edu/rrt/gallery.html, and you will see that in a 2D configuration space the RRT tends to have 3 main branches. Does this answer your question?
How does this work with a non-point system to explore... e.g. a robot has a geometric shape which rotates as well as moves linearaly, not a single point in space
Short answer: that configuration space is 3D. Any configuration is still a point in this 3D space, with coordinates (x,y,theta). My favorite example of this is ua-cam.com/video/SBFwgR4K1Gk/v-deo.html, which has an algorithm that maps obstacles in the workspace to obstacle regions in the 3D configuration space.
Longer answer: msl.cs.uiuc.edu/rrt/gallery_rigid.html is an animation of a rigid body that rotates and moves linearly, but the RRT shown is a projection from 3D into the 2D vertices. RRTs work for configuration spaces of any dimension (a 6-link robot is in a 6-dimension configuration space. If you bolt that arm to a mobile robot that can roll and turn in a planar environment, the new configuration space is 9-dimensional, which is 3 for the mobile robot's x, y, and theta and 6 for the robot.) RRTs are designed for high-dimensional state spaces because they efficiently spread out into high dimensional state spaces. Unfortunately, drawing the RRT is hard for high dimensions -- the best we can do is to project the high-dimension tree into 3 dimensions.
May you do a comparison of RRT and A*?
Chyza is right. A* can be compared to DFS and BFS, but not to a path planner without a graph.
@@AaronBecker What is DFS and BFS ?
@@hadjer168 Depth-first search en.wikipedia.org/wiki/Depth-first_search and Breadth-first search en.wikipedia.org/wiki/Breadth-first_search are algorithms for searching a graph. They have different properties. We use BFS because it quits as soon as it finds the shortest path, while DFS needs to fully explore the graph before it can return the shortest path.
@@AaronBecker thank you.
The exploration bias is used for what?
The exploration bias tries to expand the tree to the goal state. If there are no obstacles in the way, this will quickly find a solution. The authors of RRT reported that doing this 5 to 16%of the time improved performance.
thanks, this was great!
Glad you liked it!
Could you explain how the tree's nodes are actually stored? What data structure can be used to do that?
In the linked code I use a list object called "verts". Each entry has five elements: (1) the {x,y} coordinates of the node, (2) the index of the parent node, (3) the ID of this node, (4) the cost-to-go to get to this node, and (5) a list of the children of this node. demonstrations.wolfram.com/RapidlyExploringRandomTreeRRTAndRRT/
why the path planned by rrt* is smoother than the path planned by rrt
The shortest path between two points is made up of straight line segments (see demonstrations.wolfram.com/PathsInsideAPolygon/). RRT* will eventually find this shortest path, while RRT will not. Check out ua-cam.com/video/Ob3BIJkQJEw/v-deo.html
Why some studies combine RRT with A* ? For the optimality ?
@Hadjer BEN BRAHIM, that is a nuanced question. Both BFS and A* will return the shortest path. A* is an improvement on BFS because it expands fewer nodes as it searches for the shortest path.
Thank you Sir. Another question please :
Is the BFS/DFS an approach for path planning ? I read some reviews about "UAV Path Planning" and I didn't find these approaches yet. I am new to this field so I would be grateful if you suggest to me some articles or books about the subject. Thank you.
@@hadjer168 both approaches require you to have a graph of possible trajectories. Steve Lavalle's book is one of my favorites on motion planning, and it is available online for free: lavalle.pl/planning/. If you want specific advice on UAV path planning, please elaborate.
@@AaronBecker Thank you sir for sharing with me this book. If you don't mind I have another question please.... What is "smoothing the path" ? And in which case we should do it ? (is it when we include the kinematic constraint like the minimum turning radius ?) Thank you.
@@hadjer168 Smoothing is done before you implement a path on your robot. Here is a reference: www.researchgate.net/publication/277312183_Embedding_Nonlinear_Optimization_in_RRT_for_Optimal_Kinodynamic_Planning
your algorithm for rrt is wrong. when new random point selected, multiple nodes are added with the same spacing starting from nearest node to the new generated random node.
Can you give a time stamp for where you see this?
what is this aq
also look up the "informed RRT*" algorithm
Fiuftu