A Robot Map-Creation Algorithm
Jon Howell · 1999
This paper describes an algorithm by which a robot can construct a map on the fly, and localize itself to its self-constructed map. This work was performed as my term project in Artificial Intelligence class, CS 104. 1 The model A robot should be able to navigate around a space with some persistent memory of the features of that space. In my system, the robot begins by taking a sonar sounding, which produces a polar distance map of the robot’s immediate neighborhood. The robot is assumed to be at the origin (0, 0), and these initial soundings are taken to be the robot’s initial map. Then the robot proceeds to move in some direction (goal planning is outside the scope of this project), stops, and takes another sounding. This sounding is fit to the existing map, on the assumption that the features in the robot’s neighborhood have not changed much. The best fit returns a most likely location of the robot relative to the origin; the soundings are then shifted by the robot’s now-known position, and contributed to the map. This cycle repeats indefinitely as the robot explores; at each stop, the soundings pointing “behind” the robot’s path help it localize itself, and the soundings pointing ahead contribute new information to the map. In this paper, I assume the robot has reliable orientation information, such as from a compass. It may have a few degrees of error, but that error does not accumulate as would error from a relative sensing system, such as odometry. The algorithm presented here is based on Brown and Donald’s idea of a “feasible pose” [BD96].