Fast probabilistic collision checking for sampling-based motion planning using locality-sensitive hashing

Abstract

We present a novel approach to perform fast probabilistic collision checking in high-dimensional configuration spaces to accelerate the performance of sampling-based motion planning. Our formulation stores the results of prior collision queries, and then uses such information to predict the collision probability for a new configuration sample. In particular, we perform an approximate k-NN (k-nearest neighbor) search to find prior query samples that are closest to the new query configuration. The new query sample's collision status is then estimated according to the collision checking results of these prior query samples, based on the fact that nearby configurations are likely to have the same collision status. We use locality-sensitive hashing techniques with sub-linear time complexity for approximate k-NN queries. We evaluate the benefit of our probabilistic collision checking approach by integrating it with a wide variety of sampling-based motion planners, including PRM (Probabilistic roadmaps), lazyPRM, RRT Rapidly exploring random trees, and RRT∗. Our method can improve these planners in various manners, such as accelerating the local path validation, or computing an efficient order for the graph search on the roadmap. Experiments on a set of benchmarks demonstrate the performance of our method, and we observe up to 2x speedup in the performance of planners on rigid and articulated robots.