Header menu link for other important links
X
A parallel algorithm, architecture and FPGA realization for high speed determination of the complete visibility graph for convex objects
Published in
2006
Volume: 30
   
Issue: 1
Pages: 1 - 14
Abstract
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.
About the journal
JournalMicroprocessors and Microsystems
ISSN01419331
Open AccessNo
Concepts (12)
  •  related image
    COMPLETE VISIBILITY GRAPHS
  •  related image
    FPGA REALIZATION
  •  related image
    Robot navigation
  •  related image
    SEQUENTIAL ALGORITHMS
  •  related image
    Computer architecture
  •  related image
    Computer hardware
  •  related image
    Field programmable gate arrays
  •  related image
    Graph theory
  •  related image
    Motion planning
  •  related image
    Parallel algorithms
  •  related image
    Robotics
  •  related image
    Object recognition