TY - GEN
T1 - Metrics for analyzing the evolution of C-space models
AU - Morales, Marco A.A.
AU - Pearce, Roger
AU - Amato, Nancy M.
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33845662808&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33845662808&partnerID=8YFLogxK
U2 - 10.1109/ROBOT.2006.1641883
DO - 10.1109/ROBOT.2006.1641883
M3 - Conference contribution
AN - SCOPUS:33845662808
SN - 0780395069
SN - 9780780395060
T3 - Proceedings - IEEE International Conference on Robotics and Automation
SP - 1268
EP - 1273
BT - Proceedings 2006 IEEE International Conference on Robotics and Automation, ICRA 2006
T2 - 2006 IEEE International Conference on Robotics and Automation, ICRA 2006
Y2 - 15 May 2006 through 19 May 2006
ER -