RESAMPL: A Region-Sensitive Adaptive Motion Planner
Related Projects:  Robot Task and Motion Planning    Learning to Guide Sampling-Based Planners    Learning-Based Methods    Feature-Sensitive Motion Planning    Adaptive Neighbor Connection    Sampling-based Planning    Guided Planning    Spatial Awareness    Interconnect Routing  

Automatic motion planning has applications ranging from traditional robotics to computer-aided design to computational biology and chemistry. While randomized planners, such as probabilistic roadmap methods (PRMs) or rapidly-exploring random trees (RRT), have been highly successful in solving many high degree of freedom problems, there are still many scenarios in which we need better methods, e.g., problems involving narrow passages or which contain multiple regions that are best suited to different planners. 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 classifies regions based on the entropy of the samples in it, and then uses these classifications 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 significantly faster and also usually requires fewer samples to solve the problem.




Related Publications

RESAMPL: A Region-Sensitive Adaptive Motion Planner, Samuel Rodriguez, Shawna Thomas, Roger Pearce, Nancy M. Amato, Algorithmic Foundation of Robotics VII , pp. 285-300, N/A, Jan 2008. DOI: 10.1007/978-3-540-68405-3_18
Keywords: Machine Learning, Sampling-Based Motion Planning
Links : [Published]

BibTex

@Inbook{Rodriguez2008,
author="Rodriguez, Samuel
and Thomas, Shawna
and Pearce, Roger
and Amato, Nancy M.",
editor="Akella, Srinivas
and Amato, Nancy M.
and Huang, Wesley H.
and Mishra, Bud",
title="RESAMPL: A Region-Sensitive Adaptive Motion Planner",
bookTitle="Algorithmic Foundation of Robotics VII: Selected Contributions of the Seventh International Workshop on the Algorithmic Foundations of Robotics",
year="2008",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="285--300",
isbn="978-3-540-68405-3",
doi="10.1007/978-3-540-68405-3_18",
url="https://doi.org/10.1007/978-3-540-68405-3_18"
}


Abstract

Automatic motion planning has applications ranging from traditional robotics to computer-aided design to computational biology and chemistry. While randomized planners, such as probabilistic roadmap methods (PRMs) or rapidly-exploring random trees (RRT), have been highly successful in solving many high degree of freedom problems, there are still many scenarios in which we need better methods, e.g., problems involving narrow passages or which contain multiple regions that are best suited to different planners. 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 classifies regions based on the entropy of the samples in it, and then uses these classifications 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 significantly faster and also usually requires fewer samples to solve the problem.