Nathan Wedge, Michael Branicky
Randomized, sampling-based planning has a long history of success, and although the benefits associated with this use of randomization are widely-recognized, its costs are not well-understood. We examine a variety of problem in-stances solved with the Rapidly-exploring Random Tree algorithm, demonstrating that heavy-tailed runtime distributions are both common and potentially exploitable. We show that runtime mean and variability can be reduced simultaneously by a straightforward strategy such as restarts and that such a strategy can apply broadly across sets of queries. Our experimental results indicate that several-fold improvements can be achieved in the mean and variance for restrictive problem environments.
Subjects: 1.11 Planning; 15.7 Search
Submitted: May 4, 2008