Accelerating Proximity Queries Accelerating Proximity Queries for Non-convex Geometries in a Robot Cell Context
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Complex adaptive systems (MPCAS), MSc
Publicerad
2018
Författare
Thorén, Joakim
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Informations- och kommunikationsteknik , Data- och informationsvetenskap , Information & Communication Technology , Computer and Information Science