Abstract
Research on mobile robot navigation has produced two major paradigms for mapping indoor environments: grid-based and topological. While grid-based methods produce accurate metric maps, their complexity often prohibits efficient planning and problem solving in large-scale indoor environments. Topological maps, on the other hand, can be used much more efficiently, yet accurate and consistent topological maps are considerably difficult to learn in large-scale environments. This paper describes an approach that integrates both paradigms: grid-based and topological. Grid-based maps are learned using artificial neural networks and Bayesian integration. Topological maps are generated on top of the grid-based maps, by partitioning the latter into coherent regions. By combining both paradigms, the approach presented here gains the best of both worlds: accuracy/consistency and efficiency. The paper gives results for autonomously operating a mobile robot equipped with sonar sensors in populated multi-room environments.
Introduction
In the mid-1990s, the field of mobile robot navigation was characterized by a fundamental tension between two mapping paradigms. Grid-based (metric) maps represent the environment as a fine-grained grid of occupancy cells. These maps are highly effective for precise localization and handling sensor noise but suffer from high computational costs and memory requirements when used for path planning in large-scale environments. Conversely, topological maps represent the environment as a graph of landmarks and their connectivity. While computationally efficient for planning, topological maps are notoriously difficult to construct reliably from raw sensor data due to "perceptual aliasing"—the difficulty in distinguishing between similar-looking landmarks like identical hallways or doorways.
This paper proposes a hybrid approach that integrates these two paradigms. By "grounding" an abstract topological graph in a detailed occupancy grid, the authors aim to achieve the metric accuracy required for localization alongside the computational efficiency needed for high-level planning.
Methodology
The proposed system utilizes a multi-layered architecture to build and maintain environmental representations.
Grid-Based Layer
The foundation of the system is a metric occupancy grid. To handle the inherent noise and uncertainty of sonar sensors, the robot employs an artificial neural network to interpret sonar scans. This network converts raw distance data into local occupancy probabilities. These local interpretations are then integrated over time using Bayesian rules to construct a consistent 2D metric map.
Position Estimation
To maintain map consistency, the system must combat odometry drift. It integrates three distinct information sources:
- Wheel Encoders: Providing basic dead-reckoning.
- Map Correlation: Matching local sensor scans against the existing global map to refine the robot's pose.
- Wall Orientation Tracker: A global tracker that leverages the "Manhattan World" assumption—that most indoor walls are either parallel or orthogonal—to maintain a stable heading.
Topological Extraction
The most significant contribution of this work is the automated derivation of a topological map from the completed grid map. This geometric pipeline involves:
- Thresholding: Converting the probabilistic grid into a binary representation of free and occupied space.
- Voronoi Diagram Construction: Generating a "skeleton" of the free space consisting of points equidistant from the nearest obstacles.
- Critical Point Identification: Identifying narrow passages, such as doorways, by finding local minima in the clearance of the Voronoi diagram. These "critical lines" serve as natural boundaries to partition the map into coherent regions (e.g., rooms and hallways).
- Graph Generation: Each partitioned region is mapped to a node in the topological graph, with edges representing the critical lines (passageways) connecting them.
Experimental Setup
The approach was validated using several real-world mobile robots, including RHINO (University of Bonn), XAVIER, and AMELIA (Carnegie Mellon University). These robots were equipped with rings of 24 sonar sensors.
Experiments were conducted in various multi-room university office environments and during the 1994 AAAI autonomous robot competition. A mobile robot simulator was also utilized to generate training data for the neural network sonar interpreter.
Results and Discussion
The hybrid mapping approach demonstrated significant improvements in both efficiency and robustness.
Planning Efficiency vs. Path Optimality
The primary advantage of the topological layer is the reduction in search space complexity. Planning on the topological graph was found to be three to four orders of magnitude more efficient than planning directly on the high-resolution grid. Despite this massive abstraction, the resulting paths were remarkably close to optimal, averaging only 1.82% longer than the mathematically shortest path found on the grid. In 83.4% of the experimental trials, the topological planner returned a "loss-free" plan identical in length to the metric plan.
Scale and Robustness
The system successfully mapped and navigated environments exceeding 100 meters in length. By deriving the topology from the grid, the robot effectively solved the perceptual aliasing problem; the underlying metric map naturally disambiguated identical-looking rooms based on their global coordinates.
Conclusion
This research demonstrates that integrating metric and topological representations allows mobile robots to navigate complex, large-scale environments with both precision and speed. However, several limitations remain. The current position estimation relies on the "Manhattan World" assumption, which may not hold in non-orthogonal environments. Furthermore, while the system handles local drift, it does not yet implement full global loop closure (re-estimating the entire path history), which was computationally intractable at the time of publication. Future work suggests that replacing sonar with laser range finders would further enhance the accuracy of the initial grid-based layer.
Summary updated