In this work, we present RESAMPL, a motion planning strategy that uses local region information to make intelligent decisions about how and where to sample, which samples to connect together, and to find paths through the environment. Briefly, RESAMPL classies regions based on the entropy of the samples in it, and then uses these classications to further refine the sampling. Regions are placed in a region graph that encodes relationships between regions, e.g., edges correspond to overlapping regions. The strategy for connecting samples is guided by the region graph, and can be exploited in both multi-query and single-query scenarios. Our experimental results comparing RESAMPL to previous multi-query and single-query methods show that RESAMPL is generally signicantly faster and also usually requires fewer samples to solve the problem.
Based on an initial set of samples, we classify regions of C-space according to the entropy of their samples. We then use these classications to further refine the sampling. For example, we increase sampling in "narrow" regions and decrease sampling in "free" regions. Regions are placed in a region graph that encodes relationships between regions, e.g., edges correspond to overlapping regions. We use the region graph to determine appropriate connection strategies for multi-query planning and to extract a sequence of regions on which to focus sampling and connection for single-query planning.
The model is initialized with a set of samples from the C-space, including both free and collision congurations. These samples may be generated by any method. To construct the regions, each new region center is randomly selected from the set of initial samples that are not already in another region. Neighboring samples are selected from all initial samples. Samples may be selected as part of multiple regions. In this way, the region radii are relatively similar. Region construction is complete when each sample is either a region center, part of a region, or both.
Entropy Biased Region Classication
In order to identify the transition regions of C-space, we need a model that calculates how "interesting" the region is. We use the region's entropy to determine if it is a transition area. Entropy is a measure of the disorder of the region's samples. Regions containing samples that are completely free or completely blocked are considered to have low entropy. Regions containing a mixture of free and blocked samples are considered to have high entropy. Four simple and intuitive classications can be obtained based on entropy values: free (low entropy), surface (high entropy), narrow (high entropy), and blocked (low entropy).
Below is an example of how regions are created and classified in a test environment (L-Tunnel environment). For complete results please look at the paper.
RESAMPL: A Region-Sensitive Adaptive Motion Planner, Samuel Rodriguez, Shawna Thomas, Roger Pearce, Nancy M. Amato, In Proc. Int. Wkshp. on Alg.
Found. of Rob. (WAFR), pp. 285-300, New York City, NY, Jul 2006.
Proceedings(ps, pdf, abstract)
Supported by NSF
Project Alumni:Roger Pearce
Parasol Home | Research | People | General info | Seminars | Resources
Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112
firstname.lastname@example.org Phone 979.458.0722 Fax 979.458.0718
Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU
Web Accessibility Policy and Law - Web Accessibility and Usability Standards - Contact Webmaster