Source-linked AI summary
SG-Nav: Online 3D Scene Graph Prompting for LLM-based Zero-shot Object Navigation
Hang Yin, Xiuwei Xu, Zhenyu Wu, Jie Zhou, Jiwen Lu
TL;DR
Zero-shot object navigation methods lack sufficient scene context for LLM reasoning when they use only nearby object text. SG-Nav represents environments with an online hierarchical 3D scene graph, applies hierarchical chain-of-thought prompting and re-perception, and surpasses prior zero-shot methods by more than 10% SR on MP3D, HM3D, and RoboTHOR.
Problem
Existing zero-shot object-navigation methods prompt LLMs with nearby object categories, omitting spatial relationships and broader scene context needed for in-depth reasoning.
Method
SG-Nav builds an online hierarchical 3D scene graph of objects, groups, and rooms, then uses hierarchical chain-of-thought prompting and graph-based re-perception for navigation decisions.
Results
More than 10% SR improvement over previous state-of-the-art zero-shot methods is reported on MP3D, HM3D, and RoboTHOR, with explainable decisions.
Takeaways & Limitations
The scene-graph representation preserves rich environmental context and supports explainable frontier selection while helping the agent reject false-positive goal detections.
Takeaways & Limitations
SG-Nav relies on non-end-to-end, non-3D-aware online instance segmentation and currently handles only object-goal navigation.
Abstract
from arXiv · showhide
In this paper, we propose a new framework for zero-shot object navigation. Existing zero-shot object navigation methods prompt LLM with the text of spatially closed objects, which lacks enough scene context for in-depth reasoning. To better preserve the information of environment and fully exploit the reasoning ability of LLM, we propose to represent the observed scene with 3D scene graph. The scene graph encodes the relationships between objects, groups and rooms with a LLM-friendly structure, for which we design a hierarchical chain-of-thought prompt to help LLM reason the goal location according to scene context by traversing the nodes and edges. Moreover, benefit from the scene graph representation, we further design a re-perception mechanism to empower the object navigation framework with the ability to correct perception error. We conduct extensive experiments on MP3D, HM3D and RoboTHOR environments, where SG-Nav surpasses previous state-of-the-art zero-shot methods by more than 10% SR on all benchmarks, while the decision process is explainable. To the best of our knowledge, SG-Nav is the first zero-shot method that achieves even higher performance than supervised object navigation methods on the challenging MP3D benchmark.
1 Introduction
Object navigation traditionally relies on dataset-specific training, while zero-shot methods use LLMs but provide limited scene context and opaque frontier decisions. SG-Nav addresses these limitations with an online hierarchical 3D scene graph for richer, explainable reasoning.
- Conventional object navigation caches RGB-D perception in semantic maps and learns action policies, but requires costly simulation training and supports limited goal categories.
- Zero-shot navigation removes training and finetuning requirements while allowing open-vocabulary goal categories specified through text.
- Previous zero-shot methods prompt LLMs with nearby object categories, omitting spatial relationships and broader scene context.
- SG-Nav represents the observed environment with an online hierarchical 3D scene graph and prompts the LLM to exploit its structural information.
- SG-Nav further introduces graph-based re-perception to correct perception errors during zero-shot navigation.
2 Related Works
Prior work spans learned object-navigation policies, modular semantic mapping, and large pretrained models for embodied AI. SG-Nav contributes an online scene-graph-based pipeline that supplies richer context to LLM decision-making.
- Object-goal Navigation: Object-goal navigation research includes end-to-end reinforcement-learning methods and explicit modular approaches.
- SG-Nav: SG-Nav constructs an online 3D scene graph and prompts an LLM with hierarchical chain-of-thought and graph-based re-perception for decision-making.
- Object-goal Navigation: End-to-end methods may miss fine-grained context and suffer low sampling efficiency, motivating modular approaches that update BEV or 3D maps online.
- Large Pretrained Models for Robotics: Large pretrained language and vision-language models are applied to navigation, task planning, and manipulation in embodied AI.
3 Approach
SG-Nav builds an online hierarchical 3D scene graph and uses it to prompt an LLM for context-aware, explainable zero-shot navigation. The approach incrementally constructs and prunes graph edges, then combines graph-based frontier scoring with re-perception to address perception errors.
- Overview: SG-Nav represents the environment with an online hierarchical 3D scene graph and prompts an LLM with it for decision making.The pipeline uses hierarchical chain-of-thought prompting and graph-based re-perception.
- Hierarchical 3D Scene Graph: The graph contains object, group, and room nodes, with affiliation edges across levels and spatial or functional relationship edges within levels.Groups represent related objects, while same-level edges capture relationships such as objects being on top of or functionally related to one another.
- Incremental Updating and Pruning: SG-Nav incrementally registers new nodes from RGB-D observations and connects them to the previous graph to support real-time online construction.Object instances are matched across frames and merged when possible; groups are computed from related object nodes, and rooms are acquired similarly.
- Incremental Updating and Pruning: New object nodes are densely connected to existing object nodes, after which less informative long- and short-range edges are pruned using different strategies.Short-range relationships can be checked with RGB images and a vision-language model, while the edge-generation process uses efficient LLM prompting.
- Incremental Updating and Pruning: The efficient edge-generation method reduces computational complexity from O(m(m + n)) to O(m), enabling faster generation of new edge proposals.The comparison assumes 1 ≤ m ≤ 5, 1 ≤ n ≤ 100 and a small constant c in the complexity bound.
- Prompting LLM with 3D Scene Graph: For navigation decisions, SG-Nav divides the graph into object-centered subgraphs and uses hierarchical chain-of-thought prompting to estimate frontier probabilities.Each subgraph includes an object node, its parent nodes, and directly connected object nodes; frontier probabilities are averaged from subgraph predictions using frontier-to-object distances.
- Graph-based Re-perception: Graph-based re-perception addresses false-positive goal detections by having the agent approach detected goals, observe them from multiple perspectives, and accumulate credibility.This mechanism is motivated by the failure of conventional frameworks to account for perception errors.
4 Experiment
SG-Nav is evaluated across three object-navigation benchmarks using success, path-efficiency, and implementation metrics, alongside comparisons and ablations. Results show gains from scene graphs, re-perception, hierarchical structure, efficient construction, and chain-of-thought prompting.
- Benchmarks and Implementation Details: SG-Nav is evaluated on MP3D, HM3D, and RoboTHOR using SR, SPL, and SoftSPL, with higher values better for all metrics.The experiments also specify navigation, sensing, camera, and occupancy-map settings.
- Comparison with State-of-the-art: About 10% higher performance on all three benchmarks than previous zero-shot methods, while outperforming supervised methods on challenging MP3D.The SR improvement exceeds SPL because re-perception rejects false-positive goals but requires approaching them from multiple views.
- Comparison with State-of-the-art: SG-Nav outperforms other zero-shot methods by a large margin for all goal categories, especially relational categories such as fireplace and towel.The comparison uses per-category success rate on MP3D.
- Ablation Study: Removing room or group nodes degrades MP3D SR by 0.7% and 1.1%, respectively, with group nodes more important because they aggregate related objects and reduce graph complexity.The ablation compares alternative scene-graph architectures.
- Ablation Study: The efficient prompt-based construction method reduces the computational complexity of connecting new scene-graph edges relative to the naive O(m(m + n)) method.The naive method’s time consumption is described as linear in the number of edges.
- Ablation Study: Edges and hierarchical chain-of-thought prompting help the framework exploit structural scene information, while removing the scene graph causes random frontier exploration and significant degradation.Visualization further shows explainable frontier decisions and credibility accumulation for correcting perception errors.
5 Conclusion
SG-Nav combines an online hierarchical 3D scene graph, hierarchical chain-of-thought prompting, and re-perception for explainable zero-shot object navigation. Experiments on three datasets validate its performance and design effectiveness, while limitations remain in perception and task scope.
- SG-Nav constructs an online hierarchical 3D scene graph to preserve rich environmental context for goal-object inference.The framework incrementally updates and prunes graph edges, separating long-range and short-range relationships.
- Hierarchical chain-of-thought prompting scores scene-graph subgraphs and interpolates their scores to produce explainable frontier decisions.The decision process can be summarized through the LLM’s reasoning on each subgraph.
- A re-perception mechanism enables SG-Nav to give up false-positive goal detections and correct perception errors.
- Extensive experiments on three datasets validate SG-Nav’s performance and the effectiveness of its design.
- SG-Nav depends on non-end-to-end, non-3D-aware online instance segmentation and currently handles only object-goal navigation.The authors identify stronger 3D instance segmentation and extension to image-goal or vision-and-language navigation as future directions.
6 Appendix
The appendix documents implementation details, complexity analysis, prompting procedures, and visualizations for SG-Nav. It explains efficient edge generation, hierarchical chain-of-thought prompting, benchmark visualizations, and representative failures.
- Appendix contents: The appendix provides a dictionary for grouping related object categories and complete SG-Nav prompts.The relationship dictionary includes pairs such as Bed–Nightstand, Sofa–Table, and Computer–Monitor.
- Time complexity for edge updating: The efficient edge-generation method reduces relationship-generation complexity by (m + n) times, from O(m(m + n)) to O(m).The analysis assumes typical scene-graph ranges of 1 ≤ m ≤ 5 and 1 ≤ n ≤ 100, with coefficient c = 5.49.
- Hierarchical CoT: The prompts represent spatial relationships such as next to, above, opposite to, below, inside, behind, and in front of.
- Hierarchical CoT: Hierarchical chain-of-thought prompting predicts object distances, asks spatial-relation questions, answers them from subgraphs, and predicts subgraph-to-goal distances.The prompts request distances and reasons in JSON format and use scene-graph nodes and edges as input.
- Visualizations: Visualizations show constructed scene graphs, frontier scores with high scores in red and low scores in blue, LLM reasoning outputs, and three navigation failure cases.Failures include mistaking a shelf for a cabinet, failing to detect the goal, and predicting a chair location from nearby sofa and TV cues.