Single-tree search

A reasonably efficient planner can be made by directly using the algorithm in Figure 5.21 to grow a tree from ${q_{I}}$ and periodically check whether it is possible to connect the RDT to ${q_{G}}$. An easy way to achieve this is to start with a dense sequence ${\alpha }$ and periodically insert ${q_{G}}$ at regularly spaced intervals. For example, every $100$th sample could be ${q_{G}}$. Each time this sample is reached, an attempt is made to reach ${q_{G}}$ from the closest vertex in the RDT. If the sample sequence is random, which generates an RRT, then the following modification works well. In each iteration, toss a biased coin that has probability $99/100$ of being HEADS and $1/100$ of being TAILS. If the result is HEADS, then set ${\alpha }(i)$, to be the next element of the pseudorandom sequence; otherwise, set ${\alpha}(i) = {q_{G}}$. This forces the RRT to occasionally attempt to make a connection to the goal, ${q_{G}}$. Of course, $1/100$ is arbitrary, but it is in a range that works well experimentally. If the bias is too strong, then the RRT becomes too greedy like the randomized potential field. If the bias is not strong enough, then there is no incentive to connect the tree to ${q_{G}}$. An alternative is to consider other dense, but not necessarily nonuniform sequences in ${\cal C}$. For example, in the case of random sampling, the probability density function could contain a gentle bias towards the goal. Choosing such a bias is a difficult heuristic problem; therefore, such a technique should be used with caution (or avoided altogether).