A hardware-efficient scheme and FPGA realization for computation of single pair shortest path for a mobile automaton

Computing the shortest path between a pair of points is an important problem in robotics and intelligent transportation systems. The ability to compute this path in real time is valuable in a number of situations. These include an automaton attempting to reach its destination minimizing chances of collision with obstacles. Previous work on shortest path is limited to sequential algorithms and parallel algorithms (for some versions of the problem) on general-purpose architectures. The authors develop a new hardware-efficient algorithm and present an FPGA implementation for shortest path calculation between an automaton’s start point and its destination. Results of implementation in Xilinx Virtex FPGA are promising: the solution operates at approximately 68 MHz and the implementation for a graph with 58 nodes and 82 edges fits in one XC2V6000 device.