A parallel algorithm, architecture and FPGA realization for high speed determination of the complete visibility graph for convex objects

The complete visibility graph is a valuable geometric structure in robot path planning. The literature on constructing the graph has focussed on sequential algorithms and implementations on general-purpose processors. With an increasing need to handle cluttered and/or dynamic environments, a very high speed solution for constructing the graph via custom hardware becomes important. This paper presents a new parallel algorithm for construction of the complete visibility graph of an environment with multiple convex polygonal objects. The algorithm runs in O(n(p+log(n/p))) time for an environment with p objects having a total of n vertices. Results of implementation of the hardware design in Xilinx Virtex FPGA show that the design operates at high speed with low area requirement. In particular, the solution operates at 50 MHz for n close to 100. Further, the design fits on one FPGA device for fairly large input sizes. © 2005 Elsevier B.V. All rights reserved.