Authors: Arno Bücken and Sebastian Thrun (1996)
Abstract
Our goal is autonomous real-time control of a mobile robot. In this paper we want to show a possibility to learn topological maps of a large-scale indoor environment autonomously. In the literature there are two paradigms how to store information on the environment of a robot: as a grid-based (geometric) or as a topological map. While grid-based maps are considerably easy to learn and maintain, topological maps are quite compact and facilitate fast motionplanning.
Introduction
In the mid-1990s, mobile robot mapping was characterized by a divide between two competing philosophies. Grid-based (geometric) maps represent the world as a fine-grained grid of occupied or free cells, which are straightforward to build from sensor data but computationally expensive for long-distance pathfinding. Conversely, topological maps represent the environment as a graph of nodes and edges, offering high efficiency for planning but proving difficult to construct autonomously and consistently. This paper presents a method to bridge these paradigms by automatically converting high-resolution grid maps into compact, human-like topological graphs.
Methods
The authors introduce a multi-step pipeline to transform geometric data into a topological structure. The process begins by thresholding a probability grid map into a binary representation of free versus occupied space. From this, a Voronoi diagram is generated to serve as a "skeleton" of the environment, consisting of lines equidistant from the nearest obstacles.
The core innovation lies in the detection of "critical points" on this skeleton—local minima of clearance that typically correspond to narrow passages like doorways or hallway transitions. By drawing "critical lines" across the map at these points, the environment is naturally partitioned into distinct regions (rooms and hallway segments). Each region is then represented as a node in a topological graph, with edges connecting adjacent regions. An optional pruning step merges small or redundant regions to ensure the final map aligns with human-centric concepts of space.
Results and Discussion
The algorithm was integrated into the RHINO software and tested on large-scale indoor office environments. The results demonstrated significant advantages in both efficiency and performance:
- Computational Efficiency: The extraction process is highly performant, typically running in under 10 seconds.
- Planning Speedup: By utilizing the topological graph for high-level planning before calculating local geometric paths, motion planning was accelerated by a factor of $10^3$ to $10^6$.
- Path Optimality: Despite the abstraction, the resulting paths were found to be only approximately 2% longer than the absolute shortest geometric paths.
- Robustness: By deriving the topology directly from a consistent grid map, the system avoids the common alignment and loop-closure issues associated with building topological maps from scratch.
While the Voronoi-based approach can be sensitive to noise in the grid map, the pruning stage effectively mitigates extraneous branching. This representation also allows robots to identify critical lines as potential bottlenecks, which is useful for navigating dynamic environments where passages may be temporarily blocked.
Conclusion
Bücken and Thrun's approach successfully combines the strengths of geometric and topological mapping. By using narrow passages as natural boundaries for spatial segmentation, they provide a robust framework for autonomous robots to navigate complex indoor environments with human-like efficiency and minimal computational overhead.
Reference: Bücken, A., & Thrun, S. (1996). Learning Topological Maps: An Alternative Approach. Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI-96).
Summary updated