Fast probabilistic collision checking for sampling-based motion planning using locality-sensitive hashing
- 2 May 2016
- journal article
- research article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 35 (12), 1477-1496
- https://doi.org/10.1177/0278364916640908
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.Keywords
This publication has 29 references indexed in Scilit:
- Sampling-based A* algorithm for robot path-planningThe International Journal of Robotics Research, 2014
- Real-time informed path sampling for motion planning searchThe International Journal of Robotics Research, 2012
- Approximate Line Nearest Neighbor in High DimensionsPublished by Society for Industrial & Applied Mathematics (SIAM) ,2009
- Near-optimal hashing algorithms for approximate nearest neighbor in high dimensionsCommunications of the ACM, 2008
- Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling DomainPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- The Gaussian sampling strategy for probabilistic roadmap plannersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- RRT-connect: An efficient approach to single-query path planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995
- A statistical decision rule with incomplete knowledge about classesPattern Recognition, 1993