Hardware design for efficient construction of an environment map for mobile robot navigation

Various geometric structures play an important role in the solution of the robotic path planning problem. These include convex hulls, visibility graphs, tangent graphs and Voronoi diagrams. While substantial work has been done on sequential algorithms for constructing various geometric structures, reports on algorithms that can be easily ported to hardware are relatively scarce. With an increasing need to handle cluttered and dynamic environments, real-time solutions for constructing geometric structures via custom hardware is desirable. This paper presents a new hardware-directed method for construction of the complete visibility graph of a planar domain valuable for mobile robot path planning. Initial results of implementation of the hardware design are promising and point to the possibilities of developing a low-cost and high speed system for environment representation.