© Wuhan University 2025

0 Introduction

Nowadays, autonomous mobile robots play a vital role in many industries, such as logistics management, consumer rescue, and housekeeping services^[1]. Navigating to the destination is a basic ability that robots need to have. Classic navigation methods are often based on precise and digital geometric maps. When faced with complex and variable environments that lack well-constructed maps, these methods exhibit poor generalizability. With the development of machine learning and computer vision, learning-based navigation methods have emerged. During interactions with the surrounding environment, the agent uses artificial neural networks to process visual observations and make action decisions. Owing to the independence from prior maps, this end-to-end navigation method has become a research hotspot in recent years. It is known as target-driven navigation^[2], visual mapless navigation^[3-4], or object goal navigation^[5]. For the sake of clarity, this paper uniformly refers to it as object goal navigation.

Since there is no pre-built map in object goal navigation, the agent only perceives through visual images and lacks spatial cognition of the environment. This causes the agent to easily overfit the training environment, which greatly limits its generalization ability in unfamiliar environments. The core of addressing the challenge lies in endowing the agent with spatial intelligence. Spatial intelligence refers to the ability of an agent to transform visual observations into insights, insights into understanding, and understanding into actions^[6]. Without this ability, the agent simply transforms observations into actions, which makes it difficult to complete navigation tasks in unfamiliar environments. For example, assuming that the navigation target is a refrigerator, the agent with spatial intelligence will not waste time in the living room, but will move towards objects related to the kitchen. However, the agent without spatial intelligence does not have spatial cognition ability and is likely to fall into an endless loop in rooms outside the kitchen.

To endow the agent with spatial intelligence, researchers drew on Knowledge Graph (KG) in the computer field and proposed the concept of scene graph. KG is a kind of semantic network that reveals relationships between entities, facilitating a formalized depiction of real-world entities and their interconnections^[7-8]. It consists of a mesh-like structure of "entity-relationship-entity" triplets, formally denoted as $G\left(V,E\right)$, where $V$ denotes the set of entities, and $E$ denotes the set of relationships. In scene graph, entities typically describe object classes (e.g., televisions), concrete instances (e.g., gray leather sofas), zones (e.g., bedrooms), and other environmental elements. Relationships represent spatial or semantic connections between these entities, such as "next to", "above", and "inside". Scene graph provides prior information on the relationship between the navigation target and the overall scene, allowing the agent to perceive the surrounding environment, infer the target location and plan the path based on visual information. To distinguish other methods, we define the navigation method that integrates the scene graph as scene graph-based object goal navigation.

When it comes to scene graph-based object goal navigation, several questions emerge: 1) How to construct scene graph? 2) How to integrate scene graph into the object goal navigation framework? 3) How to evaluate the performance of scene graph within the object goal navigation framework? Thus, this paper undertakes a survey of research related to scene graph in object goal navigation to answer the mentioned questions: 1) offering an overview of formal description, computational framework in object goal navigation; 2) summarizing methods for constructing and applying scene graph in object goal navigation; 3) experimentally validating the performance of scene graph in object goal navigation, and outlines future directions. This paper emphasizes the role of scene graphs in object goal navigation and shows how it endows the agent with spatial intelligence.

1 Object Goal Navigation

1.1 Formal Description of Object Goal Navigation

Object goal navigation is a basic task for indoor robots in unfamiliar environments. In this task, the agent is given a specific object target, such as a laptop. The agent needs to understand what the target is and navigate towards it using visual observations. Classic navigation tasks aim to guide the agent to a point goal based on pre-built maps. This method overly relies on maps and does not form an understanding of the surrounding environment for the agent. Unlike classic navigation, the realization of object goal navigation tasks is inseparable from interaction with the surrounding environment. The interaction process of object goal navigation is described in detail below.

The subject of interaction is the navigation agent, and the object is the navigation environment. After executing an action, the agent obtains visual observations from the navigation environment and then carries out the next action based on new observations, repeating this cycle continuously. Under this interaction, the navigation agent needs to perform an action that is most conducive to the completion of the navigation task based on the observation at each moment, which is a sequential decision problem. Therefore, this problem can be mathematically described as Markov Decision Processes (MDP). One approach for addressing this problem is Reinforcement Learning (RL). This approach emphasizes the interaction between the agent and environment, facilitating the memorization of navigation experiences and learning of action strategies to maximize cumulative rewards^[9-14].

Object goal navigation defines the interaction between the agent and the environment through a quadruple $\left(\mathcal{S},\mathcal{A},\mathcal{P}\left(.\right),\mathrm{ℛ}\left(.\right)\right)$. In this context, $\mathcal{S}$ represents the state space, comprising all possible states in the environment; $\mathcal{A}$ signifies the action space, encompassing all feasible actions; $\mathcal{P}\left(.\right)$ represents the state transition function, where $\mathcal{P}\left(s_{t+\mathrm{1}}|s_t,a_t\right)$ denotes the probability when transitioning from the current state $s_t$ to the next state $s_{t+\mathrm{1}}$ given action $a_t$; $\mathrm{ℛ}\left(.\right)$ represents the reward function, where $\mathrm{ℛ}\left(s_t,a_t,s_{t+\mathrm{1}}\right)$ signifies the reward obtained when transitioning from current state $s_t$ to next state $s_{t+\mathrm{1}}$ via action $a_t$. The agent acquires information about these functions by observing states, actions, and rewards in interactions, represented as triplets $\left(s_t,a_t,r_t\right)$. As illustrated in Fig. 1, the agent moves through a "state-action-reward" loop in the environment across time steps $t=\mathrm{0,1},\dots ,T$, creating a Markov Decision Trajectory $\mathcal{T}$, defined as:

$\mathcal{T}=\left(\left(s_{\mathrm{0}},a_{\mathrm{0}},r_{\mathrm{0}}\right),\left(s_{\mathrm{1}},a_{\mathrm{1}},r_{\mathrm{1}}\right),\dots ,\left(s_T,a_T,r_T\right)\right)$(1)

Fig. 1 Interaction between the agent and environment

Referring to equation (1), the agent promptly receives reward feedback for each action. The aim is to maximize the cumulative reward, denoted as $R\left(\mathcal{T}\right)$, in order to refine the action strategy $\pi$. Here, $\pi$ represents a function that maps states to actions. By incorporating a weighting factor $\gamma \in \left[\mathrm{0,1}\right]$, $R\left(\mathcal{T}\right)$ is expressed as the weighted sum of all rewards along the trajectory:

$R\left(\mathcal{T}\right)=r_{\mathrm{0}}+\gamma r_{\mathrm{1}}+{\gamma }^{\mathrm{2}}{r}_{\mathrm{2}}+\cdots +{\gamma }^T{r}_T={\displaystyle \sum _{t=\mathrm{0}}^T}{\gamma }^t{r}_t$(2)

The expected return, represented as $E_{\mathbb{T}}\left[R\left(\mathcal{T}\right)\right]$, is used to elucidate the inherent randomness in actions and the environment. Under the policy $\pi$, the state-value function $V_{\pi }\left(s\right)$ or action-value function $Q^{\pi }\left(s,a\right)$ aids the agent in deriving the expected return. Here, $V_{\pi }\left(s\right)$ denotes the expected return achievable by adhering to policy $\pi$ from state $s$, whereas $Q^{\pi }\left(s,a\right)$ signifies the expected return from acting $a$ in state $s$ under policy $\pi$. The definitions of $V_{\pi }\left(s\right)$ and $Q^{\pi }\left(s,a\right)$ are as follows:

$V_{\pi }\left(s\right)=E_{\pi }\left[{\displaystyle \sum _{k=\mathrm{0}}^{\mathrm{\infty }}}{\gamma }^k{R}_{t+k+\mathrm{1}}|s_t=s\right]$(3)

$Q^{\pi }\left(s,a\right)=E_{\pi }\left[{\displaystyle \sum _{k=\mathrm{0}}^{\mathrm{\infty }}}{\gamma }^k{R}_{t+k+\mathrm{1}}|s_t=s,a_t=a\right]$(4)

Achieving superior action policies $\pi$ primarily involves three methods: value-based methods^[15-16], policy-based methods^[17], and hybrid methods^[18]. Value-based methods indirectly derive the agent's policy by iteratively updating value functions. Upon reaching its optimal value, the value function yields the optimal policy for the agent. This method ensures convergence toward locally optimal policies. Policy-based methods directly establish a policy network through function approximation. Actions are subsequently selected to acquire reward values, and the policy network parameters are optimized along the gradient direction to achieve an optimized policy that maximizes returns. These methods exhibit high sample training efficiency. Hybrid methods combine value-based and policy-based methods, resulting in fast training efficiency and convergence speed.

1.2 Computational Framework of Object Goal Navigation

Ongoing advancements in deep learning have led to the emergence of Deep Reinforcement Learning (DRL) algorithms, significantly facilitating spatial cognition training in object goal navigation^[19-22]. Within object goal navigation, the agent executes navigation actions guided by the current RGB image-based observation. The agent then acquires subsequent observations from the environment, continuing this iterative process to maximize cumulative rewards. The interaction process consists of the following key components:

1) Action: The action refers to the set of navigation actions. The action commonly is discrete, such as moving forward 0.25 meters, turning left or right by 45 degrees, and marking the task as completed. It is crucial for the agent to choose the appropriate action based on its perception of the surroundings. Different navigation strategies have different preferences for action selection. Aggressive strategies tend to favor moving forward, while cautious strategies often opt for turning left and right to observe the surroundings. Regardless of the navigation strategy, the most important thing is that the agent can successfully find the target object and consciously propose the done action.

2) Observation: The observation is RGB image obtained via a monocular camera, depicting the agent's first-person perspective. The quality and content of the images play a crucial role in the agent's understanding of the surroundings.

3) Target: The target could be an RGB image or an object category, like "television".

4) Rewards: Positive rewards (e.g., +5.00) are only granted upon successful task completion, aimed at minimizing the agent's path from task initiation to target discovery, while other navigation actions yield negative rewards (e.g., -0.01). A well-designed reward mechanism facilitates the training of good navigation agent.

Object goal navigation employs deep learning networks to model navigation processes and utilizes reinforcement learning algorithms for making navigation policy (refer to Fig. 2). It comprises three layers: 1) Perception layer, utilizing Convolutional Neural Networks (CNNs) like ResNet-50^[23] to extract image features to enhance the agent's perception; 2) Memory layer, employing Recurrent Neural Networks (RNNs) like LSTM^[24] to effectively represent long-term image feature sequences processed by ResNet-50, facilitating the agent's storage of navigation experiences and spatial environments memorization; 3) Decision layer, grounded on a reinforcement learning network, continuously guiding the interaction between the agent and the environment, collecting information on states, actions, and rewards, and iteratively optimizing navigation action policies and value functions based on this information. Object goal navigation network framework, solely reliant on visual sensors, transforms sight into insight, insight into understanding, and understanding into action, assisting the agent in navigating unfamiliar and map-less environments, offering a navigational solution equipped with cognition and spatial intelligence.

Fig. 2 The framework of object goal navigation based on DRL

1.3 Scene Graph in Object Goal Navigation

Scene graphs are formally defined as $G\left(V,E\right)$, with $V=\{v_{\mathrm{1}},v_{\mathrm{2}},\dots ,v_{\left|V\right|}\}$ representing the set of entities, comprising a total of $\left|V\right|$ distinct entities. $E=\{e_{\mathrm{1}},e_{\mathrm{2}},\dots ,e_{\left|E\right|}\}$ denotes the set of relationships, consisting of $\left|E\right|$ distinct types of relationships. Entities encompass objects, instances, images, or other elements within the environment, whereas relationships represent spatial or semantic connections among these entities. Scene graph provides prior knowledge about the relationships between the target and the overall scene, enabling the agent to perceive the surrounding environment, infer the target location based on visual information, and plan the path accordingly.

For instance, a typical living room contains objects such as a television (TV), sofa, coffee table, and TV stand, collectively forming an entity set denoted as $V$. The relationships among these entities, such as their relative positions, constitute the set of relationships $E$. In general, the TV is usually on the TV stand while the coffee table is near the sofa. Scene graph accurately represents the relationships between objects, which helps the agent to understand the spatial layout of the surrounding environment. For example, when the target is a TV, the agent will approach the TV stand instead of moving towards the sofa based on the scene graph.

The aforementioned example focuses on a scene graph constituted by different objects within a single room. When it comes to cross-room navigation tasks, the agent needs to understand the spatial relationships between different rooms. For example, in a large house, there are rooms such as kitchen, living room, bedroom and bathroom. These rooms constitute a room-level scene graph. When the target is a refrigerator, the agent needs to judge which room the refrigerator belongs to according to the scene graph. Usually, the refrigerator is in the kitchen. Therefore, the agent moves towards the kitchen based on the spatial relationship provided by the scene graph, instead of choosing to wander around rooms such as the living room.

Obviously, the scene graph is critical for the agent to complete the navigation task. So how to integrate the scene graph into object goal navigation? Undoubtedly, it requires a systematic approach. Initially, employing knowledge extraction techniques is necessary to collect "entity-relationship-entity" triplets for constructing the scene graph. The construction of the scene graph involves four models categorized by the types of triplets: object triplet model, instance triplet model, zone triplet model, and image triplet model. The four models provide the agent with different levels of spatial relations and semantic information, which is conducive to its spatial cognition. Subsequently, utilizing knowledge representation and reasoning techniques is essential to acquire the structural features of the scene graph. This utilization comprises three methods: multimodal feature fusion, value function estimation, and sparse reward improvement. The agent translates the spatial information provided by the scene graph into its own understanding, thereby navigating adaptively in the surroundings. The construction and usage of scene graph are introduced in detail in Section 2 and 3, respectively.

2 Construction of Scene Graph in Object Goal Navigation

The scene graph comprises multiple categories of "entity-relationship-entity" triplets, depicting different levels of spatial relationships and semantic information. Through research on scene graph-based object goal navigation, we categorize the construction methods of scene graph based on the type of triplet into the object triplet model, instance triplet model, zone triplet model, and image triplet model. In this section, we will introduce the four models respectively. At the end of this section, the four models will be compared and analyzed horizontally, pointing out their respective advantages and disadvantages.

2.1 Object Triplet Model

Yang et al^[25] first introduced the concept of the object triplet model to define the scene graph. They constructed an indoor scene graph offline using the Visual Genome dataset^[26] (refer to Fig. 3). The Visual Genome dataset comprises over 100 000 natural images, each annotated with objects, attributes, and various relationships. Every object category was represented as a node within the scene graph during the construction process. Connections between two nodes were established by computing the occurrence frequency of relationships between objects, setting a threshold of occurrence frequency exceeding 3. The scene graph based on Visual Genome dataset contains common sense about the relationship between objects. On this basis, the agent can organically combine single visual observations with spatial information, forming a primary object-level spatial intelligence. This study expanded the framework of object goal navigation, leading to increased interest in the study of scene graph.

Fig. 3 An example of scene graph based on Visual Genome dataset

Constructing the scene graph from the Visual Genome dataset involves matching external annotated data with existing objects within the navigation scenes, enabling offline graph construction. This type of graph, as a fixed common-sense graph, is integrated into the network without updating during navigation, limiting its generalizability. Consequently, there is a necessity to explore methods for dynamically constructing the scene graph in real time to enhance adaptability. Hence, Du et al^[27], inspired by human exploratory behavior, incorporated Faster R-CNN^[28] (an object detector, refer to Fig. 4) into the process of constructing the scene graph. Initially, given an input image, all objects within are detected using Faster R-CNN. If an object has multiple instances, only the one with the highest confidence level is chosen as the detected object. Subsequently, the position and confidence of each object's bounding box are recorded and concatenated to form local detection features. If some objects do not appear in the current observed image, their bounding box positions and confidences are set to zero. Next, the one-hot encoding of object is concatenated with the local detection features to form Location-Aware Features (LAF). Finally, all object node features within the scene graph are replaced with LAF. Following node determination, relationships between nodes are denoted by object occurrence, which is assigned to 1 when both targets appear in the same observation image, and 0 otherwise. The scene graph constructed based on Faster R-CNN contains real-time dynamic spatial information of the navigation environment, which has higher accuracy, effectiveness and robustness. Based on this scene graph, the agent can reason and analyze the visible objects within the current visual observation, convert the observation into insight and understanding, and finally make the correct navigation behavior. It can be said that the scene graph built based on Faster R-CNN provides the agent with more powerful object-level spatial intelligence compared with simple common-sense graph.

Fig. 4 An example of scene graph based on Faster R-CNN

Real-time object detection using a target detector has been a common approach for constructing scene graph^[28-30]. However, representing relationships between object nodes as simple binary (0 or 1) values leads to an oversimplified portrayal of spatial relationships. To precisely learn and explicitly represent relationships between objects, Dang et al^[31] introduced an unbiased Directed Object Attention (DOA) graph, providing a unique and adaptable representation of object relationships. The DOA graph is obtained through a weighted summation of the Intrinsic Object Graph (IOG) and the View Adaptive Graph (VAG): 1) the IOG represents inherent relationships between objects, such as the strong intrinsic relationship between a mouse and a computer. It is defined as a learnable matrix ${\mathit{G}}_n\in {\mathbb{R}}^{N\times N}$ featuring bidirectional edges between objects, where $N$ represents the number of objects. One end of an edge points towards the target, and the other represents objects requiring attention, with the edge weight indicating the intrinsic relationship between the target and other objects. Finally, SoftMax normalization is employed on the edge weights to ensure that the sum of weights connected to the target node equals 1. As the agent navigates various environments using reinforcement learning, ${\mathit{G}}_n$ gradually stabilizes and rationalizes; 2) the VAG demonstrates real-time adaptive relationships among objects within observed images. Upon obtaining an observed image, the agent generates global image features $I_t\in {\mathbb{R}}^{N\times \mathrm{512}}$ (derived from ResNet-18) and object features $S_t\in {\mathbb{R}}^{N\times \mathrm{518}}$ (obtained from Faster R-CNN). Object features $S_t$ consist of object visual images $S_t^{\mathrm{v}\mathrm{i}\mathrm{s}\mathrm{u}\mathrm{a}\mathrm{l}}$, object positional features $S_t^{\mathrm{p}\mathrm{o}\mathrm{s}}$, confidence $S_t^{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{f}}$, and target indicators $S_t^{\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{t}}$. To filter out noise, a confidence threshold is set, and when $S_t^{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{f}}$ > threshold, the final object feature $\widetilde{S_t}$ is obtained. Furthermore, the final image feature $\widetilde{I_t}$ is generated by concatenating the one-hot encoded feature of the target with the globally average-pooled $I_t$ to include target information in global image features. Lastly, the VAG $G_v\in {\mathbb{R}}^{N\times \mathrm{1}}$ is derived from the object feature and image feature using multi-head attention. Based on the scene graph constructed by Faster R-CNN, Dang et al^[31] employed attention mechanisms to convert fixed 0 or 1 relationships between objects into trainable parameters. The agent can not only gain insight into the spatial relationships between objects within the current visual observation, but also understand the relevance of different objects to the navigation task. Compared with the fixed-relationship scene graph proposed by Du et al^[27], the one proposed by Dang et al^[31] endows the agent with a more adaptive object-level spatial intelligence.

Regarding object goal navigation as a continual interaction between the agent and objects within the environment, solely focusing on spatial relationships between objects through "object-relation-object" triplets without considering the relationship between the agent and objects impedes the agent's grasp of spatial relationships. To tackle this issue, Hu et al^[32] introduced a technique for building two types of scene graph: 1) Object KG: This graph employs object detection algorithms for real-time extraction, similar to the previously mentioned approach. Edges in this graph illustrate horizontal positional relationships; 2) Agent-object KG: In this graph, edges represent depth relationships. These two types of scene graph allow the agent to understand the positions of objects in both horizontal and vertical directions, thereby improving navigation performance.

2.2 Instance Triplet Model

The object triplet model mentioned above concentrates on building a scene graph based on object categories. In this model, if the agent receives a target, any object aligning with the target category is deemed as a successful navigation instance. However, in real-world scenarios, the agent requires pinpointing a particular instance. For example, if the agent is instructed to "find a red wine glass", locating a "paper cup" would be considered a navigation failure. Hence, the instance triplet model is introduced to assist with precise navigation tasks encountered in real-life scenarios.

Li et al^[33] tackled instance-level navigation tasks by developing an instance-level scene graph (refer to Fig. 5), formally denoted as $G\left(V,E\right)$. $V$ denotes instance categories and $E$ signifies the spatial relationships between instances and their inherent category similarities. Each node $v\in V$ in the scene graph $G\left(V,E\right)$ comprises instance boundary $v_b$, color $v_c$, and texture $v_m$. In contrast to object-level scene graph, the instance-level scene graph exhibits two notable differences: 1) it incorporates target instance masks; 2) it selects instances from the same category instead of merely selecting the target with the highest detection score. Given the target description, an instance mask is employed to represent color and texture, while word vectors represent the target features, formally represented as $G_M\left(V_M,E\right)$. $G_M\left(V_M,E\right)$ shares edge connections with the scene graph $G\left(V,E\right)$, activating solely the target instance node $v_M^{*}$. $v_M^{*}$ is formed through the concatenation of feature vectors of color $T_c$ and texture $T_m$, while the remaining inactive instance nodes are denoted by zero vectors of identical dimensions. In cases where multiple instances of a category are detected, the crucial task is to select the most appropriate instance. Considering the detected instances $O^i,i\in \{\mathrm{1,2},\dots ,n\}$, $n$ represents the number of instances within category $i$, along with the bounding box $O_b^i$, color $O_c^i$, and texture $O_m^i$ of each instance, the process of instance selection can be formally defined as follows,

$i^{*}=\underset{i}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\left(F_d\left(\left[O_c^i,O_m^i\right],\left[T_c,T_m\right]\right)\right)$(5)

Fig. 5 An example of instance nodes

where $\left[x,y\right]$ denotes the concatenation of $x$ and $y$, and $F_d$ represents the function used to compute the Euclidean distance between two vectors. The essence of instance selection lies in choosing the instance that bears the closest resemblance to the target instance.

The instance triplet model focuses on real-world navigation tasks. Compared to the object triplet model, the nodes of the scene graph are no longer simple object categories, but specific object instances. The nodes contain the color and texture characteristics of each object, providing the agent with complex and accurate spatial relationships and semantic information. Based on instance-level scene graph, the agent can effectively distinguish the object instances in the visual observation when navigating in the real environment and determine whether it is the target object instance. Therefore, compared with the object-level scene graph, the instance-level scene graph helps the intelligent agent form spatial intelligence that is more conducive to real-world navigation tasks.

2.3 Zone Triplet Model

The object triplet model employs the object itself as a feature input, guiding the agent in planning navigation actions at each step. Nevertheless, lacking prior knowledge about the unfamiliar zone, the agent's initial navigation actions may be meaningless, such as "looking for the fridge in the bathroom". Further constraints on object relationships are necessary to substantially enhance the navigation capabilities. This necessitates the utilization of a zone triplet model, which focuses on the spatial relationships among objects within a shared zone.

Zhang et al^[34] introduced a Hierarchical Object-to-Zone graph (HOZ graph), wherein each zone comprises a correlated set of objects. For example, "microwave", "cookware", and "sink" frequently coexist within a shared zone. Therefore, if the target is designated as "microwave", the primary objective for the agent is to navigate to that particular zone. Based on the rooms and scenes present in the environment, the scene graph can be categorized into room-level HOZ graph and scene-level HOZ graphs (refer to Fig. 6).

Fig. 6 An example of room-level and scene-level HOZ graph

The room-level HOZ graph: Similar rooms tend to exhibit analogous layouts and objects^[35-36]. For example, when considering a living room, we may envision an area containing a sofa, table and television. Such areas form the room-level HOZ. Initially, within a specific room $i$, the agent randomly explores the room, acquiring a set of visual tuple features $\left(f,l\right)$. Here, $f\in {\mathbb{R}}^{N\times \mathrm{1}}$ represents a bag-of-words vector extracted by Faster-RCNN, indicating the presence of objects in the current observed image, with $N$ indicating the number of object categories. $l=\{x,z,{\theta }_{\mathrm{y}\mathrm{a}\mathrm{w}},{\theta }_{\mathrm{p}\mathrm{i}\mathrm{t}\mathrm{c}\mathrm{h}}\}$ represents the observation position, where $x$ and $z$ denote horizontal coordinates, while ${\theta }_{\mathrm{y}\mathrm{a}\mathrm{w}}$ and ${\theta }_{\mathrm{p}\mathrm{i}\mathrm{t}\mathrm{c}\mathrm{h}}$ represent the agent's yaw and pitch angles, respectively. Subsequently, implementing the K-means clustering algorithm on feature $f$ yields $K$ zones utilized for building the room-level HOZ graph $G\left(V,E\right)$, where $v_k$ and $\delta \left(v_k\right)$ represent the $k$-th region node and its feature, respectively. The zone feature corresponds to the cluster center, calculated as $\delta \left(v_k\right)=\frac{\mathrm{1}}{\left|\mathrm{z}\mathrm{o}\mathrm{n}{\mathrm{e}}_k\right|}\sum _{\left(f_i,l_i\right)\in \mathrm{z}\mathrm{o}\mathrm{n}{\mathrm{e}}_k}{f}_i$. Here, $\mathrm{z}\mathrm{o}\mathrm{n}{\mathrm{e}}_k$ denotes the $k$-th cluster after K-means clustering, and $\left|\mathrm{z}\mathrm{o}\mathrm{n}{\mathrm{e}}_k\right|$ represents the number of elements in that cluster. The edges in the room-level HOZ graph $G\left(V,E\right)$ are calculated using cosine similarity between the features of two zones, signifying the adjacency relationship between them.

The scene-level HOZ graph: Constructing the scene-level HOZ graph includes grouping, matching, and merging all room-level HOZ graphs, categorized by scene types. For a particular scene, we acquire a set of room-level HOZ graphs represented as $G=\{G_{\mathrm{1}}\left(V_{\mathrm{1}},E_{\mathrm{1}}\right),\dots ,G_n\left(V_n,E_n\right)\}$. The direct perfect matching of all HOZ nodes in the set incurs a significantly high time complexity. Hence, the procedure entails iteratively matching and merging two graphs successively until all graphs in the set are merged into the final graph, depicting the scene-level HOZ graph. The matching and merging method utilize the Kuhn-Munkres algorithm (KM algorithm)^[37-38], efficiently resolving the optimal maximum matching problem in bipartite graphs. If two equivalent subgraphs within a bipartite graph have a perfect match, it signifies the optimal maximum matching. Upon obtaining a perfect matching in the scene graph, it facilitates the averaging fusion of matched nodes and edges. The newly generated nodes represent the average of the matched nodes, and the new edges represent the average of the original edges between the matched nodes. The update process is illustrated in Fig. 7.

Fig. 7 The graph matching based on KM algorithm

The zone triplet model focuses on the spatial relationships between zones, claiming that object relationships without zone constraints can easily mislead the agent into an infinite loop. It clusters the object-level scene graph into a room-level scene graph based on the similarity of the object layout, and then constructs a scene-level scene graph from the room-level scene graph through graph matching and merging. With the help of the zone triplet model, the agent infers the scene based on the objects observed. In this way, the agent can quickly determine whether the environment is relevant to the navigation task. For example, suppose the navigation target is a TV, and the objects currently observed by the agent are a refrigerator and a microwave. The agent will judge that it is in the kitchen based on the scene graph and choose to leave instead of hanging around in it. In general, the zone triplet model endows the agent with zone-level spatial intelligence.

2.4 Image Triplet Model

The scene graphs introduced above are all constructed or extended based on the spatial relationships between objects. However, when establishing the mapping relationship between objects and the navigation environment, the feature information other than the object in the visual observation image is ignored, which limits its generalization ability to a certain extent. To address the challenge, Kwon et al^[39] introduced a Visual Graph Memory (VGM) module. This module directly utilized the observation images for constructing the scene graph $G\left(V,E\right)$. They employed the Prototypical Contrastive Learning (PCL) algorithm^[40] for feature representation learning of the graph. Initially, the observation images are clustered, and then the PCL algorithm utilizes an image encoder $F_{\mathrm{l}\mathrm{o}\mathrm{c}}$ to bring similar cluster images closer and different cluster images farther apart in encoding. The utilization of the PCL algorithm facilitates unsupervised learning of the feature representation $F_{\mathrm{l}\mathrm{o}\mathrm{c}}$ for the scene graph.

VGM module comprises two components: 1) Localization: The current position of the agent can be determined using the features of the current observation image and the node features in VGM. The computation is as follows: the node from the previous localization is denoted as $v_n\in {\mathbb{R}}^D$, and at time $t$, the number of nodes in VGM is $N_t$. A pre-trained image encoder $F_{\mathrm{l}\mathrm{o}\mathrm{c}}$ is used to encode the current observation image $o_t$ to derive the feature $e_t\in {\mathbb{R}}^D$, where $D$ is the feature dimension. Employing cosine similarity allows computing $S=\{s_i|s_i=\frac{v_i{e}_t}{|v_i||e_t|},i=\mathrm{1},\dots ,N_t\}$. When $s_i$ exceeds a set similarity threshold, the corresponding node $v_i$ is closer to the agent. Finally, the node with the highest similarity is chosen as the agent's current position; 2) Memory update: Assume the current localized position is node $v_i$. If $v_i$ matches the previously localized node $v_n$, no VGM update is needed. However, if they differ, a new edge is added between $v_i$ and $v_n$, with the feature of $v_i$ replaced by the feature $e_t$ encoded from the current observation image. If the current position cannot be localized, i.e., no $s_i$ exceeds the set similarity threshold, a new node $v_{N_{t+\mathrm{1}}}$ and its corresponding feature $e_t$ is added. Similarly, a new edge is created between $v_{N_{t+\mathrm{1}}}$ and $v_n$. Furthermore, the feature $e_t$ of each node $v_i$ incorporates time information $t$. Hence, the VGM obtained from these two modules, Localization and Memory Update, stores the agent's navigation experiences and temporal-spatial relationships. This scene graph provides the agent with image-level spatial intelligence, enabling the agent to directly use the feature information of the current observed image to determine its own position, plan the navigation path, and complete the navigation task.

2.5 Discussion

This section offers an overview of existing scene graph construction methods in scene graph-based object goal navigation classified into four categories: object triplet model, instance triplet model, zone triplet model, and image triplet model. 1) The object triplet model is the most fundamental and commonly used method in constructing scene graph, representing the co-occurrence relationships among objects within the same observed image. The object triplet model has evolved from offline construction based on existing datasets to online construction based on object detectors. Moreover, to improve the cognitive abilities of agents regarding spatial relationships, the relational features in scene graph have evolved from simple binary definitions (0 or 1) to trainable parameters. The object triplet model endows the agent with object-level spatial intelligence, which is suitable for relatively simple navigation scenarios. However, in real scenarios, agent needs to pinpoint specific instances. Simple categorization may result in failure to correctly locate a specific target. 2) The instance triplet model, focuses on real-world navigation tasks, constructing scene graph from an instance-level perspective, with nodes representing co-occurrence relationships among instance categories rather than object within the same image. These nodes incorporate attributes such as color and texture to help the agent recognize specific target instances, reflecting instance-level spatial intelligence. Despite its potential, the instance triplet model is an area that has seen limited exploration, and there is a clear need for further research and development to enhance its capabilities. 3) The zone triplet model introduces spatial constraints like rooms and scenes during the construction process. Furthermore, it employs scene graph matching and merging, resulting in relationships among nodes exhibiting inherent regional co-occurrences. This method enhances the inference capabilities of the scene graph compared to the object triplet model and the instance triplet model, showing powerful zone-level spatial intelligence. However, the construction process is computationally intensive, necessitating future research to streamline its complexity. In summary, the zone triplet model holds significant potential for broader development and application. 4) The image triplet model initiates directly from more comprehensive observation images, forming scene graph with images serving as nodes, thereby avoiding loss of image features. It endows the agent with image-level spatial intelligence and enhances its navigation generalization ability. Nonetheless, the image triplet model demands substantial computational resources, and with limited existing research, there is a pressing need for further advancements and studies to optimize its efficiency and effectiveness. Table 1 presents a detailed comparison of these four methods, including the construction methods, advantages and disadvantages, and the difficulty of the navigation tasks applied. Table 2 provides a detailed summary of the scene graph construction, categorizing the relevant works according to category and listing the salient contributions of each.

3 Usage of Scene Graph in Object Goal Navigation

The object goal navigation framework encompasses the perception, memory, and decision layers, wherein scene graph exhibit adaptability across diverse network layers. Through research exploration regarding the usage of scene graph in scene graph-based object goal navigation, we classify their usage into multimodal feature fusion, value function estimation, and sparse reward improvement. In this section, we will introduce the three usage methods respectively, explaining how the scene graph is integrated with the navigation framework. At the end of this section, the advantages and disadvantages of the three usage methods are briefly analyzed.

3.1 Multimodal Feature Fusion

In the framework of object goal navigation, the perception layer is responsible for processing the agent's visual observations. The quality of the observation features processed by the perception layer greatly influences the final decision-making. Specifically, if the perception layer only extracts a limited number of effective observation features, the agent will be unable to make effective navigation decisions and will struggle to complete the navigation task. Relevant researchers have adopted the multimodal feature fusion of scene graph and visual observations to solve the above problem.

Compared with visual observation (e.g., RGB images), scene graph contains rich semantic information and spatial relationships. For instance, the agent's current navigation target is a relatively small object (e.g., a mouse). Thus, it is difficult to complete the navigation task solely through first-person RGB images. However, the scene graph establishes relationships between different objects, which can guide the agent to first find the "desk", then the "laptop", and finally the "mouse". The spatial dependencies between objects contained in the scene graph are key to compensating for the insufficient navigation information provided by visual observations.

To leverage the spatial graph features of scene graph, graph neural networks such as Graph Convolutional Networks (GCNs)^[51], Graph Transformer Networks (GTNs)^[52], and Graph Attention Networks (GATs)^[53] are employed. These graph neural networks encode the graph into feature vectors and fuse them with feature vectors from other modalities, bolstering the agent's cognition and memory of the spatial structure of the environment^[54].

For instance, GCN extends convolutional neural networks to operate within graph structures, specifically focused on learning graph feature representations. Given the current observed image, Faster R-CNN is utilized to initialize each object node and its relationship. GCN propagates information based on node relationships, computing feature vectors for each node. Subsequently, these feature vectors are merged with image features and target word vector features via multimodal feature fusion. This fused representation is fed into the object goal navigation neural network^[41,55-56]. Fusing the spatial relationships of the scene graph with visual observations helps the perception layer extract richer navigation information. Based on the information, the agent can effectively transform visual observations into understanding, make correct navigation behaviors, and gradually form spatial intelligence. Refer to Fig. 8 for the network framework.

Fig. 8 An example of multimodal feature fusion with scene graph in the object goal navigation framework

3.2 Value Function Estimation

The object goal navigation framework is an end-to-end DRL neural network. Incorporating the scene graph within the perception layer allows the agent to autonomously train and learn the multimodal features. However, the long-distance impact on the reinforcement learning network towards the end of the model impedes rapid convergence and optimization of navigation strategies^[17]. In particular, during the training process of object goal navigation, the agent can only access local environmental information at each time step. Although recurrent neural networks encode global contextual information, they face problems of forgetting, posing a significant challenge in accurately estimating state values.

To address this challenge, Moghaddam et al^[57] proposed a Graph-based Value Estimation (GVE) module utilizing the Graph Transformer Network to capture the global contextual information of objects in the scene graph. The significance of global contextual information lies in that it contains the relationship between the objects detected and the target at each time step. With it, the agent can actively track objects related to the target. For instance, when searching for a specific small target like a "book", the agent might prioritize searching for larger objects such as a "bookshelf" or a "desk". This is because the Graph Transformer Network constantly adds new edges to the scene graph and adjust their weights at each time steps. A higher weight between the relevant object and the navigation target means higher attention. Applying the adjusted scene graph to the decision player, the related objects show higher estimated state values and are closer to the state value of the target based on the context information. This facilitates the agent in achieving more accurate state value estimations (refer to Fig. 9).

Fig. 9 An example of value function estimation with scene graph in the object goal navigation framework

In general, applying the scene graph to value function estimation helps the agent make positive state estimates related to the navigation target, showing keen insight, which is an intuitive manifestation of the combination of spatial intelligence and reinforcement learning.

3.3 Sparse Reward Improvement

In the reinforcement learning framework of object goal navigation, the agent accumulates rewards through continuous training, striving to maximize these rewards to learn the optimal navigation strategy. In the state space $\mathcal{S}$ of the environment, the reward space $\mathrm{ℛ}$ remains constant, offering positive rewards solely upon successful arrival at the target, while all other navigation actions incur negative rewards. However, this reward configuration leads to the challenge of sparse rewards. Consequently, this sparsity issue renders the agent insensitive to positions offering positive rewards, fostering a "risk-averse" mindset wherein the agent might prematurely terminate navigation tasks to mitigate negative reward penalties.

To encourage the agent to overcome "risk-averse" thinking and actively explore the environment, Qiu et al^[43] introduced the concept of "parent objects" into the scene graph. These "parent objects" are readily observable and share semantic or spatial relationships with the target. For instance, "countertop" serves as a "parent object" in kitchen and bathroom environments, while "shelf" functions as a "parent object" in bedroom and bathroom environments. Based on this concept, a set of "parent objects" denoted as $P=\{p_{\mathrm{1}},\dots ,p_M\}$ is derived to modify the original reward space. It aims to reinforce the agent's memory of these readily observable "parent objects" associated with the target and to comprehend spatial or semantic relationships between them. The rules for reward shaping are as follows: when the agent observes a "parent object" denoted as $p\in P$, it receives a partial reward denoted as $R_p=R_t{P}_r\left(t|p\right)k$, where $R_t$ is the reward for reaching the target $t$, $k\in \left(\mathrm{0,1}\right)$ represents a scaling factor, and $P_r\left(t|p\right)$ is extracted from a partial reward matrix $M$, where each row represents the relative distance between "parent objects" and the target. If multiple "parent objects" are visible in the agent's observation, the "parent object" yielding the maximum $R_p$ is chosen. Furthermore, the agent is programmed not to receive this reward upon repeated observations of the same "parent object", encouraging exploration of different "parent objects". If neither the "parent objects" nor the target are visible, the agent incurs a negative reward as a penalty. The new reward space $\mathrm{ℛ}$ is defined as,

$\mathrm{ℛ}=\{\begin{array}{c}\begin{array}{l}{R}_p,\mathrm{i}\mathrm{f}p\mathrm{i}\mathrm{s}\mathrm{v}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{e}\\ R_t,\mathrm{i}\mathrm{f}t\mathrm{i}\mathrm{s}\mathrm{v}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\\ R_t+R_p,\mathrm{i}\mathrm{f}\mathrm{b}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{v}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\\ -\mathrm{0.01},\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}\end{array}$(6)

When the "Done" action is triggered, it signifies that the termination condition has been met. Meanwhile, if $t$ is visible, the agent receives a goal reward consisting of $R_t$ and $R_p$, allowing it to associate parent objects with the target and current state. As the navigation framework is a kind of end-to-end network, this shaped reward propagates back to the GCN layers, fine-tuning them to accurately learn the "parent-target" hierarchical relationships from the input scene graph. Through continuous learning of the semantic information and spatial relationships within the scene graph, the reward function designed based on the "parent-target" relationship becomes increasingly precise, which in turn improves the problem of reward sparsity.

In contrast to the research on manually designing reward functions, Singh et al^[49] proposed the SGC learning for training the agent. SGC employs non-parametric scene graph as a training-only signal in a contrastive learning framework. The core concept of contrastive learning is to reduce the distance between positive sample pairs in the latent space while increasing the distance between negative sample pairs. Concretely speaking, in object goal navigation, the scene graphs and visual observations are sample pairs. The scene graph is collected from parallel agent rollout. The nodes of the scene graph include the agent, the room, and the object, and the edges represent different spatial relationships, such as seen and contained. The agent trained with SGC is able to pick out the most relevant graph in a large number of scene graphs based on the visual observation. The scene graph most relevant to the current visual observation can provide the agent with the most accurate semantic information and spatial relationships, thereby helping the agent make the correct navigation decisions. In this way, at each time step, the agent can obtain the most accurate scene graph, which accelerates the training process.

Singh et al^[49] evaluated SGC, by training agent on three embodied tasks, object goal navigation, multi-object navigation^[58] and arm point navigation^[59], and showed performance improvements across all of them. In general, using scene graph to improve the reward sparsity problem is essentially to enhance the spatial cognition ability of the agent through its rich spatial relationships and semantic information.

3.4 Discussion

This section provides an overview of the existing scene graph usage methods in scene graph-based object goal navigation, categorized into three methods: multimodal feature fusion, value function estimation, and sparse reward improvement.

1) Multimodal feature fusion, the most common usage, involves integrating the scene graph into the perception layer of the object goal navigation network framework. It optimizes graph feature extraction and fusion to enhance the agent's spatial intelligence. However, the approach faces certain challenges. GTN performs the best in extracting graphical features, followed by GAT and GCN. Along with the improved effectiveness, the complexity of the network model increases significantly, which in turn leads to more severe requirements for computing resources. This requires researchers to balance the performance of the network model with the computational complexity, by optimizing the model structure or proposing new graph feature extraction methods.

2) Value function estimation, originating from the decision-making layer of the object goal navigation network framework, optimizes the navigation strategy through refining the value function estimation. The goal is to incorporate relationships between objects and the target into the value function. Using scene graph for Value Function Estimation in navigation tasks, while providing valuable insights into the relationships between objects and the target, also comes with several limitations. The accuracy of value function estimate is affected to some extent by the accuracy and completeness of the scene graph. Inaccurate object relationships may lead to inaccurate value function estimates. Meanwhile, scene graph might include a lot of irrelevant information that can interfere with the learning process and affect decision making. To improve the accuracy of scene graph, researchers can apply more accurate target detectors. For task-irrelevant information in scene graph, researchers can use methods such as attention mechanisms to highlight task-related observation state features.

3) Sparse reward improvement, stemming from the Markov Decision Process described in object goal navigation, focus on the challenge of target insensitivity due to rewards sparsity in reinforcement learning. Qiu and Pal^[43] explored spatial relationships between the target and other objects within the scene graph, increasing the reward for objects associated with the target. Instead of designing the reward function directly, Singh et al^[49] used the scene graph as an auxiliary signal to compute the loss and train the agent by means of contrastive learning. Using scene graph to address the issue of sparse rewards in reinforcement learning is a promising approach, but it also has potential drawbacks. The design of scene graph and the tuning of reward functions may be highly dependent on specific tasks, limiting the method's versatility across different tasks. Utilizing contrastive learning as a training method may require a large number of negative samples, which could make the training process cumbersome and inefficient. For the sparse rewards improvement, researchers can refer to the weight mechanism used by scene graph to express spatial relationships. When the agent moves towards an area with a higher weight, a higher reward is given, and vice versa, which is beneficial to enhance the agent's spatial intelligence. Table 3 summarizes the strengths and weaknesses of the three methods.

4 Experimental Validation of Scene Graph in Object Goal Navigation

4.1 Experimental Setup

Object goal navigation is a critical task for indoor robots. It aims to direct an agent navigating to a specific target object within unseen environments. Researchers in the field have proposed several comprehensive simulators for this task, including Gibson Env^[60], Habitat Sim^[61], and AI2-THOR^[62]. Based on these simulators, the researchers constructed a variety of datasets. The Gibson Env simulator supports the Gibson dataset. The Habitat Sim is compatible with the Matterport3D^[63], Gibson and Habitat Matterport 3D dataset^[64]. The AI2-THOR simulator is paired with the iTHOR, RoboTHOR^[65] and ProcTHOR dataset^[66]. Each dataset offers unique challenges and insights, contributing to the advancement of object goal navigation.

Focusing on scene graph-based object goal navigation, most researchers chose AI2-THOR as the simulator, using the iTHOR dataset it provided as a benchmark for training and testing. The dataset is fully open source. AI2-THOR, constructed using Unity3D, provides a collection of over 120 rooms, including kitchens, living rooms, bedrooms, and bathrooms (30 rooms per room type), and hosts a catalog of more than 2 000 objects (refer to Fig. 10). For evaluating navigation performance across various scenes for training, validation, and testing, the initial 20 rooms of each room type constitute the training set, followed by 5 rooms for validation, and concluding with 5 rooms for testing.

Fig. 10 An example of AI2-THOR simulation environment

The navigation task is set as follows: in each episode, the agent is randomly initialized in position and orientation in an unknown environment, and then receives a target (e.g., a television) as a Glove embedding^[67]. The agent utilizes observations from a monocular RGB image to explore, perceive, and memorize the navigation environment. It selects navigation actions from the action space $\mathcal{A}=\{MoveAhead,RotateLeft,Rotate$

$Right,LookUp,LookDown,Done\}$. More specifically, the $MoveAhead$ action advances the agent by a step length of 0.25 m, $RotateLeft$ and $RotateRight$ actions turn the agent by 45 degrees, $LookUp$ and $LookDown$ actions adjust the view angle by 30 degrees, and $Done$ denotes the completion action. A successful navigation episode is characterized by the following conditions: 1) The agent issues the Done action within the maximum allowed time steps (set to 100 steps for kitchens, bedrooms, and bathrooms, and 200 steps for living rooms due to varying room sizes). 2) The target is within the agent's field of view. 3) The distance between the target and the agent is less than 1.5 m. Furthermore, the reward space $\mathrm{ℛ}$ is defined as follows: a negative reward of -0.01 is assigned for each step taken, a negative reward of -0.10 is given in case of collision, and a positive reward of +10.00 is assigned for a successfully completed navigation task. To evaluate and validate the enhancement in the generalization performance of navigation due to the scene graph, the targets are set as follows (refer to Table 4).

4.2 Metrics

Table 5 summarizes the simulators, datasets and metrics used in the related works. According to Table 5, the evaluation metrics consist of three primary measures^[22]: 1) Success Rate (SR) denotes the ratio of successful occurrences where the agent successfully locates the target. It is defined as $\mathrm{S}\mathrm{R}=\frac{\mathrm{1}}{N}{\displaystyle \sum _{i=\mathrm{1}}^N}{S}_i$, where $N$ represents the number of navigation episodes, and $S_i$ represents the success or failure of navigation episode $i$ ($S_i=\mathrm{1}$ denotes success, $S_i=\mathrm{0}$ denotes failure); 2) Success Weighted by Path Length (SPL) signifies the efficiency of the agent in locating the target based on the path length taken. It is defined as $\mathrm{S}\mathrm{P}\mathrm{L}=\frac{\mathrm{1}}{N}{\displaystyle \sum _{i=\mathrm{1}}^N}{S}_i\frac{L_i}{\mathrm{m}\mathrm{a}\mathrm{x}\left(P_i,L_i\right)}$, where $P_i$ denotes the path length of navigation episode $i$, and $L_i$ represents the optimal path length for navigation episode $i$. 3) Success Weighted by Action Efficiency (SAE) signifies the efficiency of all actions. It is defined as $\mathrm{S}\mathrm{A}\mathrm{E}=\frac{\mathrm{1}}{N}{\displaystyle \sum _{i=\mathrm{1}}^N}\mathrm{S}\mathrm{u}\mathrm{c}\mathrm{i}\left(\frac{{\displaystyle \sum _{t=\mathrm{0}}^T}I\left(a_t^i\in A_{\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}}\right)}{{\displaystyle \sum _{t=\mathrm{0}}^T}I\left(a_t^i\in A_{\mathrm{a}\mathrm{l}\mathrm{l}}\right)}\right)$, where $N$ represents the total number of episodes, $I\left(\cdot \right)$ is the indicator function that returns 1 if the condition inside is true, and 0 otherwise, $a_t^i$ is the action taken by the agent at time step $t$ in episode $i$, $A_{\mathrm{a}\mathrm{l}\mathrm{l}}$ is the set of all possible action categories and $A_{\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}}$ is the subset of actions that can change the agent's location.

4.3 Comparison Models

We select classic models with or without scene graph from recent years, and train and test them in AI2-THOR. The selected models are as follows:

1) Random: The agent randomly samples actions from the action space.

2) TD-A3C: Zhu et al^[2] proposed training the agent using the A3C reinforcement learning algorithm, which is a fundamental model.

3) Bayes: Wu et al^[68] introduced the variational Bayesian inference to assist the agent in envisioning the next time step's observation image for action prediction.

4) SAVN: Wortsman et al^[69] proposed using Model-Agnostic Meta-Learning (MAML) to enhance the interaction capabilities between the agent and environment.

5) SpAtt: Mayo et al^[70] introduced spatial attention mechanisms to guide the agent's focus toward areas relevant to the target.

The above are object goal navigation models without scene graph. Below, we list the models that utilized scene graph.

6) SP (Scene Priors): Yang et al^[25] introduced the object triplet model first for multimodal feature fusion, enhancing the agent's spatial memory of the environment.

7) GVE: Moghaddam et al^[57] introduced the GVE module, assisting the agent in more accurately estimating state values.

8) VGM: Kwon et al^[39] introduced the image triplet model, creating a VGM module for online training and reinforcement of memory.

9) ORG: Du et al^[27] proposes the Object Relation Graph (ORG) mentioned above, trial-driven Imitation Learning (IL), and a memory-augmented Tentative Policy Network (TPN). The TPN offers explicit action instructions during failure steps to update the navigation network.

10) HOZ: Zhang et al^[34] proposed the zone triplet model, establishing a hierarchical object-zone graph, allowing the agent to locate the region and then the target, which aids in navigation reasoning.

11) DOA: Dang et al^[31] introduced an unbiased DOA graph. The model learns DOA graph online as scene graph, providing a unique and adaptable representation of object relationships.

12) ABM: Luo et al^[48] presented a model equipped with an ARG for acquiring the structure of new scenes and retaining a graph memory to facilitate the selection of effective actions in Active Behavior Modeling (ABM).

13) VTNet: Du et al^[71] introduced a visual transformer network, known as VTNet, designed to enhance visual representations by encoding the interactions between object instances and their spatial positions. In particular, VTNet uses DETR^[72] (an object detector) rather than Faster-RCNN to extract target features to construct the scene graph.

14) GTV+MTL: Zhou et al^[73] constructed a Commonsense Graph (CG) by leveraging ground truth data from AI2-THOR to align the scene graph constructed online, The GTN is used to extract global context features of the KG as an encoder, while the Viterbi algorithm^[74] serves as a decoder to infer the probability of the next navigation action. Eventually, combining the action inference probability with the backbone network's predicted action probability serves as a supervisory signal for Meta-Transfer Learning (MTL)^[75], aiming to attain the optimal strategy.

See Table 6 for a comparison of all models.

4.4 Results

Under the AI2-THOR environment, each model was trained for 10 million episodes. The test results on the testing set are shown in Table 7, where "ALL" denotes all navigation path lengths, and "L$\ge$5" signifies optimal navigation paths of 5 or more time steps. Since only a few works use SAE as a metric, to be fair, we choose SR and SPL as metrics here.

Based on the experimental results in Table 7, we make the following analysis:

1) Effect of meta-learning. Compared with Random, TD-A3C, and Bayes, models such as SAVN and SpAtt have demonstrated better adaptability to unfamiliar environments in their testing processes by employing meta-learning without scene graph. Among them, the SpAtt model has achieved significant improvements, with SR and SPL reaching 43.2% and 16.9%, respectively. Consequently, scene graph-based models like GVE, ABM, and GTV+MTL also utilize meta-learning or meta-transfer learning to enhance their navigation generalization capabilities when training agents.

2) Effect of scene graph. SP, a basic scene knowledge-based model using GCN to extract graph features, outperforms models lacking scene graph like Random, TD-A3C, and Bayes. It endows the agent with the most basic object-level spatial intelligence. However, it simply concatenates features from scene graph, lacking sufficient extraction of spatial context features, exhibiting lower effectiveness in comparison to SAVN. In contrast to SP, GVE module utilizes the Graph Transformer Network to capture global contextual information about objects within the environment, facilitating the agent to achieve more accurate state value estimation. Thus, GVE achieves the same level of effectiveness as the SpAtt model. Unlike other models focus on the relationships between objects, VGM constructs scene graph directly from the observation images. It utilizes the PCL method to learn feature representations for the graph. Nodes that consist of raw image features preserve more valuable information, leading to better navigation performance compared to SP and GVE. It shows that image-based scene graph helps the agent show better spatial intelligence than primary object-level scene graph.

The scene graph of both SP and GVE are constructed based on Visual Genome dataset and cannot be updated in real time, limiting the generalization ability of the agent. Therefore, models such as ORG, HOZ and DOA opt for using object detectors to construct scene graph based on the navigation environment. ORG pioneered the use of Faster-RCNN to detect object in images for constructing scene graph, increasing SR to 67.3% and SPL to 39.5%. From an experimental perspective, it is proved that the scene graph built based on the object detector endows the agent with more powerful object-level spatial intelligence. Notably, HOZ also constructs scene graph based on Faster-RCNN with remarkable results, suggesting that the constraints imposed by the room-level and scene-level in the zone triplet model prove more advantageous in extracting spatial and semantic relationships compared to models like the object triplet model. Both VTNet and ABM use DETR to recognize target features and further pre-train them with a transformer to obtain more precise spatial relationships. As a result, the results of both models are superior to ORG and HOZ. It suggests that the scene graph constructed based on the navigation environment provides the agent with more accurate spatial relationships between objects.

GTV+MTL notably enhances navigation performance due to integrating scene graph with diverse modules or algorithms. It stands out as an innovative approach that harnesses the power of scene graph, representing the Graph Transformer Viterbi network coupled with Meta-Transfer Learning. The model supports efficient learning signals and the generation of new graph edges in previously unseen scenes, enabling agent to learn policies faster and exhibit enhanced generalization ability. Overall, with the continuous improvement of scene graph construction and usage methods, the agent has obtained rich spatial relationships and semantic information. Based on this, the agent has learned how to transform simple visual observations into rich insights and understanding, make correct navigation actions, and thus enhance the generalization ability in unfamiliar environments.

5 Conclusion

Following an investigation and analysis of scene graph-based object goal navigation, alongside formal description, and computational framework, this study consolidates the role of scene graph. This encompasses its construction, usage, and experimental validation. Construction methods encompass object triplet model, instance triplet model, zone triplet model, and image triplet model. Their usage involves multimodal feature fusion, value function estimation, and sparse reward improvement. Through experimental comparison, this study analyzes scene graph-based methods against those not utilizing scene graph, affirming the performance enhancement achieved with scene graph endowing agent with spatial intelligence. This research aims to underscore the significance of scene graph in navigation while fortifying its construction and utilization. Here, we list directions for future research.

1) Construction methodology: The current mainstream construction methods are based on the object detectors Faster-RCNN or DETR. Compared to the former, DETR, although able to extract better spatial relations, requires pre-training using transformers, resulting in much higher computational costs. Therefore, balancing the detection results with the computation cost is a topic that needs to be emphasized in constructing scene graph. Introducing novel node types, establishing new relationships, and applying innovative spatial or semantic constraints could improve navigation performance and generalize it across diverse navigation tasks.

2) Introducing novel memory networks: In object goal navigation, the use of LSTM as memory networks to store the spatial relationships and semantic information provided by the scene graph is worth further exploration. LSTM has limitations, such as difficulty in parallel processing and performance issues with long sequence data. This results in the spatial intelligence provided by the scene graph not being fully exploited. The Segment Anything Model (SAM)^[76] is an advanced model capable of possessing zero-shot generalization capabilities, allowing it to identify unfamiliar objects and images without additional training. The capabilities of SAM hold potential value in object goal navigation. The introduction of SAM, especially when combined with the advantages of the transformer architecture, may offer a new solution.

3) Combining scene graph with Large Language Models (LLMs): Expanding the usage of scene graph-based object goal navigation models from indoor to outdoor scenarios demands the development of a universal model, posing challenges in data volume and intricate navigation tasks. Using the LLMs to directly construct the scene graph for outdoor scenarios is a viable approach to solving this problem^[77]. In addition, utilizing the powerful reasoning capabilities of LLMs is conducive to fully exploring the semantic and spatial relationships in scene graph, endowing the agent with more powerful spatial intelligence, which is one of the most promising research directions in the future.

4) Bridging the sim-to-real gap based on scene graph: There is a huge sim-to-real gap in DRL-based object goal navigation. Gervet et al^[78] proposed that a principal factor contributing to this phenomenon was the divergence in RGB image quality between virtual and actual environments. Consequently, the degree of realism inherent to the virtual environment is of paramount importance in enabling a seamless transition from the virtual scene to the real world. The Isaac simulation platform^[79] provides a virtual environment that is nearly realistic, which markedly enhances the quality of observed images. It is postulated that the scene graph constructed on this basis will indubitably mitigate the sim-to-real gap in object goal navigation. This work focuses on helping object goal navigation move from virtual to reality and truly realize spatial intelligence based on real life, which is of great significance to the development of the field of intelligent navigation.

5) Quality assessment of scene graph: Evaluating scene graph comprehensively across various domains like knowledge modeling, storage, extraction, fusion, computation, usage, and assessment within the context of object goal navigation could enrich the understanding of their quality.

References

All Tables

All Figures

	Fig. 1 Interaction between the agent and environment
In the text

	Fig. 2 The framework of object goal navigation based on DRL
In the text

	Fig. 3 An example of scene graph based on Visual Genome dataset
In the text

	Fig. 4 An example of scene graph based on Faster R-CNN
In the text

	Fig. 5 An example of instance nodes
In the text

	Fig. 6 An example of room-level and scene-level HOZ graph
In the text

	Fig. 7 The graph matching based on KM algorithm
In the text

	Fig. 8 An example of multimodal feature fusion with scene graph in the object goal navigation framework
In the text

	Fig. 9 An example of value function estimation with scene graph in the object goal navigation framework
In the text

	Fig. 10 An example of AI2-THOR simulation environment
In the text