Please use this identifier to cite or link to this item:
Title: Shortest path computation for roadway network
Authors: Khoo, Gilbert Teng Sheng
Keywords: DRNTU::Engineering::Computer science and engineering
Issue Date: 2016
Abstract: Undeniably, autonomous vehicles have found its position within the vehicle industry. In the absence of human drivers, the vehicle is fully reliant on the on-board computers for navigation, collision avoidance, etc. For transportation, shortest path computation plays a crucial role, where besides providing the shortest path, the demand for shorter computation time is increasing from time to time, so as to adapt to the frequent changing of traffic conditions. In this project, we investigate hardware efficient architectures for shortest path computations that is based on a novel shortest path algorithm. We show that the proposed architecture is able to reduce the total amount of computations for nodes relaxations compared to the hardware implementation of the conventional Bellman- Ford algorithm,. This is achieved by incorporating Node filtering to avoid unnecessary computations. In addition, the nodes relaxation process in the proposed architecture adopts the SIMD model, where the tentative distance for neighbours of a single node can be computed in parallel. We also explored the utilization of various caches and their configurations to determine a good trade-off between performance and logic area utilization. We compared the performance of the hardware simulation model of the proposed algorithm and conventional Bellman-Ford algorithms using Singapore Roadway Network, which consists of 140219 nodes and 193071 edges. The experimental results show that the proposed architecture leads to over 40% performance improvement.
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
  Restricted Access
4.12 MBAdobe PDFView/Open

Page view(s)

Updated on Jun 17, 2021

Download(s) 50

Updated on Jun 17, 2021

Google ScholarTM


Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.