Metrics for sampling-based motion planning

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.