segmentation using Kimera [2] as the ground-truth objects for the purposes of
evaluation. For the object layer, we report two metrics: the percentage of
objects in the ground-truth scene graph that have an estimated object with the
correct semantic label within a specified radius (“ _% Found_ ”) and the
percentage of objects in the estimated scene graph that have a ground-truth
object with the correct semantic label within a specified radius (“ _%
Correct_ ”).202020As distance thresholds, we use $0.5\text{\,}\mathrm{m}$ for
the uHumans2 Apartment and Office scene, and $1\text{\,}\mathrm{m}$ for
SidPac, the Simmons Jackal scene, and the Simmons A1 scene. These thresholds
were chosen to roughly correspond to the mean Absolute Trajectory Error (ATE)
for each scene, in order to normalize the metrics between simulated and real
scenes.

We note some important trends in Fig. 14. First, when using _GT-Trajectory_ ,
Hydra produces objects that are reasonably close to the ground-truth (80–100%
found and correct objects for the Office scene), or close to the objects
produced by offline approaches (70–80% found and correct objects for SidPac
and Simmons). This demonstrates that —given the trajectory— the real-time
scene graph from Hydra is comparable to the batch and offline approaches at
the state of the art. Second, _VIO+V-LC_ , _VIO+SG-LC_ , and _VIO+GNN-LC_
maintain reasonable levels of accuracy for the objects and attain comparable
performance in small to medium-sized scenes (_i.e.,_ the uHumans2 Apartment,
Office, and Simmons A1) for the same choice of semantic segmentation method.
In these scenes, the drift is small and the loop closure strategy does not
radically impact performance (differences are within standard deviation).
However, in larger scenes (_e.g.,_ SidPac) scene graph loop closures are more
important and both _VIO+GNN-LC_ and _VIO+SG-LC_ largely outperform _VIO+V-LC_
and _VIO_ in terms of object accuracy.

Finally, as expected, the quality of the semantic segmentation impacts the
accuracy; this is much more pronounced for “ _% Found_ ” than “ _% Correct_ ”.
Note that the two metrics are somewhat coupled; a lower “ _% Found_ ” can lead
to a higher “ _% Correct_ ”; this is one reason for the inversion in
performance between OneFormer and HRNet for the uHumans2 scenes. Additionally,
note that OneFormer identifies objects that exist in the ground-truth scene
that are not exported by the simulator (this is another factor responsible for
the lower “ _% Correct_ ” of OneFormer). We also note a slight correlation
between reduced semantic segmentation performance and reduced accuracy for
_VIO+GNN-LC_ and _VIO+SG-LC_ , such as for the Simmons Jackal scene. The low
number of objects identified by HRNet in this scene contributes to fewer
scene-graph based loop closures, and as such, worse performance.

Accuracy Evaluation: Places. Figure 14f evaluates the place layer by comparing
the five configurations for Hydra. We use either the ground-truth semantics
(when available) or OneFormer (when ground-truth semantics is not available),
as the places are not influenced by the semantic segmentation quality. For the
places evaluation, we construct a “ground-truth” GVD from a 3D reconstruction
of the entire scene using the ground-truth trajectory of the scene. Using
this, we measure the mean distance of an estimated place node to the nearest
voxel in the ground-truth GVD, which we call “ _Position Error_ ”. Figure 14f
reports this metric, along with standard deviation across 5 trials shown as
black error bars.

We note some important trends in Fig. 14f. Similar to the case of objects, the
place positions errors are almost identical for all configurations of Hydra
for the uHumans2 scenes. These scenes have very low drift, and are relatively
small, so it is expected that a higher quality trajectory makes less of an
impact. For the larger scenes, we see a range of results. However, we see for
SidPac, _VIO+GNN-LC_ performs worse than _VIO+SG-LC_ , though both outperform
_VIO+V-LC_ and _VIO_. Interestingly, we note that _VIO+SG-LC_ performs
slightly worse than _VIO+V-LC_ for the Simmons Jackal scene, while _VIO+GNN-
LC_ does the same as _VIO+V-LC_ (but with lower standard deviation, as
indicated by the black confidence bars in the plot). Note that the Simmons
Jackal scene has multiple uniform rooms with very similar objects and layouts.
In general, _VIO_ is outperformed by methods that incorporate loop closures,
and the ability to correct for loop closures is important to maintaining an
accurate 3D scene graph.

Neural Tree Ablation 1: Node Classification. We first replicate the semi-
supervised node classification experiment described in [16] and compare
different message passing architectures on the original graphs (_i.e.,_
standard GNNs) and on the H-tree (_i.e.,_ the proposed neural tree). To
construct the H-tree graphs, we apply the proposed hierarchical tree
decomposition algorithm (Algorithm 1), which concatenates the tree
decomposition of each layer. The results are shown in Table II. With the
proposed tree decomposition approach, the neural tree achieves an advantage
between 1.63% to 11.72% over standard GNN models, depending on the type of
message passing architecture. In comparison to the results in [16], the
results in Table II are generated using a later version of the PyTorch
Geometric library, which supports heterogeneous GNN operators. Also note that
the tree decomposition used in Table II differs slightly from the tree
decomposition algorithm used in [16]. We provide additional results in Section
A-F that examine the impact of these changes.

Message Passing | Original | H-tree
---|---|---
GCN | $42.91\pm 2.01\%$ | $\mathbf{54.63\pm 2.19\%}$
GraphSAGE | $56.97\pm 2.02\%$ | $\mathbf{58.60\pm 2.13\%}$
GAT | $45.06\pm 2.32\%$ | $\mathbf{53.71\pm 2.10\%}$
GIN | $48.03\pm 2.21\%$ | $\mathbf{55.00\pm 2.68\%}$
TABLE II: Stanford3d: Node classification accuracy for different message passing architectures. Best results in bold. Graph Types | Original | H-tree
---|---|---
Homogeneous | absolute pos. | $45.06\pm 2.32\%$ | $\mathbf{53.71\pm 2.10\%}$
relative pos. | $46.05\pm 1.98\%$ | $\mathbf{61.16\pm 2.03\%}$
Heterogeneous | absolute pos. | $\mathbf{46.56\pm 2.42\%}$ | $45.30\pm 2.57\%$
relative pos. | $45.79\pm 2.04\%$ | $\mathbf{48.16\pm 2.21\%}$
TABLE III: Stanford3d: Node classification accuracy for different graph types and position encodings. Best results in bold. Graph Types | Original | H-Tree
---|---|---
w/o word2vec | w/o room edges | $\mathbf{41.28\pm 0.48\%}$ | $38.63\pm 0.25\%$
with room edges | $41.20\pm 1.08\%$ | $\mathbf{43.27\pm 0.59\%}$
with word2vec | w/o room edges | $\mathbf{56.74\pm 0.85\%}$ | $55.84\pm 0.37\%$
with room edges | $56.02\pm 0.84\%$ | $\mathbf{57.67\pm 0.57\%}$
TABLE IV: MP3D: Room classification accuracy for different graph types and
node features. Best results in bold.

We note that the absolute position of a node centroid is not invariant to
translation, and that invariance is important to generalize to new scenes
regardless of the choice of coordinate frames. We therefore examine using the
relative positions of node centroids as edge features, instead of including
them directly as node features. For the H-tree, which contains clique nodes
that are comprised of multiple objects or rooms, we use the mean room centroid
as the centroid of the clique when computing relative positions. In addition,
we also investigate the impact of using heterogeneous graphs (which can
accommodate different node and edge types, as the ones arising in the 3D scene
graph) against standard homogeneous graphs. For this comparison, we only use
the GAT message passing function since it is the only one in Table II that can
both handle heterogeneous message passing and incorporate edge features.

We present the results of this ablation study in Table III. Comparing the two
position encodings, the neural tree models achieve significantly higher
accuracy when using relative positions as edge features: 7.45% on homogeneous
graphs and 2.86% on heterogeneous graphs. Choosing features that are
translation invariant (_i.e.,_ relative positions) has a clear advantage when
using neural tree models. The standard GNNs show near-identical performance
between the two position encodings. The heterogeneous graph structure has no
significant impact on standard GNNs, but it degrades performance of the neural
trees. The exact mechanism behind this decrease in performance in unclear; we
posit that the heterogeneous neural tree variants have more parameters than
the other architectures, and that the Standford3D dataset may not have enough
training data for these architectures. We do not observe a significant
performance decrease between the homogeneous and heterogeneous neural tree
variants for the MP3D dataset.

Neural Tree Ablation 2: Room Classification. We compare the neural tree
against standard GNNs on a room classification task using the MP3D dataset,
predicting room semantic labels for the object-room graphs extracted from
Hydra. Compared to Stanford3d, this dataset contains both semantic labels of
the object nodes and room layer connectivity from Hydra, in addition to the
geometric features (_i.e.,_ centroid position and bounding box size) of each
node. Therefore, we study the effect of these two additional pieces of
information. We use pre-trained word2vec vectors to represent object semantic
labels and concatenate them with the geometric feature vectors. As described
previously, we filter out partially explored rooms, using a threshold of 60%
IoU. As before, we use GAT as the message passing function when training, as
all graphs are heterogeneous and have edge features. The results are shown in
Table IV. Both approaches show a significant performance improvement using the
semantic labels of the objects, ranging from 14% to 17%. The neural tree also
shows substantial improvement when incorporating room layer edges, while the
standard GNNs do not. The best-performing neural tree model is obtained when
using semantic labels for the objects and accounting for room connectivity;
this is the model we use in the rest of this paper.

Accuracy Evaluation: Rooms. We evaluate the accuracy of the room segmentation
in Hydra, by first evaluating the quality of the geometric room clustering
described in Section III-D1 and then testing the room classification from
Section III-D2 for different choices of 2D segmentation network.

Figure 15 evaluates the room clustering performance, using the precision and
recall metrics defined in [46] (here we compute precision and recall over 3D
voxels instead of 2D pixels). More formally, these metrics are:

$\begin{split}\text{\emph{Precision}}&=\frac{1}{|R_{e}|}\sum_{r_{e}\in
R_{e}}\max_{r_{g}\in R_{g}}\frac{|r_{g}\cap r_{e}|}{|r_{e}|}\\\
\text{\emph{Recall}}&=\frac{1}{|R_{g}|}\sum_{r_{g}\in R_{g}}\max_{r_{e}\in
R_{e}}\frac{|r_{e}\cap r_{g}|}{|r_{g}|}\end{split}$ (12)

where $R_{e}$ is the set of estimated rooms, $R_{g}$ is the set of ground-
truth rooms, and $|\cdot|$ returns the cardinality of a set; here, each room
$r_{e}$ (or $r_{g}$) is defined as a set of free-space voxels. We hand-label
the ground-truth rooms $R_{g}$ from the ground-truth reconstruction of the
environment. In particular, we manually define sets of bounding boxes for each
room and then identify the set of free-space voxels for $r_{g}$ as all free-
space voxels that fall within any of the defined bounding boxes for $r_{g}$.
For the estimated rooms $R_{e}$, we derive the set of free-space voxels
$r_{e}$ from the places comprising each estimated room. In eq. (12),
_Precision_ then measures the maximum overlap in voxels with a ground-truth
room for every estimated room, and _Recall_ measures the maximum overlap in
voxels with an estimated room for every ground-truth room. Intuitively, low
precision corresponds to under-segmentation, _i.e.,_ fewer and larger room
estimates, and low recall corresponds to over-segmentation, _i.e.,_ more and
smaller room estimates. For benchmarking purposes, we also include the
approach in [2] (_Kimera_) as a baseline for evaluation.

Figure 15 shows that Hydra generally outperforms Kimera [2] when given the
ground-truth trajectory, and that Hydra is slightly more robust to multi-floor
environments. This is expected, as Kimera performs room segmentation by taking
a 2D slice of the voxel-based map of the environment, which does not
generalize to multi-floor scenes. For both the split-level Apartment scene and
the multi-floor SidPac scene, we achieve higher precision as compared to
Kimera. These differences stem from the difficulty of setting an appropriate
height to attempt to segment rooms at for Kimera (this is the height at which
Kimera takes a 2D slice of the ESDF). Finally, it is worth noting that our
room segmentation approach is able to mostly maintain the same levels of
precision and recall for _VIO+GNN-LC_ , _VIO+SG-LC_ and _VIO+V-LC_. In some
cases, our approach outperforms Kimera, despite the drift inherent in
_VIO+GNN-LC_ , _VIO+SG-LC_ and _VIO+V-LC_ (Kimera uses ground-truth poses).

Finally, we report room classification accuracy for uHumans2, SidPac, and
Simmons across semantic segmentation sources in Table V using the proposed
neural tree. We manually assign a ground-truth room category to each hand
labeled ground-truth room, and compute the percentage of estimated room labels
that match their corresponding ground-truth category. Label correspondences
are computed by picking the ground-truth room that contains the most place
nodes that comprise each estimated room; an estimated room is assigned a
correspondence to _unknown_ if too few place nodes (less than 10) fall inside
the best ground-truth room.

We note two interesting trends. First, the richness of the object label space
impacts the predicted room label accuracy, as shown by the relatively poor
performance of the GT column as compared to either HRNet or OneFormer for the
uHumans2 scenes ($27$% versus $40$% or $45\%$): the GT semantics available in
the simulator has a smaller number of semantic classes for the objects,
hindering performance. This is consistent with the observations in [72].
Second, scenes such as the uHumans2 office or Simmons that are out of
distribution —compared to the MP3D dataset we use for training— perform
poorly. An example of a resulting 3D scene graph for SidPac with room category
labels is shown in Fig. 1.

Figure 15: Room metrics for all scenes across different LCD pose source configurations. Each bar shows the average precision or recall over 5 trials; standard deviation across the 5 trials is shown as a black error bar | GT | HRNet | OneFormer
---|---|---|---
uHumans2 Apartment |  $26.7\pm 3.7$% |  $38.0\pm 21.7$% |  $45.0\pm 11.2$%
uHumans2 Office |  $27.6\pm 7.5$% |  $28.4\pm 6.9$% |  $27.0\pm 10.1$%
SidPac Floor 1–3 | N/A |  $46.2\pm 11.9$% |  $47.7\pm 12.5$%
Simmons Jackal | N/A |  $32.3\pm 16.6$% |  $15.3\pm 6.5$%
Simmons A1 | N/A |  $29.0\pm 24.4$% |  $38.0\pm 28.0$%
TABLE V: Room classification accuracy for Hydra. Figure 16: Number of detected
loop closures versus error of the estimated loop closure pose for four
different loop closure detection configurations. Five individual trials and a
trend-line are shown for each configuration.

Loop Closure Ablation. Finally, we take a closer look at the quality of the
loop closures candidates proposed by our hierarchical loop closure detection
approach, and compare it against traditional vision-based approaches on the
Office scene. In particular, we compare our approach against a vision-based
loop closure detection that uses DBoW2 for place recognition and ORB feature
matching, as described in [2].

Figure 16 shows the number of detected loop closures against the error of the
registered solution (_i.e.,_ the relative pose between query and match
computed by the geometric verification) for four different loop closure
configurations: (i) “SG-LC”: the proposed handcrafted scene graph loop closure
detection, (ii) “SG-GNN”: the proposed learned scene graph loop closure
detection, (iii) “V-LC (Nominal)”: a traditional vision-based loop closure
detection with nominal parameters, and (iv) “V-LC (Permissive)”: a vision-
based loop closure detection with more permissive parameters (_i.e.,_ a
decreased score threshold and less restrictive geometric verification
settings). We report key parameters used in this evaluation in Section A-G. As
expected, making the vision-based detection parameters more permissive leads
to more but lower-quality loop closures. On the other hand, the scene graph
loop closure approach produces approximately twice as many loop closures
within $10\text{\,}\mathrm{cm}$ of translation error and
$1\text{\,}\mathrm{\SIUnitSymbolDegree}$ of rotation error as the permissive
vision-based approach. The proposed approach produces quantitatively and
quantitatively better loop closures compared to both baselines. Notably, SG-
GNN also outperforms both vision baselines and the SG-LC. We present further
discussion and a breakdown of additional statistics of the proposed loop
closures of each method in Section A-H.

|  |  | p@10
---|---|---|---
|  |  | IoU $=0.4$ | IoU = $0.6$
Objects | MP3D | Handcrafted | $\mathbf{70.9}$ | $\mathbf{58.6}$
Learned+OneHot | $65.5$ | $56.0$
Learned+Word2Vec | $60.3$ | $50.9$
uH2 Office | Handcrafted | $46.5$ | $\mathbf{31.5}$
Learned+OneHot | $\mathbf{47.4}$ | $31.4$
Learned+Word2Vec | $37.6$ | $26.5$
Places | MP3D | Handcrafted | $\mathbf{76.4}$ | $\mathbf{58.0}$
Learned | $59.5$ | $47.4$
uH2 Office | Handcrafted | $\mathbf{68.6}$ | $\mathbf{41.4}$
Learned | $54.1$ | $34.9$
TABLE VI: p@k results for loop closure detection. Best results in bold.

To further examine the relative performance of SG-LC and SG-GNN, we evaluate
the top-k precision of both approaches on both the test split of the MP3D
dataset used to train the descriptors, and the uHumans2 office scene. For this
metric, we compute the percent of the $k$-highest-scored212121We map distances
between descriptors to a $[0,1]$ range, where $1$ corresponds to a match, and
$0$ corresponds to a non-match  descriptors for each query descriptor that are
valid matches; two descriptors are determined to match if the bounding box of
their corresponding sub-graphs have a IoU above a specified threshold. We
include two configurations of SG-GNN for object sub-graphs in this analysis;
one that uses a one-hot encoding and one that uses word2vec embeddings to
represent the semantic labels of the object nodes. We report this metric for
both SG-LC (handcrafted) and SG-GNN (learned) in Table VI for two IoU
thresholds: 0.4 and 0.6.

We note some interesting trends in Table VI. First, the one-hot encoding
outperforms the word2vec encoding for both datasets, and appears to transfer
better between datasets (_i.e.,_ showing 5% better performance for the MP3D
dataset, but 10% better performance for uHumans2). Additionally, the original
handcrafted descriptors maintain good performance compared to the learned
descriptors, and only the learned object descriptors appear competitive to the
handcrafted descriptors in terms of precision. We believe that the high
performance of the handcrafted descriptors is due to the semantic and
geometric diversity among the scenes of the MP3D dataset. Previous experiments
(using the _VIO+GNN-LC_ configuration of Hydra) imply that the learned
descriptors offer improved performance in environments with a more uniform
object distribution (_i.e.,_ the Simmons Jackal scene).

####  VI-C3 Onboard Operation on a Robot

Figure 17: Intermediate 3D scene graph created by Hydra onboard the A1
quadruped while exploring building 31 on the MIT campus. Estimated room labels
are shown.

This section shows that Hydra is capable of running in real-time and is
deployable to a robot. We show this by performing a qualitative experiment,
running Hydra online on the Unitree A1. We run Hydra and the chosen 2D
semantic segmentation network (MobilenetV2 [67]) on the Nvidia Xavier NX
mounted on the back of the A1. Additionally, we run our room classification
approach in the loop with Hydra on the CPU of the same Nvidia Xavier. In this
test, to circumvent the computational cost of running Kimera-VIO, we use an
Intel RealSense T265 to provide odometry estimates to Hydra. As a result, we
use our proposed scene-graph loop closure detection method without the
appearance-based descriptors (which would rely on Kimera-VIO for computation
of the visual descriptors and vision-based geometric verification). To
maintain real-time performance, we configure the frontend of Hydra to run
every fifth keyframe (instead of every keyframe), and limit the reconstruction
range to $3.5\text{\,}\mathrm{m}$ (instead of the nominal
$4.5\text{\,}\mathrm{m}$). Note that this results in a nominal update rate of
$1\text{\,}\mathrm{Hz}$ for Hydra, though we still perform dense 3D metric-
semantic reconstruction at keyframe rate ($5\text{\,}\mathrm{Hz}$). A
breakdown of the runtime of Hydra’s modules during this experiment is
available in Section VI-C4.

For this experiment, we partially explore a floor of building 31 on the MIT
campus consisting of a group of cubicles, a conference room, two impromptu
lounge areas, all of which are connected by a hallway. An intermediate scene
graph produced by Hydra while running the experiment is shown in Fig. 17, and
video is available of the experiment.222222https://youtu.be/AEaBq2-FeY0 Hydra
estimates four rooms for the scene graph; of these four rooms, room 3 is
centered over one of the two lounges, and room 0 covers both the conference
room (located in the lower right corner of Fig. 17) and a portion of the
hallway. Qualitatively, Hydra over-segments the scene, but the produced rooms
and labels are still somewhat consistent with the underlying room structure
and labels. In this instance, only room 0 has an incorrectly estimated label;
however the room categories that Hydra estimates over the course of the
experiment are not as consistent. This is likely due to the poor quality of
the 2D semantics from MobilenetV2, and general lack of useful object
categories for inferring room labels.

Figure 18: Runtime required for scene graph construction vs. timestamp for the SidPac Floor 1–3 dataset for a batch approach (Kimera) and for the proposed incremental approach (Hydra). For timing of the low-level processes in Hydra, we refer the reader to the analysis in [2], as we also rely on Kimera-VIO. | Objects [ms] | Places [ms] | Rooms [ms]
---|---|---|---
uH2 Apartment | $52.8\pm 14.9$ | $11.3\pm 6.1$ | $1.8\pm 0.9$
uH2 Office | $34.0\pm 26.1$ | $12.5\pm 6.9$ | $14.6\pm 11.9$
SidPac Floor 1–3 | $57.4\pm 55.7$ | $15.7\pm 9.2$ | $5.9\pm 9.0$
Simmons Jackal | $63.9\pm 45.8$ | $19.6\pm 13.1$ | $6.6\pm 9.0$
Simmons A1 | $71.1\pm 50.5$ | $18.6\pm 11.7$ | $1.4\pm 1.0$
TABLE VII: Hydra: timing breakdown.

####  VI-C4 Runtime Evaluation

Figure 18 reports the runtime of Hydra versus the batch approach in [2]. This
plot shows that the runtime of the batch approach increases over time and
takes more than five minutes to generate the entire scene graph for moderate
scene sizes; as we mentioned, most processes in the batch approach [2] entail
processing the entire ESDF (_e.g.,_ place extraction and room detection),
inducing a linear increase in the runtime as the ESDF grows. On the other
hand, our scene graph frontend (_Hydra Mid-Level_ in Fig. 18) has a fixed
computation cost. In Fig. 18, a slight upward trend is observable for _Hydra
High-Level_ , driven by room detection and scene graph optimization
computation costs, though remaining much lower than batch processing.
Noticeable spikes in the runtime for _Hydra High-Level_ (_e.g.,_ at 1400
seconds) correspond to the execution of the 3D scene graph optimization when
new loop closures are added.

When reconstructing the scene shown in Fig. 18 (SidPac Floor1–3), Hydra uses a
maximum of $7.2\text{\,}\mathrm{MiB}$ for the TSDF,
$19.1\text{\,}\mathrm{MiB}$ for the storage of the semantic labels, and
$47.8\text{\,}\mathrm{MiB}$ for the storage of the dense GVD inside the active
window, for a total of $74.1\text{\,}\mathrm{MiB}$. Kimera instead uses
$79.2\text{\,}\mathrm{MiB}$ for the TSDF, $211\text{\,}\mathrm{MiB}$ for the
storage of semantic labels, and $132\text{\,}\mathrm{MiB}$ for the storage of
the ESDF when reconstructing the entire environment, for a total of
$422\text{\,}\mathrm{MiB}$ of memory. Note that the memory storage requirement
of Hydra for the active window is a fifth of the memory required for Kimera,
and that the memory usage of Kimera grows with the size of the scene.

Table VII reports timing breakdown for the incremental creation of each layer
across scenes for a single trial. The object layer runtime is determined by
the number of mesh vertices in the active window and the number of possible
object semantic classes. The room layer runtime is determined by the number of
places (a combination of how complicated and large the scene is); this is why
the Office has the largest computation cost for the rooms despite being
smaller than the SidPac scenes. Note that our target keyframe rate implies a
limit of $200\text{\,}\mathrm{ms}$ for any of these processes. While the mean
and standard deviation of all layers are well below this rate, we do see that
the real-time rate is exceeded in some cases for extracting the objects. This
specifically occurs for larger scenes (_i.e.,_ SidPac and Simmons Jackal), due
to the presence of many objects. At the same time, we remark that Hydra is
architected in such a way that temporarily exceeding the real-time threshold
does not preclude online performance and real-time operation is restored
shortly after these delays occur.

While the timing results in Table VII are obtained with a relatively powerful
workstation, here we restate that Hydra can run in real-time on embedded
computers commonly used in robotics applications. Towards this goal, we report
the timing statistics from the online experiment running Hydra onboard the
Unitree A1 as shown in Fig. 17. Hydra processes the objects in
$83.9\pm{}65\text{\,}\mathrm{ms}$, places in
$114.8\pm{}103\text{\,}\mathrm{ms}$, and rooms in
$34.7\pm{}37.6\text{\,}\mathrm{ms}$. While these numbers imply that Hydra can
run faster than the $1\text{\,}\mathrm{Hz}$ target rate on the Xavier, note
that the $1\text{\,}\mathrm{Hz}$ limit is chosen to not fully max out the
computational resources of the Xavier. Additionally, there are other modules
of Hydra and external processes that limit (sometimes significantly) the
computational resources of the Xavier (_e.g.,_ the reconstruction of the TSDF
and GVD). While there is still margin to optimize computation (see
conclusions), these initial results stress the practicality and real-time
capability of Hydra in building 3D scene graphs.

##  VII Related Work

We provide a broad literature review touching on abstractions and symbolic
representations (Section VII-A), metric-semantic and hierarchical map
representations and algorithms to build them from sensor data (Section VII-B),
and loop closure detection and optimization (Section VII-C).

###  VII-A Need for Abstractions and Symbolic Representations

State and Action Abstractions. The need to abstract sensor data into higher-
level representations has been studied in the context of planning and
decision-making. Konidaris [73] points out the necessity of state and action
abstraction for efficient task and motion planning problems. Konidaris et al.
[74] extract task-specific state abstractions. James et al. [75] show how
task-independent state abstractions can also be learned. James et al. [76]
show how to autonomously learn object-centric representations of a continuous
and high-dimensional environment, and argue that such a representation enables
efficient planning for long-horizon tasks. Berg et al. [77] propose a
hierarchical representation for planning in large outdoor environments. The
hierarchy contains three levels: landmarks (_e.g.,_ forests, buildings,
streets), neighborhoods, and cities. Several related works also discuss action
abstractions, _e.g.,_ how to group a sequence of actions into macro-actions
(usually referred to as _options_). Jinnai et al. [78], for instance, provide
a polynomial-time approximation algorithm for learning options for a Markov
decision process.

Ontologies and Knowledge Graphs. A fundamental requirement for an embodied
agent to build and communicate a meaningful representation of an environment
is to use a common vocabulary describing concepts of interest232323The term
“concept” may be ambiguous without context as concepts may include a
description of a task, a thought process, or simply the labels for a
classifier. This ambiguity is discussed in more detail in [79]. and their
relations. Such a vocabulary may be represented as an _ontology_ or _the
Kimera-VIO estimatesknowledge graph_. The precise definition ofthe Kimera-VIO
estimates an ontology varies between communities [80, 81]. A well accepted
definition was proposed by Gruber [82] as an explicit specification of
conceptualization and later extended to require the conceptualization must be
a shared view [83] and written as a formal language [84]. In practice, the
definition used is often not as strict. For example, the definition provided
by W3C as part of the Web Ontology Language (OWL) [85] describes an ontology
as a set of terms in a vocabulary and their inter-relationships. Generally, an
embodied agent is committed to a conceptualization regardless if the
commitment is explicit (e.g., represented as knowledge graph) or implicit
(e.g., represented as a set of labels for a classifier) [86].

The need to create a standard ontology was identified by [87], which resulted
in the emergence of several knowledge processing frameworks focused on
robotics applications [88, 89, 90, 91]. A significant effort has been made in
the creation of common-sense ontologies and knowledge graphs [92, 93, 94, 95,
96, 97, 98, 99, 100]. In recent years, there has been a surge in applying
these ontologies and knowledge graphs to problems such as 2D scene graph
generation [101, 102, 103, 104], image classification [105, 106], visual
question answering [107, 108, 109, 110, 111], task planning [112, 113, 114],
and representation learning [115, 116], to name a few.

Scene Grammars and Compositional Models. Compositionality, which is the
ability of humans to perceive reality as a hierarchy of parts, has been
considered fundamental to human cognition [117, 118]. Geman et al. [117]
propose a mathematical formulation of _compositional models_ , by recursively
grouping or composing constituents and assigning probability factors to
composition. Zhu et al. [119] represent and infer visual patters as a
recursive compositional model, which is nothing but a tree-structured
graphical model where the leaf nodes represent the visual patters, and the
higher-layers represent complex compositions. Zhu and Mumford [120], Zhu and
Huang [121] discuss how to model objects, images, and scenes using such a
hierarchical tree structure, called _stochastic grammar_ , and advocate it to
be a general framework for visual representation. Inspired by these insights,
recent works such as [122, 123, 124] propose probabilistic generative models
to capture hierarchical relationship between entities in a scene.

Recent works have tended to use such a hierarchical structure along with deep
neural networks to provide better learning models. Wang et al. [125] show that
using a hierarchical, compositional model of the human body results in better
human pose estimation. The model consists of body parts (_e.g.,_ shoulder,
elbow, arm) organized as a hierarchy (_e.g.,_ shoulder, elbow are children of
arm). A bottom-up/top-down inference strategy is proposed that is able to
correct ambiguities in perceiving the lowest-level parts. Niemeyer and Geiger
[126] show that modeling a 3D scene as one composed of objects and background
leads to more controllable and accurate image synthesis. Mo et al. [127] model
object shape as a hierarchical assembly of individual parts, and the object
shape is then generated by transforming the shape parameter of each object
part. Ichien et al. [128] show that compositional model significantly
outperform deep learning models on the task of analogical reasoning. Yuan et
al. [129] survey work on compositional scene representation. While early work
by Fodor and Pylyshyn [130] argued that neural-network-based models are not
compositional in nature, recent works have suggested otherwise. The works
[131, 132, 133] show that deep convolutional networks avoid the curse of
dimensionality in approximating a class of compositional functions. Webb et
al. [134] show that large language models such as GPT-3 show compositional
generalizability as an emergent property. Such compositionality, however, is
not yet evident in generative models trained on multi-object scenes [135].

###  VII-B Metric-semantic and Hierarchical Representations
for Scene Understanding and Mapping

2D Scene Graphs in Computer Vision. 2D scene graphs are a popular model for
image understanding that describes the content of an image in terms of objects
(typically grounded by bounding boxes in the image) and their attributes and
relations [136, 137]. The estimation of 2D scene graphs (either from a single
image or a sequence of images) has been well studied in the computer vision
community and is surveyed in [28]. The seminal works [136, 137] advocated the
use of 2D scene graphs to perform cognitive tasks such as image search, image
captioning, and answering questions. These tasks, unlike object detection,
require the model to reason about object attributes and object-to-object
relations, and therefore, enable better image understanding. 2D scene graphs
have been successfully used in image retrieval [137], caption generation [138,
139], visual question answering [140, 136], and relationship detection [141].
GNNs are a popular tool for joint object labels and/or relationship inference
on scene graphs [142, 143, 144, 145]. Chang et al. [146] provide a
comprehensive survey on the various methods that have been proposed to infer a
2D scene graph from an image.

Despite their popularity, 2D scene graphs have several limitations. First of
all, they are designed to ground concepts in the image space, hence they are
not suitable to model large-scale scenes (see discussion in Section II).
Second, many of the annotated object-to-object relationships in [136] like
“behind”, “next to”, “near”, “above”, “under” are harder to assess from a 2D
image due to the lack of depth information, and are more easily inferred in
3D. Finally, 2D representations such as 2D scene graphs are not invariant to
viewpoint changes (_i.e.,_ viewing the same 3D scene from a different viewing
angle may result in a different 2D scene graph), as observed in [3].

Flat Metric-Semantic Representations. The last few years have seen a surge of
interest towards _metric-semantic mapping_ , simultaneously triggered by the
maturity of traditional 3D reconstruction and SLAM techniques, and by the
novel opportunities for semantic understanding afforded by deep learning. The
literature has focused on both object-based maps [147, 148, 149, 150, 151,
152] and dense maps, including volumetric models [153, 14, 154], point clouds
[155, 156, 157], and 3D meshes [34, 158]. Some approaches combine objects and
dense map models [159, 160, 161, 162]. These approaches are not concerned with
estimating higher-level semantics (_e.g.,_ rooms) and typically return dense
models that might not be directly amenable for navigation [40].

Building Parsing. A somewhat parallel research line investigates how to _parse
the layout of a building_ from 2D or 3D data. A large body of work focuses on
parsing 2D maps [46], including rule-based [47] and learning-based methods
[163]. Friedman et al. [164] compute a Voronoi graph from a 2D occupancy grid,
which is then labeled using a conditional random field. Recent work focuses on
3D data. Liu et al. [163] and Stekovic et al. [165] project 3D point clouds to
2D maps, which however is not directly applicable to multi-story buildings.
Furukawa et al. [166] reconstruct floor plans from images using multi-view
stereo combined with a Manhattan World assumption. Lukierski et al. [167] use
dense stereo from an omni-directional camera to fit cuboids to objects and
rooms. Zheng et al. [168] detect rooms by performing region growing on a 3D
metric-semantic model.

Hierarchical Representations and 3D Scene Graphs. Hierarchical maps have been
pervasive in robotics since its inception [169, 170, 171, 172]. Early work
focuses on 2D maps and investigates the use of hierarchical maps to resolve
the divide between metric and topological representations [173, 174, 175, 176,
177]. These works preceded the “deep learning revolution” and could not
leverage the rich semantics currently accessible via deep neural networks.

More recently, _3D scene graphs_ have been proposed as expressive hierarchical
models for 3D environments. Armeni et al. [3] model the environment as a graph
including low-level geometry (_i.e.,_ a metric-semantic mesh), objects, rooms,
and camera locations. Rosinol et al. [2, 4] augment the model with a
topological map of places (modeling traversability), as well as a layer
describing dynamic entities in the environment. The approaches in [3, 2, 4]
are designed for offline use. Other papers focus on reconstructing a graph of
objects and their relations [5, 6, 7]. Wu et al. [7] predict objects and
relations in real-time using a graph neural network. Izatt and Tedrake [8]
parse objects and relations into a scene grammar model using mixed-integer
programming. Gothoskar et al. [9] use an MCMC approach. Gay et al. [178] use a
quadric representation to estimate 3D ellipsoids for objects in the scene
given input 2D bounding boxes, and use an RNN to infer relationships between
detected objects.

###  VII-C Maintaining Persistent Representations

Loop Closures Detection. Established approaches for visual loop closure
detection in robotics trace back to place recognition and image retrieval
techniques in computer vision; these approaches are broadly adopted in SLAM
pipelines but are known to suffer from appearance and viewpoint changes [179].
Alternative approaches investigate place recognition using image sequences
[180, 181, 182] or deep learning [183]. More related to our proposal is the
set of papers leveraging semantic information for loop closure detection.
Gawel et al. [184] perform object-graph-based loop closure detection using
random-walk descriptors built from 2D images. Liu et al. [185] use similar
object-based descriptors but built from a 3D reconstruction. Lin et al. [186]
adopt random-walk object-based descriptors and then compute loop closure poses
via object registration. Qin et al. [187] propose an object-based approach
based on sub-graph similarity matching. Zheng et al. [168] propose a room-
level loop closure detector. None of these approaches are hierarchical in
nature.

Loop Closures Correction. After a loop closure is detected, the map needs to
be corrected accordingly. While this process is easy in sparse (_e.g.,_
landmark-based) representations [30], it is non-trivial to perform in real-
time when using dense representations. Stückler and Behnke [188] and Whelan et
al. [189] optimize a map of _surfels_ , to circumvent the need to correct
structured representations (_e.g.,_ meshes or voxels). Dai et al. [190]
propose reintegrating a volumetric map after each loop closure. Reijgwart et
al. [191] correct drift in volumetric representations by breaking the map into
submaps that can be rigidly re-aligned after loop closures. Whelan et al.
[192] propose a 2-step optimization that first corrects the robot trajectory
and then deforms the map (represented as a point cloud or a mesh) using a
deformation graph approach [17]. Rosinol et al. [2] unify the two steps into a
single pose graph and mesh optimization. None of these works are concerned
with simultaneously correcting multiple layers in a hierarchical
representation.

##  VIII Conclusions

This paper argues that large-scale spatial perception for robotics requires
hierarchical representations. In particular, we show that hierarchical
representations scale better in terms of memory and are more suitable for
efficient inference. Our second contribution is to introduce algorithms to
build a hierarchical representation of an indoor environment, namely a _3D
scene graph_ , in real-time as the robot explores the environment. Our
algorithms combine 3D geometry (_e.g.,_ to cluster the free space into a graph
of places), topology (to cluster the places into rooms), and geometric deep
learning (_e.g.,_ to classify the type of rooms the robot is moving across).
Our third contribution is to discuss loop closure detection and correction in
3D scene graphs. We introduce (handcrafted and learning-based) hierarchical
descriptors for loop closure detection, and develop a unified optimization
framework to correct drift in the 3D scene graph in response to loop closures.
We integrate our algorithmic contributions into a heavily parallelized system,
named _Hydra_ , and show it can build accurate 3D scene graphs in real-time
across a variety of photo-realistic simulations and real datasets.

Limitations. While we believe the proposed contributions constitute a
substantial step towards high-level scene understanding and spatial perception
for robotics, our current proposal has several limitations. First, the sub-
graph of places captures the free-space in 3D, which is directly usable for a
drone to navigate. However, traversability for ground robots is also
influenced by other aspects (_e.g.,_ terrain type, steepness). These aspects
are currently disregarded in the construction of the GVD and the places sub-
graph, but we believe they are particularly important for outdoor extensions
of 3D scene graphs. Second, our approach for room segmentation, which first
clusters the rooms geometrically, and then labels each room, mainly applies to
rooms with clear geometric boundaries (_e.g.,_ it would not work in an open
floor-plan). We believe this limitation is surmountable (at the expense of
using extra training data) by replacing the 2-stage approach with a single
learning-based method (_e.g.,_ a neural tree or a standard graph neural
network) that can directly classify places into rooms. Third, for
computational reasons, we restricted the inference in the neural tree to
operate at the level of objects, rooms, and buildings. However, it would be
desirable for high-level semantic concepts (_e.g.,_ room and object labels) to
propagate information downward towards the mesh geometry. While a more compact
representation of the low-level geometry [193, 194] might facilitate this
process, it remains unclear how to fully integrate top-down reasoning in the
construction of the 3D scene graph, which is currently a bottom-up process.

Future Work. This work opens many avenues for current and future
investigation. First of all, while this paper mostly focused on inclusion and
adjacency relations, it would be interesting to label nodes and edges of the
3D scene graph with a richer set of relations and affordances, for instance
building on [7]. Second, the connections between our scene graph optimization
approach and pose graph optimization offer opportunities to improve the
efficiency of the optimization by leveraging recent advances in pose graph
sparsification as well as novel solvers. Third, it would be interesting to
replace the sub-symbolic representation (currently, a 3D mesh and a graph of
places) with neural models, including neural implicit representations [21] or
neural radiance fields [195], which can more easily incorporate priors and
better support shape completion [196]. Fourth, the current set of detectable
objects is fairly limited and restricted by the use of pre-trained 2D
segmentation networks. However, we have noticed in Section VI and in [72] that
a larger object vocabulary leads to better room classification; therefore, it
would be interesting to investigate novel techniques that leverage language
models for open-set segmentation, _e.g.,_ [197, 198]. Fifth, it would be
desirable the extend the framework in this paper to arbitrary (_i.e.,_ mixed
indoor-outdoor environments). Finally, the implications of using 3D scene
graphs for prediction, planning, and decision-making are still mostly
unexplored (see [199, 200, 201] for early examples).

## Disclaimer

Research was sponsored by the United States Air Force Research Laboratory and
the United States Air Force Artificial Intelligence Accelerator and was
accomplished under Cooperative Agreement Number FA8750-19-2-1000. The views
and conclusions contained in this document are those of the authors and should
not be interpreted as representing the official policies, either expressed or
implied, of the United States Air Force or the U.S. Government. The U.S.
Government is authorized to reproduce and distribute reprints for Government
purposes notwithstanding any copyright notation herein.

## References

  * Davison [2018] A. J. Davison, “FutureMapping: The computational structure of spatial AI systems,” _arXiv preprint arXiv:1803.11288_ , 2018.
  * Rosinol et al. [2021] A. Rosinol, A. Violette, M. Abate, N. Hughes, Y. Chang, J. Shi, A. Gupta, and L. Carlone, “Kimera: from SLAM to spatial perception with 3D dynamic scene graphs,” _Intl. J. of Robotics Research_ , vol. 40, no. 12–14, pp. 1510–1546, 2021, arXiv preprint: 2101.06894, (pdf).
  * Armeni et al. [2019] I. Armeni, Z. He, J. Gwak, A. Zamir, M. Fischer, J. Malik, and S. Savarese, “3D scene graph: A structure for unified semantics, 3D space, and camera,” in _Intl. Conf. on Computer Vision (ICCV)_ , 2019, pp. 5664–5673.
  * Rosinol et al. [2020a] A. Rosinol, A. Gupta, M. Abate, J. Shi, and L. Carlone, “3D dynamic scene graphs: Actionable spatial perception with places, objects, and humans,” in _Robotics: Science and Systems (RSS)_ , 2020, (pdf), (media), (video). [Online]. Available: http://news.mit.edu/2020/robots-spatial-perception-0715
  * Kim et al. [2019] U. Kim, J. Park, T. Song, and J. Kim, “3-D scene graph: A sparse and semantic representation of physical environments for intelligent agents,” _IEEE Trans. Cybern._ , vol. PP, pp. 1–13, Aug. 2019.
  * Wald et al. [2020] J. Wald, H. Dhamo, N. Navab, and F. Tombari, “Learning 3D semantic scene graphs from 3D indoor reconstructions,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 3961–3970.
  * Wu et al. [2021] S. Wu, J. Wald, K. Tateno, N. Navab, and F. Tombari, “SceneGraphFusion: Incremental 3D scene graph prediction from RGB-D sequences,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * Izatt and Tedrake [2021] G. Izatt and R. Tedrake, “Scene understanding and distribution modeling with mixed-integer scene parsing,” in _technical report (under review)_ , 2021\.
  * Gothoskar et al. [2021] N. Gothoskar, M. Cusumano-Towner, B. Zinberg, M. Ghavamizadeh, F. Pollok, A. Garrett, J. Tenenbaum, D. Gutfreund, and V. Mansinghka, “3DP3: 3D scene perception via probabilistic programming,” in _ArXiv preprint: 2111.00312_ , 2021.
  * Oleynikova et al. [2017] H. Oleynikova, Z. Taylor, M. Fehr, R. Siegwart, and J. Nieto, “Voxblox: Incremental 3d euclidean signed distance fields for on-board mav planning,” in _IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS)_. IEEE, 2017, pp. 1366–1373.
  * Hughes et al. [2022] N. Hughes, Y. Chang, and L. Carlone, “Hydra: a real-time spatial perception engine for 3D scene graph construction and optimization,” in _Robotics: Science and Systems (RSS)_ , 2022, (pdf).
  * Bavle et al. [2022a] H. Bavle, J. L. Sanchez-Lopez, M. Shaheer, J. Civera, and H. Voos, “Situational graphs for robot navigation in structured indoor environments,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 9107–9114, 2022.
  * Bavle et al. [2022b] ——, “S-graphs+: Real-time localization and mapping leveraging hierarchical representations,” _arXiv preprint arXiv:2212.11770_ , 2022.
  * Grinvald et al. [2019] M. Grinvald, F. Furrer, T. Novkovic, J. J. Chung, C. Cadena, R. Siegwart, and J. Nieto, “Volumetric Instance-Aware Semantic Mapping and 3D Object Discovery,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 3, pp. 3037–3044, 2019.
  * Huber [2021] S. Huber, “Persistent homology in data science,” in _Data Science–Analytics and Applications: Proceedings of the 3rd International Data Science Conference–iDSC2020_. Springer, 2021, pp. 81–88.
  * Talak et al. [2021] R. Talak, S. Hu, L. Peng, and L. Carlone, “Neural trees for learning on graphs,” in _Conf. on Neural Information Processing Systems (NeurIPS)_ , 2021, (pdf).
  * Sumner et al. [2007] R. Sumner, J. Schmid, and M. Pauly, “Embedded deformation for shape manipulation,” _ACM SIGGRAPH 2007 papers on - SIGGRAPH ’07_ , 2007.
  * Harnad [1990] S. Harnad, “The symbol grounding problem,” _Physica D: Nonlinear Phenomena_ , vol. 42, no. 1, pp. 335–346, 1990.
  * Garcia-Garcia et al. [2017] A. Garcia-Garcia, S. Orts-Escolano, S. Oprea, V. Villena-Martinez, and J. García-Rodríguez, “A review on deep learning techniques applied to semantic segmentation,” _ArXiv Preprint: 1704.06857_ , 2017.
  * Zeng et al. [2013] M. Zeng, F. Zhao, J. Zheng, and X. Liu, “Octree-based fusion for realtime 3d reconstruction,” _Graphical Models_ , vol. 75, no. 3, pp. 126–136, 2013\.
  * Park et al. [2019] J. Park, P. Florence, J. Straub, R. Newcombe, and S. Lovegrove, “DeepSDF: Learning continuous signed distance functions for shape representation,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_. IEEE, 2019.
  * Bodlaender [2006] H. L. Bodlaender, “Treewidth: Characterizations, applications, and computations,” in _Graph-Theoretic Concepts in Computer Science_. Springer Berlin Heidelberg, 2006, pp. 1–14.
  * Dechter and Mateescu [2007] R. Dechter and R. Mateescu, “AND/OR search spaces for graphical models,” _Artificial Intelligence_ , vol. 171, no. 2-3, pp. 73–106, 2007.
  * Feder and Vardi [1993] T. Feder and M. Vardi, “Monotone monadic snp and constraint satisfaction,” in _ACM Symp. on Theory of Computing (STOC)_. New York, NY, USA: ACM Press, 1993, pp. 612–622.
  * Grohe et al. [2020] M. Grohe, D. Neuen, P. Schweitzer, and D. Wiebking, “An improved isomorphism test for bounded-tree-width graphs,” _ACM Trans. Algorithms_ , vol. 16, no. 3, Jun. 2020.
  * Chandrasekaran et al. [2008] V. Chandrasekaran, N. Srebro, and P. Harsha, “Complexity of inference in graphical models,” in _Conf. on Uncertainty in Artificial Intelligence (UAI)_ , 2008, p. 70–78.
  * Cooper [1990] G. Cooper, “The computational complexity of probabilistic inference using Bayesian belief networks,” _Artificial Intelligence_ , vol. 42, no. 2-3, pp. 393–405, 1990.
  * Zhu et al. [2022] G. Zhu, L. Zhang, Y. Jiang, Y. Dang, H. Hou, P. Shen, M. Feng, X. Zhao, Q. Miao, S. A. A. Shah _et al._ , “Scene graph generation: A comprehensive survey,” _arXiv preprint arXiv:2201.00443_ , 2022.
  * Tagliasacchi et al. [2016] A. Tagliasacchi, T. Delame, M. Spagnuolo, N. Amenta, and A. Telea, “3d skeletons: A state-of-the-art report,” in _Computer Graphics Forum_ , vol. 35, no. 2. Wiley Online Library, 2016, pp. 573–597.
  * Cadena et al. [2016] C. Cadena, L. Carlone, H. Carrillo, Y. Latif, D. Scaramuzza, J. Neira, I. Reid, and J. Leonard, “Past, present, and future of simultaneous localization and mapping: Toward the robust-perception age,” _IEEE Trans. Robotics_ , vol. 32, no. 6, pp. 1309–1332, 2016, arxiv preprint: 1606.05830, (pdf).
  * Chang et al. [2017] A. Chang, A. Dai, T. Funkhouser, M. Halber, M. Niessner, M. Savva, S. Song, A. Zeng, and Y. Zhang, “Matterport3d: Learning from rgb-d data in indoor environments,” _International Conference on 3D Vision (3DV)_ , 2017.
  * Bodlaender and Koster [2010] H. L. Bodlaender and A. M. Koster, “Treewidth computations I: Upper bounds,” _Information and Computation_ , vol. 208, no. 3, pp. 259 – 275, 2010.
  * Maniu et al. [2019] S. Maniu, P. Senellart, and S. Jog, “An Experimental Study of the Treewidth of Real-World Graph Data,” in _Intl. Conf. Database Theory_ , 2019, pp. 12:1–12:18.
  * Rosinol et al. [2020b] A. Rosinol, M. Abate, Y. Chang, and L. Carlone, “Kimera: an open-source library for real-time metric-semantic localization and mapping,” in _IEEE Intl. Conf. on Robotics and Automation (ICRA)_ , 2020, arXiv preprint: 1910.02490, (video), (code), (pdf).
  * Whelan et al. [2012] T. Whelan, J. B. McDonald, M. Kaess, M. F. Fallon, H. Johannsson, and J. J. Leonard, “Kintinuous: Spatially extended Kinect-Fusion,” in _RSS Workshop on RGB-D: Advanced Reasoning with Depth Cameras_ , Sydney, Australia, July 2012.
  * Nießner et al. [2013] M. Nießner, M. Zollhöfer, S. Izadi, and M. Stamminger, “Real-time 3d reconstruction at scale using voxel hashing,” _ACM Transactions on Graphics (ToG)_ , vol. 32, no. 6, p. 169, 2013.
  * Rusu [2009] R. B. Rusu, “Semantic 3D object maps for everyday manipulation in human living environments,” Ph.D. dissertation, Computer Science department, Technische Universitaet Muenchen, Germany, October 2009.
  * Yang et al. [2020] H. Yang, J. Shi, and L. Carlone, “TEASER: Fast and Certifiable Point Cloud Registration,” _IEEE Trans. Robotics_ , vol. 37, no. 2, pp. 314–333, 2020, extended arXiv version 2001.07715 (pdf).
  * Talak et al. [2023] R. Talak, J. Shi, D. Maggio, and L. Carlone, “A correct-and-certify approach to self-supervise object pose estimators via ensemble self-training,” _Robotics: Science and Systems (RSS)_ , 2023, (pdf).
  * Oleynikova et al. [2018] H. Oleynikova, Z. Taylor, R. Siegwart, and J. Nieto, “Sparse 3D topological graphs for micro-aerial vehicle planning,” in _IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS)_ , 2018.
  * Lau et al. [2013] B. Lau, C. Sprunk, and W. Burgard, “Efficient grid-based spatial representations for robot navigation in dynamic environments,” _Robot. Auton. Syst._ , vol. 61, no. 10, p. 1116–1130, Oct. 2013. [Online]. Available: https://doi.org/10.1016/j.robot.2012.08.010
  * Foskey et al. [2003] M. Foskey, M. C. Lin, and D. Manocha, “Efficient computation of a simplified medial axis,” _J. Comput. Inf. Sci. Eng._ , vol. 3, no. 4, pp. 274–284, 2003\.
  * Blanco and Rai [2014] J. L. Blanco and P. K. Rai, “nanoflann: a C++ header-only fork of FLANN, a library for nearest neighbor (NN) with kd-trees,” https://github.com/jlblancoc/nanoflann, 2014.
  * Ali et al. [2022] D. Ali, A. Asaad, M.-J. Jimenez, V. Nanda, E. Paluzo-Hidalgo, and M. Soriano-Trigueros, “A survey of vectorization methods in topological data analysis,” _arXiv preprint arXiv:2212.09703_ , 2022.
  * Aktas et al. [2019] M. E. Aktas, E. Akbas, and A. E. Fatmaoui, “Persistence homology of networks: methods and applications,” _Applied Network Science_ , vol. 4, no. 1, pp. 1–28, 2019.
  * Bormann et al. [2016] R. Bormann, F. Jordan, W. Li, J. Hampp, and M. H agele, “Room segmentation: Survey, implementation, and analysis,” in _2016 IEEE International Conference on Robotics and Automation (ICRA)_ , 2016, pp. 1019–1026.
  * Kleiner et al. [2017] A. Kleiner, R. Baravalle, A. Kolling, P. Pilotti, and M. Munich, “A solution to room-by-room coverage for autonomous cleaning robots,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2017, pp. 5346–5352.
  * Kipf and Welling [2017] T. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _Intl. Conf. on Learning Representations (ICLR)_ , Apr. 2017.
  * Hamilton. et al. [2017] W. L. Hamilton., R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _Advances in Neural Information Processing Systems (NIPS)_ , Dec. 2017, p. 1025–1035.
  * Jordan [2002] M. Jordan, “An introduction to probabilistic graphical models,” November 2002, unpublished Lecture Notes.
  * Koller and Friedman [2009] D. Koller and N. Friedman, _Probabilistic Graphical Models: Principles and Techniques_. The MIT Press, 2009.
  * Henaff et al. [2015] M. Henaff, J. Bruna, and Y. LeCun, “Deep convolutional networks on graph-structured data,” _arXiv preprint arXiv:1506.05163_ , Jun. 2015.
  * Defferrard et al. [2016] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in _Advances in Neural Information Processing Systems (NIPS)_ , vol. 29, Dec. 2016, pp. 3844–3852.
  * Bronstein et al. [2017] M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst, “Geometric deep learning: going beyond euclidean data,” _IEEE Signal Process. Mag._ , vol. 34, no. 4, pp. 18–42, 2017.
  * Veličković et al. [2018] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lió, and Y. Bengio, “Graph attention networks,” in _Intl. Conf. on Learning Representations (ICLR)_ , May 2018.
  * Lee et al. [2019] J. Lee, R. Rossi, S. Kim, N. Ahmed, and E. Koh, “Attention models in graphs: A survey,” _ACM Trans. Knowl. Discov. Data_ , vol. 13, no. 6, Nov. 2019.
  * Busbridge et al. [2019] D. Busbridge, D. Sherburn, P. Cavallo, and N. Y. Hammerla, “Relational graph attention networks,” _arXiv preprint arXiv:1904.05811_ , Apr. 2019.
  * Fey and Lenssen [2019] M. Fey and J. E. Lenssen, “Fast graph representation learning with PyTorch Geometric,” in _Intl. Conf. on Learning Representations (ICLR) Workshop on Representation Learning on Graphs and Manifolds_ , 2019.
  * Gálvez-López and Tardós [2012] D. Gálvez-López and J. D. Tardós, “Bags of binary words for fast place recognition in image sequences,” _IEEE Transactions on Robotics_ , vol. 28, no. 5, pp. 1188–1197, October 2012.
  * Li et al. [2019] Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli, “Graph matching networks for learning the similarity of graph structured objects,” in _Intl. Conf. on Machine Learning (ICML)_. PMLR, 2019, pp. 3835–3845.
  * Antonante et al. [2021] P. Antonante, V. Tzoumas, H. Yang, and L. Carlone, “Outlier-robust estimation: Hardness, minimally tuned algorithms, and applications,” _IEEE Trans. Robotics_ , vol. 38, no. 1, pp. 281–301, 2021, (pdf).
  * Savva et al. [2019] M. Savva, A. Kadian, O. Maksymets, Y. Zhao, E. Wijmans, B. Jain, J. Straub, J. Liu, V. Koltun, J. Malik, D. Parikh, and D. Batra, “Habitat: A Platform for Embodied AI Research,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2019.
  * Reinke et al. [2022] A. Reinke, M. Palieri, B. Morrell, Y. Chang, K. Ebadi, L. Carlone, and A. Agha-mohammadi, “LOCUS 2.0: Robust and computationally efficient lidar odometry for real-time underground 3D mapping,” vol. 7, no. 4, pp. 9043–9050, 2022, (pdf).
  * Chang et al. [2022a] Y. Chang, K. Ebadi, C. Denniston, M. F. Ginting, A. Rosinol, A. Reinke, M. Palieri, J. Shi, C. A, B. Morrell, A. Agha-mohammadi, and L. Carlone, “LAMP 2.0: A robust multi-robot SLAM system for operation in challenging large-scale underground environments,” _IEEE Robotics and Automation Letters (RA-L)_ , vol. 7, no. 4, pp. 9175–9182, 2022, (pdf).
  * Jain et al. [2023] J. Jain, J. Li, M. Chiu, A. Hassani, N. Orlov, and H. Shi, “OneFormer: One Transformer to Rule Universal Image Segmentation,” 2023.
  * Wang et al. [2021] J. Wang, K. Sun, T. Cheng, B. Jiang, C. Deng, Y. Zhao, D. Liu, Y. Mu, M. Tan, X. Wang, W. Liu, and B. Xiao, “Deep high-resolution representation learning for visual recognition,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 43, no. 10, pp. 3349–3364, 2021.
  * Sandler et al. [2018] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen, “Mobilenetv2: Inverted residuals and linear bottlenecks,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2018, pp. 4510–4520.
  * Zhou et al. [2017] B. Zhou, H. Zhao, X. Puig, S. Fidler, A. Barriuso, and A. Torralba, “Scene parsing through ade20k dataset,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017.
  * Mikolov et al. [2013] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of word representations in vector space,” _arXiv preprints arXiv:1301.3781_ , 2013\.
  * Schroff et al. [2015] F. Schroff, D. Kalenichenko, and J. Philbin, “Facenet: A unified embedding for face recognition and clustering,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2015, pp. 815–823.
  * Xu et al. [2019a] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in _Intl. Conf. on Learning Representations (ICLR)_ , May 2019\.
  * Chen et al. [2022] W. Chen, S. Hu, R. Talak, and L. Carlone, “Leveraging large language models for robot 3D scene understanding,” _arXiv preprint: 2209.05629_ , 2022, (pdf).
  * Konidaris [2019] G. Konidaris, “On the necessity of abstraction,” _Current Opinion in Behavioral Sciences_ , vol. 29, pp. 1–7, Oct. 2019.
  * Konidaris et al. [2018] G. Konidaris, L. P. Kaelbling, and T. Lozano-Perez, “From Skills to Symbols: Learning Symbolic Representations for Abstract High-Level Planning,” _J. of Artificial Intelligence Research_ , vol. 61, pp. 215–289, Jan. 2018.
  * James et al. [2020] S. James, B. Rosman, and G. Konidaris, “Learning portable representations for high-level planning,” in _Intl. Conf. on Machine Learning (ICML)_. PMLR, 2020, pp. 4682–4691.
  * James et al. [2022] ——, “Autonomous Learning of Object-Centric Abstractions for High-Level Planning,” in _Intl. Conf. on Learning Representations (ICLR)_ , May 2022.
  * Berg et al. [2022] M. Berg, G. Konidaris, and S. Tellex, “Using Language to Generate State Abstractions for Long-Range Planning in Outdoor Environments,” in _IEEE Intl. Conf. on Robotics and Automation (ICRA)_ , May 2022, pp. 1888–1895.
  * Jinnai et al. [2019] Y. Jinnai, D. Abel, D. Hershkowitz, M. Littman, and G. Konidaris, “Finding options that minimize planning time,” in _Intl. Conf. on Machine Learning (ICML)_. PMLR, 2019, pp. 3120–3129.
  * Smith [2004] B. Smith, _Beyond Concepts: Ontology as Reality Representation_ , 2004.
  * Guarino et al. [2009] N. Guarino, D. Oberle, and S. Staab, “What is an ontology?” _Handbook on ontologies_ , pp. 1–17, 2009.
  * Jepsen [2009] T. Jepsen, “Just what is an ontology, anyway?” _IT Professional Magazine_ , vol. 11, no. 5, p. 22, 2009.
  * Gruber [1995] T. R. Gruber, “Toward principles for the design of ontologies used for knowledge sharing?” _International journal of human-computer studies_ , vol. 43, no. 5-6, pp. 907–928, 1995.
  * Borst [1997] W. N. Borst, “Construction of engineering ontologies for knowledge sharing and reuse,” 1997, phD Dissertation.
  * Studer et al. [1998] R. Studer, R. Benjamins, and D. Fensel, “Knowledge engineering: Principles and methods,” _Data & Knowledge Engineering_, vol. 25, no. 1-2, pp. 161–197, 1998.
  * McGuinness and Van Harmelen [2004] D. McGuinness and F. Van Harmelen, “OWL web ontology language overview,” _W3C recommendation_ , 2004.
  * Genesereth and Nilsson [2012] M. R. Genesereth and N. J. Nilsson, _Logical Foundations of Artificial Intelligence_. Morgan Kaufmann, 2012.
  * Schlenoff et al. [2012] C. Schlenoff, E. Prestes, R. Madhavan, P. Goncalves, H. Li, S. Balakirsky, T. Kramer, and E. Miguelanez, “An IEEE standard ontology for robotics and automation,” in _IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS)_. IEEE, 2012, pp. 1337–1342.
  * Lemaignan et al. [2010] S. Lemaignan, R. Ros, L. Mösenlechner, R. Alami, and M. Beetz, “ORO, a knowledge management platform for cognitive architectures in robotics,” in _IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS)_. IEEE, 2010, pp. 3548–3553.
  * Tenorth and Beetz [2013] M. Tenorth and M. Beetz, “Knowrob: A knowledge processing infrastructure for cognition-enabled robots,” _Intl. J. of Robotics Research_ , vol. 32, no. 5, pp. 566–590, 2013.
  * Beetz et al. [2018] M. Beetz, D. Beßler, A. Haidu, M. Pomarlan, A. K. Bozcuoğlu, and G. Bartels, “KnowRob 2.0—a 2nd generation knowledge processing framework for cognition-enabled robotic agents,” in _IEEE Intl. Conf. on Robotics and Automation (ICRA)_. IEEE, 2018, pp. 512–519.
  * Diab et al. [2019] M. Diab, A. Akbari, M. Ud Din, and J. Rosell, “PMK—a knowledge processing framework for autonomous robotics perception and manipulation,” _Sensors_ , vol. 19, no. 5, p. 1166, 2019.
  * Miller [1995] G. A. Miller, “Wordnet: A lexical database for english,” _Commun. ACM_ , vol. 38, no. 11, p. 39–41, Nov. 1995. [Online]. Available: https://doi.org/10.1145/219717.219748
  * Lenat [1995] D. B. Lenat, “Cyc: A large-scale investment in knowledge infrastructure,” _Communications of the ACM_ , vol. 38, no. 11, pp. 33–38, 1995.
  * Niles and Pease [2001] I. Niles and A. Pease, “Towards a standard upper ontology,” in _Proceedings of the International Conference on Formal Ontology in Information Systems_ , 2001, pp. 2–9.
  * Auer et al. [2007] S. Auer, C. Bizer, G. Kobilarov, J. Lehmann, R. Cyganiak, and Z. Ives, “DBpedia: A nucleus for a web of open data,” in _Semantic Web_. Springer, 2007, pp. 722–735.
  * Suchanek et al. [2008] F. M. Suchanek, G. Kasneci, and G. Weikum, “YAGO: A large ontology from wikipedia and WordNet,” _Journal of Web Semantics_ , vol. 6, no. 3, pp. 203–217, 2008.
  * Bollacker et al. [2008] K. Bollacker, C. Evans, P. Paritosh, T. Sturge, and J. Taylor, “Freebase: a collaboratively created graph database for structuring human knowledge,” in _Proceedings of the ACM SIGMOD International Conference on Management of Data_ , 2008, pp. 1247–1250.
  * Carlson et al. [2010] A. Carlson, J. Betteridge, B. Kisiel, B. Settles, E. Hruschka, and T. Mitchell, “Toward an architecture for never-ending language learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 24, no. 1, 2010, pp. 1306–1313.
  * Vrandečić and Krötzsch [2014] D. Vrandečić and M. Krötzsch, “Wikidata: A free collaborative knowledgebase,” _Commun. ACM_ , vol. 57, no. 10, p. 78–85, sep 2014. [Online]. Available: https://doi.org/10.1145/2629489
  * Speer et al. [2017] R. Speer, J. Chin, and C. Havasi, “ConceptNet 5.5: an open multilingual graph of general knowledge,” in _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence_ , ser. AAAI’17. AAAI Press, 2017, p. 4444–4451.
  * Zareian et al. [2020] A. Zareian, S. Karaman, and S.-F. Chang, “Bridging knowledge graphs to generate scene graphs,” in _European Conf. on Computer Vision (ECCV)_. Springer, 2020, pp. 606–623.
  * Guo et al. [2021] Y. Guo, L. Gao, X. Wang, Y. Hu, X. Xu, X. Lu, H. T. Shen, and J. Song, “From general to specific: Informative scene graph generation via balance adjustment,” in _Intl. Conf. on Computer Vision (ICCV)_ , 2021, pp. 16 383–16 392.
  * Amodeo et al. [2022] F. Amodeo, F. Caballero, N. Díaz-Rodríguez, and L. Merino, “Og-sgg: Ontology-guided scene graph generation—a case study in transfer learning for telepresence robotics,” _IEEE Access_ , vol. 10, pp. 132 564–132 583, 2022.
  * Chen et al. [2023] Z. Chen, S. Rezayi, and S. Li, “More knowledge, less bias: Unbiasing scene graph generation with explicit ontological adjustment,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2023, pp. 4023–4032.
  * Movshovitz-Attias et al. [2015] Y. Movshovitz-Attias, Q. Yu, M. C. Stumpe, V. Shet, S. Arnoud, and L. Yatziv, “Ontological supervision for fine grained classification of street view storefronts,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2015, pp. 1693–1702.
  * Porello et al. [2015] D. Porello, M. Cristani, and R. Ferrario, “Integrating Ontologies and Computer Vision for Classification of Objects in Images,” in _Workshop on Neural Cognitive Integration_ , 2015, p. 15.
  * Aditya et al. [2018] S. Aditya, Y. Yang, C. Baral, Y. Aloimonos, and C. Fermüller, “Image understanding using vision and reasoning through scene description graph,” _Computer Vision and Image Understanding_ , vol. 173, pp. 33–45, 2018.
  * Gardères et al. [2020] F. Gardères, M. Ziaeefard, B. Abeloos, and F. Lecue, “ConceptBert: Concept-aware representation for visual question answering,” in _Conference on Empirical Methods in Natural Language Processing_ , 2020, pp. 489–498.
  * Marino et al. [2021] K. Marino, X. Chen, D. Parikh, A. Gupta, and M. Rohrbach, “KRISP: Integrating implicit and symbolic knowledge for open-domain knowledge-based VQA,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2021, pp. 14 111–14 121.
  * Zheng et al. [2021] W. Zheng, L. Yin, X. Chen, Z. Ma, S. Liu, and B. Yang, “Knowledge base graph embedding module design for visual question answering model,” _Pattern Recognition_ , vol. 120, p. 108153, 2021.
  * Ding et al. [2022] Y. Ding, J. Yu, B. Liu, Y. Hu, M. Cui, and Q. Wu, “MuKEA: Multimodal knowledge extraction and accumulation for knowledge-based visual question answering,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2022, pp. 5089–5098.
  * Chen et al. [2020] H. Chen, H. Tan, A. Kuntz, M. Bansal, and R. Alterovitz, “Enabling robots to understand incomplete natural language instructions using commonsense reasoning,” in _IEEE Intl. Conf. on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 1963–1969.
  * Daruna et al. [2021] A. Daruna, L. Nair, W. Liu, and S. Chernova, “Towards robust one-shot task execution using knowledge graph embeddings,” in _IEEE Intl. Conf. on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 11 118–11 124.
  * Tuli et al. [2022] S. Tuli, R. Bansal, R. Paul _et al._ , “ToolTango: Common sense generalization in predicting sequential tool interactions for robot plan synthesis,” _The Journal of Artificial Intelligence Research_ , vol. 75, pp. 1595–1631, 2022.
  * Hao et al. [2019] J. Hao, M. Chen, W. Yu, Y. Sun, and W. Wang, “Universal representation learning of knowledge bases by jointly embedding instances and ontological concepts,” in _ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2019, pp. 1709–1719.
  * Kwak et al. [2022] J. H. Kwak, J. Lee, J. J. Whang, and S. Jo, “Semantic grasping via a knowledge graph of robotic manipulation: A graph representation learning approach,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 9397–9404, 2022\.
  * Geman et al. [2002] S. Geman, D. F. Potter, and Z. Chi, “Composition Systems,” _Quarterly of Applied Mathematics_ , vol. 60, no. 4, pp. 707–736, 2002.
  * Lake et al. [2017] B. M. Lake, T. D. Ullman, J. B. Tenenbaum, and S. J. Gershman, “Building machines that learn and think like people,” _Behavioral and Brain Sciences_ , vol. 40, 2017.
  * Zhu et al. [2011] L. L. Zhu, Y. Chen, and A. Yuille, “Recursive Compositional Models for Vision: Description and Review of Recent Work,” _Journal of Mathematical Imaging and Vision_ , vol. 41, no. 1, pp. 122–146, Sep. 2011.
  * Zhu and Mumford [2006] S.-C. Zhu and D. Mumford, “A Stochastic Grammar of Images,” _Foundations and Trends in Computer Graphics and Vision_ , vol. 2, no. 4, pp. 259–362, 2006.
  * Zhu and Huang [2021] S.-C. Zhu and S. Huang, _Computer Vision: Stochastic Grammars for Parsing Objects, Scenes, and Events_. Springer, 2021.
  * Izatt and Tedrake [2020] G. Izatt and R. Tedrake, “Generative modeling of environments with scene grammars and variational inference,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 6891–6897.
  * Qi et al. [2018] S. Qi, Y. Zhu, S. Huang, C. Jiang, and S.-C. Zhu, “Human-Centric Indoor Scene Synthesis Using Stochastic Grammar,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , Jun. 2018, pp. 5899–5908.
  * Chua [2018] J. Chua, “Probabilistic Scene Grammars: A General-Purpose Framework For Scene Understanding,” _Brown University Thesis_ , pp. 1–146, 2018.
  * Wang et al. [2022] W. Wang, T. Zhou, S. Qi, J. Shen, and S.-C. Zhu, “Hierarchical Human Semantic Parsing With Comprehensive Part-Relation Modeling,” _IEEE Trans. Pattern Anal. Machine Intell._ , vol. 44, no. 7, pp. 3508–3522, Jul. 2022\.
  * Niemeyer and Geiger [2021] M. Niemeyer and A. Geiger, “GIRAFFE: Representing Scenes as Compositional Generative Neural Feature Fields,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , Jun. 2021, pp. 11 448–11 459.
  * Mo et al. [2020] K. Mo, P. Guerrero, L. Yi, H. Su, P. Wonka, N. J. Mitra, and L. J. Guibas, “StructEdit: Learning Structural Shape Variations,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2020, pp. 8859–8868.
  * Ichien et al. [2021] N. Ichien, Q. Liu, S. Fu, K. Holyoak, A. Yuille, and H. Lu, “Visual Analogy: Deep Learning Versus Compositional Models,” _Annual Meeting of the Cognitive Science Society_ , vol. 43, 2021.
  * Yuan et al. [2023] J. Yuan, T. Chen, B. Li, and X. Xue, “Compositional Scene Representation Learning via Reconstruction: A Survey,” Feb. 2023.
  * Fodor and Pylyshyn [1988] J. A. Fodor and Z. W. Pylyshyn, “Connectionism and cognitive architecture: A critical analysis,” _Cognition_ , vol. 28, no. 1, pp. 3–71, Mar. 1988\.
  * Mhaskar [1996] H. N. Mhaskar, “Neural networks for optimal approximation of smooth and analytic functions,” _Neural Computation_ , vol. 8, no. 1, pp. 164–177, 1996\.
  * Mhaskar and Poggio [2016] H. N. Mhaskar and T. Poggio, “Deep vs. shallow networks: An approximation theory perspective,” _Analysis and Applications_ , vol. 14, no. 06, pp. 829–848, 2016.
  * Poggio et al. [2017] T. Poggio, H. Mhaskar, L. Rosasco, B. Miranda, and Q. Liao, “Why and when can deep - but not shallow - networks avoid the curse of dimensionality: A review,” _Int. J. Autom. Comput._ , vol. 14, pp. 503–519, Mar. 2017.
  * Webb et al. [2022] T. Webb, K. J. Holyoak, and H. Lu, “Emergent Analogical Reasoning in Large Language Models,” Dec. 2022.
  * Xie et al. [2022] S. Xie, A. S. Morcos, S.-C. Zhu, and R. Vedantam, “COAT: Measuring Object Compositionality in Emergent Representations,” in _Intl. Conf. on Machine Learning (ICML)_ , Jun. 2022, pp. 24 388–24 413.
  * Krishna et al. [2016] R. Krishna, Y. Zhu, O. Groth, J. Johnson, K. Hata, J. Kravitz, S. Chen, Y. Kalantidis, L. Li, D. Shamma, M. Bernstein, and L. Fei-Fei, “Visual Genome: Connecting language and vision using crowdsourced dense image annotations,” _arXiv preprints arXiv:1602.07332_ , 2016.
  * Johnson et al. [2015] J. Johnson, R. Krishna, M. Stark, L. Li, D. Shamma, M. Bernstein, and L. Fei-Fei, “Image retrieval using scene graphs,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2015, pp. 3668–3678.
  * Karpathy and Fei-Fei [2015] A. Karpathy and L. Fei-Fei, “Deep visual-semantic alignments for generating image descriptions,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2015.
  * Anderson et al. [2016] P. Anderson, B. Fernando, M. Johnson, and S. Gould, “Spice: Semantic propositional image caption evaluation,” in _European Conf. on Computer Vision (ECCV)_ , 2016, pp. 382–398.
  * Ren et al. [2015] M. Ren, R. Kiros, and R. S. Zemel, “Image question answering: A visual semantic embedding model and a new dataset,” _arXiv preprints arXiv:1505.02074_ , 2015.
  * Lu et al. [2016] C. Lu, R. Krishna, M. Bernstein, and F.-F. Li, “Visual relationship detection with language priors,” in _European Conference on Computer Vision_ , 2016, pp. 852–869.
  * Xu et al. [2017] D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei, “Scene graph generation by iterative message passing,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2017, pp. 3097–3106.
  * Li et al. [2017] Y. Li, W. Ouyang, B. Zhou, K. Wang, and X. Wang, “Scene graph generation from objects, phrases and region captions,” in _International Conference on Computer Vision (ICCV)_ , 2017.
  * Yang et al. [2018] J. Yang, J. Lu, S. Lee, D. Batra, and D. Parikh, “Graph R-CNN for scene graph generation,” in _European Conf. on Computer Vision (ECCV)_ , 2018.
  * Zellers et al. [2017] R. Zellers, M. Yatskar, S. Thomson, and Y. Choi, “Neural motifs: Scene graph parsing with global context,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * Chang et al. [2023] X. Chang, P. Ren, P. Xu, Z. Li, X. Chen, and A. Hauptmann, “A comprehensive survey of scene graphs: Generation and application,” _IEEE Trans. Pattern Anal. Machine Intell._ , vol. 45, no. 1, pp. 1–26, 2023.
  * Salas-Moreno et al. [2013] R. F. Salas-Moreno, R. A. Newcombe, H. Strasdat, P. H. J. Kelly, and A. J. Davison, “SLAM++: Simultaneous localisation and mapping at the level of objects,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2013.
  * Dong et al. [2017] J. Dong, X. Fei, and S. Soatto, “Visual-Inertial-Semantic scene representation for 3D object detection,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * Shan et al. [2020] M. Shan, Q. Feng, and N. Atanasov, “Object residual constrained visual-inertial odometry,” in _IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS)_ , 2020, pp. 5104–5111.
  * Nicholson et al. [2018] L. Nicholson, M. Milford, and N. Sünderhauf, “QuadricSLAM: Dual quadrics from object detections as landmarks in object-oriented SLAM,” _IEEE Robotics and Automation Letters_ , vol. 4, pp. 1–8, 2018.
  * Bowman et al. [2017] S. Bowman, N. Atanasov, K. Daniilidis, and G. Pappas, “Probabilistic data association for semantic SLAM,” in _IEEE Intl. Conf. on Robotics and Automation (ICRA)_ , 2017, pp. 1722–1729.
  * Ok et al. [2021] K. Ok, K. Liu, and N. Roy, “Hierarchical object map estimation for efficient and robust navigation,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 1132–1139.
  * McCormac et al. [2017] J. McCormac, A. Handa, A. J. Davison, and S. Leutenegger, “SemanticFusion: Dense 3D Semantic Mapping with Convolutional Neural Networks,” in _IEEE Intl. Conf. on Robotics and Automation (ICRA)_ , 2017.
  * Narita et al. [2019] G. Narita, T. Seno, T. Ishikawa, and Y. Kaji, “Panopticfusion: Online volumetric semantic mapping at the level of stuff and things,” in _IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS)_ , 2019.
  * Behley et al. [2019] J. Behley, M. Garbade, A. Milioto, J. Quenzel, S. Behnke, C. Stachniss, and J. Gall, “SemanticKITTI: A Dataset for Semantic Scene Understanding of LiDAR Sequences,” in _Intl. Conf. on Computer Vision (ICCV)_ , 2019.
  * Tateno et al. [2015] K. Tateno, F. Tombari, and N. Navab, “Real-time and scalable incremental segmentation on dense SLAM,” in _IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS)_ , 2015, pp. 4465–4472.
  * Lianos et al. [2018] K. Lianos, J. Schönberger, M. Pollefeys, and T. Sattler, “Vso: Visual semantic odometry,” in _European Conf. on Computer Vision (ECCV)_ , 2018, pp. 246–263.
  * Rosu et al. [2019] R. Rosu, J. Quenzel, and S. Behnke, “Semi-supervised semantic mapping through label propagation with semantic texture meshes,” _Intl. J. of Computer Vision_ , 06 2019.
  * Li et al. [2016] C. Li, H. Xiao, K. Tateno, F. Tombari, N. Navab, and G. D. Hager, “Incremental scene understanding on dense SLAM,” in _IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS)_ , 2016, pp. 574–581.
  * McCormac et al. [2018] J. McCormac, R. Clark, M. Bloesch, A. Davison, and S. Leutenegger, “Fusion++: Volumetric object-level SLAM,” in _Intl. Conf. on 3D Vision (3DV)_ , 2018, pp. 32–41.
  * Xu et al. [2019b] B. Xu, W. Li, D. Tzoumanikas, M. Bloesch, A. Davison, and S. Leutenegger, “MID-Fusion: Octree-based object-level multi-instance dynamic SLAM,” 2019, pp. 5231–5237.
  * Schmid et al. [2021] L. Schmid, J. Delmerico, J. Schönberger, J. Nieto, M. Pollefeys, R. Siegwart, and C. Cadena, “Panoptic multi-tsdfs: a flexible representation for online multi-resolution volumetric mapping and long-term dynamic scene consistency,” _arXiv preprint arXiv:2109.10165_ , 2021.
  * Liu et al. [2018] C. Liu, J. Wu, and Y. Furukawa, “FloorNet: A unified framework for floorplan reconstruction from 3d scans,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , September 2018.
  * Friedman et al. [2007] S. Friedman, H. Pasula, and D. Fox, “Voronoi random fields: Extracting the topological structure of indoor environments via place labeling,” in _Intl. Joint Conf. on AI (IJCAI)_. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2007, p. 2109–2114.
  * Stekovic et al. [2021] S. Stekovic, M. Rad, F. Fraundorfer, and V. Lepetit, “MonteFloor: Extending MCTS for reconstructing accurate large-scale floor plans,” 2021.
  * Furukawa et al. [2009] Y. Furukawa, B. Curless, S. M. Seitz, and R. Szeliski, “Reconstructing building interiors from images,” in _Intl. Conf. on Computer Vision (ICCV)_ , 2009.
  * Lukierski et al. [2017] R. Lukierski, S. Leutenegger, and A. J. Davison, “Room layout estimation from rapid omnidirectional exploration,” in _IEEE Intl. Conf. on Robotics and Automation (ICRA)_ , 2017, pp. 6315–6322.
  * Zheng et al. [2020] T. Zheng, G. Zhang, L. Han, L. Xu, and L. Fang, “Building fusion: Semantic-aware structural building-scale 3d reconstruction,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , pp. 1–1, 2020.
  * Kuipers [2000] B. Kuipers, “The Spatial Semantic Hierarchy,” _Artificial Intelligence_ , vol. 119, pp. 191–233, 2000.
  * Kuipers [1978] ——, “Modeling spatial knowledge,” _Cognitive Science_ , vol. 2, pp. 129–153, 1978.
  * Chatila and Laumond [1985] R. Chatila and J.-P. Laumond, “Position referencing and consistent world modeling for mobile robots,” in _IEEE Intl. Conf. on Robotics and Automation (ICRA)_ , 1985, pp. 138–145.
  * Thrun [2003] S. Thrun, “Robotic mapping: a survey,” in _Exploring artificial intelligence in the new millennium_. Morgan Kaufmann, Inc., 2003, pp. 1–35.
  * Ruiz-Sarmiento et al. [2017] J.-R. Ruiz-Sarmiento, C. Galindo, and J. Gonzalez-Jimenez, “Building multiversal semantic maps for mobile robot operation,” _Knowledge-Based Systems_ , vol. 119, pp. 257–272, 2017.
  * Galindo et al. [2005] C. Galindo, A. Saffiotti, S. Coradeschi, P. Buschka, J. Fernández-Madrigal, and J. González, “Multi-hierarchical semantic maps for mobile robotics,” in _IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS)_ , 2005, pp. 3492–3497.
  * Zender et al. [2008] H. Zender, O. M. Mozos, P. Jensfelt, G.-J. Kruijff, and W. Burgard, “Conceptual spatial representations for indoor mobile robots,” _Robotics and Autonomous Systems_ , vol. 56, no. 6, pp. 493–502, 2008, from Sensors to Human Spatial Concepts.
  * Choset and Nagatani [2001] H. Choset and K. Nagatani, “Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization,” _IEEE Trans. Robot. Automat._ , vol. 17, no. 2, pp. 125 – 137, April 2001\.
  * Beeson et al. [2010] P. Beeson, J. Modayil, and B. Kuipers, “Factoring the mapping problem: Mobile robot map-building in the hybrid spatial semantic hierarchy,” _Intl. J. of Robotics Research_ , vol. 29, no. 4, pp. 428–459, 2010.
  * Gay et al. [2018] P. Gay, J. Stuart, and A. Del Bue, “Visual graphs from motion (VGfM): Scene understanding with object geometry reasoning,” in _Asian Conf. on Computer Vision (ACCV)_. Springer International Publishing, 2018, pp. 330–346.
  * Lowry et al. [2016] S. Lowry, N. Sünderhauf, P. Newman, J. Leonard, D. Cox, P. Corke, and M. Milford, “Visual place recognition: A survey,” _IEEE Trans. Robotics_ , vol. 32, no. 1, pp. 1–19, 2016.
  * Schubert et al. [2021] S. Schubert, P. Neubert, and P. Protzel, “Fast and memory efficient graph optimization via ICM for visual place recognition,” in _Proc. of Robotics: Science and Systems (RSS)_ , 2021.
  * Milford and Wyeth [2012] M. Milford and G. Wyeth, “Seqslam: Visual route-based navigation for sunny summer days and stormy winter nights,” in _IEEE Intl. Conf. on Robotics and Automation (ICRA)_ , may 2012, pp. 1643 –1649.
  * Garg and Milford [2021] S. Garg and M. Milford, “Seqnet: Learning descriptors for sequence-based hierarchical place recognition,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 3, pp. 4305–4312, 2021.
  * Arandjelovic et al. [2016] R. Arandjelovic, P. Gronat, A. Torii, T. Pajdla, and J. Sivic, “NetVLAD: CNN architecture for weakly supervised place recognition,” in _IEEE Conf. on Computer Vision and Pattern Recognition (CVPR)_ , 2016, pp. 5297–5307.
  * Gawel et al. [2018] A. Gawel, C. D. Don, R. Siegwart, J. Nieto, and C. Cadena, “X-view: Graph-based semantic multi-view localization,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 3, pp. 1687–1694, 2018.
  * Liu et al. [2019] Y. Liu, Y. Petillot, D. Lane, and S. Wang, “Global Localization with Object-Level Semantics and Topology,” in _2019 International Conference on Robotics and Automation (ICRA)_ , May 2019, pp. 4909–4915, iSSN: 2577-087X.
  * Lin et al. [2021] S. Lin, J. Wang, M. Xu, H. Zhao, and Z. Chen, “Topology aware object-level semantic mapping towards more robust loop closure,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 4, pp. 7041–7048, 2021.
  * Qin et al. [2021] C. Qin, Y. Zhang, Y. Liu, and G. Lv, “Semantic loop closure detection based on graph matching in multi-objects scenes,” _Journal of Visual Communication and Image Representation_ , vol. 76, p. 103072, 2021.
  * Stückler and Behnke [2014] J. Stückler and S. Behnke, “Multi-resolution surfel maps for efficient dense 3d modeling and tracking,” _J. Vis. Comun. Image Represent._ , vol. 25, no. 1, pp. 137–147, 2014.
  * Whelan et al. [2016] T. Whelan, R. Salas-Moreno, B. Glocker, A. J. Davison, and S. Leutenegger, “ElasticFusion: Real-Time Dense SLAM and Light Source Estimation,” 2016.
  * Dai et al. [2017] A. Dai, M. Nießner, M. Zollhöfer, S. Izadi, and C. Theobalt, “Bundlefusion: Real-time globally consistent 3d reconstruction using on-the-fly surface reintegration,” _ACM Transactions on Graphics (ToG)_ , vol. 36, no. 4, p. 1, 2017.
  * Reijgwart et al. [2020] V. Reijgwart, A. Millane, H. Oleynikova, R. Siegwart, C. Cadena, and J. Nieto, “Voxgraph: Globally consistent, volumetric mapping using signed distance function submaps,” _IEEE Robotics and Automation Letters_ , 2020\.
  * Whelan et al. [2015] T. Whelan, M. Kaess, H. Johannsson, M. Fallon, J. Leonard, and J. McDonald, “Real-time large-scale dense RGB-D SLAM with volumetric fusion,” _Intl. J. of Robotics Research_ , vol. 34, no. 4–5, pp. 598–626, 2015.
  * Czarnowski et al. [2020] J. Czarnowski, T. Laidlow, R. Clark, and A. Davison, “DeepFactors: Real-time probabilistic dense monocular SLAM,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 721–728, 2020.
  * Sucar et al. [2020] E. Sucar, K. Wada, and A. Davison, “NodeSLAM: Neural object descriptors for multi-view shape reconstruction,” in _2020 Intl. Conference on 3D Vision (3DV)_ , 2020, pp. 949–958.
  * Rosinol et al. [2022] A. Rosinol, J. Leonard, and L. Carlone, “NeRF-SLAM: Real-time dense monocular SLAM with neural radiance fields,” _arXiv preprint: 2210.13641_ , 2022, (pdf).
  * Kong et al. [2023] X. Kong, S. Liu, M. Taher, and A. Davison, “vMAP: Vectorised object mapping for neural field SLAM,” _ArXiv, preprint: 2302.01838_ , 2023.
  * Ha and Song [2022] H. Ha and S. Song, “Semantic abstraction: Open-world 3d scene understanding from 2d vision-language models,” 2022.
  * Jatavallabhula et al. [2023] K. M. Jatavallabhula, A. Kuwajerwala, Q. Gu, M. Omama, T. Chen, S. Li, G. Iyer, S. Saryazdi, N. Keetha, A. Tewari, J. Tenenbaum, C. M. de Melo, , M. Krishna, L. Paull, F. Shkurti, and A. Torralba, “ConceptFusion: Open-set multimodal 3D mapping,” _arXiv: 2302.07241_ , 2023.
  * Ravichandran et al. [2022] Z. Ravichandran, L. Peng, N. Hughes, J. Griffith, and L. Carlone, “Hierarchical representations and explicit memory: Learning effective navigation policies on 3D scene graphs using graph neural networks,” in _IEEE Intl. Conf. on Robotics and Automation (ICRA)_ , 2022, (pdf).
  * Agia et al. [2022] C. Agia, K. M. Jatavallabhula, M. Khodeir, O. Miksik, V. Vineet, M. Mukadam, L. Paull, and F. Shkurti, “Taskography: Evaluating robot task planning over large 3D scene graphs,” in _Conference on Robot Learning (CoRL)_. PMLR, Jan. 2022, pp. 46–58.
  * Chang et al. [2022b] Y. Chang, L. Ballotta, and L. Carlone, “D-Lite: Navigation-oriented compression of 3D scene graphs under communication constraints,” _arXiv preprint: 2209.06111_ , 2022, (pdf),(video).
  * Becker and Geiger [1996] A. Becker and D. Geiger, “A sufficiently fast algorithm for finding close to optimal junction trees,” in _Conf. on Uncertainty in Artificial Intelligence (UAI)_ , Feb. 1996, pp. 81–89.
  * Thomas and Green [2009] A. Thomas and P. J. Green, “Enumerating the junction trees of a decomposable graph,” _J. Comput Graph Stat._ , vol. 18, no. 4, pp. 930–940, Dec. 2009\.
  * Bodlaender and Koster [2011] H. L. Bodlaender and A. M. Koster, “Treewidth computations II: Lower bounds,” _Information and Computation_ , vol. 209, no. 7, pp. 1103 – 1119, 2011.
  * Jensen and Jensen [1994] F. V. Jensen and F. Jensen, “Optimal junction trees,” in _Conf. on Uncertainty in Artificial Intelligence (UAI)_ , Jul. 1994, p. 360–366.
  * Bodlaender [1988] H. L. Bodlaender, “Dynamic programming on graphs with bounded treewidth,” in _Automata, Languages and Programming_ , 1988, pp. 105–118.

##  Appendix A Appendix

###  A-A Preliminaries on Tree Decomposition and Treewidth

For a graph $\mathcal{G}$ with vertices ${\cal V}({\cal G})$ and edges ${\cal
E}({\cal G})$, a _tree decomposition_ is a tuple $({\cal T},{\cal B})$ where
${\cal T}$ is a tree graph and ${\cal
B}=\\{B_{\tau}\\}_{\tau\in\mathcal{V}({\cal T})}$ is a family of _bags_ ,
where $B_{\tau}\subset\mathcal{V}(\mathcal{G})$ for every tree node
$\tau\in\mathcal{V}({\cal T})$, such that the tuple $({\cal T},{\cal B})$
satisfies the following two properties:

(1) _Connectedness Property:_ for every graph node
$v\in\mathcal{V}(\mathcal{G})$, the sub-graph of ${\cal T}$ induced by tree
nodes $\tau$ whose bag contains node $v$, is connected, _i.e.,_

${\cal T}_{v}\triangleq{\cal T}\left[\\{\tau\in\mathcal{V}({\cal
T})~{}|~{}v\in B_{\tau}\\}\right]$ (13)

is a connected sub-graph of ${\cal T}$ for every
$v\in\mathcal{V}(\mathcal{G})$.

(2) _Covering Property:_ for every edge $\\{u,v\\}\in\mathcal{E}(\mathcal{G})$
there exists a node $\tau\in\mathcal{V}({\cal T})$ such that $u,v\in
B_{\tau}$.

The simplest tree decomposition of any graph $\mathcal{G}$ is a tree with a
single node, whose bag contains all the nodes in $\mathcal{G}$. However, in
practical applications, it is desirable to obtain decompositions where the
size of the largest bag is small. This is captured by the notion of
_treewidth_. The treewidth of a tree decomposition $({\cal T},{\cal B})$ is
defined as the size of the largest bag minus one:

$\text{tw}\left[({\cal T},{\cal
B})\right]\triangleq\max_{\tau\in\mathcal{V}({\cal T})}|B_{\tau}|-1.$ (14)

The treewidth of a graph $\mathcal{G}$ is defined as the minimum treewidth
that can be achieved among all tree decompositions of $\mathcal{G}$. While
finding a tree decomposition with minimum treewidth is NP-hard, many
algorithms exist that generate tree decompositions with small (_i.e.,_ close
to the minimum attainable for that graph) treewidth [202, 22, 203, 32, 204].

One of the most popular tree decompositions is the _junction tree
decomposition_ , which was introduced in [205]. In it, the graph $\mathcal{G}$
is first triangulated. Triangulation is done by adding a chord between any two
nodes in every cycle of length $4$ or more. This eliminates all the cycles of
length $4$ or more in the graph $\mathcal{G}$ to produce a chordal graph
$\mathcal{G}_{c}$. The collection of bags ${\cal B}=\\{B_{\tau}\\}_{\tau}$ in
the junction tree is chosen as the set of all maximal cliques in the chordal
graph $\mathcal{G}_{c}$. Then, an _intersection graph_ ${\cal I}$ on ${\cal
B}$ is built, which has a node for every bag in ${\cal B}$ and an edge between
two bags $B_{\tau}$ and $B_{\mu}$ if they have a non-empty intersection,
_i.e.,_ $|B_{\tau}\cap B_{\mu}|\geq 1$. The weight of every link
$\\{\tau,\mu\\}$ in the intersection graph ${\cal I}$ is set to $|B_{\tau}\cap
B_{\mu}|$. Finally, the desired junction tree is obtained by extracting a
maximum-weight spanning tree on the weighted intersection graph ${\cal I}$. It
is know that this extracted tree ${\cal T}$, with the bag ${\cal B}$, is a
valid tree decomposition of $\mathcal{G}$ that satisfies the connectedness and
covering property.

###  A-B Proof of Proposition 3

The proposition provides an upper-bound on the treewidth of a hierarchical
graph. We can deduce this bound from Algorithm 1 by noting that: (i) all the
bags in the tree decomposition of an $\ell$-layered hierarchical graph are
nothing but the bags from the tree decomposition of either the layer-$\ell$
graph ${\cal G}[{\cal V}_{\ell}]$ or the graphs ${\cal G}[C(v)]$, for
$v\in{\cal V}$; and (ii) the size of the bags of all tree decompositions of
$C(v)$ are increased by one in Algorithm 1 of Algorithm 1. Since the treewidth
of a tree decompositions is defined as the size of its maximum bag minus one,
and since the treewidth of the graph is the minimum attainable by any possible
tree decompositions, the bound in eq. (5) follows.

###  A-C Proof of Lemma 4

Let ${\cal G}_{R}$ be the room graph, as described in the statement of the
theorem. We first note that the nodes in ${\cal G}_{R}$ that have degree one
are those rooms that connect to only one other room. If we were to remove all
the degree one rooms, in ${\cal G}_{R}$, and form another graph ${\cal
G}^{{}^{\prime}}_{R}$, then _(i) the treewidth ${\cal G}_{R}$ and ${\cal
G}^{{}^{\prime}}_{R}$ would be the same_. We can see this by noting that one
can form a tree decomposition for ${\cal G}_{R}$ by appending the tree
decomposition of ${\cal G}^{{}^{\prime}}_{R}$ with additional bags of size
$2$, representing the degree-one room node $v$ in ${\cal G}_{R}\backslash{\cal
G}^{{}^{\prime}}_{R}$ and its connecting room in ${\cal G}^{{}^{\prime}}_{R}$.
Now we note that _(ii) the treewidth of ${\cal G}^{{}^{\prime}}_{R}$ is always
bounded by two under the theorem’s assumptions_. This is because all nodes in
${\cal G}^{{}^{\prime}}_{R}$ have degree less than or equal to $2$ (by
assumption). And, hence, ${\cal G}^{{}^{\prime}}_{R}$ will never have a
complete graph of four nodes as a sub-graph. This is enough to conclude that
the graph ${\cal G}^{{}^{\prime}}_{R}$ will have a treewidth less than or
equal to $2$ [206].

###  A-D Object and Room Labels

Objects. For any configuration of Hydra that uses a 2D semantic segmentation
network as input, we use the following set of object labels, which is derived
from the mpcat40 label space [31]: _chair_ , _table_ , _picture_ , _cabinet_ ,
_cushion_ , _sofa_ , _bed_ , _curtain_ , _chest of drawers_ , _plant_ , _sink_
, _toilet_ , _stool_ , _towel_ , _mirror_ , _tv monitor_ , _bathtub_ ,
_fireplace_ , _lighting_ , _shelving_ , _blinds_ , _seating_ , _board panel_ ,
_furniture_ , _appliances_ , _clothes_ , _objects_. In addition, the following
labels are detected, but treated as structure: _wall_ , _floor_ , _door_ ,
_window_ , _stairs_ , _ceiling_ , _column_ , _counter_ , _railing_. We
manually construct a mapping from the ADE20k label space [68] that the 2D
semantic segmentation networks provide output in to this subset of the mpcat40
label space [31]. The ground truth segmentation for the uHumans2 dataset has a
smaller label space. For the apartment, we use the following set of object
labels: _chair_ , _couch_ , _computer_ , _lamp_ , _bed_ , _table_ ,
_trashcan_. For the office, we use the following set of object labels: _chair_
, _bench_ , _couch_ , _objects_ , _painting_ , _plant_ , _trashcan_. Both
scenes also have similar structure labels that are detected (_e.g.,_ _wall_ ,
_floor_ , _ceiling_).

Rooms. We predict a subset of the room category labels available in MP3D [31],
as we group several room category synonyms together. First, MP3D includes
several synonyms for “outdoor” regions in the provided ground-truth room
labels (_i.e.,_ _porch_ , _balcony_ , _outdoor_). As we only focus on indoor
applications, we group these outdoor labels with the original _unknown_ label
from MP3D, and ignore this label for both computing the training loss and
label accuracy. Additionally, we group _toilet_ and _bathroom_ together into a
single label (_bathroom_), and group _other room_ and _junk_ with _unknown_.
This gives us the following room label space: _bedroom_ , _closet_ , _dining
room_ , _lobby_ , _family room_ , _garage_ , _hallway_ , _library_ , _laundry
room_ , _kitchen_ , _living room_ , _conference room_ , _lounge_ , _office_ ,
_game room_ , _stairwell_ , _utility room_ , _theater_ , _gym_ , _balcony_ ,
_bar_ , _classroom_ , _dining booth_ , _spa_ , _bathroom_. Rooms that do not
meet the criteria for inference are given the label _unknown_.

###  A-E Graph Neural Network Training

We provide more details on (i) the pre-processing performed on the 3D scene
graphs in the MP3D dataset, (ii) the implementation of the examined
architectures, (iii) the training and testing runtime on the Stanford3d and
MP3D datasets, (iv) the approach we used for hyper-parameter tuning.

MP3D Graph Processing. Here we describe additional pre-processing steps that
we take to better condition the room classification training on the MP3D
dataset. For the room classification ablation in Section VI-C, we use the
ground-truth room geometry in MP3D to re-segment the places layer, and add
intra-layer edges between the re-segmented rooms as described in Section
III-D1. This allows us to disentangle the room classification accuracy from
potential errors in the room clustering. We then extract object-room graphs by
connecting room and object nodes through places nodes in between. We discard
all room nodes that both have no adjacent rooms and contain two or fewer
objects.

Implementation. We implement all graph learning architectures in PyTorch
Geometric [58], which supports all four types of message passing functions we
test on, as well as a heterogeneous data structure for learning on
heterogeneous graphs. We use the ReLU activation function and dropout in
between message passing operations unless otherwise specified. For semi-
supervised learning on homogeneous graphs, we send the final node hidden
states —after performing message passing— through a linear layer to project
embeddings to room and object label spaces separately, and then through
softmax layers for the final prediction. For the neural tree, we add an
additional mean pooling layer to combine leaf node hidden states after all
message passing iterations on the H-tree. For semi-supervised learning on
heterogeneous graphs and room classification on both graph types, we match the
hidden dimension of the last message passing iteration to the number of labels
and hence remove the final linear layers before softmax.

Message Passing | Original | H-tree
---|---|---
Training | Testing | Training | Testing
GCN | 0.087s | 0.021s | 0.135s | 0.035s
GraphSAGE | 0.083s | 0.020s | 0.127s | 0.033s
GAT | 0.092s | 0.022s | 0.169s | 0.042s
GIN | 0.088s | 0.020s | 0.132s | 0.033s
TABLE VIII: Stanford3d: training and testing runtimes. Graph Types | Original | H-tree
---|---|---
Training | Testing | Training | Testing
Homogeneous | absolute pos. | 0.092s | 0.022s | 0.169s | 0.042s
relative pos. | 0.100s | 0.023s | 0.181s | 0.045s
Heterogeneous | absolute pos. | 0.294s | 0.079s | 1.023s | 0.275s
relative pos. | 0.329s | 0.083s | 1.142s | 0.298s
TABLE IX: Stanford3d, GAT: training and testing runtimes for different graph types. Graph Types | Original | H-tree
---|---|---
Training | Testing | Training | Testing
w/o word2vec | w/o room edges | 1.915s | 0.216s | 6.106s | 0.704s
with room edges | 1.960s | 0.222s | 6.498s | 0.750s
with word2vec | w/o room edges | 2.020s | 0.261s | 6.637s | 0.906s
with room edges | 2.075s | 0.238s | 7.065s | 0.875s
TABLE X: MP3D, GAT: training and testing runtimes for different graph types.

Runtime. Here we report the time required for pre-processing the datasets, as
well as training and testing our models. We save all object-room scene graphs
with at least one room and one object node for both Stanford3d and MP3D
datasets. The total H-tree construction time is $2.8\text{\,}\mathrm{s}$ for
482 Stanford3d scene graphs with a maximum of $0.087\text{\,}\mathrm{s}$ for a
single graph. For the MP3D dataset the total H-tree construction time is
$516\text{\,}\mathrm{s}$ for a total of 6114 graphs, with a maximum of
$0.84\text{\,}\mathrm{s}$ for a graph. Table VIII reports the (per epoch)
train and test time for the standard GNN architectures —GCN, GraphSAGE, GAT,
GIN— and the corresponding neural trees on the homogeneous Stanford3d scene
graphs with the training batch size set to 128. Tables IX and X report timing
for the GAT architecture with various input scene graph types. We observe that
the neural tree takes 1.5 to 2 times as long compared to the corresponding
standard GNN for homogeneous graph inputs. This is expected as the neural tree
often uses more message passing iterations, and the H-trees are larger than
the original graphs. For heterogeneous graphs, the neural tree takes around
3.5 times as long, as heterogeneous H-trees are both larger than the
corresponding original graphs and contain more node and edge types.

Message Passing | iter. | hidden dim. | learning rate | regularization
---|---|---|---|---
GCN | Original | 3 | $64$ | 0.01 | 0.0
H-tree | 4 | $128$ | 0.01 | 0.0
GraphSAGE | Original | 3 | $128$ | 0.005 | 0.001
H-tree | 4 | $128$ | 0.005 | 0.001
GAT | Original | 2 | $128$ | 0.001 | 0.0001
H-tree | 4 | $128$ | 0.0005 | 0.0001
GIN | Original | 3 | $64$ | 0.005 | 0.001
H-tree | 4 | $128$ | 0.005 | 0.001
TABLE XI: Stanford3d: tuned hyper-parameters. Graph Types | heads | learning rate | dropout
---|---|---|---
w/o word2vec | Original | 5 | 0.001 | 0.2
H-tree | 5 | 0.001 | 0.2
with word2vec | Original | 3 | 0.002 | 0.4
H-tree | 3 | 0.002 | 0.4
TABLE XII: MP3D: tuned hyper-parameters.

Hyper-Parameter Tuning. For replicating the experiments in [16] on Stanford3d,
we tune hyper-parameters in the same order as [16], by searching over the
following sets:

  * •

Message passing iterations: [1, 2, 3, 4, 5, 6]

  * •

Message passing hidden size: [16, 32, 64, 128, 256]

  * •

Learning rate: [0.0005, 0.001, 0.005, 0.01]

  * •

Dropout probability: [0.25, 0.5, 0.75]

  * •

$L_{2}$ regularization strength: [0, 0.0001, 0.001, 0.01]

For both the standard GNN and the neural tree, the choice of the number of
message passing iterations, message passing hidden dimensions, and learning
rate has a significantly higher impact on accuracy than the other two hyper-
parameters. Therefore, these three hyper-parameters are first tuned using a
grid search while keeping dropout and $L_{2}$ regularization to the lowest
values. With these three hyper-parameters fixed, the dropout and $L_{2}$
regularization are then tuned via another grid search. A dropout ratio of 0.25
turns out to be the optimal choice in all cases. The other tuned hyper-
parameters —used in the experiment in Table II— are reported in Table XI. We
find the best hyper-parameters to be consistent with those reported in [16].
Any changes within the search space does not result in more than 0.5 standard
deviations of improvement.

Therefore, we use the same sets of hyper parameters as in [16] and report them
in Table XI. Apart from the four listed hyper-parameters, some architectures
(GAT, GraphSAGE, GIN) have architecture-specific design choices and hyper-
parameters. In the case of GAT, we use 6 attention heads with concatenated
output and ELU activation function (instead of ReLU) to be consistent with the
original paper. For GraphSAGE, we use the GraphSAGE-mean from the original
paper, which does mean-pooling after each convolution operation. In the case
of GIN, we use the more general GIN-$\epsilon$ for better performance. For the
additional ablation study in Table III, we keep the same hyper parameters,
though we set the hidden dimension to 64 for training on heterogeneous graphs.
We use the Adam optimizer and run optimization for 1000 epochs to achieve
reasonable convergence during training.

We use a similar hyper-parameter tuning procedure for experiments on MP3D. The
parameter range we explored are:

  * •

Message passing iterations: [2, 3, 4]

  * •

Message passing hidden size: [16, 32, 64, 128]

  * •

Number of attention heads: [1, 3, 5]

  * •

Learning rate: [0.0005, 0.001, 0.002]

  * •

Dropout probability: [0, 0.2, 0.4]

  * •

$L_{2}$ regularization strength: [0, 0.0001, 0.001]

For MP3D, all parameters except $L_{2}$ regularization have significant impact
on accuracy. Therefore, we perform grid search over these hyper parameters
first, and then tune $L_{2}$ regularization. For all setups with more than 1
attention head, we observe averaging over the output performs consistently
better than concatenation and therefore use the average when using multi-heads
attention. For both approaches, we tune separate sets of hyper parameters for
configurations with and without word2vec object semantic features. We reuse
these hyper parameters for configurations without room edges. Following this
approach, we find that 3 message passing iterations with a hidden dimension of
64 (for the first two iterations) and a $L_{2}$ regularization constant of
0.001 work best for all setups. The rest of hyper parameters are summarized in
Table XII. Training is run for 800 epochs of SGD using the Adam optimizer.

Message Passing | PyG version | Original | H-tree
---|---|---|---
GCN | $1.7.0^{*}$ | $40.88\pm 2.28\%$ | $\mathbf{50.63\pm 2.25\%}$
2.2.0 | $42.91\pm 2.01\%$ | $\mathbf{51.45\pm 2.00\%}$
GraphSAGE | $1.7.0^{*}$ | $59.54\pm 1.35\%$ | $\mathbf{63.57\pm 1.54\%}$
2.2.0 | $56.97\pm 2.02\%$ | $\mathbf{59.39\pm 2.10\%}$
GAT | $1.7.0^{*}$ | $46.56\pm 2.21\%$ | $\mathbf{62.16\pm 2.03\%}$
2.2.0 | $45.06\pm 2.32\%$ | $\mathbf{53.86\pm 2.06\%}$
GIN | $1.7.0^{*}$ | $49.25\pm 1.15\%$ | $\mathbf{63.53\pm 1.38\%}$
2.2.0 | $48.03\pm 2.21\%$ | $\mathbf{59.43\pm 2.12\%}$
TABLE XIII: Stanford3d: Node classification accuracy using different versions
of PyTorch Geometric and the tree decomposition from [16]. PyTorch Geometric
version 1.7.0 (starred in the table) corresponds to the version used by Talak
et al. [16]. Best results in bold.

###  A-F Additional Experiments on Semi-supervised Node Classification

The semi-supervised node classification experiment in Table II shows a
significant accuracy change compared to the same experiment in [16]. Our
implementation differs from [16] in two ways: the PyTorch Geometric version
used and the H-tree decomposition method. Here, we provide additional
experimental results with respect to these changes.

We use PyTorch Geometric 2.2.0 for the results in Table II, which has support
for heterogeneous GNN operators. The previous results from [16] used PyTorch
Geometric 1.7.0, which was the latest version at the time of publication. We
keep the tree decomposition the same as in [16] and re-run the neural tree
experiments using PyTorch Geometric 2.2.0. Table XIII compares the results
trained using different versions. While the advantage of using the neural tree
is retained, the table shows a significant accuracy penalty in moving from
PyTorch Geometric 1.7.0 to 2.2.0, especially for the neural tree. The only
exception is GCN, where there is a slight improvement for both networks. Using
GraphSAGE, GAT, and GIN message passing architecture, standard GNNs trained on
original graphs show 1 to 3% decrease in accuracy moving to PyTorch Geometric
2.2.0. For the neural tree models, there is about 4% accuracy drop using
GraphSAGE and GIN, and a more significant 8.3% drop using GAT. As a side note,
using the proposed tree decomposition, we are able to get comparable accuracy
using GAT on the H-tree with relative position feature representations,
compared to the approach in [16] (see Table III).

The neural tree results in Table XIII computed using PyTorch Geometric 2.2.0
and those in Table II also differ in the H-tree decomposition method. The
former computes a tree decomposition of the entire graph, while the later
breaks down hierarchical graphs into sub-graphs and then combines the
decomposed trees according to Algorithm 1. These results are within 0.5
standard deviations when we use GraphSAGE or GAT. The proposed tree
decomposition gains a 3.19% advantage with GCN, but a 4.43% disadvantage with
GIN. This could be due to the difference in the H-tree construction, or to the
PyTorch Geometric updates which make training certain message passing
architectures much more sensitive.

Overall, regardless of PyTorch Geometric versions and H-tree decomposition
methods, the neural tree maintains a clear advantage over standard GNNs on all
message passing architectures.

###  A-G Loop Closure Ablation Parameters

Table XIV reports key parameters used for “V-LC (Permissive)” and “V-LC
(Nominal)” in the loop closure ablation study in Fig. 16. For the meaning of
these parameters we refer the reader to the open-source Kimera implementation
from [2].

Parameter | V-LC (Permissive) | V-LC (Nominal)
---|---|---
L1 Score Threshold | 0.05 | 0.4
5pt RANSAC Inlier Threshold | $1\text{\times}{10}^{-5}$ | $1\text{\times}{10}^{-5}$
Lowe Matching Ratio | 0.9 | 0.9
TABLE XIV: Visual loop closure parameters.

Table XV reports key parameters used for “SG-LC” in the ablation study in Fig.
16. SG-LC does not use NSS (Normalized Similarity Scoring) to filter out
matches. As such, the matching threshold for the agent visual descriptors as
shown in Table XIV was chosen to produce similar numbers of matches at the
visual level as “V-LC (nominal)”. For the meaning of each parameter (and
details on other parameters), we refer the reader to our open-source
implementation at https://github.com/MIT-SPARK/Hydra.

Parameter | SG-LC
---|---
Agent L1 Match Threshold | 0.01
Object L1 Match Threshold | 0.3
Places L1 Match Threshold | 0.5
5pt RANSAC Inlier Threshold | $1\text{\times}{10}^{-6}$
Lowe Matching Ratio | 0.8
Object L1 Registration Threshold | 0.8
Object Minimum Inliers | 5
TEASER Noise Bound [m] | 0.1
TABLE XV: Scene graph loop closure parameters.

Finally, Table XVI reports key model parameters used for the GNN architecture
of “SG-GNN” in the ablation study in Fig. 16. In this table, we denote a
multi-layer perceptron (MLP) as
$\mathcal{M}\left(i,h_{1},h_{2},\ldots,h_{n},o\right)$, where $i$ is the input
feature size, $o$ is the last (_i.e.,_ output) layer size, and
$h_{1},h_{2}\ldots,h_{n}$ are the hidden layer sizes. All intermediate layers
are connected via a ReLU nonlinearity activation function. In our
architecture, the input node and edge features are passed through node and
edge MLP encoders and then fed through multiple iterations of message passing.
After message passing, the resulting node embedding are aggregated through
another MLP (Graph Aggregation in Table XVI), and then the final aggregated
result is passed through another MLP (Graph Transform in Table XVI). As we
follow the architecture from [60], we refer the reader to that paper for more
details.

Parameter | Places | Objects
---|---|---
Message Passing Iterations | 3 | 3
Message Passing Channels | 256 | 128
Edge Encoder | $\mathcal{M}\left(1,3,3,1\right)$ | $\mathcal{M}\left(1,3,3,1\right)$
Node Encoder | $\mathcal{M}\left(2,3,3\right)$ | $\mathcal{M}\left(43,128,64\right)$
Graph Aggregation | $\mathcal{M}\left(128,128\right)$ | $\mathcal{M}\left(128,128\right)$
Graph Transform | $\mathcal{M}\left(128,96,64,64\right)$ | $\mathcal{M}\left(128,96,64,64\right)$
TABLE XVI: Model Parameters for SG-GNN.

(a)

(b)

Figure 19: (a) Distribution of time difference in seconds between current and
matched agent poses for detected loop closures. (b) Distribution of rotation
angle in degrees between current and matched agent poses for detected loop
closures.

###  A-H Additional Loop Closure Experiments

Here we report additional results examining the properties of the loop closure
detection configurations presented in Fig. 16. In particular, we show two
different pieces of data for each loop closure that was detected over the five
trials: (i) the timestamp difference in seconds between the current pose of
the agent and the matched pose of the agent in Fig. 19a and (ii) the rotation
angle between the current pose of the agent and the matched pose of the agent
in Fig. 19b.

We note two important trends. One is that in Fig. 19a the vision-based loop
closure detection configurations (_i.e.,_ “V-LC (Nominal)” and “V-LC
(Permissive)”) are centered around $100\text{\,}\mathrm{s}$ and
$500\text{\,}\mathrm{s}$, which correspond to the portions of the recorded
data for the uHumans2 office scene where the robot revisits the same area in
the scene with a similar viewpoint. This is also supported by both vision-
based configurations having a rotation angle between the current and matched
pose centered around $0\text{\,}\mathrm{\SIUnitSymbolDegree}$ in Fig. 19b. In
contrast, both “SG-GNN” and “SG-LC” have a wider distribution of time
differences and rotation angles in Fig. 19a and Fig. 19b, suggesting an
improved viewpoint invariance.

Note that some of the loop closures resulting from “SG-GNN” and “SG-LC” have a
small time difference (see left-most part of Fig. 19a). In these cases, the
sub-graphs being registered often are not disjoint (_i.e.,_ a subset of nodes
is common to both), and the registration (via TEASER, as described in Section
IV-A) returns an identity pose between the two sub-graphs. This relative pose
already agrees with the current estimate of the relative pose between the
current and the match agent node, hence it does not provide any additional
information to the optimization (but does act to constrain the deformation of
the scene locally). Regardless, “SG-LC” and “SG-GNN” outperform vision-only
loop closures with respect to the overall system performance of Hydra.

The second trend to note is that “SG-GNN” has a wider distribution of time
differences than “SG-LC”, especially in the range of
$150\text{\,}\mathrm{s}250\text{\,}\mathrm{s}$. While many of the loop
closures detected by both of these configurations are from overlapping regions
of the scene graph, “SG-GNN” does appear to provide loop closures over a
slightly longer horizon than “SG-LC”.