Time Advancement and Bounds Intersection Checking for Faster Broad-Phase Collision Detection of Paired Object Trajectories
For self-driving mechanisms, the motion planning requires a reasonably fast algorithm for collision detection along the trajectories. We present three algorithms for the detection of collision among objects with predefined trajectories. The first algorithm uses the intersection of the path’s boundin...
Saved in:
Main Authors: | , |
---|---|
Format: | text |
Published: |
Archīum Ateneo
2018
|
Subjects: | |
Online Access: | https://archium.ateneo.edu/discs-faculty-pubs/86 https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1085&context=discs-faculty-pubs |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Ateneo De Manila University |
id |
ph-ateneo-arc.discs-faculty-pubs-1085 |
---|---|
record_format |
eprints |
spelling |
ph-ateneo-arc.discs-faculty-pubs-10852020-05-07T09:44:39Z Time Advancement and Bounds Intersection Checking for Faster Broad-Phase Collision Detection of Paired Object Trajectories Fernandez, Proceso L, Jr Germar, Mary Aveline For self-driving mechanisms, the motion planning requires a reasonably fast algorithm for collision detection along the trajectories. We present three algorithms for the detection of collision among objects with predefined trajectories. The first algorithm uses the intersection of the path’s bounding box. The second algorithm sequentially checks for intersection between each pair of corresponding axis-aligned bounding boxes (AABB) from the trajectories of the two paths. Lastly, the latter algorithm is modified using iterative time advancement to an estimated earliest possible collision time. Simulation experiments on a variety of pair trajectories demonstrate a significant speedup of the proposed algorithms over the existing baseline algorithm. They are, therefore, preferable alternatives for faster broad-phase collision detection in applications such as motion planning. 2018-07-01T07:00:00Z text application/pdf https://archium.ateneo.edu/discs-faculty-pubs/86 https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1085&context=discs-faculty-pubs Department of Information Systems & Computer Science Faculty Publications Archīum Ateneo Computer Sciences Theory and Algorithms |
institution |
Ateneo De Manila University |
building |
Ateneo De Manila University Library |
country |
Philippines |
collection |
archium.Ateneo Institutional Repository |
topic |
Computer Sciences Theory and Algorithms |
spellingShingle |
Computer Sciences Theory and Algorithms Fernandez, Proceso L, Jr Germar, Mary Aveline Time Advancement and Bounds Intersection Checking for Faster Broad-Phase Collision Detection of Paired Object Trajectories |
description |
For self-driving mechanisms, the motion planning requires a reasonably fast algorithm for collision detection along the trajectories. We present three algorithms for the detection of collision among objects with predefined trajectories. The first algorithm uses the intersection of the path’s bounding box. The second algorithm sequentially checks for intersection between each pair of corresponding axis-aligned bounding boxes (AABB) from the trajectories of the two paths. Lastly, the latter algorithm is modified using iterative time advancement to an estimated earliest possible collision time. Simulation experiments on a variety of pair trajectories demonstrate a significant speedup of the proposed algorithms over the existing baseline algorithm. They are, therefore, preferable alternatives for faster broad-phase collision detection in applications such as motion planning. |
format |
text |
author |
Fernandez, Proceso L, Jr Germar, Mary Aveline |
author_facet |
Fernandez, Proceso L, Jr Germar, Mary Aveline |
author_sort |
Fernandez, Proceso L, Jr |
title |
Time Advancement and Bounds Intersection Checking for Faster Broad-Phase Collision Detection of Paired Object Trajectories |
title_short |
Time Advancement and Bounds Intersection Checking for Faster Broad-Phase Collision Detection of Paired Object Trajectories |
title_full |
Time Advancement and Bounds Intersection Checking for Faster Broad-Phase Collision Detection of Paired Object Trajectories |
title_fullStr |
Time Advancement and Bounds Intersection Checking for Faster Broad-Phase Collision Detection of Paired Object Trajectories |
title_full_unstemmed |
Time Advancement and Bounds Intersection Checking for Faster Broad-Phase Collision Detection of Paired Object Trajectories |
title_sort |
time advancement and bounds intersection checking for faster broad-phase collision detection of paired object trajectories |
publisher |
Archīum Ateneo |
publishDate |
2018 |
url |
https://archium.ateneo.edu/discs-faculty-pubs/86 https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1085&context=discs-faculty-pubs |
_version_ |
1681506593595719680 |