by introducing a small probability of sampling the goal to the state sampling procedure. The higher this probability, the more greedily the tree grows towards the goal. Algorithm For a general configuration space C, the algorithm in pseudocode is as follows: Input: Initial configuration qinit, number of vertices in RRT K, incremental distance Δq Output: RRT graph G G.init(qinit) for k = 1 to K do qrand ← RAND_CONF() qnear ← NEAREST_VERTEX(qrand, G) qnew ← NEW_CONF(qnear, qrand, Δq) G.add_vertex(qnew) G.add_edge(qnear, qnew) return G In the algorithm above, "RAND_CONF" grabs a random configuration qrand in C. This may be replaced with a function "RAND_FREE_CONF" that uses samples in Cfree, while rejecting those in Cobs using some collision detection algorithm. "NEAREST_VERTEX" is a function that runs through all vertices v in graph G, calculates the distance between qrand and v using some measurement function thereby returning the nearest vertex. "NEW_CONF" selects a new configuration qnew by moving an incremental distance Δq from qnear in the direction of qrand. (According to in holonomic problems, this should be omitted and qrand used instead of qnew.) Variants and improvements for motion planning RRT-Rope, a method for fast near-optimal path planning using a deterministic shortening approach, very effective in open and large environments. Parti-game directed RRTs (PDRRTs), a method that combines RRTs with the parti-game method to refine the search where it is needed (for example around obstacles) to be able to plan faster and solve more motion planning problems than RRT Closed-loop rapidly-exploring random (CL-RRT), an extension of RRT that samples an input to a stable closed-loop system consisting of the vehicle and a controller It has been shown that, under 'mild technical conditions', the cost of the best path in the RRT converges almost surely to a non-optimal value. For that reason, it is desirable to find variants of the RRT that converges to an optimum, like RRT*. Below follows is a list of RRT*-based methods (starting with RRT* itself). Not all of the derived methods do themselves converge to an optimum, though. Rapidly-exploring random graph (RRG) and RRT*, a variant of RRT that converges towards an optimal solution LQR-RRT, a kinodynamic variant for complex or underactuated dynamics RRT, a family of RRT-based planners aiming to generate solutions for high-dimensional systems in real-time, by progressively searching in lower-dimensional subspaces. RRT*-Smart, a method for accelerating the convergence rate of RRT* by using path optimization (in