SG-Nav: Online 3D Scene Graph Prompting for LLM-based Zero-shot Object Navigation
Authors: Hang Yin
Xiuwei Xu
Zhenyu Wu
Jie Zhou
Jiwen Lu
Venue: NeurIPS 2024 poster (2024)
Keywords: navigation
scene graph
large language model
Primary area: robotics
TL;DR: We propose a scene graph representation to prompt LLM for zero-shot object navigation, which achieves state-of-the-art performance while being explainable.

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 \textbf{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.
Code of this project will be released in the final version.

SG-Nav: Online 3D Scene Graph Prompting for LLM-based Zero-shot Object Navigation
Hang Yin', Xiuwei Xul-f, Zhenyu Wu', Jie Zhou', Jiwen Lu 4
TTingguu University
Beijing University of Posts and Telecommunications {yinh23, xxw21 Amaiiss. tsinghua. eeigghuaaudu...... edu.
wuzhenyu@bupt.c wwwp::etpppppeuuuee.cm. cn, {jzhou, (eriwwn]@tssinnuue edu. cn
Abstract
In this paper, we propose 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 hierarchical Mhain-of-thoughe prompt help LLM reason the goal location according to scene context by traversing the nodes and edges. Moreover, benefit from the scene graph representation, further design a re- re-perception mechanism to empower the object navigation framework with the ability correct perception error. We conduct extensive experiments MP3D, HM3D and RoboTHOR environments, where SG-Nav surpasses previous state-of-the-art zero-shot methods by more than 10% SR all benchmarks, while the decision process is explainable. To the best of our knowledge, SG-Nay is the first zero-shot method that achieves even higher performance than supervised object navigation methods on the challenging MP3D benchmark. Project page.
Introduction
Object navigation, which requires an agent to navigate to an object specified by its category in unknown environment [3]. is a fundamental problem in wide range of robotic tasks. Thanks to the advancements in deep learning and reinforcement learning (RL), modular- based object navigation approaches (6 32 48 have achieved impressive performance in recent years, which caches the visual perception results of the RGB-D observation into semantic map and learns policy to predict actions according to this map. However, conventional methods rely time-consuming training in simulation environment, which only works well on specific datasets and can only handle limited categories of goal object.
order to solve above limitations and enhance the generalization ability object navigation, zero- shot object navigation has received increasing attention. In the zero-shot setting, the system does not require any training or finetuning before applied to real-world scenarios, and the goal category can be freely specified by text in apen-vocabulae manner. Since training data is unavailable, recent zero-shot object navigation methods [46] 522 leverage large language models (LLM) [I instead of RL agent perform decision-makinn processes, where the extensive knowledge in LLM helps to address various common-sense reasoning problems zero-shot, In these works, the LLM is required to select frontier for the agent to explore the unobserved area. As LLM cannot perceive the
Equal contribution. Project lead.
Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Q Where
TV
TAM
Roore Lewal
lovel
Ukinng Rooes Humnitune
ceiject lowel Liokng Safte
Subgraah ralated TV
A: Opposite to sofa.
In living room, TV and sofa are on hoth sides of table.
Our 5G Agent
DDD
Conventional Agent
TV is next to (sofa, chair, table).
Figure I: Different from previous zero-shot object navigation methods 46
2 that directly prompt LLM with text of nearby object categories, construct hierarchical 3D scene graph represent the observed environment and prompts LLM to fully exploit the structure information in the graph. Our SG-Nav preserves fine-grained scene context and makes reasonable and explainable decisions.
environment visually, they select the categories of objects near each frontier to prompt LLM and rate the possibility of each frontier. While these approaches achieve zero-shot object navigation, there are still some drawbacks in their design: (1) they prompt LLM with only the text of nearby object categories, which is less informative and lacks scene context such as spatial relationship: (2) they let LLM directly output the possibility for each frontier, which is abstract task and does not fully utilizes the reasoning ability of the LLM. As result, their reasoning process is not explainable and the performance is far from satisfactory.
In this paper, we propose new object navigation framework namely SG-Nav, which fully exploits the reasoning ability of L.M for zero-shot navigation planning with high accuracy and fast speed. As shown in Figure different from previous L.LM-based object navigation framework that prompts LLM with only text of object categories and directly outputs probability, SG-Nav represents the complicated 3D environment in an online updated hicrarchical 3D scene graph and utilizes it to hierarchically prompt LLM for reliable and explainable decision making. Benefit from the scene graph representation, we further design a graph- based re- re-perception mechanism to empower the object navigation framework with the ability to correct perception error. Specifically, we first construct an online 3D hierarchical scene graph along with the exploration of the agent. Since there many levels and nodes in the scene graph, it is challenging time. To solve this problem, we propose to densely connect the newly detected nodes to previous nodes in incremental manner. We design a complexity of this dense connecting process linear to the number of new nodes, which followed by pruning process discard less informative edges. With the 3D scene graph, we divide into several subgraphs and propose a hierarchical chain-of-thought to let LLM perceive the structural information in each subgraph for explainable probability prediction. Then we interpolate the probability of each subgraph to the frontiers for decision making, which can be further explained by summarizing the reasoning process for the most related subgraphs. Moreover, we also notice that previous object navigation framework fails when detecting out false positive goal object. So we propose a graph- based pe-rcepption mechanism to judge the credibility of the observed goal object by accumulating relevant probability of subgraphs. The agent will give up goal object with low credibility for robust navigation. We conduct extensive experiments on MP3D, HM3D and RoboTHOR environments. Our SG-Nav achieves state-of- oo-the-art zero-shot performance on all benchmarks, surpassing previous pop-performance zero-shot method by more than 10% in terms of SR. SG-Nav can also explain the reason for its decision at each step, making it more practical in human-agent interaction scenarios.
build the scene graph in real
form of prompt to control the computational
Related Works
Object-goal Navigation: Objec-goal navigation methods can be divided into two categories: end-to- end RL methods [38] 29
43
44
26 25 50) and explicit modular- based methods [6] 32 48
46

---

Ordbiity
focutoate
Agent Pose
Mapping
Deterministic Local Policy
Re- pee-perception
Hierarchical Scene Graph
Action
Observation
Occupancy Map
in living room, TV and sofa are on boch sides of tabble.
Object Goal
Subgraphs
H-CoT
Frontier Score
Explanation
Figure 2: Pipeline of SG-Nav. We construct a hierarchical 3D scene graph as well as an occupancy map online. At each step, we divide the scene graph into several subgraphs, each of which prompted to LLM with a hierarchical chain-of tiiin-of-iie of-thhuugt for structural understanding of the scene context. We interpolate the probability score of each subgraph to the frontiers and select the frontier with highest score for exploration. This decision is also explainable by summarizing the reasoning process of the LLM. With the scene graph representation, we further design a re-perception mechanism, which helps the agent give up false positive goal object by continuous credibility judgement.
52]. DD-PPO 38
implicitly encodes the visual observation into latent code and predicts low-level
actions. Follow-up works increase the performance by better visual representation 29 4 auxiliary
tasks [4 and data augmentation [26]. However, since this kind of methods implicitly encode 3D scene and directly predict actions, which may fail capture fine- fine-grained context. The end-to-end RL also suffers from low sampling efficiency. To solve these problems, modular-based methods and update online. The agent In persuit of open-vocabulary object navigation, COWs 11 and 7SON (25) align the goal to CLIP embedding (30). L.MVV [46] and ESC [52) further utilize large language models for zero-shot decision making. Our SG-Nav is also LLM-based zero-shot framework. But differently, we propose to construct 3D scene graph instead of semantic map to prompt LLM with hierarchical chain-of-thought and graph-based re-perception, which better preserves the scene context and makes the decision more robust.
map the visual perception results to BEV or 3D map 49
learns where to navigate with this semantic map 6 32 48
Large Pretrained Models for Robotics: Large pretrained language models
36 and vision-
language models 30 20: 23 20;
2T have received increasing attention recent years, which
widely applied in embodied Al tasks including navigation [17
1
25
46
52
51, task observed that large
35
13
planning 2
39 K 40
manipulation 222
14
15
47
vision-language models becomes good hand in dealing with embodied AI problems due to its end-to-end processing of images and language. NLMap 7 leverages CLIP embedding [30] to build open-vocabulary map for task planning. Voxposer [15) automatically generates code to interacts with VLMs [28] [8]. which produces a sequence of 3D affordance maps and constraint maps to guide the optimization of path planning. However, is still hard to process streaming RGB-D video for vision- Lision-language models. To better make use the observed 3D scenes, recent methods [52 51 of navigation describe the scene in pure text and utilize it to prompt LLM. Our SG-Nav, instead, represents the 3D scene using scene graph, which preserves much more context information. The proposed hierarchical thain-of-thoughe and graph-based re-perception methods can also better exploit the potential of L.L for object navigation.
Approach
In this section, we first provide definition zero-shot object navigation and introduce the overall pipeline of SG-Nav. Then we describe how to construct an open- vicenvocabulary and hierarchical 3D scene graph online. Finally we show how to prompt the L.LM with 3D scene graph achieve context-aware and robust object navigation.

---

3.1 Zero-shot Object Navigation
Problem Definition. A mobile agent is tasked with navigating to an object specified by its category in an unknown environment. The agent receives streaming RGB-D video as input along with its exploration and decides where to go until finds the goal object. Formally, at each time instant I, the input to the agent is a posed RGB-D image and and the agent should execute an action ~ A, where A consists of move move_ forward, turn_ sarn_left, turn_ _arnhtthhttt and stop. The task successful if the agent stops within de meters of the goal object in less than 7 steps. Otherwise it fails.
Different from conventional object navigation which requires training in simulation environment with fixed vocabulary of categories c, we study zero-shot object navigation: the goal category can be freely specified with text in an open- vocabulary manner, and the navigation system does not require any training or finetuning, which is of great generalization ability.
Since performing open-vocabulary object navigation without training is very challenging, we resort to large language model (LLM) [6 [ to solve this problem. LLM demonstrates extensive knowledge and surprising generalization ability, which is a best choice to handle this zero-shot task. To make LLM aware of the visual observation of the environment, we propose to construct an online 3D scene graph, which contains rich context information about the environment and is suitable for interacting with LLM. At each step, we prompt the LLM with our 3D scene graph with hierarchical chain-of-thougle and graph-based re-perception for decision making. The pipeline is shown in Figure 2
Overview.
3.2 Online 3D Scene Graph Construction
In this subsection, we first provide formal definition of our 3D scene graph. Then we detail how to construct the scene graph in real time and online.
Hierarchical 3D Scene Graph. 3D scene graph describe the 3D scene with nodes and edges between these nodes. We define three kinds of nodes: object, group and room, to rep- resent the scenes in different graininess. Here group indicates a set of related objects, such as dining table and its surrounding chairs, TV and TV cabinet. Edge can exist between any pair of nodes. two nodes are not the same level (e.g, chair and living room), the edge be- tween them represents affiliation (i.e. this chair belongs to this living room). If two nodes are in the same level, the edge represents the re- lationship between them, which can be spatial relationship such as on the top of between close objects, or functional relationship between far away objects like a TV and its opposite sofa.
Dense Connect
Prune Edge
New Node
New Node
New Edge
Long Edge
Short Edge
Pruned Edge
Long Edge Pruning
Short Edge Pruning
Not Obstructed
Parallel Wall
VLM
Same Room
Incremental Updating and Pruning. Since there are many objects in the environment and the relationship between them are complicated, building the scene graph for the whole scene is time-consune cime-consuming. To enable real-time online construction of the 3D scene graph, we propose to incrementally update it across frames. That is, the RGB-D observation, and connect these nodes with the previous scene graph G.-1 to acquire G,
The incremental generation of edges. We densely connect newly registered nodes (pur- ple) to all other nodes by efficiently prompting the LLM. We divide the edges into long edges and short edges and prune less informative ones with different strategies.
Figure 3:
at each time t, we register new nodes Ar, from
We adopt different strategy to acquire different level of nodes. For object nodes, we leverage online open-vocabulary 3D instance segmentation method [12 to acquire the 3D instance. Formally, at each time I, the method detects and segments objects from the RGB-D observation and synchronously reconstruct the 3D point clouds for the environment. These newly detected objects will be matched with object nodes detected from the previous match with any previous one will be registered as new object node. Each object node has semantic
frames and merged into them. Objects that do not

---

category and its confidence score. Then group nodes are computed based on all object nodes up to time t. If two object nodes are connected by an edge and their categories are related, we register a group for them. This process will iterate until no new node can be assign to this group. We pre-define a dictionary to tell which pair of categories are related by L.M,, which is detailed in Section 6.2 For room nodes, we follow the same paradigm for acquiring object nodes, where room is regarded as instance and thus we can prompt the open-vocabulary 3D instance segmentation model with the room type.
We also design different strategies to build edges between the nodes of different levels. We first connect high-level nodes with their affiliated low-level nodes. For room-object node pair, we think the object belongs to the room if the instance mask of this object on the point clouds is contained in the instance mask of this room. For room- goooup node pair, we connect them if all objects in this group belongs to the room. We do not additionally connect group and object nodes since the former is registered based on the latter.
Then we connect related object nodes to build intra-level edges, shown in Figure 3 Note there is no intra-level edges between group and room nodes, For newly registered object nodes at time remove less
we first densely connect them with all object nodes, and then perform pruning informative edges. We combine y newly registered nodes and previous nodes to form m(m + n) edges. For each edge, we can prompt LLM with the categories of connected nodes and ask LLM to infer their relationship. However, traversing all m(m + n.) edges and feed prompts to LLM requires Omm(m + ri)) computational complexity. To speed up the dense comnecting process for real-time processing, we propose a new format of prompt: Predict the most likely relationships between these pairs of objects: (( b) E Sn, E S, U. Sp where S, and S, are the set of m newly registered nodes and n previous nodes. This enables LLM to generate relationships between all pairs of nodes in one-shot with much less computational cost, for which we provide theoretical derivation below.
According to 377, complexity of processing L tokens for LLM is O(""), where 1 < r S 2. Suppose Lero and Lres represent the number of tokens of the prompt and LLM's response respectively. Then the computational complexity of processing m(m + n) pairs of nodes for our method and the naive O(m(m + n)) method are Tour = O ((Lpro + m(m + n)) Lyes + m(mm + +n) 2))) and Thaive = m(m + n2) O ([Lpro + Lrre)")) respectieel) Since Lyro > 2 and Lyro > Lyee, we can approximately treat Ly..
and Lree a (a S 0.01). Assume that S m S 5, S n S 100.
Lero
We then compute the ratio between them:
Tour
(Lero + m(m + n)- Lyes + m(m + n) 2)"
(1)
T Tnaive
m(m+ + n)- (Lyro + Lrea)"
m + n
where e is a small constant. Consequently, our method reduces the complexity from O(m(m + n)) to Om). In this way, the LLM can generate new edge proposals in fast speed.
We further prune the dense connected edges to make the 3D scene graph more precise. We divide newly generated relationships into two categories: long-range and short-range. The basis for this division is whether there is a RGB-D image containing the two connected objects. true, this edge is short-range, for which we can feed the RGB image to vision language model (VLM) like LLaVA (23) and ask whether this relationship exists. Nonexistent ones will be pruned. Otherwise the edge is a long- rongerange one. We design two standards to validate it: (1) the line connecting two objects is unobstructed and parallel to the wall of room; (2) these two object nodes belong to the same room node. Only edges meet with both standards can be preserved.
3.3 Prompting LLM with 3D Scene Graph
In this subsection, we describe how to prompt LLM with the 3D scene graph at each step for decision making. Since directly predicting is hard for LLM, we adopt Frontier-based Exploration (FBE) strategy to divide the decision into two part: (1) synchronous with the 3D scene graph, we build an online occupancy map to indicate explored, unexplored and occupied area in BEV, based on which we compute the frontiers of explored area. In order to further explore the environment, the agent must go through one of the frontier. So in high level, the LLM is only required to select one of the frontier which has the highest probability to find o; (2) once the frontier to be explore is chosen, we simply apply local policy like Fast Marching Method [34 for path planning and output
We provide detailed proof process and illustrated examples in Section 6.3
5

---

Hierarchical Chain-of-thought Prompting, Different from previous methods 46 52 that prompt LLM with only categories of objects near each frontier, we compute the probability pfre of each frontier by prompting L.M with our 3D scene graph. At time I, we divide the scene graph G. into subgraphs, each of which determined by an object node with all its parent nodes and other directly connected object nodes. For each subgraph, we predict paub, the possibility of goal appearing near this subgraph. Then the probability p. of the i-th frontier can be averaged by:
pauh pl100 1 (i (1.2,...,
D. Dij
where M is the total number of subgraphs and Diy is the distance between the center of the i-th frontier and the central object node of the j-th subgraph.
In order to make the prediction of pauh accurate and explainable, we propose a hierarchical chain- of-thought method to prompt LLM, which fully exploits the structure information contained the subgraphs. Specifically, for each subgraph, L.M is first prompted with Predict the most likely distance between [object] and [goal], where [object] means the category of the central object node. Then prompt LLM to ask question related to the navigation goal, with the prompt: Ask questions about the [object] and [goal] for predicting their distance. After obtaining the questions about goal, prompt LLM to answer those questions according to the information of subgraph, with the prompt: Given [nodes] and [edges] of subgraph, answer above [questions]. Therefore, from those answers get all the necessary information required for inferring the position of goal. Finally, prompt LLM to summarize the conversation and predict P, with the prompt Based on the above conversation, determine the most likely distance between this subgraph and [goal]. And psuh can be simply computed by taking the inverse of the outputted distance. The LLM also summarizes the analysis process of the nearest 3 subgraphs the selected frontier to explain the reason for decision.
Graph-based Re-perception. Conventional object navigation framework does not take perception error into consideration. Once the agent detects out false positive objects of the goal category, it will not explore or perceive the environment any more and directly navigate to this object.
To solve this problem, we enhance the current object navigation framework with graph graph-based based re- perception mechanism. When the agent detects out goal object, it will approach to this object, observe it from multiple perspectives and accumulate a credibility score S. For the k-th RGB-D observation since this moment, we compute the credibility of it by:
S Ck Σ
Dj
where Cp is the confidence score of this goal object, Dj is the distance between the central object node of the j-th subgraph and this object. The success condition for our re-perception mechanism is:
N-1 Nstop Nmaz: where N Natop = N, S.L. S
N
S
1=1
where Nmaz is pre-defined maximum number of steps. If succeed, the agent will navigate to this goal object without any further exploration or perception. Otherwise, it will give up this object and continue the exploration.
4 Experiment
In this section, we first describe our datasets and implementation details. Then we compare our SG-Nav with state-of-the-an object navigation methods in different settings. We further conduct several ablation studies to validate the effectiveness of our design. Finally we demonstrate some qualitative results of SG-Nav.
4.1 Benchmarks and Implementation Details
We evaluate our method on three datasets: Matterport3D (MP3D) 5. HM3D 31 and RoboTHOR (9. MP3D is large-scale 3D scene dataset, which is used in Habitat ObjectNav challenges. We test our

---

Table 1: Object-goal navigation results on MP3D, HM3D and RoboTHOR. We compare the SR and SPL of state-of-the methods in different settings.
MP3D
HM33
RoboTHOR
Method
Unsupervised
Zero-shot
SR
SPL
SR
SPL
SR
SPL
SemEXP 6
No
No
36.0
14.4
PONI 32
No
No
31.8
12.1
Proc THOR
No
No
54.4
31.8
65.2
28.8
ZSON
Yes
No
15.3
4.8
23.5
12.6
ProcTHOR-
10
Yes
No
13.2
7.7
55.0
23.7
CoW 11
Yes
Yes
7.4
3.7
26.7
16.9
ESC 52
Yes
Yes
28.7
14.2
39.2
22.3
38.1
22.2
L3MVN 46
Yes
Yes
34.9
14.5
48.7
23.0
41.2
22.5
MNay
19
Yes
Yes
37.2
15.7
52.5
24.1
44.1
23.3
VI.FM 45
Yes
Yes
36.2
15.9
52.4
30.3
42.3
23.0
-LLMAAALLLA
Yes
Yes
40.1
16.0
53.9
24.8
47.3
23.7
SG-Nav-GPT
Yes
Yes
40.2
16.0
54.0
24.9
47.5
24.0
SG-Nav on the validation set, which contains 11 indoor scenes, 21 object goal categories and 2195
object-goal navigation episodes. HM3D is used in Habitat 2022 ObjectNav challenge, containing 2000 validation episodes on 20 validation environments with 6 goal object categories. RoboTHOR is used RoboTHOR 2020, 2021 ObjectNav challenge, containing 1800 validation episodes on 15
validation environments with 12 goal object categories.
Durs
Ours Naive
60-
50
Cow
20
80
Tineeto
60
20
10
Jink
that
couna
bed
dower
20
40
50
60
70
80
100
Number of Edgts
Figure 4: Per category SR MP3D.
Figure 5: Time cost of connecting edges.
We report three metrics including success rate (SR), success rate weighted by path length (SPL) and SoftSPL. SR is the core metric of object-goal navigation task, representing the success rate of successful navigation episode. SPL measures the ability of agent to find the optimal path. If success, SPL optimal path length
Evaluation Metrics:
otherwise SPL O. SoftSPL 8 measures the navigation progress and navigation efficiency of the agent. Higher is better for all the three metrics.
path length
We set 500 as the maximal navigation steps. The farthest and closest perceived distances of the agent are 10m and 1.5m. Each step of the agent takes 0.25m, and each rotation takes 30". The camera agent 0.90m above the ground, and perspective is horizontal. The camera outputs 640 480 RGB-D images. We maintain a 800 x 800 2D occupancy map with the resolution of 0.05m, which can represent a 40m 40m large-scale scene. In equation 4 the cypre-parameter. Nmaz is 10 and Sthres is 0.8. For the verification of short edge, adopt LLa 1.6 (Mistral-7B) (24) as the VLM for discrimination. We choose LLaMA-7B (6) and GPT-4-0613 the LLM for our SG-Nav, which discriminated by SG-Nav-LLaMA and SG-Nav-GPT.
Implementation Details:
Comparison with State-of-the-art
We compare SG-Nav and with state-of-the-art object navigation methods of different setting, including supervised, unsupervised and zero-shot methods in Table SG-Nav surpasses previous zero-shot

---

Table 2: Effect of the 3D scene graph (SG) and re-perception mechanism (RP).
MP3D
HM3D
RoboTHOR
Method
SR
SPL
SoftSPL
SR
SPL
SoftSPL
SR
SPL
SG-Nav w/o SG&RP
25.7
12.9
22.6
38.6
18.9
27.7
34.9
21.1
SG-Nav w/o RP
36.5
15.0
23.9
49.6
23.6
33.0
41.9
22.6
SG-Nav
40.1
16.0
24.9
53.9
24.8
33.8
47.3
23.7
methods by about 10% on all three benchmarks. We also notice that on the challenging MP3D) dataset, SG-Nav even outperforms supervised methods including SemEXP and PONI. Note that the improvement SR is larger than SPL, this is because our graph-based re-perception mechanism can help the agent give up false positive goal object, which significantly increase the success rate. However, during the process the re-perception, the agent still needs to approach to the goal to observe it from multi views. So this strategy cannot reduce the length of path.
We also compare pet-coty success rate of different zero-shot methods in Figure For all goal categories, SG-Nav outperforms other methods by large margin, especially categories that have more relationships with other objects such as fireplace and towel.
Table 3: Effect of the room level node and group Table 4: Effects of the edges in scene graph & on MP3D dataset.
level node on MP3D dataset.
Room
Group
SR
SPL
SoftSPL.
Method
SR
SPI.
x
38.3
15.3
23.9
G with only nodes
38.0
15.2
x
39.0
15.8
24.4
Remove short edges from G
39.0
15.5
X
V
39.4
15.8
24.6
Remove long edges from
39.5
15.7
V
v
40.1
16.0
24.9
Complete G
40.1
16.0
4.3 Ablation Study
Scene Graph and Re-perception. In Table 2 we compare the design choices of scene graph (SG) and
Table Effects of the CoT prompting on MP3D dataset.
re-perception (RP). Without RP, SG-Nav will move to the goal once the detector finds goal, even thought the goal a false positive. Due to the complexity of the scene, is common for detector make mistakes, which leads to irreversible navigation. If we further remove the whole SG, our framework degenerates to random exploration model. The agent randomly selects frontier, resulting in a significant performance degradation on all datasets.
Method
SR
SPL
Text prompting
36.5
14.9
Text prompting seperately
37.0
15.0
w/o Inter-level Edges G
38.2
15.5
Raw
40.2
16.0
Room Node and Group Node. As shown in Table 3 we compare the performance between different architectures of scene graph by ablating the design of group and room nodes. We remove the room or group node with the edges connected to it and obtain different scene graph architecture. The removal of room node and group node results in 0.7% and 1. % SR degradation MP3D dataset respectively. We observe the group node is more important than room node, which is because the group nodes aggregate objects into whole and thus reduce the redundant information and the complexity of scene graph.
show the speed of generating densely connected new edges for our proposed efficient prompt- based method and the naive O(m + n)) method. The naive method requires time consumption that is linear to the number of edges, while efficient prompt significantly reduces the computational complexity.
Efficiency of Scene Graph Construction. In Figure 5
Effects of edges. In Table 4 we study the importance of different kinds of edges. The results validate that edges play an important role our framework, which helps the hierarchical chain-of-thought better exploit the structural information contained in the environment.

---

Bedroom
Agent
Path
Goall
Step
Step 16
Step 64
Step 80
Step 104
bedroom, there
cabinet
Redramm
Dedromm
Guorsom
Hicuuee
Overall Occupancy
Subgraphh-based Inference
Chair
Bed
Chair
Cabinet
Mistake Sofa
Agent
for Chair
Re-perception
Step Step 110
Step Step 115
Step 101
Step 190
Overall Occupancy Map
Chair
Accumulate credibility
Arrive at Chair
Figure 6: Visualization of the navigation process of SG-Nav.
Effects COT. T we demonstrate the importance of CoT prompting. "Text prompting" refers to directly converting the 3D scene graph into text and prompting the I.LM. "TTet prompt separately" means converting the nodes and edges into text individually. Additionally, we removed the edges between layers to further validate the necessity of hierarchical graph structure. The experimental results show that our CoT prompting can effectively exploit the structure information contained in the 3D scene graph.
4.4 Qualitative Analysis
We visualize the navigation process of SG-Nav in Figure The upper example shows that SG-Nav is able to explain the reason for its decision based on the nearest 3 subgraphs to the selected frontier. The lower example demonstrates that SG-Nav can accumulate credibility of the detected goal object and utilize it judge the authenticity of this goal, which effectively corrects perception
5
Conclusion
In this paper, we have proposed SG-Nav, a zero-shot object-goal navigation framework that prompts LLM with scene graph inference the position of goal object. We first construct hierarchical 3D scene graph online to preserve rich context information of the environment. To speed up the building of scene graph, we propose an incremental updating and pruning strategy, which first densely connects newly registered nodes to all nodes by efficiently prompting the LLM. Then we divide the edges long-range and short-range to prune them with different strategies. At each step, divide the scene graph into subgraphs and prompt LLM with hierarchical chain-of-ther ofothoughtthtttthh to

---

output the probability score of each subgraph. Then the score for each frontier can be acquired by simple interpolation. which is also explainable as we can summarize the decision process of LLM on each subgraph. With the graph representation, we further design re-perception mechanism to empower SG-Nav with the ability to give up false positive goal objects and thus correct perception error. Extensive experiments on three datasets validate the great performance of SG-Nav and the effectiveness of our design.
Potential Limitations. Despite of the great performance, SG-Nav still has several limitations: (I) SG-Nav relies on online 3D instance segmentation method for scene graph construction. Currently we adopt 2D Dision-langual model and vision foundation model to segment each frame and merge the masks across different frames, which is not end-to-end and 3D-aware. A stronger online 3D instance segmentation model will further boost the performance of SG-Nav. (2) SG-Nav can only handle object-ge goal navigation yet. However, due to the strong zero-shot generalization ability of ILM and the rich context contained in 3D scene graph, we believe SG-Nav can be further extended to more tasks such as image-gon moage-goal navigation and vision-and-langee lanlauugee navigation.
Acknowledgments
This work was supported in part by the National Natural Science Foundation of China under Grant 62125603, Grant 62336004, and Grant 62321005, and in part by the Beijing Natural Science Foundation under Grant L247009.
References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Igge Akkaya, Florencia Lconi Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Gpt-4 technical report. arXiv preprint arXiv:2303.0877 2023.
[2] Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan. Karol Hausman, et as can, not as say: Grounding language in robotic affordances. arXiv preprint arXiv:2204.0166 2022.
[3] Dhruv Batra, Aaron Gokaslan, Aniruddha Kembhavi, Oleksandr Maksymets, Roozbeh Mottaghi, Manolis Savva, Alexander Toshev, and Frik Wijmans. Objectnav revisited: On evaluation of embodied agents navigating to objects. arXiv preprint UrXiv:2006.131777 2020.
[4] Valts Blukis, Chris Paxton, Dieter Fox, Animesh Garg, and Yoav Artzi A persistent spatial semantic representation for high-level natural language instruction execution. In CoRL, pages 717. PMLR, 2022.
[5] Angel Chang, Angela Dai, Thomas Funkhouser. Maciej Halber, Matthias Niessner, Manolis Savva, Shuran Song, Andy Zeng, and Yinda Zhang. Matterport3d: Learning from rgb-d data in indoor environments. 3DV, 2017.
[6] Devendra Singh Chaplot, Dhiraj Prakashchand Gandhi, Abhinav Gupta, and Russ R Salakhutdinov. Object goal navigation using goal-oriented semantic exploration. NeurlPS, 33:4247-4258, 2020.
[7] Boyuan Chen, Fei Xia, Brian lchter, Kanishka Rao, Keerthana Gopalakrishnan, Michael Ryoo, Austin Stone, and Daniel Kappler. Open-voce vocabuubyy queryable scene representations for real world planning. In ICRA, pages 11509- 11522. IEEE, 2023.
[8] Samyak Datta, Oleksandr Maksymets, Judy Hoffman, Stefan Lee, Dhruv Batra, and Devi Parikh, Integrat- ing egacentric localization for more realistic point-goal navigation agents. CoRL, 2020.
[9] Mau Deitke, Winson Han. Alvaro Herrasti, Aniruddha Kembhavi, Eric Kolve, Roozbeh Mottaghi. Jordi Salvador, Dustin Schwenk, Eli VanderBilt, Matthew Wallingford, Luca Weihs, Mark Yatskar, and Ali Farhadi. Robothor: An open simulation-to-rca embodied ai platform. In CVPR, June 2020.
[10] Matt Deitke, Eli VanderBilt, Alvaro Herrasti, Luca Weihs, Jordi Salvador, Kiana Ehsani, Winson Han, Fric Kolve, Ali Farhadi, Aniruddha Kembhavi, and Roozheh Mottaghi. Procthor: Large-scale embodied ai using procedural generation, 2022.
[11] Samir Yitzhak Gadre, Mitchell Wortsman, Gabriel Ilharco, Ludwig Schmidt, and Shuran Song. Cows pasture: Baselines and benchmarks for language-drin driven zero-shot object navigation. In CVPR, pages 23171-203 1-11181, 2023.
10

---

[12] Qiao Gu, Alihusein Kuwajerwala. Sacha Morin. Krishna Murthy Jatavallabhula, Bipasha Sen, Aditya Agarwal, Corban Rivera, William Paul. Kirsty Ellis, Rama Chellappa, al. Conceptgraphs: Open- vocabulary 3d scene graphs for perception and planning. arXiv preprint arXiv:2309. 160..1660, 2023.
[13] Weituo Hao, Chunyuan Li, Xiujun Li, Lawrence Carin, and Jianfeng Gao. Towards learning generic agent for vision-and- -ann-uagg navigation via pre-training. In CVPR, pages 13137-13146, 2020.
[14] Siyuan Huang, Zhengkai Jiang. Hao Dong. Qiao, Peng Gao, and Hongsheng Li. Instruct2act: Mapping multi-modality instructions to robotic actions with large language model. arXiv preprint arXiv:2305.11176 2023.
[15] Wenlong Huang, Chen Wang, Ruohan Zhang. Yunzhu Li, Jiajun Wu, and Fei-Fee. Voxposer: Composable 3d value maps for robotic manipulation with language models, arXiv preprint 230.:2307.0097. 2023.
[16] Wenlong Huang. Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng. Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, al. Inner monologue: Embodied reasoning through planning with language models. arXiv preprint arXiv:2207,0566 2022.
[17] Apoorv Khandelwal, Luca Weihs, Roozbeh Mottaghi, and Aniruddha Kembhavi. Simple but effective: Clip embeddings for embodied ai. In CVPR, pages 14829-14838 2022.
[18] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Yen Lo, et al. Segment anything. In ICCV, pages 4015-4026, 2023.
[19] Yuxuan Kuang, Hai Lin, and Meng Jiang. Openfmnav: Towards open-set zero-shot object navigation via vision-language foundation models. arXiv preprint urXiv:2402.06670 2024.
[20] Junnan Li. Dongxu Li, Caiming Xiong, and Steven Hoi. Blip: Bootstrapping language image we-ttrinnig for unified vision-language understanding and generation. In ICMI., pages 2888-12900. PMLR, 2022.
[21] Liunian Harold Li. Pengchuan Zhang. Haotian Zhang, Jianwei Yang. Chunyuan Li, Yiwu Zhong, Lijuan Wang. Yuan, Lei Zhang. Jenq-Neng Hwang, et al. Grounded language-image pre-training, CVPR. pages 10965-10975, 2022.
[22] Jacky Liang. Wenlong Huang, Fei Xia, Peng Xu, Karol Hausman, Brian lchter, Pete Florence, and Andy Zeng. Code as policies: Language model programs for embodied control. In ICRA, pages 9493-9500. TEFF, 2023.
[23] Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. Visual instruction tuning. NeurlPS, 36, 2023.
[24] Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. Visual instruction tuning, 2023.
[25] Arjun Majumdar, Gunjan Aggarwal, Bhavika Devnani, Judy Hoffman, and Dhruv Batra. Zson: Zero-shot object-goal navigation using multimodal goal embeddings. Neur/PS, 35:32340-32533 2022.
[26] Oleksandr Maksymets, Vincent Cartillier, Aaron Gokaslan, Frik Wijmans, Wojeiech Galuba, Stefan Lee, and Dhruv Batra. Thda: Treasure hunt data augmentation for semantic navigation. In ICCV, pages 15373-15383, 2021.
[27] So Ycon Min, Devendra Singh Chaplot, Pradeep Ravikumar, Yonatan Bisk, and Ruslan Salakhutdinov, Film: Following instructions in language with modular methods. arXiv preprint aXiiv2210007344 2021.
[28] M Minderer, A Gritsenko, Stone, Neumann, D) Weissenborn, A Dosovitskiy, A Mahendran, A Amab, M Dehghani, Z Shen, et al. Simple open-vocabulary object detection with vision transformers. arxiv 2022. arXiv preprint arXiv:2205.000 062300 2, 2022.
[29] Arsalan Mousavian, Alexander Toshev, Marek Fišer, Jana Košecká, Ayzaan Wahid, and James Davidson. Visual representations for semantic target driven navigation. In ICRA, pages 8846 8852. IEEE, 2019.
[30] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, al. Learning transferable visual models from natural language supervision. In ICML, pages 148-8773. PMLR, 2021.
[31] Santhosh K. Ramakrishnan, Aaron Gokaslan, Erik Wijmans, Oleksandr Maksymets, Alex Clegg, John Turner, Eric Undersander, Wojeiech Galuba, Andrew Westbury, Angel X. Chang, Manolis Savva, Yili Zhao, and Dhruv Batra. Habitat matierpott 3d dataset (hm3d): 1000 large-scale 3d environments for embodied ai, 2021.
11

---

[32] Santhosh Kumar Ramakrishnan, Devendra Singh Chaplot, Ziad Al-Halah, Jitendra Malik, and Kristen Grauman. Poni: Potential functions for objectgoal navigation with interaction-free learning. In CVPR, pages 18890-18900, 2022.
[33] Krishan Rana, Jesse Haviland, Sourav Garg, Jad Abou- -hakka, Ian Reid, and Niko Suenderhauf. Sayplan: Grounding large language models using 3d scene graphs for scalable task planning. In CoRL, 2023.
[34] James A Sethian. Fast marching methods. SIAM review, 41(2):199223 1999.
[35] Dhruv Shah, Blažej Osiński, Sergey Levine, et al. Lm-nav: Robotic navigation with large pre-trained models of language, vision, and action. In CoRL, pages 492-504. PMLR, 2023.
[36] Hugo Touvron, Thibaut I Lavril, Gautier Izacard, Xavier Martinet, Maric- Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave. and Guillaume Lample. Llama: Open and efficient foundation language models. arXiv preprint Stti::2302.13771 2023.
[37] Sinong Wang. Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006. 04768, 2020.
[38] Erik Wijmans, Abhishek Kadian, Ari Morcos. Stefan Lee, Irfan Essa, Devi Parikh, Manolis Savva, and Dhruv Batra. Dd-ppo: Learning near-perfect pointgoal navigators from 2.5 billion frames. arXiv preprint 19Xiv:9111.0033 2019.
[39] Zhenyu Wu, Ziwei Wang, Xiuwei Xu, Jiwen Lu, and Haibin Yan. Embodied task planning with large language models. arXiv preprint arXiv:2307.01888 2023.
[40] Zhenyu Wu, Ziwei Wang, Xiuwei Xu, Jiwen Lu, and Haibin Yan. Embodied instruction following in unknown environments. arXiv preprini arXiv:2406. 1184401.1884 11888 2024.
[41] Xiuwei Xu, Huangxing Chen, Linqing Zhao, Ziwei Wang, Jie Zhou, and Jiwen Lu. Embodiedsam: Online segment any 3d thing real time. arXiv preprint arXiv:2408. 1111, 2024.
[42] Xiuwei Xu, Chong Xia, Ziwei Wang, Linqing Zhao, Yueqi Duan, Jie Zhou, and Jiwen Lu. Memory-based adapters for online 3d scene perception. In CVPR, pages 21604-21666 2024.
[43] Wei Yang, Xiaolong Wang. Ali Farhadi, Abhinav Gupta, and Roozbeh Mottaghi. Visual semantic navigation using scene priors. arXiv preprint 1810:0810.0054. 2018
[44] Joel Ye, Dhruv Batra, Abhishek Das, and Erik Wijmans. Auxiliary tasks and exploration enable objectgoal navigation. In ICCV, pages 16117-16126, 2021.
[45] Naoki Yokoyama, Sehoon Ha, Dhruv Batra, Jiuguang Wang, and Bernadette Bucher. Vifm: Vision- language frontier maps for zero-shot semantic navigation. In ICRA, 2024.
[46] Bangguo Yu. Hamidreza Kasaei, and Ming Cao. L3mvn: Leveraging large language models for visual target navigation. In IROS, pages 3560- JEEE, 2023.
[47] Wenhao Yu, Nimrod Gileadi, Chuyuan Fu, Sean Kirmani, Kuang- Lee, Montse Gonzalez Arenas, Hao-Tien Lewis Chiang. Tom Erez, Leonard Hasenclever, Jan Humplik, et al. Language to rewards for robotic skill synthesis. arXiv preprint
2023.
[48] Jiazhao Zhang, Liu Dai, Fanpeng Meng, Qingnan Fan, Xuelin Chen, Kai Xu, and He Wang. 3d-aware object goal navigation via simultaneous exploration and identification. In CVPR, pages 6672-6688 2023.
[49] Jiazhao Zhang, Chenyang Zhu, Lintao Zheng, and Kai Xu. Fusion-aware point convolution for online semantic scene segmentation. In CVPR, pages 4534 4543, 2020.
[50] Sixian Zhang, Xinhang Song, Yubing Bai, Weijie Li, Yakui Chu, and Shuqiang Jiang. Hierarchical tbjece-to-zone graph for object navigation. In ICCV, pages 15130-15140, October 2021.
[51] Gengze Zhou, Yicong Hong, and Qi Wu. Navgpt: Explicit reasoning in vision-and-language navigation with large language models. In AAAI, volume 38. pages 7641-7649, 2024.
[52] Kaiwen Zhou, Kaizhi Zheng, Connor Pryor, Yilin Shen, Hongxia Jin, Lise Getoor, and Xin Eric Wang. Esc: Exploration with soft commonsense constraints for zero-shot object navigation. In ICML, pages 42829 42842. PMLR, 2023.
12

---

Lrro
2
x m(m m)
Aro
Prompt
Navie LLM
Our LLM
Aspended token
Response
Tyees
mmm n) x
Lyres
m(n
Lnavle = m(m + nt) (ppro bres)
lour = Lepoo + m(m + n) (bres + 2)
Figure 7: The illustration of the computational complexity.
6 Appendix
6.1
Overview
In this appendix, first provide the dictionary for grouping object nodes in Section 6.2 Then provide the proof process and illustrated example on computational complexity of our efficient edge generation method in Section 6.3 Next provide the complete prompts used in approach in Finally we provide more visualization results in Section 6.5
Section 6.4
6.2 Related Categories
When registering a new group node, we need to judge whether two object categories are related. use LLM to generate the relationship dictionary, as shown below:
(Bed, Nightstand) (Wardrobe, Dresser) (Bookshelf, Chair) (Counter, Stove) (Table, Chair) (Bathroom Sink, Mirror) (Shower; Bathitb) (Refrigerator, Freezer) (Oven, Microwave) (Washing Machine, Dryer) (Safa, Table) (Desk, Office Chair) (Computer, Monitor) (Piano. Bench) (Fireplace, Mantel) (Table, Mirror) (Window, Curtains) (Closet, Hangers) (Bathroom Cabinet, Toiletries) (Living Room Rug, Coffee Table) (Kitchen Cabinet, Dishes) (Dining Room Chandelier, Dining Table) (Clock, Wall) (Floor Lamp, Reading Chair) (Couch, Throw Pillows) (Bookcase, Books)
6.3 Time Complexity for Edge Updating
Here we provide detailed proof for Eq (T) As shown in Figure 7 the computational com- plexity of processing m(m + n) pairs of nodes for the naive method is O(m(m n)) and the time is Tnaive = m(m + n) O ((T + )") Complexity of our method is Tour O ((Lpro + m(m + n) Lrea m(m n) 2))), where Lyro > 2 and Lpro Lrea.
So approximate that Lpro
0 and frez (a 0.01). According to the actual scene Eyro
graph, usually S m 5, < 100. Then we compute the ratio as:
(1+
mlm n) brae + m(m+n))22 Lipoo
Tour
(Lpro + m(m + n) Lree + m(m + n) 2)" m(m + n) (Lyro + Lres)"
(5)
T Thaive
m(m + nn): (1 +++ frnce
Since 2_ O. we have: Topro
Tour Tuaive
1+ (m² + mn)
(6)
m(m + n))
1
13

---

Since a meets 0 < a < 1, we can use the small value approximation principle
[Lya I+ga
)
(1 + (p - a)a"" simplify the equation:
Tour
1
(1 (m² + mn - 1) aa)
miive
Then we use the prior 1 1 m & 5 and S n & 100 to scale the coefficient into a constant c. The coefficient monotonically increases with and at
(1 + (m² + mm 1) a) rm 2,n 0.01 (0.01m² + m -0.01)
(8)
m
m
The coefficient decreases first and then increases with m. It takes the maximum value when m is its maximum:
(0.01m² + - 0.01) m=5
5.49
m
Consequently, we obtain the ratio:
Tour
(10)
naivee + n
where 5.49. Our method reduces the complexity by (m + n) times, from O(m(m + n)) to (mm) So LLM generates relationship with ((m) complexity, which much faster than the naive baseline.
6.4 Prompt
We provide the complete prompts of SG-Nav.
Edge Connecting. In the edge connecting process, the complete prompt is as follows:
You are an AI assistant with commonsense and strong ability to infer the spatial relationships in an indoor scene.
need to provide the possible spatial relationships between several pairs of objects. Relationships include ["next to" "above", "opposite to", "below", "inside", "behind", "in front of", ...]. ...).
All the pairs of objects are provided in JSON format, and you should also response in JSON format. Here examples:
1.
Input:
[['objecti"; "chair", "object2": "table"), ("objecti": "monitor",
"object2": "desk"]]
Response:
[<"rellatonshiip""
"next to"), ("relationships": "above"]]
2.
Input:
[['object1": "sofa", "object2": "TV"), ("objecti"; "plant", "object2": "chair"]]
Response:
[""relationshipa": "opposite to"), ("relationships"" "behind")]
Now you predict these pairs of objects: [["object1";
0, "object2":
O {"objecti"; O, "object2": 0), ...]
where (} will be replace by the object categories.
14

---

Hierarchical COT. In the process of goal inference, we use the following prompts to let LLM predict the most likely position of goal.
Step (Predict Distance of Object):
You are an AI assistant with commonsense and strong ability to infer the distance between two objects an indoor scene.
You need to predict the most likely distance of two objects in a room. You need to answer the distance in meters and give your reason. Here is the JSON format:
Input:
("objecti"; "table", "object2": "chair")
Response:
("distance"; 0.5, "reason": "Because there is always a chair next to the table.")
Now predict the distance and give your reason: ("object1": 0, "object2": (}}
where () will be replace by the object.
Step 2 (Ask Question):
You are AI assistant with commonsense and strong ability to infer the spatial relationships in an indoor scene.
But you have insufficient information. You need to ask question about the spatial relationship between object and the goal in the following JSON format:
Input:
("object": "sofa", "goal": "TV"}
Response:
("question":
"Is there table next the sofa?"} ask question: ("object";
O "goal": 0})
where {} will be replace by the object and goal.
Step 3 (Answer Question):
You are an AI assistant with commonsense and strong ability to answer question about the objects in an indoor scene.
Given graph scene of the scene, you need to answer the question in the following JSON format:
Input:
("subgraph": ("nodes": ["sofa", "table", ...]. "edges": ["sofa next to table", ...]}, "question": "Is there a table next to the sofa?"}
Response:
{"answer": "Yes"}
Now answer question: ("subgraph":
0, "question"; 0})
where () will be replace by the subgraph and question.
Step 4 (Predict Distance of Subgraph):
15

---

You are an AI assistant with commonsense and strong ability to infer the distance between a subgraph and a goal in an indoor scene.
You need to predict the most likely distance of subgraph and goal in a room. You need to answer the distance in meters and give your reason.
Here is the JSON format:
Input:
("subgraph"; {"nodes": ["sofa", "table", ...], "edges": ["sofa next to table", ...,,, "goal": "TV"}
Response:
("distance": 2, "reason": "Because TV and sofa are on both sides of table.") "}
Now predict the distance and give your reason: ("subgraph": 0, "goal": O}
where {} will be replace by the subgraph and goal.
6.5
Visualization
We further provide visualizations on the constructed scene graphs, the frontier scores along with the LLM reasoning output, and failure case help comprehensive understanding our approach.
Figure 8: Visualization of two scene graphs.
Mistake Sofa for Chair
Agennt
perception
Step 31
Step 70
Step 101.
The living room usually has sofa next to table, because it common space for and spending time with family.
Go to the living room to find a chair because is the designated seating area in most homes.
Dccupancy Map
Reason Output of LLM
Reason Output LLM
Figure 9: Visualization for the sequential frontier scoring and reasoning output of LLM. We color the frontiers, where frontiers with high score are in red and ones with low score are in blue.
16

---

Agent
Occupancy Map
Occupancy Map
Occupancy Map
Figure 10: Three failure cases of navigation. In the first case, agent mistakes shelf for cabinet and navigates to In the second case, agent fails detect the goal object. In the third case, L.LM predicts wrong location of chair because there are sofa and TV near this frontier, where there is high probability of chair appear here. This makes the agent harder to find the goal in limited steps.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations in Section S
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
17

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide the full set of assumptions well as a complete proof in Sec-
tion 6.3
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The results in our paper can be reproduced by the readers.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often
18

---

one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We have uploaded our code on MP3D dataset in the supplementary materials. We will release all code upon acceptance. It takes some time for us to clean the whole project and make the code easy to play with.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
wwmiiissssiccccccccc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https wwaiicccgueeeeeeee www.oooooidissiooooooooooo sww.bbmiiciiooociccc.c.... for more details.
/ //nips
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have specify the experimental settings in Section 4.1
19

---

Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Error bars reported because it would be too computationally expensive.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
The evaluation of our model is performed on four RTX 3090 GPUs.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:://///aaappp.cccccplll///ta
Answer: [Yes]
20

---

The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our method is currently only used for academic research.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
21

---

12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We have cited all the code and dataset that we use.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification:
Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
22

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "MFcuS7F9Qt", "reviewer": "Reviewer_zzdn", "summary": "This paper introduces a zero-shot object navigation framework using a 3D scene graph to represent the environment. It employs a hierarchical chain-of-thought prompt to LLMs for goal location navigation and includes a re-perception mechanism to correct errors. Experiments are conducted on MP3D, HM3D, and RoboTHOR.", "questions": "- How is the accuracy of the 3D scene graph validated?\n\n- The chain-of-thought method to prompt LLM is interesting. Are there other methods to prompt LLM? Comparing different prompt methods could make the experimental results more solid.\n\n- Is the zero-shot object definition meant to be training-free, or does it mean that the target is not predefined? While the problem definition mentions open-vocabulary, Figure 1 and the selected object categories in the experiments are still common objects.\n\n- I would like to see some failure cases. What are the reasons behind these failures?", "limitations": "The authors discuss potential limitations in the conclusion section.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The task is aimed at open vocabulary ObjectNav, which is a more general task.\n\n- Edge updating considers computational complexity.\n\n- The idea of a hierarchical chain-of-thought method to prompt LLM is interesting.\n\n- The paper is well-structured and easy to understand.", "weaknesses": "- Although the paper claims to target open vocabulary (zero-shot) object navigation, the method uses some closed-set settings, such as a predefined relationship dictionary, which contradicts the open vocabulary premise.\n\n- In the experiments, the target objects chosen (on MP3D and HM3D) are the same as those in regular ObjectNav settings, where the objects are common. This seems to undermine the method's capability in handling open vocabulary objects.\n\n- The proposed 3D scene graph is defined with objects, groups, and rooms. There is a related work for ObjectNav that also constructs a similar graph with objects, zones, and scene nodes. I suggest that authors can compare their graph construction with this work and include it in the references to enrich the paper.\n[1] Hierarchical object-to-zone graph for object navigation, ICCV 21.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. About open-vocabulary setting, is it training-free**\n\nOur method is training-free and open-vocabulary. Since most objects occur in the scene belong to some common categories, we can pre-define the relationship among these categories and save them to a dictionary, which accelerates inference speed. Note that the relationship is acquired by prompting LLM, so this process is also training-free. When SG-Nav receives object categories that have not been saved before, we simply prompt LLM to generate the relationship and update the dictionary.\n\n**2. The choice of object categories**\n\nWe select the categories as same as those in regular ObjectNav settings in order to compare with supervised and close-vocabulary methods, following the experimental setting of ESC. But SG-Nav is not limited to any category set.\n\n**3. Comparison with “Hierarchical object-to-zone graph for object navigation”**\n\nThis paper proposes a hierarchical object-to-zone (HOZ) graph for ObjectNav. There are several differences between SG-Nav and this work. First, SG-Nav is completely training-free, but HOZ needs to finetune a Fast-RCNN for graph construction and train a LSTM policy module via reinforcement learning. Second, the 3D scene graph in SG-Nav contains more hierarchy and relationship between objects, while HOZ mainly consists of zone nodes and using adjacent probability as the edges between nodes. Third, SG-Nav adopts LLM to exploit the hierarchical and structural information in 3D scene graph in zero-shot, while HOZ trains a network to parse the graph. We will cite this paper and compare with it in the final version of paper.\n\n**4. The accuracy of 3D scene graph**\n\nSince our method mainly focuses on how to leverage 3D scene graph to enable context-aware reasoning for ObjectNav, we do not quantitively evaluate the accuracy of 3D scene graph. To better demonstrate the intermediate process of SG-Nav, we provide some visualization results in the attached PDF file.\n\n**5. Ablation on CoT-Prompting**\n\nWe further design ablation study on the Chain-of-Thought Prompting method. The raw performance on MP3D is 40.2/16.0 (SR/SPL). If we directly convert the 3D scene graph into a text and prompting LLM, the performance on MP3D is 36.5/14.9 (SR/SPL). By converting the nodes and edges into text separately, the performance on MP3D is 37.0/15.0 (SR/SPL), which is better than previous one but still worse than our CoT-prompting. The results show that fully exploiting the hierarchical graph structure of scene graph can help LLM understand the scene context and make better decision.\n| **Method** | **SR** | **SPL** |\n| -- | :--: | :--: |\n| Text prompting | 36.5 | 14.9 |\n| Text prompting seperately | 37.0 | 15.0 |\n| **Raw** | **40.2** | **16.0** |\n\n**6. Failure case**\n\nWe demonstrate failure case in the attached PDF file. Please refer to the global rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sizMKfeT1r", "reviewer": "Reviewer_7ZKj", "summary": "This paper propose to use 3D Scene Graph Prompt in LLM-based Zero-shot Object Navigation, which fully use information of whole scene and is explainable. Also it propose prune-based method to accelerate the construct of graph. Enough expriments show the superority of the method and the effectiveness of each modules.", "questions": "1.In line 39-41, the author mentions previous methos are abstract and unexplainable. Please explain this viewpoint in more detail and show how your method solve this problem.\n\n2.Will the already constructed scene graph vary based on changes in perspective? (For example, in the previous timestamp when A and B objects did not appear in the same image, Long Edge Pruning is required, while in the next time when A and B appear in the same image, Short Edge Pruning is required, the scene graph may be differnet). Does using Incremental Updating and Pruning ignore this change and result in cumulative errors.", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.This paper solves the problem of insufficient use of scene information in LLM based Zero shot Object Navigation in the past.\n\n2. A fast way to establish a scene graph is proposed to ensure fast speed, and theoretical proof is provided.\n\n3. The experiment achieves good results and achieved SOTA results on multiple datasets.\n\n4. The language of the paper is fluent, easy to understand, and there are few grammar errors.", "weaknesses": "1.VLM and is needed for Short Edge Pruning which may increase the time consumption of model to construct graph.\n\n2.The Incremental Updating and Pruning may have some issue. (See in Question.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Inference latency of SG-Nav**\n\nIn each step of navigation, the time cost of SG-Nav can be divided into perception, graph construction and reasoning, which takes 0.3s, 1.3s, 0.14s on average, accounting for 17.3%, 74.8% and 7.9%. The edge pruning belongs to graph construction, which only takes **11.5%** of the overall time.\n| **Component**             | **Average Time (s)** | **Percentage (%)** |  \n|---------------------------|:----------------------:|:--------------------:|  \n| Perception                | 0.3                  | 17.3               |  \n| Graph Construction        | 1.3                  | 74.8               |  \n| &emsp;&emsp;**Edge Pruning**  | **0.2** (part of GC)      | **11.5** (part of GC)       |  \n| Reasoning                 | 0.14                 | 7.9                |\n\n**2. Why SG-Nav is explainable compared with previous methods like L3MVN and ESC**\n\nPrevious LLM-based ObjNav methods like L3MVN and ESC directly score each frontier based on the nearby object categories. For example, if there are table, computer and chair near a frontier, these method directly prompting language model with the text of these three categories to predict the probability of this frontier, which do not consider the relationship between objects.\n\n**3. Inconsistency of Long Edge and Short Edge**\n\nWe thank the reviewer for the constructive advice. Currently, we do not consider the change of perspective in our paper. We further add this verification mechanism to our system. At each timestamp, we not only validate newly generated edges, but also check whether there are some existing object nodes that has been updated (merged with newly detected objects). For edges which have at least one updated node, we also perform validation on them. With this modification, the performance of SG-Nav changes from 40.2/16.0 to 40.2/16.1 (SR/SPL), which shows that the proportion of inconsistency between long and short edges in actual samples is relatively small.\n| **Method** | **SR** | **SPL** |\n| -- | :--: | :--: |\n| w/o Verification | 40.2 | 16.0 |\n| **w Verification** | **40.2** | **16.1** |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k7Lqt5ZI85", "reviewer": "Reviewer_aSmS", "summary": "The paper proposes a 3D scene graph prompting strategy and designs a hierarchical chain-of-thought prompt for improving LLM-based zero-shot object navigation. The 3D scene graph is incrementally updated and pruned to reduce the computational complexity. A re-perception mechanism is also introduced to correct the perception error. Experimental results on MP3D, HM3D, and RoboTHOR environments show the superiority of the proposed method over the competitors.", "questions": "See details in the weaknesses.", "limitations": "Limitations have been discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1 The proposal of 3D scene graph prompting and hierarchical chain-of-thought is well-motivated and effective for encouraging the scene context reasoning and improving the decision interpretability. \n\n2 The author provides a detailed time complexity analysis for the proposed edge updating method.\n\n3 Extensive experiments are conducted on three different datasets and the results show the effectiveness of the proposed method.\n\n4 The paper is well-written with figures and tables nicely presented.", "weaknesses": "1 The approach utilizes the LLM to predict the possible relationships between objects, and possible distances between object and goal. However, this information may be various in different scenes. What if the prediction is inconsistent with the real scene? Would it largely impact the navigation success? I suggest the author give more results and analyses about this. \n\n2 Although Figure 6 gives the visualization of the navigation process, the author did not provide the visualization for the sequential frontier scoring and reasoning output of LLM. It would be better to present this visualization to help further understand the advantages of the approach.\n\n3 There are some recent works surpassing the reported compared methods, e.g., L3MVN (IROS 2023), VoroNav (ICML 2024), OpenFMNav (NAACL 2024), and VLFM (ICRA 2024). The authors should add them to the table for a more complete comparison and analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Error in the prediction of relationship and distance**\n\nWe measure the accuracy of relationship and distance prediction on episodes of MP3D validation set. \nFor relationship prediction, we conduct human study to annotate the correctness of each relationship predicted by SG-Nav. For each episode, we let the annotators to evaluate the scene graph of the final navigation step. If all annotators think more than 80% edges in this scene graph correctly describe the real relationship, we annotate this episode with correct relationship. \nFor distance prediction, we consider the prediction to be correct if the error between a predicted distance and the actual distance is less than 20%. For each episode, we compute the success rate of distance predictions on the final prompt, because the scene graph at this time is the most complete and the number of subgraphs is sufficient.\nAs shown below, the overall accuracy of relationship prediction and distance prediction is **74.7%** and **68.4%** respectively, which is accurate. We observe that correct relationship and distance prediction will increase the success rate of navigation. However, even if the predicted relationship and distance is incorrect, the agent still has a relatively high probability to successfully navigate to the goal (**33.2%** success rate of navigation for incorrect relationship, and **35.4%** for incorrect distance). This validates the robustness of our framework.\n\nSR of navigation:\n| Condition |SR|  \n| -- | :--: |  \n| Correct Relationship | 42.6 |  \n| Incorrect Relationship | **33.2** |  \n| Correct Distance     | 42.8 |  \n| Incorrect Distance   | **35.4** |\n| Unconditional | 40.2 |\n\nAccuracy of relationship:\n| Result/Relation | Correct Relationship | Incorrect Relationship | Total |  \n| -- | :--: | :--: | :--: |  \n| Navigation Success | 31.8% | 8.4% | 40.2% |  \n| Navigation Failure | 42.9% | 16.9% | 59.8% |  \n| Total | **74.7%** | 25.3% | 100% |\n\nAccuracy of distance:\n| Result/Relation | Correct Distance | Incorrect Distance | Total |  \n| -- | :--: | :--: | :--: |  \n| Navigation Success | 29.3% | 11.2% | 40.5% |  \n| Navigation Failure | 39.1% | 20.4% | 59.5% |  \n| Total | **68.4%** | 31.6% | 100% |\n\n**2. Visualization for the sequential frontier scoring and reasoning output of LLM**\n\nWe provide the visualization in the attached PDF file.\n\n**3. Comparison with more methods**\n\nWe further compare SG-Nav with more recent works including L3MVN, VoroNav, VLFM and OpenFMNav on MP3D, HM3D and RoboTHOR. For LLM-based methods (SG-Nav, L3MVN, VoroNav, OpenFMNav), we uniformly set LLaMA-7B as the LLM for fair comparison. The results are shown in the table below. It is shown that SG-Nav achieves state-of-the-art performance on the challenging MP3D and RoboTHOR benchmarks. On HM3D, SG-Nav also outperforms recent methods like L3MVN and VoroNav. However, we observe SG-Nav fall slightly behind VLFM and OpenFMNav on HM3D. This is because HM3D is the relatively simplest benchmark among the three, where SG-Nav’s ability to reason and plan in complex and large scenes cannot be fully utilized. Considering the overall performance on three benchmarks, SG-Nav shows leading advantage, especially on complicated and challenging scenarios. \n| **Method** | **MP3D SR** | **MP3D SPL** | **HM3D SR** | **HM3D SPL** | **RoboTHOR SR** | **RoboTHOR SPL** |  \n| -- | :--: | :--: | :--: | :--: | :--: | :--: |  \n| L3MVN | 34.9 | 14.5 | 48.7 | 23.0 | 41.2 | 22.5 |  \n| VoroNav | 31.2 | 14.2 | 42.0 | 26.0 | 38.4 | 22.2 |  \n| VLFM | 36.2 | 15.9 | 52.4 | **30.3** | 42.3 | 23.0 |  \n| OpenFMNav | 37.2 | 15.7 | **52.5** | 24.1 | 44.1 | 23.3 |  \n| **SG-Nav** | **40.2** | **16.0** | 49.1 | 24.3 | **47.5** | **24.0** |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5bp8orMEua", "reviewer": "Reviewer_JsEs", "summary": "This paper presents a new framework for zero-shot object navigation. Unlike previous methods that only provide objects in close proximity, this paper constructs a scene graph that captures the relationships between objects, groups, and rooms. \nThis scene graph allows for a more comprehensive understanding of the environment by the navigation system, enabling it to make decisions based on a wider context rather than immediate surroundings. This method significantly improves the robustness and versatility of the navigation system, making it more effective in a variety of settings.", "questions": "1. Line 198， I think a hint that $a$ is an action would be clearer. In addition, why is it said that direct prediction of action by LLM is difficult? Any references or experiments to prove this?", "limitations": "The authors discuss limitation very well.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper tries to solve the problem of zero-shot navigation with LLM and scene graph, and experimental results show that this combination does improve the navigation performance.\n\n2. The way the scene graph is updated is interesting. The authors combine the capabilities of LLM and VLM to create connections between nodes and reduce irrelevant edges to make the graph more precise.\n\n3. The experimental results show that there is no significant difference between the results of LLaMA-7B and GPT-4, indicating that the method can work in small-volume LLMs, which is friendly to the demand of computational resources.", "weaknesses": "1. The use of scene graphs is not very new in the field of navigation. I think it's important to discuss the use of the scene graph in navigation in related work.\n   \n2. I think the authors should take some LLM-based object Navigation method as baseline in the experiments to compare with the proposed method. The authors mention in the abstract that the previous LLM based navigation method promotes LLM with the text of spatially closed objects. Yet no comparison is made in the experimental section, which hardly demonstrates the superiority of the scene context. For example, \"L3MVN: Leveraging Large Language Models for Visual Target Navigation\" shows comparable success rate than the proposed method in HM3D benchmark, which is also mentioned in the Line 77.\n   \n3. The way LLM utilizes the scene graph is still through text prompt, which makes me think that the authors have overpacked it as \"LLM friendly structure\" a little bit. I think here the usage of the scene graph is just a prompt design and doesn't reflect the hierarchy of the scene graph very well. I consider this reference to be the basis on which I made this judgment: \"SayPlan: Grounding Large Language Models using 3D Scene Graphs for Scalable Robot Task Planning\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1. Discussion of scene-graph-based navigation**\n\nWe thank the reviewer for the constructive advice. We will add more literature on scene graph-based navigation in the final version of paper. \n3D scene graph is widely utilized in various embodied tasks, such as grounding [1] and task planning [2]. In the field of navigation, we find [3,4] most relevant to our work, which focus on graph-based ObjectNav.\nStructNav [3] constructs a scene graph to represent the observed scene. It adopts BERT to predict the similarity between each object node and the goal. Then the scene graph is used to propagate semantics to the geometric frontiers for action planning. Here the edges of scene graph are only used to represent connectivity, rather than relationship between objects.\nVoroNav [4] constructs a Voronoi graph, where nodes represent regions and edges represent whether two regions are connected. VoroNav directly prompts LLM with the object categories contained in each node to score regions for navigation. The graph is only used for determining explorable area.\nThese two methods do not make use of the relationship between objects. On the contrary, SG-Nav constructs a hierarchical 3D scene graph with rich node and edge information. We also propose a Chain-of-Thought Prompting method to exploit the nodes and edges contained in scene graph with LLM. In this way, LLM can understand the hierarchical and structural information in the 3D scene graph for better reasoning.\n\n[1] Context-Aware Entity Grounding with Open-Vocabulary 3D Scene Graphs, CoRL 2023\n\n[2] SayPlan: Grounding Large Language Models using 3D Scene Graphs for Scalable Robot Task Planning, CoRL 2023\n\n[3] How To Not Train Your Dragon: Training-free Embodied Object Goal Navigation with Semantic Frontiers, RSS 2023\n\n[4] VoroNav: Voronoi-based Zero-shot Object Navigation with Large Language Model, ICML 2024\n\n**2. Comparison with more LLM-based navigation methods**\n\nWe have compared with ESC, a LLM-based ObjNav method in our experiments. Following the reviewers’ advice, we further compare with some more recent LLM-based methods including L3MVN, VoroNav and OpenFMNav on MP3D, HM3D and RoboTHOR. We uniformly set LLaMA-7B as the LLM for fair comparison. The results are shown in the table below. It is shown that SG-Nav achieves state-of-the-art performance on the challenging MP3D and RoboTHOR benchmarks. On HM3D, SG-Nav also shows comparable performance with the most recent methods. We observe SG-Nav works better on MP3D and RoboTHOR than on HM3D. This is because HM3D is the relatively simplest benchmark among the three, where SG-Nav’s ability to reason and plan in complex and large scenes cannot be fully utilized. Considering the overall performance on three benchmarks, SG-Nav shows leading advantage, especially on complicated and challenging scenarios.\n\n| **Method** | **MP3D SR** | **MP3D SPL** | **HM3D SR** | **HM3D SPL** | **RoboTHOR SR** | **RoboTHOR SPL** |  \n| -- | :--: | :--: | :--: | :--: | :--: | :--: |  \n| L3MVN | 34.9 | 14.5 | 48.7 | 23.0 | 41.2 | 22.5 |  \n| VoroNav | 31.2 | 14.2 | 42.0 | **26.0** | 38.4 | 22.2 |  \n| OpenFMNav | 37.2 | 15.7 | **52.5** | 24.1 | 44.1 | 23.3 |  \n| **SG-Nav** | **40.2** | **16.0** | 49.1 | 24.3 | **47.5** | **24.0** |\n\n[1] L3MVN: Leveraging Large Language Models for Visual Target Navigation, IROS 2023\n\n[2] VoroNav: Voronoi-based Zero-shot Object Navigation with Large Language Model, ICML 2024\n\n[3] OpenFMNav: Towards Open-Set Zero-Shot Object Navigation via Vision-Language Foundation Models, NAACL 2024\n\n**3. The usage of hierarchy in SG-Nav**\n\nWe have considered the hierarchical graph structure in our Chain-of-Thought Prompting. Although we prompt LLM with only texts, the LLM is required to exploit the graph through nodes and their connected edges. For example, the prompt “Given [nodes] and [edges] of subgraph, answer above [questions].” makes the reasoning of LLM aware of the graph structure.\nThe ablation study in Table 4 in our paper also shows that there will be a performance drop if we remove all edges and keep only nodes. This means our method really makes use of the graph structure.\nWe further conduct ablation experiments by removing edges between nodes in different level. We observe the performance on MP3D changes from **40.2/16.0** to **38.2/15.5** (SR/SPL), which shows that our CoT-Prompting effectively utilize the hierarchical information of the 3D scene graph.\nBut we agree with the reviewer that how to better exploit the structure information contained in 3D scene graph with LLM is a very promising direction. The current prompting strategy could be further improved (e.g., by designing a more graph-related workflow for LLM), which we leave for future work.\n| **Method** | **SR** | **SPL** |\n| -- | :--: | :--: |\n| Removing Inter-level Edges | 38.2 | 15.5 |\n| **Raw** | **40.2** | **16.0** |\n\n**4. Explanation of $a$ in Line 198**\n\nWe have defined $a$ in L105, which means the action of agent. It is very difficult to directly predict action for navigation. In most state-of-the-art object navigation methods [1,2,3], the prediction is divided into global and local policy. First, a global policy is adopted to predict the position to be explored. Then a local policy is used to plan action based on the predicted position and occupancy map. As for LLM, its advantage mainly lies in reasoning, so it is more suitable for LLM to serve as a global policy, while action planning can be simply solved by traditional methods such as Fast Marching Method and A*.\n\n[1] PONI: Potential Functions for ObjectGoal Navigation with Interaction-free Learning, CVPR 2022\n\n[2] L3MVN: Leveraging Large Language Models for Visual Target Navigation, IROS 2023\n\n[3] ESC: Exploration with Soft Commonsense Constraints for Zero-shot Object Navigation, ICML 2023", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for their valuable and constructive comments. We provide detailed answers to these questions and will revise the paper accordingly.

Meta-review: This paper presents a zero-shot object navigation framework with a 3D scene graph to represent the observed scene.
Initially it received rating of 6654.
Most of the concerns were resolved during rebuttal and the Reviewer aSmS raised the score from rating of 5 to 6.
However, the Reviewer JsEs found the performace and novelty are not strong enough, and the rating was dropped from 4 to 3 after rebuttal.
The author provided detail response and additional experiments.
The AC carefully looked into this case and had discussion with the SAC.
Both the SAC and AC agree that the requested experiment results are qualified to support the argument of this paper, and the concerns from Reviewer JsEs are not significant enough to reject the paper.
The AC thus recommends acceptance for this paper.
The authors are urged to include the new experiments (e.g., ones with stronger LLMs) in the camera-ready version of the paper.
Decision: Accept (poster)