The design of a hardware accelerator for real-time complete visibility graph construction and efficient FPGA implementation

A valuable geometric structure in mobile robot path planning is the complete visibility graph. This letter proposes new parallel algorithms that can be mapped to reconfigurable hardware for construction of the complete visibility graph in an environment with: 1) multiple convex polygonal objects and 2) multiple nonconvex polygonal objects. Results of implementation in a Xilinx Virtex field-programmable gate array demonstrate that the proposed approach is area-time efficient: the design for an environment with roughly 60 vertices fits on one XCV3200E device and operates at dose to 60 MHz. © 2005 IEEE.