File:Automated cartography by an autonomous mobile robot using ultrasonic range finders (IA automatedcartogr1094539971).pdf

The problem solved was for an autonomous mobile robot to generate a precise map of its orthogonal, indoor environment. The maps generated by the robot's sensors must be perfect so they can be used in subsequent navigation tasks using the same sensors. Our approach performed map-making incrementally with a partial world data structure describing incomplete polygons. A striking feature of the partial world data structure was they consist of 'real' and 'inferred' edges. Basically, in each learning step, the robot's sensors scan an unexplored region to obtain new 'real' and 'inferred' edges by eliminating at least one 'inferred' edge. The process continues until no 'inferred' edges remain in the partial world. In order to make this algorithm possible, linear fitting of sensor input, smooth vehicle motion control, dead reckoning error correction, and a mapping algorithm were developed. This algorithm was implemented on the autonomous mobile robot Yamabico-11. The results of this experiment using Yamabico-11 were threefold. (1) A smooth path tracking algorithm resulted in motion error of less than 2% in all experiments. (2) Dead reckoning error correction experiments revealed small, consistent vehicle odometry errors. The maximum observed error was 1.93 centimeters and 1.04 deg over a 9.14 meter course. (3) Precise mapping was demonstrated with a map accuracy in the worst case of 25 centimeters and 2 deg of hand measured maps. The ability to explore an indoor world space while correcting dead reckoning error is a significant improvement over previous work (Leonard 91) (Crowley 86) (Cox 91)