Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
RESAMPL: A Region-Sensitive Adaptive Motion Planner

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.

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

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
Narrow
Blocked
Initial Samples
Final Samples

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