The random loop generator greatly improves the chance of obtaining closure by iteratively restricting the range on each of the active variables. The method requires that the active variables appear sequentially along the chain (i.e., there is no interleaving of active and passive variables). The coordinates of are obtained sequentially as follows. First, compute an interval, , of allowable values for . The interval serves as a loose bound in the sense that, for any value , it is known for certain that closure cannot be obtained. This is ensured by performing a careful geometric analysis of the linkage, which will be explained shortly. The next step is to generate a sample in , which is accomplished in  by picking a random point in . Using the value , a bounding interval is computed for allowable values of . The value is obtained by sampling in . This process continues iteratively until and are obtained, unless it terminates early because some for . If successful termination occurs, then the active variables are used to find values for the passive variables. This step still might fail, but the probability of success is now much higher. The method can also be applied to linkages in which there are multiple, common loops, as in the Stewart-Gough platform, by breaking the linkage into a tree and closing loops one at a time using the loop generator. The performance depends on how the linkage is decomposed .
Steven M LaValle 2012-04-20