high performance computing on graphics processing units: hgpu.org

In industrial manufacturing, like the automotive industry, digital mock-ups are used to design complex machinery with the help of computer systems. In this field, motion planning algorithms play an important role to ensure the (de-)composability of the digital prototypes. In the last decades, sampling-based motion planning algorithms have shown themselves to be practical in this application. In order to construct a (dis-)assembly path for a virtual 3D object, these algorithms generate a high number of different placements for the object and validate these positions by utilizing a collision detection routine. Hence, collision detection is a very important sub-task in sampling-based motion planning and an efficient collision detection routine is essential to every sampling-based planner. One of the main difficulties for these planners results from "narrow passages" that appear whenever the movements of the assembled component are highly restricted. It can then be difficult to find a sufficient number of collision free samples and more sophisticated techniques might be required to enhance the performance of the algorithm. The present work is organized in two parts: In the first part, we analyze parallel collision detection algorithms. Focusing on the application to sampling-based motion planning, we formulate the a basic collision query as testing the same two rigid body objects in a number of different relative placements. We implement and compare different approaches based on bounding volume hierarchies and hierarchical grids that are executed in parallel on multiple CPU cores. Besides, we describe the design of different parallel CUDA kernels that perform collision tests based on bounding volume hierarchies. In addition to different distributions of the work amongst the available GPU threads, we analyze the effect of different memory access patterns on the performance of our CUDA kernels. Furthermore, we propose to improve the performance of the algorithms at the expense of their accuracy and analyze a family of different approximate collision tests. In the second part, we describe a novel parallel, sampling-based motion planner that is especially suited for complex motion planning problems with many narrow passages. The algorithm works in two phases. The basic idea is to conceptually allow small object interpenetrations and not to enforce a high accuracy in the first planning phase. We describe a non-conservative motion planner that is based on an Expansive Space Tree. The approach uses an iterative sample retraction mechanism to actively improve the performance in highly restricted environments. To further improve the performance, we optionally allow to apply approximate collision tests in the first planning phase. This results in a disassembly path that is not completely collision free. In the second phase, we repair this path with a new type of sampling-based motion planner that locally re-plans a valid path in close proximity to the non-conservative solution. To benchmark our new algorithm and show its strength for highly complex motion planning problems with many narrow passages, we have modeled and solved a new family of very complex metal puzzles in addition to the well known alpha puzzle. To the best of our knowledge, there is no comparably complex benchmark set of rigid body motion planning problems publicly available, neither have comparable benchmarks been described in the motion planning literature.