| dc.description.abstract | A motion planner finds a sequence of potential motions for a robot to transit
from an initial to a goal state. To deal with the intractability of this problem, a class
of methods known as sampling-based planners build approximate representations of
potential motions through random sampling. This selective random exploration of
the space has produced many remarkable results, including solving many previously
unsolved problems. Sampling-based planners usually represent the motions as a graph
(e.g., the Probabilistic Roadmap Methods or PRMs), or as a tree (e.g., the Rapidly
exploring Random Tree or RRT). Although many sampling-based planners have been
proposed, we do not know how to select among them because their different sampling
biases make their performance depend on the features of the planning space. Moreover,
since a single problem can contain regions with vastly different features, there
may not exist a simple exploration strategy that will perform well in every region.
Unfortunately, we lack quantitative tools to analyze problem features and planners
performance that would enable us to match planners to problems.
We introduce novel metrics for the analysis of problem features and planner
performance at multiple levels: node level, global level, and region level. At the node
level, we evaluate how new samples improve coverage and connectivity of the evolving
model. At the global level, we evaluate how new samples improve the structure of the
model. At the region level, we identify groups or regions that share similar features.
This is a set of general metrics that can be applied in both graph-based and tree-based planners. We show several applications for these tools to compare planners, to decide
whether to stop planning or to switch strategies, and to adjust sampling in different
regions of the problem. | en |
