RESAMPL | Algorithms & Applications Group

Algorithms & Applications Group
RESAMPL

RESAMPL: A Region-Sensitive Adaptive Motion Planner
supported by NSF
Sam Rodriguez, Shawna Thomas, Roger Pearce, Nancy Amato

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.

Overview
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.

C-Space Initial Sampling Region Construction Region Classification Resulting Sampling

Region Construction
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).

Example Region Classication

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.

Free Surface Inital Samples

Narrow Blocked Final Samples

Papers

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), New York City, NY, Jul 2006. Also, Technical Report, TR06-004, Parasol Laboratory, Department of Computer Science, Texas A&M University, Mar 2006.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Department of Computer Science | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science Engineering TAMU


C-Space	Initial Sampling	Region Construction	Region Classification	Resulting Sampling