# Does RRT perform graph search?

The basic RRT explores the space by sampling and if the goal is connected to the tree, the solution is returned. Can you define retrieving the path as a graph search?

I would argue, that it is not graph search.

In the implementation, you keep all the nodes in a flat list and check which of the nodes is closest to the sampled point. As all nodes are checked, this might be seen as a brute-force graph search, but in the implementation is just for loop iterating though all the points in a list.

The goal check is done for the newly added points to the tree. It is checked if it is in the vicinity of the goal point. If yes, then the path is defined by going up the tree to the root. This is also not search, since the list is available in the form of pointers from the child nodes to the parent nodes.

• "In the implementation, you keep all the nodes in a flat list and check which of the nodes is closest to the sampled point. As all nodes are checked, this might be seen as a brute-force graph search, but in the implementation is just for loop iterating though all the points in a list." There are much more efficient ways to check the distance from a point to a set of points using something like a kd-tree Jul 2 '21 at 19:17
• Yes, there is. I doubt that the original RRT implementation can use a more efficient structure. You can probably combine RRT with kd-trees, but the question refers to the basic RRT algorithm
– 50k4
Jul 2 '21 at 19:31
• I was curious about your claim, and it turns out the first RRT implementation (here) does actually use a KDTree. See line 35 of nn.h. Jul 3 '21 at 2:41
• Here is the pseudocode, clearly a flat list where every element is checked msl.cs.uiuc.edu/rrt/about.html
– 50k4
Jul 3 '21 at 5:04
• Sorry, I think my question was not entirely clear. Octopuscabbage interpreted it as I meant to. I will be clearer next time. Jul 3 '21 at 7:41

Assuming RRT is done in two steps:

1. Grow your tree from start state until one node is near enough to the goal state
2. Output path from start state to goal state along tree

I'm assuming based on your question that you're asking if part 2 is a graph search?

Usually in RRT, each node has exactly one parent (since it's a tree) and you can just walk back from the end node to the start node by following the parents of each node. I guess that kind of qualifies as a graph search?

If each node has more than one parent (like in PRM) then you need to use a shortest path graph search algorithm to find the shortest path in your graph from the start state to end state

• Thanks for your response. Yes, I meant whether you could call step 2 graph search. I think I agree with you, as you search the parents in the tree from goal-start. Jul 3 '21 at 7:41
• I would argue that going back the tree does not qualify as graph search. If going upward a tree is graph search that would make traversing a linked list also graph search. The worst case complexity is $n$, which is trivial. There is no cost function.
– 50k4
Jul 3 '21 at 8:17