RRTs

RRTs, or rapidly exploring random trees, are a family of randomized motion planning algorithms used to compute feasible paths for robots in high-dimensional configuration spaces. They were introduced by Steven LaValle and Jim Kuffner in 1998. RRTs build a tree incrementally from a start configuration by randomly sampling configurations in the space and extending the tree toward these samples, subject to collision constraints.

The core steps are: sample x_rand, find the nearest tree node x_near, extend toward x_rand by a fixed step to x_new, and, if the path from x_near to x_new is collision-free, add x_new to the tree. This process repeats until a configuration that reaches the goal is included or a time limit is reached. The method favors rapid exploration of large spaces and does not require an explicit global optimization.

RRTs are probabilistically complete: if a feasible path exists, the probability of finding one approaches one as the number of samples grows. Variants include RRT*, which rewires connections to minimize path cost and is asymptotically optimal; and RRT-Connect, which grows two trees toward each other to speed search. Other forms address efficiency, biasing, and dynamic environments.

Applications span motion planning for mobile robots, robotic manipulators, drones, and autonomous vehicles. Strengths include robustness in high-dimensional spaces and straightforward implementation. Limitations include potentially suboptimal initial solutions in basic RRT, sensitivity to tuning and sampling distribution, and the need for reliable collision checking and post-processing to improve path quality.