RRT, RRT* & Random Trees

[@Talon_24]

Thank you for the video, this helped me a lot in three different lectures at once! Your style of explaining and presenting is great!

[@AaronBecker]

@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!

[@shravangulvadi]

The visualization and explanation are just great, thanks a lot for sharing!!

[@xianqihe]

Great demo, high quality as usual, love your patience and tone when you speak prof❤

[@vitalram1985]

Its a great video for me to learn robot motion planning. Thanks a lot, only these kind of videos make youtube worth watching.

[@Vedrajrm]

Was looking for rrts, somehow found this, liked it

[@AaronBecker]

If there are other videos you'd like, let me know

[@decophotclicks9631]

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?

[@AaronBecker]

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.

[@dharmiknaik1772]

Great UI to demonstrate the algos

[@Al-dp1pe]

Very Good Description of the Concept-Need to understand program structure

[@AaronBecker]

You can follow the link to see the code used for the video.

[@slugma_nuts]

I searched youtube for "planting rows of trees vs random placement" referring to physical trees and was pleasantly surprised by this video.

[@AaronBecker]

Funny! Here in Texas the commercial pecan groves are in straight rows. I hope you find your desired video.

[@mohammedtalha4649]

This is great. Please do more videos on motion planning.

[@Khan0156]

Thank you!

[@vellyxenya3970]

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)?

[@AaronBecker]

@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.

[@vellyxenya3970]

@@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 :)

[@VarshiniKannan1998]

What algorithm was used to find the path from the start node to the end node? Dijkstra's?

[@AaronBecker]

@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.

[@VarshiniKannan1998]

Got it. Thank you!

[@faxer999]

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!

[@AaronBecker]

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.

[@hadjer168]

Why some studies combine RRT with A* ? For the optimality ?

[@AaronBecker]

​ @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.

[@hadjer168]

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.

[@AaronBecker]

@@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.

[@hadjer168]

@@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.

[@AaronBecker]

@@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

[@snackbob100]

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?

[@AaronBecker]

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?

[@mariusbrateng9575]

thanks, this was great!

[@AaronBecker]

Glad you liked it!

[@MinhVu-fo6hd]

Could you explain how the tree's nodes are actually stored? What data structure can be used to do that?

[@AaronBecker]

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/

[@30svich]

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.

[@AaronBecker]

Can you give a time stamp for where you see this?

[@hunghoang-riclab]

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 )

[@AaronBecker]

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.

[@alangiovannysanchez5368]

May you do a comparison of RRT and A*?

[@AaronBecker]

Chyza is right. A* can be compared to DFS and BFS, but not to a path planner without a graph.

[@hadjer168]

@@AaronBecker What is DFS and BFS ?

[@AaronBecker]

@@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.

[@hadjer168]

@@AaronBecker thank you.

[@MarcusVinicius-lq3fe]

The exploration bias is used for what?

[@AaronBecker]

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.

[@dehaizhu1770]

why the path planned by rrt* is smoother than the path planned by rrt

[@AaronBecker]

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 kzbin.info/www/bejne/hZOWc3yAoLZ9e9k

[@buckcostanza3483]

great!

[@Snoopod]

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

[@AaronBecker]

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 kzbin.info/www/bejne/iXOpqJqIabBkfc0, 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.

[@ЕвгенияЛевина-м7э]

3056 Balistreri Light

[@WatCaesar-f9f]

Tyree Greens

[@malachy2666]

nice

[@CarrieGrover-h9c]

Welch Lights

[@gumbo64]

also look up the "informed RRT*" algorithm

[@NatalieRalbovsky-k5k]

Kohler Points

[@NicholsKing-c9i]

Laverna Manor

[@EmilyWalker-w8e]

Kautzer Unions

[@HodgeEudora-f1j]

Morar Square

[@pegadinhasmelhores5759]

what is this aq

[@guddubariya2286]

Fiuftu