On Heavy-tailed Runtimes and Restarts in Rapidly-exploring Random Trees

Contents

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.