USS-Nav: Unified Spatio-Semantic Scene Graph for Lightweight UAV Zero-Shot Object Navigation

3 min read

USS-Nav builds a four-layer scene graph (grid, topology, region, object) on board a small quadrotor and uses it for zero-shot object search, such as “find a sofa in the living room”. The topology layer grows by fitting polyhedra to free space in a rolling 8 m by 8 m by 4 m occupancy grid and linking neighbours. Regions come from Leiden community detection on the polyhedron graph, re-run only on new nodes plus their adjacent regions so region IDs stay stable. Objects come from YOLO-E open-vocabulary masks; Mobile-CLIP embeds the text of each predicted label into a 512-dimensional vector (the image crop is never encoded), and a new detection fuses with an old object if cosine similarity exceeds 0.75 with some point overlap, or if the two point clouds overlap strongly both ways. An LLM (Qwen-3 through its API) picks the next region from a JSON summary of regions, objects and visit history, and a TSP solver orders the frontiers inside that region.

Findings

  • Map updates run at 15 Hz on a Jetson Orin NX (16 GB) carried by a custom quadrotor with a Livox Mid-360 LiDAR (Fast-LIO2) and a RealSense D455. YOLO-E runs under TensorRT in FP16. The LLM is the only module that runs off the drone.
  • In the authors’ Marsim and Unity simulator, LLM region selection raised SPL by 146.61% on average over a frontier-utility baseline on complex multi-region tasks (5 trials per task). On simple single-room tasks the two performed about the same.
  • The comparison table quotes other systems’ update rates: Hydra 5 Hz on a Xavier NX, ApexNav 3 Hz on an RTX 4060, BeliefMapNav and SG-Nav below 1 Hz. These come from different papers and hardware.
  • Once built, the graph handles “I want to attend a meeting” by retrieving the meeting-room region and searching paths on the topology graph without re-exploring, and answers “Describe current area” from the objects inside a region. Both are shown qualitatively.

Limits

  • The LLM runs on an external server, so region decisions need a network link. The paper does not discuss link loss; its stated fallback (pure frontier utility) is for when semantic context is thin.
  • Room adjacency priors (a corridor connects to an office) are written by hand into a list and injected.
  • Each object is anchored to the topology node at the drone’s position when it was seen, so an object seen through a doorway can land in the wrong region.
  • Only the label embedding is stored, so two objects with the same label are told apart by geometry alone.
  • Real-flight results are qualitative, with no success rate or SPL. The comparison with other methods is a capability checklist, and its “GPS” column stands for global path searching.
  • Indoor multi-room scenes, one drone.

Relevance

USS-Nav comes nearest in the cluster to an open-vocabulary scene graph that fits on a small drone. It gets there by embedding labels instead of image crops, keeping only a local dense map and moving the LLM off board; it lists ConceptGraphs as offline and Hydra at 5 Hz for comparison. For a drone team the region and object layers are small enough to share, but Leiden region IDs are local to each drone, so matching regions across robots is an open question for multi-robot multimodal perception and aerial-swarms; see also open-vocabulary-mapping and language-grounded-planning.