Accelerating Proximity Queries Accelerating Proximity Queries for Non-convex Geometries in a Robot Cell Context

Abstract

Sampling-based motion-planners, for example rapidly exploring dense tree (RRT) based planners, depend on fast proximity queries. Regrettably, bounding volume tests are significant bottlenecks of proximity queries. Sampling-based motion-planners are therefore accelerated by reducing the number of bounding volume tests. To this end, a novel algorithm called Forest Proximity Query (FPQ) is developed. Contrary to previous research, FPQ traverses several pairs of BVHs simultaneously, effectively exploiting an actuality that only a single minimal separation distance — out of several possible separation distances — is required during sampling-based motion-planning. An implementation of FPQ show that FPQ performs up to 67% fewer BV tests in comparison to the well-known Proximity Query Package, increasing proximity querying performance by up to 46%. In conclusion, FPQ is successful in its attempt at improving performance of sampling-based motion-planners.