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 is a VLN-CE framework that combines a dynamically-built hierarchical semantic scene graph (object→region→zone), an optimal transport (OT)-based topological planner, and a GCN-augmented PPO policy for low-level control. On R2R-CE validation unseen, it achieves 64% SR and 0.59 SPL, outperforming the strongest baseline (LLaVA-Nav) by 6% absolute SR. The OT planner provides formal optimality guarantees via Kantorovich duality.

Problem

VLN-CE agents fail on long-horizon tasks because: (1) static/flat maps cannot adapt to instruction-specific semantics; (2) heuristic planners lack rigorous mechanisms to balance semantic relevance with spatial cost; (3) vanilla RL controllers without topological context struggle with obstacle avoidance and subgoal chaining in continuous 3D meshes.

Method

Hierarchical Semantic Scene Graph. At each step, Grounded-SAM detects objects from 12-view RGB-D panoramas. Objects are clustered into regions via spectral clustering on a Gaussian-kernel similarity graph (combining Euclidean distance and cosine similarity of LLaVA-Onevision-generated text descriptions, δ=1.5m geodesic threshold). Regions are aggregated into zones using connectivity-based grouping, also VLM-verified. Nodes carry SigLIP visual features; the graph is updated incrementally via a localization function comparing Euclidean distance and feature similarity.

Optimal Transport Planner. Goal selection over "ghost" (unexplored-but-observed) nodes is formulated as an OT problem. The cost matrix C is diagonal: C_ii = dist(n_i, P_t) + 0.5·ρ_i − 1.0·s_i, where s_i is the max cosine alignment between BERT-encoded instruction tokens and the node description, and ρ_i is an exploration penalty. Sinkhorn's algorithm solves the OT problem; the goal n* = argmax_i T_ii. Dijkstra on the scene graph then produces a topological path.

Graph-Aware RL Control. A GCN (3 layers, pre-trained on Matterport3D connectivity prediction) encodes the local subgraph. State = [SigLIP visual features; mean GCN node embeddings; pose; next subgoal position]. PPO trains the policy with rewards +1.0 (subgoal reached), −0.01·dist (step penalty), −1.0 (collision). A "Tryout" heuristic rotates heading in ±{15°,...,90°} increments on collision.

Training. Student-forcing on R2R-CE/RxR-CE; joint loss = cross-entropy on teacher actions + 0.1×PPO loss. 8×A100 GPUs, 100k episodes.

Key Contributions

• Dynamic hierarchical semantic scene graph (object/region/zone levels) built online using VLM descriptions and spectral clustering
• OT-based topological planner with theoretical optimality guarantee (Kantorovich duality) via Sinkhorn algorithm
• GCN-augmented PPO low-level controller using subgraph embeddings for obstacle-aware subgoal navigation
• State-of-the-art on R2R-CE and RxR-CE including multilingual (English/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, OSR=0.65); +6% SR, −9.4% NE
• 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); +6% SR
• RxR-CE multilingual (2,000 eps): 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 (500 eps): SR=0.61, SPL=0.56, NE=4.2m vs. LLaVA-Nav (SR=0.54, SPL=0.50)
• Ablation (R2R-CE): removing hierarchical graph −7% SR; removing OT planner −5% SR; removing graph-aware control −8% SR; removing VLM descriptions −6% SR

Limitations

• Real-time hierarchical graph construction incurs significant computational overhead; inference runs at only 5 FPS on a single GPU
• OT cost matrix is diagonal (C_ij=∞ for i≠j), which simplifies the transport problem substantially and weakens the theoretical generality of the OT framing
• Evaluated only in simulated indoor environments (Matterport3D/Habitat); no real-robot or outdoor experiments
• Temporal reasoning for dynamic obstacles is absent; noted as future work
• Multilingual support relies on XLM-RoBERTa-large but the paper does not analyze failure modes per language

Relevance to Vision-Language Models

HSAN demonstrates a concrete pattern for using VLMs (LLaVA-Onevision, SigLIP) not just for flat instruction-observation alignment but as structured scene annotators feeding a symbolic graph—a direction relevant to embodied VLM research. The hierarchical graph bridges the gap between raw VLM outputs and formal planning algorithms, illustrating how grounding can be made spatially compositional. For researchers tracking VLMs, the OT-based alignment between language and environmental nodes offers a rigorous alternative to cross-attention softmax scoring. The work also benchmarks multilingual instruction following with VLMs in navigation, a relatively underexplored dimension of VLM generalization.