A parallel algorithm, architecture and FPGA realization for landmark determination and map construction in a planar unknown environment

摘要

Good representations of the environment are crucial for navigation of autonomous systems. This paper presents a time and space-efficient hardware-based solution for construction of an environment map based on range sensor data gathered by a robot at P locations in an unknown 2D environment. In particular, the paper proposes a new parallel algorithm based on training a set of K place units for generating "perceptual landmarks" and connecting the landmarks based on sensor information. The computational complexity of this parallel algorithm is O(MP log K) where M is the number of training iterations. The algorithm has been mapped to hardware. The architecture comprises of components such as Content Addressable Memory and Wallace tree adders. The architecture has been implemented in Xilinx Field Programmable Gate Array (FPGA) and results show that the proposed design achieves high speed taking approximately 100 ms to identify 49 landmarks and build a map of an environment of size 3.75 m x 3.75 m. Further, the entire design for an environment with 196 sample points and 49 processing elements fits in one XCV3200E (or XC2V6000) device. The details of the experimental setup for gathering data are also presented.