Faster broad-phase collission detection for motion planning

Date of Award

2018

Document Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Information Systems & Computer Science

First Advisor

Fernandez, Proceso L., Ph.D.

Abstract

This study presents three proposed algorithms for broad-phase collision detection for motion planning that is faster than the Bounding Volume Hierarchy (BVH) algorithm for certain types of input instances. The first algorithm is the bounding volume intersection (BVI) which obtains the intersection between a pair of trajectory bounding volumes before doing the BVH tree creation. The last two proposed algorithms avoid the BVH tree creation completely. The second algorithm is the synchronized intersection (SI) that compares the sequentially ordered bounding boxes. Lastly, the speed-time advancement (STA) uses the same sequential bounding boxes, but advances to the earliest possible time of collision according to the distances of the current bounding boxes and the maximum speeds of the trajectories. A good number of experiments were run under many different test cases to compare the performances of the proposed algorithms against the commonly used BVH. From these experiments, it was observed that the BVI is only more efficient than BVH when two trajectories are involved. However, both SI and STA show speed improvement when the number of trajectories is not sufficiently high. For 24 trajectories and more, the bottom-up BVH still performed best because the time invested on BVH tree creation is compensated by its fast checking for collision. Thus, the selection of the most efficient broad-phase algorithm would rely heavily on the number of trajectories for collision checking.

Comments

The C7.G476 2018

Link to Full Text

Share

COinS