Time and space complexities of RRT and RRT*

Question

What are the time and space complexities of RRT and RRT*? How does the incremental sampling based algorithms perform when compared to graph based incremental heuristic algorithms

Answer 1

RRT (Rapidly-exploring Random Tree) and RRT* (Rapidly-exploring Random Tree Star) are both probabilistic motion planning algorithms. The time and space complexities of these algorithms are as follows:

RRT:

Time Complexity: O(K log K), where K is the number of nodes in the tree.

Space Complexity: O(K)

RRT*:

Time Complexity: O(K log K)

Space Complexity: O(K log K)

As for the second part of your question, incremental sampling based algorithms (such as RRT) and graph based incremental heuristic algorithms (such as PRM) have different strengths and weaknesses. Incremental sampling based algorithms are generally more efficient in high-dimensional spaces, while graph based incremental heuristic algorithms are more efficient in low-dimensional spaces.

Moreover, incremental sampling based algorithms can efficiently explore the configuration space in a uniform manner, while graph based incremental heuristic algorithms rely on domain-specific heuristics to guide the search.

It is difficult to make a general comparison between these two types of algorithms as their performance may depend on the specific problem at hand. It is often best to choose an algorithm that is well-suited to the particular problem being solved.