robotics//motion planning//RRT

A rapidly-exploring random tree (RRT) is a sampling-based motion planning algorithm that grows a tree from the start by repeatedly drawing a random configuration and extending the nearest node of the tree one step toward it, keeping the step only if it is free of collisions; it is used for robot arms and other planning problems of many dimensions, where a grid over the configuration space would have astronomically many cells.

A rapidly-exploring random tree (RRT) is a sampling-based motion planning algorithm that grows a tree from the start by repeatedly drawing a random configuration and extending the nearest node of the tree one step toward it, keeping the step only if it is free of collisions; it is used for robot arms and other planning problems of many dimensions, where a grid over the configuration space would have astronomically many cells.

1Draw a random configuration2Find the nearest node of the tree3Take one step from it toward the sample4Keep the step if it collides with nothing

The tree reaches into empty space quickly for a geometric reason. Nodes on the frontier of the tree sit next to large unexplored regions, so a random sample is most likely to land nearest to one of them, and the tree is pulled outward instead of thickening where it already is. The search stops when a node comes within a step of the goal.

It is probabilistically complete: if a path exists, the probability of finding it tends to one as samples accumulate. It is not optimal, and its paths zigzag, so they are shortened and smoothed afterwards (path smoothing). RRT* rewires nearby nodes whenever a cheaper parent appears and is asymptotically optimal: the path keeps improving with more time, which makes it an anytime algorithm.

The main cost is collision checking. Every candidate step is tested against the obstacles, at a resolution fine enough not to jump through a thin bar; growing the tree itself is cheap. Biasing a few percent of samples toward the goal speeds the end of the search.

It struggles with narrow passages. A doorway a few centimetres wider than the robot occupies a tiny fraction of the space, random samples rarely fall inside it, and probabilistic completeness says nothing about how long that takes. Its randomness also means two runs give two different paths, which complicates testing and explaining a robot's behaviour unless the seed is fixed.

In practice it ships inside the OMPL library used by MoveIt for robot arms. For a robot that only needs a position and heading on a floor, a grid with A* search is simpler, repeatable and optimal.