A hardware accelerator and FPGA realization for reduced visibility graph construction using efficient bit representations

The reduced visibility graph (RVG) is an important structure for computation of shortest paths for mobile robots. An efficient bit representation is proposed to construct segments that are part of the RVG. Based on the bit representation, a hardware-efficient scheme is presented whose computational complexity is O(k2 log(n/k)), where k is the number of objects and n is the total number of vertices. An architecture that accomplishes the construction of the RVG without division or explicit intersection point calculations is proposed. An efficient field-programmable gate array implementation using block random access memory on an XCV3200E device is presented. © 2007 IEEE.