# Sparse 3D Topological Graphs for Micro-Aerial Vehicle Planning

arXiv: https://arxiv.org/abs/1803.04345 · HTML: https://mlsanity.com/paper/1803.04345/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2018.

## Built on by (most cited first, 6 of 6)

- [Kimera: from SLAM to Spatial Perception with 3D Dynamic Scene Graphs](https://mlsanity.com/paper/2101.06894/) (2021)
- [S-Graphs+: Real-time Localization and Mapping leveraging Hierarchical Representations](https://mlsanity.com/paper/2212.11770/) (2022)
- [Learning High-level Semantic-Relational Concepts for SLAM](https://mlsanity.com/paper/2310.00401/) (2023)
- [Advanced Situational Graphs for Robot Navigation in Structured Indoor Environments](https://mlsanity.com/paper/2211.08754/) (2022)
- [TOPO-Bench: An Open-Source Topological Mapping Evaluation Framework with Quantifiable Perceptual Aliasing](https://mlsanity.com/paper/2510.04100/) (2025)
- [Prior-SG: Task and Prior Driven Region Segmentation for Scene Graphs in Arbitrarily-Structured Environments](https://mlsanity.com/paper/2608.06170/) (2026)

## Abstract (arXiv)

Micro-Aerial Vehicles (MAVs) have the advantage of moving freely in 3D space. However, creating compact and sparse map representations that can be efficiently used for planning for such robots is still an open problem. In this paper, we take maps built from noisy sensor data and construct a sparse graph containing topological information that can be used for 3D planning. We use a Euclidean Signed Distance Field, extract a 3D Generalized Voronoi Diagram (GVD), and obtain a thin skeleton diagram representing the topological structure of the environment. We then convert this skeleton diagram into a sparse graph, which we show is resistant to noise and changes in resolution. We demonstrate global planning over this graph, and the orders of magnitude speed-up it offers over other common planning methods. We validate our planning algorithm in real maps built onboard an MAV, using RGB-D sensing.