Sampling Distribution Induced by Our Algorithm in 2D

black represent low-high sampling probability density. The actual obstacle configuration appears in (d), obstacles are red. Abstract — This document contains improved and updated proofs of convergence for the sampling method presented in our paper “Free-configuration Biased Sampling for Motion Planning ” [2] The following is the abstract of the original paper: In sampling-based motion planning algorithms the initial step at every iteration is to generate a new sample from the obstacle-free portion of the configuration space. This is usually accom-plished via rejection sampling, i.e., repeatedly drawing points from the entire space until an obstacle-free point is found. This strategy is rarely questioned because the extra work associated with sampling (and then rejecting) useless points contributes at most a constant factor to the planning algorithm’s asymptotic runtime complexity. However, this constant factor can be quite large in practice. We propose an alternative approach that enables sampling from a distribution that provably converges to a uniform distribution over only the obstacle-free space. Our method works by storing empirically observed estimates of obstacle-free space in a point-proximity data structure, and then using this information to generate future samples. Both theoretical and experimental results validate our approach. I