RRTConnect

RRT-Connect is a bidirectional motion-planning algorithm in the family of Rapidly-exploring Random Trees (RRT). It was proposed by J. J. Kuffner and Steven M. LaValle in the early 2000s as an efficient approach to sampling-based motion planning. The algorithm is designed to find a collision-free path for a robot or articulated system through a high-dimensional configuration space.

The algorithm grows two trees, one starting from the initial configuration and one from the goal configuration. At each iteration, a random configuration q_rand is sampled. The tree closest to q_rand is extended toward q_rand by a single forward step, creating a new node q_new if the extension is collision-free. Then the second tree is attempted to connect to q_new by repeatedly extending toward the new node. If a connection is made, the two trees form a continuous path from start to goal, which can be extracted by traversing the trees and joining the two subpaths.

RRT-Connect emphasizes rapid exploration and often finds feasible paths faster than unidirectional RRT, particularly in high-dimensional spaces. It is probabilistically complete, meaning that if a path exists, the algorithm will find one with probability approaching 1 as time grows, assuming accurate collision checks and a well-behaved configuration space. However, it does not guarantee optimality; path quality may be improved through post-processing or by combining ideas with optimality-focused variants like RRT* or path-smoothing techniques.

Practical considerations include the cost of collision checking, the choice of distance metric, and the step size used for extensions. The algorithm is widely used in robotics and automated planning for manipulators, mobile robots, and other systems requiring collision-free motion in high-dimensional spaces. Variants and implementations are available in many planning libraries and robotics frameworks.