A new Hough transform based position estimation algorithm

This paper proposes a fast, robust Hough transform based algorithm for estimating the location (position and orientation) of a robot in a two-dimensional terrain by using range sensor data. In our approach, the overall workspace is divided into M×N grids to form a “global” map. From the acquired range sensor data, a “local” map which represents the robot´s line of sight environment is constructed. Then the error of the location of the robot can be determined by matching the found “local” map with the “global” map. In this paper, the matching process is performed by a Hough transform technique which is in many aspects an improvement over the simple template matching. Our proposed technique has the advantages of large noise tolerance and it is amenable to parallel implementation on a suitable network of rather simple processing elements