Foundations of Spatial Perception for Robotics: Hierarchical Representations and Real-time Systems

3 min read

The journal version of Hydra adds the theory for why maps should be hierarchical and rebuilds two of Hydra’s heuristics. The argument has two parts. Memory: a flat voxel map storing L labels per voxel costs O(L·V/δ³), while a hierarchy stores each symbol once (a toy 336-cell example drops from 1680 stored symbols to 355 symbols plus 354 edges, losslessly). Inference: a “hierarchical graph” (single parent, edges only within or between adjacent layers, disjoint children) has treewidth bounded by the worst layer, and the object-room-building graph has treewidth at most 1 + the largest number of objects in one room, independent of building size. That bound is what lets them run a neural tree (a GNN that passes messages over a tree decomposition) to label rooms in real time. Rooms are now clustered with persistent homology (pick the number of rooms that stays stable longest across dilation distances in 0.5 to 1.2 m), and loop-closure descriptors can be learned GNN embeddings of object and place subgraphs.

Findings

  • On the 90 Matterport3D scenes, measured room-graph treewidth is at most 2 and object-graph treewidth stays below 20, matching the lemmas.
  • Against SceneGraphFusion on uHumans2 with ground-truth poses: Hydra (OneFormer semantics) reaches 68.4/53.6% correct/found on Apartment and 71.6/60.4% on Office, against 25.0/17.9% and 35.4/36.0% for SceneGraphFusion. With ground-truth semantics Hydra reaches 95.5/82.1% and 86.5/83.3%.
  • With ground-truth poses, objects are 80 to 100% found and correct on the Office scene and 70 to 80% on the real SidPac and Simmons datasets. Scene-graph loop closures help most in the large SidPac building.
  • The neural tree beats standard GNNs by 1.63 to 11.72% on Stanford3D node classification depending on message-passing type; adding object labels as word2vec features lifts room classification by 14 to 17% on MP3D.
  • End-to-end room labelling is still weak: 15.3% to 47.7% accuracy across uHumans2, SidPac and Simmons depending on the segmentation network. Out-of-distribution scenes (Office, Simmons) do worst.
  • Memory on SidPac Floors 1 to 3: 74.1 MB for Hydra’s active window against 422 MB for Kimera’s whole-scene volumetric model. Batch Kimera takes over five minutes to rebuild the graph.
  • Runs onboard a Unitree A1 on a Xavier NX at a nominal 1 Hz frontend rate (objects 83.9 ± 65 ms, places 114.8 ± 103 ms, rooms 34.7 ± 37.6 ms), with T265 odometry and no appearance descriptors.

Limits

  • The authors list three: places ignore terrain type and slope, so traversability for ground robots outdoors is not captured; geometric room clustering fails on open floor plans; and inference is bottom-up only, with no route for room-level beliefs to correct the mesh.
  • The treewidth bound depends on the “disjoint children” assumption (no edges between objects in different rooms). Real relations such as “the cable runs from this desk to that one” would break it.
  • Single robot, single building, static scene. Ground truth for the real datasets comes from LiDAR SLAM or hand-tuned pose graphs.
  • Learned components (room classifier, GNN descriptors) are trained on MP3D and degrade off-distribution, which the room-accuracy table shows plainly.
  • Object labels are closed-set (ADE20k). The authors note a larger vocabulary helps room classification and point to open-set segmentation as future work.

Relevance

The treewidth result gives a formal argument for why 3D scene graphs are layered at all, and it applies to multi-robot fusion: a merged graph keeps the bound only if it still satisfies single-parent and disjoint-children, and a wrong cross-robot object match can hand one object two parent rooms. See multi-robot perception and long-term autonomy, where graphs grow for weeks.