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

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.