RRT

Rapidly-exploring Random Tree (RRT) is a family of sampling-based motion planning algorithms designed to efficiently explore high-dimensional configuration spaces. Introduced in 1998 by Steven M. LaValle and J. J. Kuffner Jr., the method incrementally builds a tree of configurations by randomly sampling the space and connecting samples to the nearest tree node when a collision-free path exists. This approach focuses exploration on unexplored regions, enabling rapid progress in complex environments.

Basic RRT starts from an initial configuration and iteratively samples a random configuration, finds the nearest node in the current tree, and extends toward the sample by a fixed step. If the projection along that step is collision-free, the new configuration is added to the tree with an edge from the nearest node. The process repeats until a path to the goal is found or resources are exhausted.

Several variants have been developed to improve performance or optimality. RRT modifies the tree with rewiring to produce asymptotically optimal paths, while bi-directional versions and RRT-Connect aim to accelerate search by growing two trees from the start and goal. Other forms, such as RRT with different steering functions, adapt the method to kinodynamic or differential constraints.

RRT and its variants are widely used in robotics, autonomous systems, and computer-aided design for motion planning in high-dimensional spaces, including manipulators, mobile robots, drones, and virtual environments. Limitations include potential inefficiency in narrow passages, dependence on tuning parameters such as step size and sampling strategy, and the need to handle dynamics and collision checking efficiently for real-time applications.

Related topics include probabilistic roadmap methods and other sampling-based planners.