PaperlayerView exact revision on arXiv

Source-linked AI summary

Yggdrasil: a Layer-First 3D Scene Graph for Real-Time Querying

Arshia Akhavan, Ermanno Bartoli, Afnan Algharbi, Alireza Hoseinpur, Iolanda Leite, Bryan Donyanavard

arXiv:2609.38640v1cs.RO

TL;DR

3D scene graphs have received limited attention as objects to optimize for consumption, despite pipelines needing to query them within real-time budgets. Yggdrasil is a layer-first graph with a typed query interface, and its queries are up to 121× faster than the DSG baseline on Q1a.

  • Problem

    Scene-graph consumption performance is a target of the paper: the authors measure how much computation a graph designed for consumption removes from pipelines not built around one.

    Source: §VI · p. 6

  • Method

    Yggdrasil uses generic nodes, edges, and layers arranged as a DAG, with a typed query interface for semantic and spatial queries without intermediate conversion.

    Source: §I · p. 2, §VII · p. 8

  • Results

    121× faster than DSG on Q1a on the Jetson; the fully featured targets answer Q1a in about 2 µs on both machines.

    Source: E. Results · p. 5

  • Takeaways & Limitations

    On the Jetson, 1,000 visibility probes per cycle take 6.7 ms on mint versus 350 ms on DSG, which exhausts the keyframe budget before perception work.

    Source: F. Discussion · p. 6

Abstract

from arXiv · show

Robotic agents use 3D scene graphs (3DSG) to perform tasks ranging from scene understanding to scene interaction. Although an extensive body of work addresses scene graph generation, little attention has been paid to optimizing the graph for consumption, which leaves state-of-the-art perception pipelines to work around their own scene graph and to pay a latency cost that does not fit the real-time budget a perception loop runs on. We present Yggdrasil, the first 3D scene graph designed to be efficient for both generation and consumption: a layer-first hierarchical graph built from generic nodes, edges, and layers, which expresses the representations existing pipelines already produce, indoor or outdoor, flat or hierarchical, while natively answering the positional and semantic queries downstream tasks issue. Against a published DSG baseline, Yggdrasil answers queries up to $121\times$ faster, and every query we measure falls between 2 and 127 microseconds, three to five orders of magnitude inside the 200 microsecond keyframe budget a 3DSG consumer lives in, on both a workstation and embedded class device. We integrate Yggdrasil into three published pipelines spanning human trajectory prediction, object-goal navigation, and human-aware motion planning, where it removes up to 99% of the time each spends on its scene graph. The implementation, benchmark harness, and all three integrations are available online.

I. INTRODUCTION

Robotic agents need scene models that combine geometry and semantics and can be queried quickly enough to support action. YGGDRASIL addresses the underdesigned consumption side with a scene graph that supports both pipeline construction and native downstream queries.

I. INTRODUCTION

  • Robotic agents must build and interrogate models of their surroundings quickly enough to act, combining SLAM geometry with associated semantic content.These models are commonly organized as 3D scene graphs.Source: §I · p. 1
  • The graph serves downstream tasks such as planning and navigation by answering queries about nearby objects, observable sub-scenes, labels, and paths.The query contract is how scene graphs provide actionable information to consuming applications.Source: §I · p. 1
  • Much prior work emphasizes graph construction, while downstream systems often serialize graphs or copy them into general-purpose libraries to run queries.These workarounds can be slow, face context-window limits, or require repeated conversion when a scene updates.Source: §I · p. 1
  • YGGDRASIL is designed for both generation and consumption, using generic nodes, edges, and layers to represent existing pipelines and answer semantic and spatial queries in place.It supports indoor or outdoor, flat or hierarchical representations without intermediate conversion.Source: §I · pp. 1–2
  • YGGDRASIL combines a DAG layer hierarchy with pattern matching, nearest-neighbor, field-of-view, and traversal queries backed by maintained spatial indexes.The paper also integrates it into published tools for trajectory prediction, object-goal navigation, and human-aware motion planning.Source: §I · p. 2

II. RELATED WORK AND BACKGROUND

3D scene graphs vary in whether they are flat or hierarchical and in how they support construction and consumption. YGGDRASIL’s layer-first design uses a DAG to represent these structures while enabling room-scoped queries and flexible graph content.

A. 3D Scene Graphs: Definitions, Hierarchy, and Layering

  • A 3D scene graph is the storage backbone of a perception pipeline, commonly modeled as nodes and edges grounded in maps, with features and optional hierarchical labels.Without the labeling function, the graph is flat.Source: A. 3D Scene Graphs: Definitions,… · p. 2
  • Flat 3D scene graphs emphasize richer node attributes, while hierarchical graphs add abstraction layers that can narrow searches along ancestry.The literature includes dynamic-scene, SLAM-coupled, and outdoor-oriented variants.Source: A. 3D Scene Graphs: Definitions,… · p. 2

B. Scene Graph Construction and Consumption

  • Construction builds a graph from sensor data, whereas consumption uses an existing graph for tasks such as question answering, planning, navigation, and prediction.The cited work covers learned and open-vocabulary construction as well as SLAM-coupled layered graphs and downstream applications.Source: B. Scene Graph Construction and… · p. 2

III. CORE DESIGN

  • YGGDRASIL uses generic nodes, edges, and layers so one graph can express existing indoor or outdoor, flat or hierarchical representations while scoping queries to a room.Layers form a DAG of largely isolated graphs, each representing one scene abstraction and information type.Source: §III · p. 2
  • Unlike a stack, YGGDRASIL’s layer DAG lets one layer parent multiple children, representing incomparable abstractions such as road lanes and object instances under a shared segment layer.This permits structures that a stack cannot express without imposing a false parent-child ordering.Source: §III · p. 2
  • Room-specific layers bound searches to local scene content and allow per-layer indexing, while sub-scene graphs retain even empty layers for merging and conflict resolution.Nodes and edges accept arbitrary information; optional bounding boxes speed spatial estimates but incur update costs when maintained.Source: §III · p. 3

IV. QUERY APIS

YGGDRASIL provides semantic and spatial queries for the varied scenarios encountered by downstream applications.

IV. QUERY APIS

  • YGGDRASIL offers a rich set of semantic and spatial queries suited to downstream applications’ varied scenarios.Source: §IV · p. 3

A. Pattern Matching

The query API supports feature-based graph matching and spatial operations that can be scoped to layers or subtrees. It also exposes general graph traversal and subgraph retrieval.

A. Pattern Matching

  • Feature-based queries retrieve nodes by feature values or keys and filter edges by source, destination, or relation, over either the whole graph or one layer.Source: A. Pattern Matching · p. 3

B. Spatial and Traversal Queries

  • Nearest-neighbor queries return nearby nodes, optionally limited by radius or a root node’s subtree; layer- and node-level indexes can accelerate these searches.Indexes trade memory and update time for query runtime and are maintained as the graph changes.Source: B. Spatial and Traversal Queries · p. 3
  • Field-of-view queries check nodes in a root node’s subtree, while standard traversal algorithms and rooted subgraph retrieval are also supported.Subtree scoping can confine field-of-view results to the room an agent occupies.Source: B. Spatial and Traversal Queries · p. 3

V. EVALUATION

The evaluation ports a published DSG scene graph into YGGDRASIL and measures downstream query costs through an ablation ladder. The tests use a single-story office graph and progressively alter its structure and indexing.

V. EVALUATION

  • Each evaluation target adds one YGGDRASIL feature to its predecessor, separating implementation, layer-first design, and live-index effects from their memory costs.The ladder begins with the published DSG baseline and includes a naive port, a redesigned graph, indexed variants, and a point-level physical layer.Source: §V · p. 3, B. Targets · p. 4

A. Dataset

  • The uHumans2 test graph is a single-story office with 3,532 nodes and 11,012 edges across four DSG layers, plus a 354,885-vertex mesh array.Of the mesh vertices, 88.3% belong to no object, and 126 of 215 objects have claimed vertices outside their stored bounding boxes.Source: A. Dataset · pp. 3–4

B. Targets

  • The chocolate port isolates a room-scoped layer redesign, mint adds live spatial indexes, and saffron gives each mesh point its own node.Chocolate allocates four layers per room; mint isolates the indexing effect, while saffron isolates the cost of a finer-grained physical representation.Source: B. Targets · p. 4

C. Query Workload

The workload compares spatial and semantic queries across the targets, using identical answers to make latency comparisons meaningful. Measurements average five runs on a workstation and an embedded-class device.

C. Query Workload

  • All YGGDRASIL query flavors return the same answers as DSG on 576 spatial queries per configuration, so the latency comparisons use identical results.DSG and vanilla use brute-force scans; chocolate, mint, and saffron use room-scoped YGGDRASIL APIs, with indexes serving mint and saffron.Source: C. Query Workload · p. 4
  • The workload tests nearest-object distance, radius-based object retrieval, field-of-view visibility, and retrieval by frequent, median, rare, or absent labels.Spatial queries use 64 reference points in each of nine rooms; radii range from 0.25 to 4 m, and field-of-view half-angles range from 30° to 70°.Source: C. Query Workload · pp. 4–5

D. Experimental Setup

  • Each query is run five times on a 32-core Threadripper workstation and a six-core Jetson Orin Nano Super, with average latency reported.The Jetson has 7.4 GiB of unified memory and runs in uncapped MAXN_SUPER mode.Source: D. Experimental Setup · p. 5

E. Results

YGGDRASIL’s query-latency improvements appear on both tested machines, with the largest end-to-end gains for nearest-object and visibility queries. The discussion also reports query-budget implications and memory, update, and representation trade-offs.

E. Results

  • About 2 µs on both machines: the fully featured targets answer nearest-object queries 50× faster than DSG on Threadripper and 121× faster on Jetson, and cut visibility latency by 52×.The latency patterns are essentially the same across the workstation and Jetson, indicating the improvements persist on the constrained device.Source: E. Results · p. 5, Figure 3 · p. 6
  • For radius queries, indexing gains fall from 23–31× over chocolate at 0.25 m to 1.1–1.7× at 4 m; room isolation buys nothing when every point in scope must be touched.At larger radii, the query ball covers the whole room, and the added layers leave chocolate marginally slower than vanilla.Source: E. Results · p. 5
  • All four YGGDRASIL targets are about twice as fast as DSG for label queries, with similar latency across label-frequency classes.Saffron has 96× more nodes yet remains in the same range because its added geometric nodes carry no labels and those layers can be skipped.Source: E. Results · p. 5

F. Discussion

  • 33.7 MB: chocolate remains below the DSG baseline, while mint’s indexes add 37.2 MB over chocolate and saffron reaches 144.6 MB, 3.6× the baseline.Vanilla is 36% smaller than DSG.Source: F. Discussion · p. 5
  • 2.06–126.3 µs: every measured query on chocolate, mint, and saffron falls two to five orders of magnitude below the stated SLAM-frame and 3DSG keyframe budgets.A visibility consumer probing 1,000 candidate poses per cycle spends 6.7 ms on mint but 350 ms on DSG on Jetson, exhausting the keyframe budget before perception work,.Source: F. Discussion · pp. 5–6
  • Chocolate favors low memory use, while mint and saffron trade more memory for speed; saffron updates take 129 µs versus 6.91 µs on chocolate and 12.7 µs on mint.Saffron’s point-level physical layer supports modifying a single point without rewriting an array, while mint lacks that precision for graph update and merge.Source: F. Discussion · p. 6

VI. CASE STUDIES

The case studies test YGGDRASIL across downstream-only use, graph construction and querying within one control loop, and augmentation of an existing graph. In LP2, it preserves the original outputs while substantially reducing scene-graph time through faster queries and eliminating rebuilt representations.

VI. CASE STUDIES

  • LP2 reads a graph that is built once, and the YGGDRASIL integration preserves its nodes, edges, relations, prompts, and predicted trajectory distributions.The study replays cached LLM responses and runs each configuration five times per scene.Source: A. LP2: Long-Term Human Trajectory… · p. 6

A. LP2: Long-Term Human Trajectory Prediction

  • 99.6% of LP2 scene-graph time is removed in the office scene and 98.8% in the home scene.The comparison pools five repetitions per scene; Table II reports query costs and per-run totals.Source: A. LP2: Long-Term Human Trajectory… · p. 6, Table II · p. 7
  • 873× faster office and 636× faster home waypoint-to-room queries use a nesting edge as a single parent pointer instead of scanning the edge list.The original query cost scales with graph size; YGGDRASIL’s does not.Source: A. LP2: Long-Term Human Trajectory… · pp. 6–7
  • YGGDRASIL’s spatial indexing answers radius queries 107× faster in the office and 87× faster at home, and nearest-waypoint queries 30× and 25× faster, respectively.Source: A. LP2: Long-Term Human Trajectory… · p. 7
  • Rebuilding the NetworkX copy and KD-tree costs 2681 ms per office run and 1355 ms per home run, versus 35 ms and 27 ms for YGGDRASIL.When a deployed robot updates the graph during downstream work, the original conversion must be repaid after each update.Source: A. LP2: Long-Term Human Trajectory… · p. 7

B. OSG: Zero-shot LLM-Guided Object-Search Navigation

OSG builds and queries its graph during object-goal navigation. YGGDRASIL’s layered representation accommodates OSG’s flat graph, preserves episode behavior, and reduces total graph latency and memory, with a cost for edge insertion.

a) Setup

  • Across 400 episodes, the original and YGGDRASIL configurations have zero action-sequence divergence and identical mean success, SPL, and step count.Source: B. OSG: Zero-shot LLM-Guided… · p. 7

b) Structure

  • OSG’s entrance-to-object “is near” relation is represented between shadow nodes in a physical layer, because YGGDRASIL edges join nodes within the same layer.Each shadow node is nested under its owning entrance or object node.Source: B. OSG: Zero-shot LLM-Guided… · p. 7, Figure 4 · p. 7

c) Performance

C. S3DSG: Social 3D Scene Graphs for Human-Aware Reasoning

S3DSG augments an existing scene graph with human-centric nodes and activity edges for socially aware motion planning. YGGDRASIL’s layer indexing improves cost-field evaluation even against the original pipeline’s hand-maintained spatial indexes.

a) Setup

  • The comparison evaluates 2,115,650 nearest-neighbour queries on an apartment scene; both systems’ cost fields agree within 3.2 × 10^-6.Traversing the store’s 84 edges costs 41 µs and is not under test.Source: C. S3DSG: Social 3D Scene Graphs for… · p. 8

b) Performance

  • YGGDRASIL evaluates the cost field in 4936 ms versus 6885 ms for the original, a speedup of 1.39, and saves a further 1343 ms by reusing its metric layer.The speedup holds to within two percent across runs.Source: C. S3DSG: Social 3D Scene Graphs for… · p. 8
  • One metric-layer kd-tree serves queries across that layer, while the original probes one object-keyed tree per object and reduces the answers to a minimum.The original’s query cost grows with the number of indexed objects; YGGDRASIL’s does not.Source: C. S3DSG: Social 3D Scene Graphs for… · p. 8
  • Even against hand-rolled kd-tree indexes, YGGDRASIL gains performance while maintaining indexes internally as the graph is updated.The original already maintains external indexes, making this a deliberately modest comparison.Source: C. S3DSG: Social 3D Scene Graphs for… · p. 8

VII. CONCLUSION

The conclusion presents YGGDRASIL as a layer-first scene graph with typed queries and no intermediate conversion, integrated into three robotic and perception pipelines. It also identifies schema design and concurrency as remaining gaps.

VII. CONCLUSION

  • YGGDRASIL combines generic nodes, edges, and layers with a DAG hierarchy and typed queries that serve semantic and spatial queries in place.Source: §VII · p. 8
  • Three integrations span human trajectory prediction, object-goal navigation, and human-aware motion planning, covering downstream use, in-loop construction and consumption, and graph augmentation.Source: §VII · p. 8
  • YGGDRASIL lacks concurrency control, and all reported measurements are single-threaded; its per-room schema was also designed by hand.The authors identify automatic schema inference and concurrent readers and writers as future work.Source: §VII · p. 8
Loading 2609.38640v1…