Metrics for planning monitoring, performance studies, and planning adaptation
Marco Morales, Roger Pearce, Nancy M. Amato

There are many sampling-based motion planning methods that model the connectivity of a robot's configuration space (C-space) with a graph whose nodes are valid configurations and whose edges represent valid transitions between nodes. One of the biggest challenges faced by users of these methods is selecting the right planner for their problem. While researchers have tried to compare different planners, most accepted metrics for comparing planners are based on efficiency, e.g., number of collision detection calls or samples needed to solve a particular set of queries, and there is still a lack of useful and efficient quantitative metrics that can be used to measure the suitability of a planner for solving a problem. That is, although there is great interest in determining which planners should be used in which situations, there are still many questions we cannot answer about the relative performance of different planning methods. We propose a metric that can be applied to each new sample considered by a sampling-based planner to characterize how that sample improves, or not, the planner's current C-space model. This characterization requires only local information and can be computed quite efficiently, so that it can be applied to every sample. We show how this characterization can be used to analyze and compare how different planning strategies explore the configuration space. In particular, we show that it can be used to identify three phases that planners go through when building C-space models: quick learning (rapidly building a coarse model), model enhancement (refining the model), and learning decay (oversampling -- most samples do not provide additional information). Hence, our work can also provide the basis for determining when a particular planning strategy has 'converged' on the best C-space model that it is capable of building.

2D environment with a single obstacle Sample added, visibility region is dashed Another sample added, visibility region of two samples intersect A sample is added on the intersection of visibility regions, a connection is possible

Related Projects

Feature-Sensitive Motion Planning
Iterative Map Generation (IMG)
Biasing and Composing Samplers

Papers

Metrics for Sampling-Based Motion Planning, Marco Morales, Ph.D. Thesis, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, Dec 2007.
Ph.D. Thesis(abstract)

Analysis of the Evolution of C-Space Models built through Incremental Exploration, Marco Morales, Roger Pearce, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 1029-1034, Rome, Italy, Apr 2007. Also, Technical Report, TR06-013, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, U.S.A., Sep 2006.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Metrics for Analyzing the Evolution of C-Space Models, Marco A. Morales A., Roger Pearce, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 1268-1273, Orlando, Florida, U.S.A., May 2006.
Proceedings(ps, pdf, abstract)

Parasol Home | Research | People | General info | Seminars | Resources   Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112  Contact Webmaster      Phone 979.458.0722     Fax 979.458.0718  Department of Computer Science | Dwight Look College of Engineering | Texas A&M University     Privacy statement: Computer Science Engineering TAMU