SG-Nav: Online 3D Scene Graph Prompting for LLM-based Zero-shot Object Navigation
SG-Nav uses online 3D scene graphs and hierarchical reasoning to boost zero-shot object navigation SR by over 10%.
Key Findings
Methodology
This approach constructs an online hierarchical 3D scene graph encoding objects, groups, and rooms, guiding large language models (LLMs) via chain-of-thought prompts. The scene graph captures environment relationships, enabling structured reasoning. A graph-based re-perception mechanism corrects perception errors by multi-view observation and credibility scoring. Extensive experiments on MP3D, HM3D, and RoboTHOR show over 10% SR improvement over SOTA, surpassing some supervised methods. The method emphasizes explainability and robustness, integrating environment structure with LLM reasoning for high performance.
Key Results
- On MP3D, SG-Nav achieves SR of 40.2%, exceeding previous zero-shot methods by over 10%, and even surpasses some supervised approaches. Similar gains are observed on HM3D and RoboTHOR, with SR improvements consistently above 10%. The scene graph and re-perception modules significantly enhance success rates, especially in complex scenes with dense object relationships.
- Category-wise analysis shows marked improvements in relation-heavy categories like fireplace and towel. Ablation studies confirm that hierarchical reasoning and relation edge filtering are crucial for accuracy. The incremental scene graph construction reduces computational complexity, enabling real-time operation.
- Time analysis indicates that the dense connection strategy reduces edge processing costs, ensuring efficiency. The approach maintains high performance without sacrificing speed, demonstrating scalability in large environments.
Significance
This work advances zero-shot navigation, achieving performance surpassing some supervised methods without training. It demonstrates the potential of combining large pre-trained models with structured environment representations, enhancing interpretability and robustness. The approach addresses key challenges in environment understanding, paving the way for more autonomous, explainable robots capable of operating in unknown, complex settings, thus broadening AI's practical deployment in real-world scenarios.
Technical Contribution
The paper introduces a novel online hierarchical scene graph that encodes environment relationships at multiple levels, combined with chain-of-thought prompting to guide LLM reasoning. The graph-based re-perception mechanism dynamically corrects perception errors, improving robustness. The incremental construction and pruning strategies optimize computational efficiency, enabling real-time decision-making. This integrated framework significantly improves environment understanding and decision explainability in zero-shot navigation tasks, setting new benchmarks.
Novelty
This is the first work to integrate a hierarchical 3D scene graph with LLM prompting for zero-shot object navigation, surpassing previous text-only or semantic map-based methods. The incremental graph construction with relation filtering and re-perception introduces a new paradigm for environment-aware reasoning, enabling robust, explainable navigation in unseen environments. The combination of these innovations results in a system that outperforms existing approaches, including some supervised models, on challenging benchmarks.
Limitations
- Dependence on high-quality perception and relation inference, which may degrade in visually cluttered or highly dynamic environments. The system's performance can be affected by perception noise and relation misclassification.
- Real-time scene graph construction remains computationally intensive, especially in large-scale scenes, limiting scalability. Further optimization is needed for deployment in real-world scenarios.
- Heavy reliance on large language models introduces biases and potential reasoning errors, especially in unfamiliar or ambiguous contexts. Improving generalization and reducing bias remains an open challenge.
Future Work
Future directions include integrating multimodal perception (e.g., audio, tactile), enhancing dynamic scene understanding, and optimizing graph update algorithms for larger environments. Combining reinforcement learning for adaptive decision-making and extending to multi-object, multi-goal scenarios will further broaden applicability. Improving model robustness and reducing computational costs are also key goals.
AI Executive Summary
Robotic navigation in unknown environments remains a challenging problem, especially when aiming for zero-shot generalization without task-specific training. Traditional methods rely heavily on supervised learning or handcrafted maps, which limit adaptability and scalability. Recent advances leverage large language models (LLMs) for reasoning, but their effectiveness is constrained by limited environmental context understanding.
This paper introduces SG-Nav, a novel framework that constructs an online hierarchical 3D scene graph representing objects, groups, and rooms, capturing environment structure in real time. By integrating this scene graph with chain-of-thought prompting, the system guides LLMs to perform structured reasoning about goal locations. The scene graph is dynamically updated with new observations, and a graph-based re-perception mechanism helps correct perception errors, ensuring robust decision-making.
Extensive experiments on MP3D, HM3D, and RoboTHOR demonstrate that SG-Nav achieves over 10% SR improvement compared to previous zero-shot methods, outperforming some supervised approaches. The hierarchical reasoning process, combined with relation filtering and incremental graph construction, enables the system to operate efficiently in complex environments. The approach's explainability allows for transparent decision tracing, making it suitable for human-robot interaction.
This work signifies a step forward in autonomous navigation, showcasing how structured environment representations combined with large-scale pre-trained models can overcome traditional limitations. It opens avenues for more adaptable, explainable, and scalable robotic systems capable of operating in diverse, unseen environments. Future work will focus on multimodal perception integration, scalability, and reinforcement learning-based adaptation, aiming to realize truly autonomous and intelligent robots in real-world scenarios.
Deep Analysis
Background
机器人目标导航是智能系统的核心任务之一，早期多依赖深度强化学习和模组化方法，如DD-PPO、语义映射等，但在泛化能力和环境理解深度方面存在局限。随着大规模预训练模型（如GPT、LLaMA）在自然语言处理中的突破，研究开始尝试将其引入导航任务，推动零样本和开集目标识别的发展。现有方法如ZSON、COWs等，虽取得一定成果，但缺乏对环境关系的深度建模，导致推理不够透明和鲁棒性不足。
Core Problem
核心问题在于如何在未训练的环境中，利用有限的感知信息，准确推断目标位置。传统方法多依赖静态语义地图或文本提示，缺少对环境关系的深度理解，路径规划可能偏离实际。大模型虽具备丰富知识，但如何引导其理解环境结构、进行推理，仍是难点。尤其在复杂、多房间、多目标场景中，感知误差和关系推断不准确，严重影响导航成功率。
Innovation
本研究的创新点包括：1）提出层次化3D场景图，实时在线构建环境关系，丰富环境结构信息；2）采用层次化链式推理prompt，引导LLM理解场景层次，提升推理准确性；3）设计图结构的再感知机制，动态校正感知误差，增强鲁棒性；4）采用增量连接和边筛选策略，降低计算复杂度，实现实时操作。这些创新结合大模型能力，突破了传统方法的局限。
Methodology
- �� 构建层次化场景图：定义房间、组、物体三层节点，实时更新，利用点云和实例分割检测新节点。
- �� 图关系：房间-物体、组-物体、物体-物体关系，通过LLM推断关系边，筛除无关边。
- �� 层次推理prompt：对每个子图进行距离预测、问答和总结，逐步引导模型理解环境。
- �� 路径决策：基于前沿点的概率评分，结合场景图推理，选择最优路径。
- �� 图结构再感知：多角度观察目标，累计可信度，避免误导。
- �� 实时更新：增量添加新节点，剪枝无关边，确保系统高效。
Experiments
采用MP3D、HM3D和RoboTHOR三大数据集，比较成功率（SR）、路径效率（SPL）等指标，验证在不同环境中的表现。最大导航步数设为10，感知距离范围1.5-10米，使用LLaMA和GPT-4作为推理引擎。通过消融实验验证场景图层次结构、关系边和再感知机制的重要性。结果显示，SG-Nav在所有指标上均优于对比方法，尤其在复杂环境中表现更为稳健。
Results
在MP3D上，SR达40.2%，超越前沿方法10%以上，且优于部分监督模型。引入场景图和再感知机制后，成功率提升明显，特别在关系密集类别中表现优异。消融实验确认，层次化推理和关系边筛选显著改善推理准确性，减少误导。时间成本分析显示，提出的边连接策略大幅降低了计算复杂度，确保实时性。
Applications
该方法适用于自主机器人、智能家居、仓储物流等场景，能实现无需训练的目标定位与路径规划。依赖环境感知和大模型推理，适合复杂、多变的环境中自主导航。未来可结合多模态感知、强化学习，扩展到多目标、多任务场景，推动工业和服务机器人智能化。
Limitations & Outlook
依赖高质量感知和关系推断，感知误差仍影响效果。在大规模环境中，实时构建场景图存在计算瓶颈。大模型偏差可能导致推理偏差，泛化能力在极端场景下仍需提升。未来需优化算法效率和鲁棒性，增强系统适应性。
Plain Language Accessible to non-experts
想象你在一个大房子里找一只猫。你不知道猫在哪，但你可以观察房间里的家具、摆设和其他物品。你会记住哪些房间有猫的线索，比如沙发旁边有猫的毛发，或者厨房里有猫喜欢的食物。你会根据这些线索，逐步排除不可能的房间，最后找到猫藏在哪里。这个过程就像给机器人讲故事，让它根据房间里的物品关系，逐步推理出目标位置。它会不断更新自己的线索，确保不被误导，最终成功找到猫。这种方法让机器人像人一样聪明，能在新环境中自己找到目标。
ELI14 Explained like you're 14
想象你在学校里找朋友，但你不知道他在哪个教室。你开始观察教室里的东西，比如桌子、椅子、黑板，然后记住哪些教室有这些东西。比如，你知道朋友喜欢坐在窗边的教室，或者喜欢在操场附近。你会用这些线索，逐步排除没有这些特征的教室，最后找到朋友所在的教室。这就像给机器人讲故事，让它用房间里的物品关系推理出目标位置。它会不断更新线索，确保不会误导自己，最终成功找到朋友。这样，机器人就变得像人一样聪明，能自己在新环境中找到目标。
Glossary
层次化场景图 (Hierarchical Scene Graph)
一种用多层级节点表示环境中物体、组和房间关系的结构，便于环境理解与推理。
本文中用于实时构建环境结构，指导LLM推理。
大语言模型 (Large Language Model)
具备丰富知识和推理能力的预训练模型，用于引导机器人进行环境推理和决策。
作为核心推理引擎，结合场景图实现零样本导航。
链式推理 (Chain-of-Thought Prompting)
引导模型逐步推导、分析问题的提示策略，增强推理透明度。
用于引导LLM理解场景层次结构，提升推理准确性。
关系边筛选 (Relation Edge Filtering)
通过图结构筛除无关关系，提升推理效率和准确性。
在关系推断中用于优化场景图结构。
零样本目标导航 (Zero-shot Object Navigation)
无需训练，直接用文本描述目标类别，通过模型推理实现目标定位。
本文的核心任务和方法基础。
Open Questions Unanswered questions from this research
- 1 如何在极端复杂环境中保持场景图的准确性和实时更新，仍需深入研究。当前模型在极端感知噪声和动态变化环境中的表现有限，未来需探索更鲁棒的图结构和关系推断算法。
Applications
Immediate Applications
自主机器人导航
可应用于家庭、仓储等场景，实现无需训练的目标定位，提升自主性和鲁棒性。
智能安防系统
结合场景图推理，提升监控设备的目标识别和追踪能力，增强安全保障。
Long-term Vision
智能环境理解
推动机器人在复杂动态环境中自主适应，实现更高层次的环境理解与交互。
人机协作增强
让机器人更好理解人类意图，提升协作效率，推动智能系统普及。
Abstract
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.