Abstract
Embodied AI agents that search for objects in large environments such as households often need to make efficient decisions by predicting object locations based on partial information. We pose this as a new type of link prediction problem: link prediction on partially observable dynamic graphs. Our graph is a representation of a scene in which rooms and objects are nodes, and their relationships are encoded in the edges; only parts of the changing graph are known to the agent at each timestep. This partial observability poses a challenge to existing link prediction approaches, which we address. We propose a novel state representation — Scene Graph Memory (SGM) — which captures the agent's accumulated set of observations, as well as a neural net architecture called a Node Edge Predictor (NEP) that extracts information from the SGM to search efficiently. We evaluate our method in the Dynamic House Simulator, a new benchmark that creates diverse dynamic graphs following the semantic patterns typically seen at homes, and show that NEP can be trained to predict the locations of objects in a variety of environments with diverse object movement dynamics, outperforming baselines both in terms of new scene adaptability and overall accuracy.
Introduction
Finding objects in a household is a fundamental task for embodied AI, yet most research assumes a static world where furniture and items never move. In reality, homes are dynamic environments where people constantly rearrange their surroundings. For a robot with only partial observability—limited to what its sensors can see at any given moment—maintaining an accurate internal model of these changes is a significant challenge.
This paper introduces a framework that treats object search as a link prediction problem on partially observable dynamic graphs. By representing the environment as a graph of rooms and objects, the task becomes predicting which edges (relationships like Mug onTop Table) are most likely to exist currently.
Methodology: Scene Graph Memory and Node Edge Predictor
To address the challenges of dynamic environments and partial observability, we propose two core components:
- Scene Graph Memory (SGM): A structured representation that aggregates past observations. SGM tracks "temporal features," such as the time elapsed since an edge was last observed and the historical frequency of object movements. It also incorporates "hypothetical edges" based on common-sense semantic priors (e.g., a "mug" is likely in a "kitchen").
- Node Edge Predictor (NEP): A neural architecture designed to reason over the SGM. It utilizes HEAT (Heterogeneous Edge-enhanced Graph Attentional layers) to propagate information and Transformers to compare potential object locations. Semantic understanding is grounded via word embeddings, allowing the model to generalize behaviors across similar object categories.
Evaluation and Results
We evaluated our approach using the Dynamic House Simulator, a new benchmark featuring realistic object movement patterns, and iGridson, a 2D grid-world for embodied agents.
The proposed NEP-HEAT model significantly outperformed heuristic and Bayesian baselines. In dynamic environments, NEP achieved approximately 35% accuracy in predicting exact object locations, doubling the performance of models relying solely on prior knowledge (~16%). Furthermore, in the "Find Object" task, the NEP agent demonstrated superior search efficiency, finding targets in significantly fewer actions than non-neural baselines.
A key finding is the model's ability to "learn" the specific dynamics of a new environment over time. As shown in the accuracy-over-time plots, NEP's performance improves as it accumulates observations, eventually approaching the performance of an "Oracle" with full knowledge of the environment.
Discussion and Future Work
Our results highlight the power of graph-based memory for high-level reasoning. By treating the house as a graph rather than a 3D voxel map, agents can leverage "common sense" to search efficiently even in unfamiliar areas. Temporal awareness proved crucial; knowing when an object was last seen allows the agent to appropriately discount stale information in a changing world.
Future work will focus on bridging the sim-to-real gap by deploying these models in 3D physics-based simulations and physical robotic platforms. Additionally, integrating SGM with end-to-end Reinforcement Learning for navigation remains a promising but challenging direction.
Summary updated