Metrics for analyzing the evolution of C-space models

Marco A.A. Morales, Roger Pearce, Nancy M. Amato

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 quantitive 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. In this paper we make some progress towards this goal. 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.

Original languageEnglish (US)
Title of host publicationProceedings 2006 IEEE International Conference on Robotics and Automation, ICRA 2006
Number of pages6
StatePublished - 2006
Externally publishedYes
Event2006 IEEE International Conference on Robotics and Automation, ICRA 2006 - Orlando, FL, United States
Duration: May 15 2006May 19 2006

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729


Other2006 IEEE International Conference on Robotics and Automation, ICRA 2006
Country/TerritoryUnited States
CityOrlando, FL

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering


Dive into the research topics of 'Metrics for analyzing the evolution of C-space models'. Together they form a unique fingerprint.

Cite this