# Hierarchical 3D Scene Graph Construction and Belief-based Planning for Semantic Navigation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 34 of its 43 references that are in the map.
- First posted on arXiv 30 Jun 2026.

## Builds on (most cited first, 30 of 34)

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Matterport3D: Learning from RGB-D Data in Indoor Environments](https://mlsanity.com/paper/1709.06158/) (2017)
- [Habitat-Matterport 3D Dataset (HM3D): 1000 Large-scale 3D Environments for Embodied AI](https://mlsanity.com/paper/2109.08238/) (2021)
- [On Evaluation of Embodied Navigation Agents](https://mlsanity.com/paper/1807.06757/) (2018)
- [Object Goal Navigation using Goal-Oriented Semantic Exploration](https://mlsanity.com/paper/2007.00643/) (2020)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [ConceptGraphs: Open-Vocabulary 3D Scene Graphs for Perception and Planning](https://mlsanity.com/paper/2309.16650/) (2023)
- [3D Scene Graph: A Structure for Unified Semantics, 3D Space, and Camera](https://mlsanity.com/paper/1910.02527/) (2019)
- [Habitat 3.0: A Co-Habitat for Humans, Avatars and Robots](https://mlsanity.com/paper/2310.13724/) (2023)
- [VLFM: Vision-Language Frontier Maps for Zero-Shot Semantic Navigation](https://mlsanity.com/paper/2312.03275/) (2023)
- [Hierarchical Open-Vocabulary 3D Scene Graphs for Language-Grounded Robot Navigation](https://mlsanity.com/paper/2403.17846/) (2024)
- [CoWs on Pasture: Baselines and Benchmarks for Language-Driven Zero-Shot Object Navigation](https://mlsanity.com/paper/2203.10421/) (2022)
- [ZSON: Zero-Shot Object-Goal Navigation using Multimodal Goal Embeddings](https://mlsanity.com/paper/2206.12403/) (2022)
- [Habitat Synthetic Scenes Dataset (HSSD-200): An Analysis of 3D Scene Scale and Realism Tradeoffs for ObjectGoal Navigation](https://mlsanity.com/paper/2306.11290/) (2023)
- [InstructNav: Zero-shot System for Generic Instruction Navigation in Unexplored Environment](https://mlsanity.com/paper/2406.04882/) (2024)
- [Uni-NaVid: A Video-based Vision-Language-Action Model for Unifying Embodied Navigation Tasks](https://mlsanity.com/paper/2412.06224/) (2024)
- [Kimera: from SLAM to Spatial Perception with 3D Dynamic Scene Graphs](https://mlsanity.com/paper/2101.06894/) (2021)
- [ESC: Exploration with Soft Commonsense Constraints for Zero-shot Object Navigation](https://mlsanity.com/paper/2301.13166/) (2023)
- [L3MVN: Leveraging Large Language Models for Visual Target Navigation](https://mlsanity.com/paper/2304.05501/) (2023)
- [Habitat-Matterport 3D Semantics Dataset](https://mlsanity.com/paper/2210.05633/) (2022)
- [SG-Nav: Online 3D Scene Graph Prompting for LLM-based Zero-shot Object Navigation](https://mlsanity.com/paper/2410.08189/) (2024)
- [GOAT: GO to Any Thing](https://mlsanity.com/paper/2311.06430/) (2023)
- [Open3DSG: Open-Vocabulary 3D Scene Graphs from Point Clouds with Queryable Objects and Open-Set Relationships](https://mlsanity.com/paper/2402.12259/) (2024)
- [OpenFMNav: Towards Open-Set Zero-Shot Object Navigation via Vision-Language Foundation Models](https://mlsanity.com/paper/2402.10670/) (2024)
- [Foundations of Spatial Perception for Robotics: Hierarchical Representations and Real-time Systems](https://mlsanity.com/paper/2305.07154/) (2023)
- [VoroNav: Voronoi-based Zero-shot Object Navigation with Large Language Model](https://mlsanity.com/paper/2401.02695/) (2024)
- [UniGoal: Towards Universal Zero-shot Goal-oriented Navigation](https://mlsanity.com/paper/2503.10630/) (2025)
- [FUEL: Fast UAV Exploration using Incremental Frontier Structure and Hierarchical Planning](https://mlsanity.com/paper/2010.11561/) (2020)
- [ImagineNav: Prompting Vision-Language Models as Embodied Navigator through Scene Imagination](https://mlsanity.com/paper/2410.09874/) (2024)
- [CogNav: Cognitive Process Modeling for Object Goal Navigation with LLMs](https://mlsanity.com/paper/2412.10439/) (2024)

## Abstract (arXiv)

Semantic navigation is a fundamental task for embodied agents operating in unseen environments, requiring both semantic understanding and long-term decision-making. Recent foundation models have empowered agents with rich semantic priors for this task. However, without structured global representations, decision-making often falls back on local observations and greedy strategies, resulting in inefficient exploration and myopic behaviors, especially in long-distance navigation. To address these challenges, we propose a zero-shot semantic navigation framework. Our method incrementally maintains an online Hierarchical 3D Scene Graph (HSG) to form a multi-granular semantic topology over objects, zones, and regions, serving as a compact state abstraction for global planning. Building on this memory, we introduce a hierarchical belief-based planning framework that fuses semantic priors with exploration evidence on the HSG, and performs finite-horizon rollouts on an HSG-based simulator to explicitly estimate the long-term expected returns of candidate macro-actions. This enables globally consistent decisions and reduces redundant backtracking. Extensive experiments in high-fidelity simulation environments across multiple tasks and datasets demonstrate that our method outperforms existing state-of-the-art methods, particularly in long-distance scenarios, where our approach improves SR and SPL by an average of 9.4% and 5.0%, respectively.