Toward Optimal Configuration Space Sampling

Abstract

Sampling-based motion planning discovers the implicit connectivity of a configuration space by selecting and connecting sets of configurations. The structure of every configuration space dictates a number of optimal sets of samples whose selection by a sampling-based planner results in a complete roadmap of the space. Though it is generally computationally impractical to develop complete knowledge of configuration space, each individual sample provides information about the configuration space. We propose a new utility-guided sampling strategy that accumulates this information into an approximate model of the configuration space. The model is an approximation of both the state (obstructed or free) of individual configurations and the connectivity of the configuration space. Our proposed sampler uses the approximate configuration space model to select samples that are maximally relevant to the planning task. The relevance of a sample is measured by its expected utility to the further coverage of the configuration space roadmap. The utility metric blends information from both configuration space state and connectivity. The planner incorporates the information obtained from each sample into its approximation and uses these improved models for subsequent sampling. Experimental results with an implementation of this approach to motion planning indicate that it is capable of significantly reducing the runtime required to construct a complete roadmap for configuration spaces with arbitrary degrees of freedom.