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.
['Joshua Bialkowski', 'Michael W. Otte', 'Emilio Frazzoli']
Free-configuration Biased Sampling for Motion Planning: Errata