Rapidly exploring random Trees (RRT) and their much nicer properties.

Rapidly exploring random Trees (RRT) is a randomized data structure that was invented by Professor Dr. Steven LaVelle. This data structure is hugely useful for handling path-planning queries with non-holonomic constraints involving dynamics and high degrees of freedom. RRTs and their variants are highly popular in the robot motion planning community as they tend to facilitate advanced path-planning queries. But most of its nicer properties are often forgotten or overshadowed by its much-glorified applications. This article tries to highlight the properties of the RRTs which make them so useful. Also, this article demonstrates the working of RRT in a 6-DoF Collaborative manipulator (UR5e — Universal Robot) for a pick and place task.

What is an RRT? An RRT is a randomized tree that iteratively expands by attempting to make connections between a randomly spawned node (X_rand) in the state space and a node in a tree that is closest to X_Rand. This might sound abstract and similar to RDT — Random dense trees, but the nuances in the tree expansion process would be made much clearer later in this article.

Why RRT? Even before RRTs came into existence there were methods like Probabilistic Roadmaps (PRM) and Potential fields(PF) that were used to solve path-planning problems. These methods were not much capable of planning with non-holonomic constraints. Potential field approaches depended heavily on heuristics which made it very hard to validate and apply in environments with…