rapidly exploring random tree

A sampling-based motion planningmotion planning, n.: Working out how a robot should move from where it is to where it needs to be, without hitting anything and within the limits of what its body can do. algorithm that incrementally builds a tree of collision-free configurations rooted at the start. At each iteration it samples a random configuration, finds the nearest node already in the tree, extends from that node a short step toward the sample, and adds the new node if the connecting motion is collision-free. Because nodes on the frontier of explored space are the likeliest to be nearest to a random sample, the tree keeps reaching into the biggest stretches of space it has not yet visited. RRTs need only a collision checker and a way to extend motions, so they handle high-dimensional configuration spacesconfiguration space, n.: An imaginary space in which a robot's whole body position is a single point, which turns 'move this many-jointed robot without hitting things' into 'find a path for a dot'. and kinodynamic constraints such as a car's steering limits. They are probabilistically complete but return jagged, suboptimal paths that are usually smoothed afterward. Variants include RRT-Connect, which grows trees from start and goal toward each other, and RRT*, which rewires the tree so that path cost converges to the optimum as samples increase. RRT-family planners are standard in open-source motion-planning libraries.

RRT-Connect finds a path for the arm in about 50 milliseconds; then we shortcut and smooth it.