Superquadrics Augmented Rapidly-exploring Random Trees.

Sammanfattning: This thesis work investigated the advantages and disadvantages of using superquadrics (SQ) to do the collision-checking part of the Rapidly-exploring Random Trees (RRT) motion planning algorithm for higher Degree of Freedom (DoF) motion planning, comparing it with an established proximity querying method known as the Gilbert-Johnson-Keerthi (GJK) algorithm. In the RRT algorithm, collision detection is the main bottleneck, making this topic interesting to research. The SQ-based collision detection method was compared to the GJK algorithm both qualitatively and quantitatively, comparing computational speed, memory requirements, as well as the ability to handle arbitrary shapes. Furthermore, how appropriate they are in modelling a 6 DoF arm was analyzed. A qualitative comparison between the RRT algorithm and the A' algorithm was also provided, comparing their suitability for searching in higher dimensional spaces. When there were no collisions the SQ-based algorithms performed roughly at parity with the GJK algorithm in terms of computational speed. However, when a collision had occurred, the SQ-based algorithms were able to return a positive faster than the GJK algorithm, outperforming it. From a memory standpoint the SQ-based algorithms required less memory as they could leverage the explicit and implicit representations of the SQ objects, whereas the GJK algorithm requires both objects being checked for collision to be explicitly represented as convex sets of points. Regarding handling arbitrary shapes, the SQ-based algorithms have an advantage in that they can allow for certain non-convex shapes to be. Conversely, the GJK algorithm is limited to convex shapes. The GJK algorithm would thus require more geometric primitives to accurately capture the same non-convex shape. Thus, it can be concluded that the SQ-based method is more suitable for modelling a 6 DoF arm. However, a GJK-based collision detection module would in most cases be a lot more straightforward than the alternative to set up, as it is very simple to collect a set of points. Finally, both collision detection method types were implemented with the RRT algorithm. Due to the inherently random nature of the RRT algorithm the results of this set of tests could not be used to make any further conclusions beyond showing that it is possible to combine the SQbased algorithm with the RRT algorithm. Instead, one should see the RRT algorithm as a multiplicative factor applied to the inherent properties of the previously examined collision detection methods.