This paper presents a new map specifically designed for robots operating in large environments and possibly in higher dimensions. We call this map the hierarchical atlas because it is a multilevel and multiresolution representation. For this paper, the hierarchical atlas has two levels: at the highest level there is a topological map that organizes the free space into submaps at the lower level. The lower-level submaps are simply a collection of features. The hierarchical atlas allows us to perform calculations and run estimation techniques, such as Kalman filtering, in local areas without having to correlate and associate data for the entire map. This provides a means to explore and map large environments in the presence of uncertainty with a process named hierarchical simultaneous localization and mapping. As well as organizing information of the free space, the map also induces well-defined sensor-based control laws and a provably complete policy to explore unknown regions. The resulting map is also useful for other tasks such as navigation, obstacle avoidance, and global localization. Experimental results are presented showing successful map building and subsequent use of the map in large-scale spaces.

In this paper we present a new technique for improving the azimuth resolution of ultrasonic range sensors frequently used with mobile robots. This improvement is achieved without a significant increase in the latency, or processing delay, of the system. Our approach decreases the azimuth uncertainty of a sensor reading by eliminating portions of the reading that are contradicted by subsequent readings. Our idea bears resemblance to space carving as used by the vision community, where a ray of light is used to define the boundaries of an obstacle. A sonar model similar to that commonly utilized by occupancy grids is used. Our method, termed arc carving, can be used to produce maps that are both accurate and with low enough latency for robust mobile robot navigation. Experimental results verify this approach over spaces as large as 5000 square meters.

This paper presents a novel method of combining topological and feature-based mapping strategies to create a hierarchical approach to simultaneous localization and mapping (SLAM). More than simply running both processes in parallel, we use the topological mapping procedure to organize local feature-based methods. The result is an autonomous exploration and mapping strategy that scales well to large environments and higher dimensions while confronting the issue of obstacle avoidance. We have obtained successful results of our approach in an area spanning 5000 square meters.