Title :
Hardware architecture for finding shortest paths
Author :
Sridharan, K. ; Priya, T.K. ; Kumar, Rajesh P.
Author_Institution :
Dept. of Electr. Eng., Indian Inst. of Technol. Madras, Chennai, India
Abstract :
The computation of shortest path for a mobile automaton between two points in the plane is considered in this paper. An architecturally-efficient solution based on Dijkstra´s algorithm is presented for this problem. Results of implementation in Xilinx FPGA are encouraging: the solution operates at approximately 46 MHz and the implementation for a graph with 64 nodes and 88 edges fits in one XCV3200E-FG1156 device.
Keywords :
computational complexity; computer architecture; field programmable gate arrays; Dijkstra algorithm; Xilinx FPGA; finding shortest paths; hardware architecture; mobile automaton; Costs; Data structures; Field programmable gate arrays; Fuzzy control; Hardware; Mobile computing; Mobile robots; Service robots; Shortest path problem; Very large scale integration; Dijkstra´s Algorithm; Field Programmable Gate Arrays; Hardware Architecture; Shortest Path;
Conference_Titel :
TENCON 2009 - 2009 IEEE Region 10 Conference
Conference_Location :
Singapore
Print_ISBN :
978-1-4244-4546-2
Electronic_ISBN :
978-1-4244-4547-9
DOI :
10.1109/TENCON.2009.5396155
