Skip to content

Hierarchical Semantic-Augmented Navigation: Optimal Transport and Graph-Driven Reasoning for Vision-Language Navigation

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

HSAN (Hierarchical Semantic-Augmented Navigation) is a VLN-CE framework that combines a dynamically-built multi-level semantic scene graph, an optimal-transport-based goal planner grounded in Kantorovich duality, and a graph-convolutional RL controller for low-level action execution. It achieves state-of-the-art success rates on R2R-CE (64% SR) and RxR-CE (59% SR), outperforming the best prior baseline (LLaVA-Nav) by 6% absolute on both datasets.

Problem

Vision-Language Navigation in Continuous Environments (VLN-CE) fails in long-horizon tasks because: (1) existing methods use static or flat maps that lack hierarchical spatial context; (2) heuristic planners lack principled optimization when balancing semantic relevance against spatial cost; (3) low-level RL controllers without graph-structural awareness perform poorly at subgoal navigation and obstacle avoidance in cluttered scenes.

Method

HSAN operates as a three-module pipeline at each decision step:

  1. Hierarchical Semantic Scene Graph: Grounded-SAM detects objects from 12-view panoramic RGB-D; LLaVA-Onevision generates rich textual descriptions per object. Objects are clustered into regions via spectral clustering on a Gaussian-kernel similarity graph (combining spatial proximity and text-embedding cosine similarity, δ=1.5m geodesic threshold). Regions are aggregated into zones via connectivity; nodes carry SigLIP visual features. The graph is updated incrementally using Euclidean + feature-similarity matching.

  2. Optimal Transport-Based Topological Planner: Long-term goal selection is formulated as an OT problem between a uniform distribution over "ghost" (unexplored) nodes and a target distribution biased by semantic relevance. The cost matrix encodes geodesic distance plus an exploration penalty minus a semantic alignment score (max cosine similarity between BERT instruction tokens and node description). The Sinkhorn algorithm solves the OT efficiently; the node with maximum diagonal transport mass is selected as the goal. Theorem 3.1 (proved via Kantorovich duality) establishes optimality under mild continuity conditions.

  3. Graph-Aware Low-Level Controller: A 3-layer GCN encodes the local subgraph; its mean node embedding is concatenated with SigLIP visual features, agent pose, and next subgoal position into a state vector for a PPO policy. Rewards: +1 for subgoal reached, −0.01·distance otherwise, −1 for collision. A "Tryout" heuristic probes alternative headings (−90° to +90°) on collision. Training uses student-forcing with a joint OT planning loss + PPO loss (λ_RL=0.1).

Key Contributions

  • Dynamic hierarchical scene graph (object → region → zone) built online using VLMs and spectral clustering, replacing static or flat maps.
  • Optimal transport formulation for long-term goal selection with provable optimality guarantees via Kantorovich duality, solved efficiently via Sinkhorn's algorithm.
  • GCN-augmented PPO policy for low-level control that leverages local topological structure for obstacle avoidance and subgoal navigation.
  • SOTA results on R2R-CE and RxR-CE, including multilingual (Hindi, Telugu) and high-clutter subsets.

Results

  • R2R-CE val-unseen: SR=0.64, SPL=0.59, NE=3.28m, OSR=0.71 vs. best baseline LLaVA-Nav (SR=0.58, SPL=0.53, NE=3.62m).
  • RxR-CE val-unseen: SR=0.59, SPL=0.54, NE=3.76m, OSR=0.66 vs. LLaVA-Nav (SR=0.53, SPL=0.48, NE=4.08m).
  • RxR-CE multilingual subset (2,000 episodes): SR=0.57, SPL=0.52, NE=4.7m, OSR=0.62 vs. LLaVA-Nav (SR=0.51, SPL=0.47).
  • R2R-CE high-clutter subset (500 episodes): SR=0.61, SPL=0.56, NE=4.2m, OSR=0.66 vs. LLaVA-Nav (SR=0.54, SPL=0.50).
  • Ablations (R2R-CE val-unseen): Removing hierarchical graph −7% SR; removing OT planner −5% SR; removing graph-aware control −8% SR; removing VLM descriptions −6% SR.

Limitations

  • Real-time scene graph construction introduces significant computational overhead (inference at 5 FPS on a single GPU).
  • The diagonal cost matrix assumption in the OT formulation (C_ij=∞ for i≠j) reduces the OT problem to a weighted assignment, which may not exploit full distributional flexibility of transport plans.
  • Evaluated exclusively on indoor Matterport3D environments; no outdoor or sim-to-real transfer experiments.
  • Dynamic obstacles are not modeled; temporal reasoning for moving objects is listed as future work.
  • Multilingual support relies on XLM-RoBERTa-large; performance gap on non-English instructions (Hindi, Telugu) vs. English is not reported separately.

Relevance to Agentic AI / LLM Agents

HSAN directly exemplifies the core challenge of embodied agentic systems: grounding natural language instructions into sequential physical actions over long horizons in partially observable environments. The integration of VLMs as real-time scene describers (not just pretrained encoders) to build structured world representations is a pattern increasingly central to agentic architectures. The optimal transport planner demonstrates how rigorous mathematical frameworks can replace ad hoc heuristics in agent planning modules, offering a principled alternative to LLM chain-of-thought for spatial reasoning. For researchers tracking LLM agents, HSAN's modular decomposition—perception → structured world model → goal selection → execution—maps directly onto the perception-planning-action hierarchy debated in agentic AI system design.