Source-linked AI summary
Topomap: Topological Mapping and Navigation Based on Visual SLAM Maps
Fabian Blöchliger, Marius Fehr, Marcin Dymczyk, Thomas Schneider, Roland Siegwart
TL;DR
Occupancy-map planning and navigation can be computationally demanding, especially with noisy input data, limiting mobile-platform capabilities. Topomap derives occupancy information from sparse visual SLAM landmarks, forms convex free-space clusters, and uses their topological connections for planning. Topomap showed no significant quality loss against RRT* on a dense TSDF map, with drastically lower A* planning time and compact maps.
Problem
Occupancy-map planning and navigation can be computationally demanding, especially with noisy input data, limiting mobile-platform capabilities.
Source: §I · p. 2Method
Topomap derives occupancy information from sparse visual SLAM landmarks, forms convex free-space clusters, and uses their topological connections for planning.
Source: §I · p. 2, B. Occupancy from Sparse Features · p. 3Results
Topomap showed no significant quality loss against RRT* on a dense TSDF map, with drastically lower A* planning time and compact maps.
Source: C. Path Planning · p. 7, §V · p. 8Takeaways & Limitations
Abstract
from arXiv · showhide
Visual robot navigation within large-scale, semi-structured environments deals with various challenges such as computation intensive path planning algorithms or insufficient knowledge about traversable spaces. Moreover, many state-of-the-art navigation approaches only operate locally instead of gaining a more conceptual understanding of the planning objective. This limits the complexity of tasks a robot can accomplish and makes it harder to deal with uncertainties that are present in the context of real-time robotics applications. In this work, we present Topomap, a framework which simplifies the navigation task by providing a map to the robot which is tailored for path planning use. This novel approach transforms a sparse feature-based map from a visual Simultaneous Localization And Mapping (SLAM) system into a three-dimensional topological map. This is done in two steps. First, we extract occupancy information directly from the noisy sparse point cloud. Then, we create a set of convex free-space clusters, which are the vertices of the topological map. We show that this representation improves the efficiency of global planning, and we provide a complete derivation of our algorithm. Planning experiments on real world datasets demonstrate that we achieve similar performance as RRT* with significantly lower computation times and storage requirements. Finally, we test our algorithm on a mobile robotic platform to prove its advantages.
I. INTRODUCTION
Occupancy-map navigation can require costly sensors and computation while providing little higher-level structure, especially with noisy input. Topomap derives convex free-space clusters and a planning graph directly from sparse visual SLAM maps.
I. INTRODUCTION
- Occupancy-map planning can demand costly sensors and computation, and occupancy maps do not encode higher-level divisions such as rooms.These constraints can limit mobile platforms.Source: §I · pp. 1–2
- Topomap extracts free space from sparse visual SLAM landmarks and represents it as convex clusters connected by portals for safe transitions.The topological graph records cluster connectivity, while its dual navigation graph supports global planning.Source: §I · p. 2
- The work proposes a pipeline from sparse visual SLAM maps to a free-space representation and topological map for global planning.Its cluster-growing and merging algorithm uses a volumetric occupancy grid to form convex clusters from noisy, partly incomplete data.Source: §I · p. 2
- The authors report an extensive real-world dataset evaluation and comparison with a state-of-the-art grid-based planner.The introduction does not give comparative results.Source: §I · p. 2
II. RELATED WORK
Prior topological mapping approaches partition environments in different ways, but the authors distinguish Topomap by deriving convex free-space regions from sparse visual SLAM features. They argue that free-space and convexity information better suits path planning than similarity-based clusters or local-grid strategies.
II. RELATED WORK
- Earlier work partitions environments into discrete places for topometric localization, hierarchical bundle adjustment, or map reduction –.Topological mapping combined with vision sensors has a longer history.Source: §II · p. 2
- Voronoi-based partitions can delimit free-space regions by narrow passages, but applying them to noisy, sparse visual SLAM landmarks is challenging.An incremental version is also described in prior work.Source: §II · p. 2
- Co-visibility clusters can form human-meaningful groups, but lack explicit free-space and convexity information needed for the authors’ planning approach –.Low viewpoint invariance can also split one place traversed from different directions.Source: §II · pp. 2–3
- Local occupancy grids attached along a metric SLAM map may capture topology, but still require local path planning through topological vertices.The authors contrast this with their assumption that vertices are convex.Source: §II · p. 3
- For MAV trajectory generation, prior methods use many overlapping convex regions –, whereas Topomap proposes compact cluster expansion and integration with discrete occupancy maps.Source: §II · p. 3
III. METHODOLOGY
The methodology builds a topological map from free-space information derived from sparse visual SLAM features, then uses its convex regions for global planning.
III. METHODOLOGY
- The methodology first defines the topological map representation, then derives free space from sparse visual SLAM features.Source: §III · p. 3
- Voxel-based growing forms compact, convex free-space clusters, and neighboring clusters are merged when their combined shape contains few obstacle voxels.This reduces the number of clusters.Source: §III · p. 3
- The resulting topological map is used for global path planning.Source: §III · p. 3
A. Topological Map Representation
Topomap represents traversable space as convex voxel clusters linked by portals, while deriving approximate occupancy from sparse visual landmarks through a TSDF and post-processing.
A. Topological Map Representation
- Each convex voxel region represents a partially enclosed area, such as a room, connected to neighboring regions by portals.Only the convex hulls are serialized, preserving vertex volume, connections, and portals without storing occupancy maps.Source: A. Topological Map Representation · p. 3
B. Occupancy from Sparse Features
- Sparse landmarks are ray-traced from their observer poses through a voxel grid to build an approximate TSDF of projective distances to obstacle surfaces.The distance updates stop at a predefined truncation distance.Source: B. Occupancy from Sparse Features · p. 3
- Occupancy is binarized by thresholding voxel distances at 90% of the truncation distance, then isolated small occupied groups are filtered out.Such outliers may come from dynamic objects or badly triangulated landmarks.Source: B. Occupancy from Sparse Features · p. 3
C. Compact Cluster Growing
The algorithm grows compact, convex voxel clusters from the binarized TSDF. It expands from high-confidence free-space locations while constraining cluster shape and preventing obstacle voxels from entering the convex hull.
C. Compact Cluster Growing
- Clusters start at random voxels along the explorer trajectory, where free-space certainty is highest.Source: C. Compact Cluster Growing · p. 3
- Each iteration considers directly adjacent non-occupied voxels and uses PCA to select compact candidates based on the cluster’s principal axes.The axes capture 98% of included voxels; candidates are limited to a distance of rmin + δ from the center.Source: C. Compact Cluster Growing · pp. 3–4, Figure 3 · p. 4
- Only candidates that preserve convexity are added, with obstacle-free rays between candidates and existing cluster voxels enforcing the condition.Growing stops when no candidates can be added, and new clusters are grown until the explorer trajectory is covered.Source: C. Compact Cluster Growing · p. 4, Figure 3 · p. 4
D. Convex Cluster Merging
Topomap first merges conservative convex clusters to reduce their number, then plans through the resulting cluster connectivity using portal centers.
D. Convex Cluster Merging
- Merging neighboring clusters reduces the number of conservative regions while allowing a small number of obstacle voxels in the combined convex hull.The obstacle ratio threshold controls this trade-off; higher values yield fewer clusters but leave more responsibility to a local planner.Source: D. Convex Cluster Merging · p. 4
- The algorithm repeatedly tests adjacent cluster pairs in randomized order and merges a pair when its combined convex hull meets the obstacle-ratio threshold.It computes each combined hull with Quickhull and stops when no further merges satisfy the criterion.Source: D. Convex Cluster Merging · p. 4
E. Topological Navigation
- For navigation, clusters are graph vertices and adjacent clusters are connected by portals; A* searches a graph linking the start and destination to portal centers.The start and destination must lie within clusters because the method has no information about space outside them.Source: E. Topological Navigation · p. 4
IV. EXPERIMENTAL EVALUATION
The evaluation covers sparse-landmark TSDF integration, cluster creation in real-world environments, and comparison of the topological planner with RRT*. A reported office example contrasts sparse-landmark and dense-stereo TSDF construction.
IV. EXPERIMENTAL EVALUATION
- The evaluation assesses sparse-landmark TSDF integration against dense stereo, cluster creation across real-world environments, and the topological planner against RRT*.Source: §IV · p. 4
- Experiments used synchronized visual-inertial datasets, a dual-core Intel i7-7600U processor, and SLAM maps built with visual-inertial odometry, bundle adjustment, and loop closure.Source: §IV · p. 4
- 2.1 s versus 43.3 s: integrating 177′269 landmarks produced 39′791 TSDF voxels, while integrating 1322 stereo images produced 65′231 voxels.The comparison uses a 0.25 m voxel size; the caption reports that sparse landmarks preserve most relevant environment structure.Source: Figure 4 · p. 5
A. TSDF Maps from Visual Landmarks
Sparse visual landmarks are evaluated as a source of TSDF occupancy information against dense stereo maps. Larger voxels capture more free space, but also increase discretization error.
A. TSDF Maps from Visual Landmarks
- The evaluation compares landmark-based TSDF maps with dense stereo maps built from semi-global-matching depth images using identical integration parameters.The stereo images came from a 10 cm baseline camera; maximum ray length and truncation distance were set to 4.0–7.0 m and 0.1–0.5 m, respectively.Source: A. TSDF Maps from Visual Landmarks · p. 5
- Sparse-landmark TSDF maps retain relevant structures such as walls, corridors, and doorways despite sparsity and outlier voxels in some free-space areas.Later filtering removes small disconnected occupied components, while convexity constraints limit cluster growth through or around obstacles despite missing occupancy information.Source: A. TSDF Maps from Visual Landmarks · p. 5
- Larger voxel sizes capture more free space but increase discretization errors, such as missing small obstacles; the dense-map reference shares these effects.Source: A. TSDF Maps from Visual Landmarks · p. 5, Figure 5 · p. 5
B. Topological Map Creation
Topomap grows and merges voxel clusters to simplify the map while preserving useful free-space structure. Its obstacle-ratio threshold trades map complexity against obstacle inclusion, and the compact representation can omit environmental detail.
B. Topological Map Creation
- 105 clusters become 24 in three merging steps, while topological edges fall from 121 to 29 at a 5% obstacle-ratio threshold.Merging combines small clusters along corridors while retaining finer clustering in corners.Source: B. Topological Map Creation · p. 5, Figure 6 · p. 6
- Office maps separate rooms and corridors, open-space maps form large convex clusters, and ray-traced pillar gaps enable paths beyond the explorer’s trajectory.The open-space example also simplifies a winding explorer trajectory.Source: B. Topological Map Creation · pp. 5–6, Figure 7 · p. 6
- Raising the obstacle-ratio threshold reduces cluster count but admits more obstacle voxels, shifting some collision-avoidance responsibility to the local planner.Lower thresholds permit fewer obstacle voxels but produce many small clusters; tuning is harder in large spaces with varying obstacle/free-space configurations.Source: Figure 8 · p. 6, B. Topological Map Creation · pp. 6–7
- Topological maps were created for most datasets in under a minute and require low storage, though their compactness can oversimplify environments and lose details.The reported storage requirement is significantly lower than for the full TSDF.Source: B. Topological Map Creation · p. 7, Table I · p. 7
C. Path Planning
Topomap plans on a small navigation graph, producing paths slightly longer than RRT* paths while requiring much less planning time. The system was also tested on a Turtlebot in an industrial site.
C. Path Planning
- The evaluation covers generated-path assessment and deployment on a real robotic platform.The Turtlebot’s VI sensor provided global localization within the SLAM map; the laser served only local obstacle avoidance.Source: C. Path Planning · p. 7, Figure 10 · p. 7
- Topomap paths are slightly longer than RRT* paths, while A* planning typically takes some 100 µs versus RRT*’s 2 s planning limit.The comparison samples 100 random start-goal trajectories and normalizes path distance by direct-line distance.Source: C. Path Planning · p. 7
- A Turtlebot completed an approximately 15 m trajectory using visual-SLAM localization and a 2D laser only for local obstacle avoidance.The robot was deployed at a semi-structured industrial site with a VI sensor and computationally constrained processing unit.Source: C. Path Planning · p. 7, Figure 10 · p. 7
V. CONCLUSIONS
The conclusions present Topomap as a framework for navigation from sparse, noisy visual measurements, using convex free-space clusters to support fast planning and compact maps. Evaluations report comparable path quality to RRT* and successful mobile-robot deployment.
V. CONCLUSIONS
- Voxel-based growing and merging segments sparse, noisy visual measurements into convex clusters, enabling planning orders of magnitude faster than conventional grid-based planners and compact maps.The authors also report that the approach reduces hardware requirements compared with state-of-the-art approaches.Source: §V · pp. 7–8
- Evaluations found no significant quality loss versus RRT* on a dense TSDF map, and the system was successfully deployed on a mobile robot.The authors also report reliable TSDF-map construction from sparse vision-based measurements.Source: §V · p. 8
- Future work includes testing larger real-world scenarios, integrating the system on a flying platform, and adding semantic information to topological maps.Source: §V · p. 8