Shortest path computation for roadway network

• Main Author: Khoo, Gilbert Teng Sheng
• Other Authors: Lam Siew Kei
• Format: Final Year Project
• Language: English
• Published: 2016
• Subjects: DRNTU::Engineering::Computer science and engineering
• Online Access: http://hdl.handle.net/10356/69217
• Institution: Nanyang Technological University

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.