In English

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

Joakim Thorén
Göteborg : Chalmers tekniska högskola, 2018. 142 s.
[Examensarbete på avancerad nivå]

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.

Nyckelord: bounding volume traversal tree, priority directed search, front tracking, rectangle swept sphere, proximity query, distance computation, motion planning, non-convex, geometry, robotics.



Publikationen registrerades 2018-06-19. Den ändrades senast 2018-06-19

CPL ID: 255144

Detta är en tjänst från Chalmers bibliotek