Rapidly-exploring Random Tree (RRT) is a sampling-based probabilistic path planning method. It was firstly proposed by LaValle in 1998, but the first real usage was done by Bruce on UAVs, in 2002.

In essence, an RRT planner searches for a path from an initial state to a goal state by expanding a search tree.

The main features of the RRT method, which make it suitable for our purpose are:

• Probabilistic completeness, meaning that given enough time, the probability that the planner fails to find a path, if one exists, asymptotically approaches zero.
• No pre-caclulations required, making it completely dynamic
• Fast execution

Although it is recommended by Bruce and many others to use kd-trees to store the tree, I used a linear array data structure. In my tests it was faster than kd-tree, and my best guess is that it’s because of less cache misses.

In 2006, Bruce improved the method by biasing the search tree toward the last successful result, and called it Execution-extended RRT (ERRT). It was shown that in many cases the execution time was reduced, so the success rate of the method was improved.

From an implementation point of view, the RRT is used for each robot separately in our software. So it’s done on multiple threads on MacBook, and on multiple SPUs on PS3 using a simple fork/join pattern. The execution time is limited by limiting the maximum number of nodes the search tree can have.