A hardware-architecture for control-law based Voronoi diagram computation and FPGA implementation

Map-making is a challenging task when the environment is unknown and the collected information is local. This paper presents the design of a hardware architecture for sensor-based map construction in a planar environment. In particular, the map is a Voronoi diagram of the environment. The Voronoi construction is based on a control law. Features of the proposed architecture are absence of arithmetic operations expensive in digital hardware and a planning algorithm for completing the map. Also, the implementation of control-law uses look-up tables and reuse of CORDIC module to avoid matrix multiplications. A highly area-efficient FPGA implementation of the architecture is also reported. Experiments with an FPGA-based robot confirm the effectiveness of the proposed approach.