Source-linked AI summary
Hierarchical Semantic-Augmented Navigation: Optimal Transport and Graph-Driven Reasoning for Vision-Language Navigation
Xiang Fang, Wanlong Fang, Changshuo Wang
TL;DR
VLN-CE remains difficult for long-horizon navigation because existing methods have limited scene understanding and inefficient planning. HSAN combines hierarchical semantic graphs, optimal-transport goal selection, and graph-aware control, achieving state-of-the-art results on R2R-CE and RxR-CE with improved success, efficiency, and generalization.
Problem
Existing VLN approaches struggle with long-horizon navigation because static maps, sparse rewards, and unstructured VLM representations limit adaptation and reasoning.
Method
HSAN integrates a dynamic VLM-based hierarchical scene graph, an optimal-transport topological planner, and a graph-aware reinforcement-learning controller.
Results
HSAN achieves state-of-the-art performance on R2R-CE and RxR-CE, with significant improvements in success rate, path efficiency, and generalization to unseen environments.
Takeaways & Limitations
The combined framework supports navigation of challenging instructions and cluttered spaces while addressing static maps, heuristic planners, and flat scene representations.
Abstract
from arXiv · showhide
Vision-Language Navigation in Continuous Environments (VLN-CE) poses a formidable challenge for autonomous agents, requiring seamless integration of natural language instructions and visual observations to navigate complex 3D indoor spaces. Existing approaches often falter in long-horizon tasks due to limited scene understanding, inefficient planning, and lack of robust decision-making frameworks. We introduce the \textbf{Hierarchical Semantic-Augmented Navigation (HSAN)} framework, a groundbreaking approach that redefines VLN-CE through three synergistic innovations. First, HSAN constructs a dynamic hierarchical semantic scene graph, leveraging vision-language models to capture multi-level environmental representations, from objects to regions to zones, enabling nuanced spatial reasoning. Second, it employs an optimal transport-based topological planner, grounded in Kantorovich's duality, to select long-term goals by balancing semantic relevance and spatial accessibility with theoretical guarantees of optimality. Third, a graph-aware reinforcement learning policy ensures precise low-level control, navigating subgoals while robustly avoiding obstacles. By integrating spectral graph theory, optimal transport, and advanced multi-modal learning, HSAN addresses the shortcomings of static maps and heuristic planners prevalent in prior work. Extensive experiments on multiple challenging VLN-CE datasets demonstrate that HSAN achieves state-of-the-art performance, with significant improvements in navigation success and generalization to unseen environments.
1 Introduction
HSAN targets long-horizon VLN-CE challenges by combining hierarchical scene understanding, optimal-transport planning, and graph-aware control. Its evaluations report state-of-the-art performance and generalization to unseen environments.
- VLN-CE requires agents to navigate continuous 3D environments using low-level actions while following natural-language instructions.
- Existing methods rely on static maps, struggle with sparse-reward long-horizon tasks, and often lack structured environmental representations.
- HSAN dynamically builds a hierarchical semantic scene graph spanning objects, regions, and zones using VLM-generated descriptions.
- Its optimal-transport planner selects long-term goals by balancing semantic relevance and spatial accessibility, while graph-aware reinforcement learning handles low-level control.
- The framework combines large-scale pre-training, student-forcing fine-tuning, and real-time inference strategies, with stated convergence and stability guarantees.
- HSAN is evaluated extensively on standard VLN-CE benchmarks and reports state-of-the-art performance with generalization to unseen environments.
2 Related Work
Related VLN work has moved from discrete navigation graphs toward continuous 3D environments and increasingly uses vision-language models. HSAN differs by combining hierarchical graph reasoning with planning and control without predefined graphs.
- VLN-CE extends earlier discrete navigation by requiring low-level actions in continuous 3D meshes.
- Vision-language models improve landmark recognition and instruction grounding but commonly process observations as flat representations.
- HSAN operates in continuous spaces without relying on predefined navigation graphs, supporting its stated suitability for real-world applications.
- Its scene graph represents objects, regions, and zones, adding structured hierarchical reasoning beyond prior VLM-based grounding methods.
3 Method
HSAN builds a dynamic hierarchical scene graph, uses optimal transport to select semantically relevant and accessible goals, and applies graph-aware reinforcement learning for subgoal control.
- Task Setup: VLN-CE is modeled as navigation through a continuous 3D mesh using forward, rotation, and stop actions guided by language instructions.
- Framework: HSAN iteratively constructs a scene graph, selects a long-term goal with optimal transport, computes a high-level path, and executes it through low-level actions.
- Hierarchical Semantic Scene Graph Construction: The scene graph contains object, region, and zone nodes connected by containment and spatial relationships, and is updated by matching new observations to existing nodes.
- Hierarchical Semantic Scene Graph Construction: Object nodes combine projected 3D coordinates, VLM-generated descriptions, and SigLIP visual features.
- Hierarchical Semantic Scene Graph Construction: Regions group spatially and semantically coherent objects using a 1.5m geodesic threshold and spectral clustering with Gaussian-kernel edge weights.
- Optimal Transport-Based Topological Planning: The planner scores instruction-node relevance, accounts for geodesic accessibility and exploration penalties, and solves an optimal-transport problem over ghost nodes.
- Optimal Transport-Based Topological Planning: Sinkhorn optimization selects the node with maximal transported self-mass, while the stated theorem links selection to minimum expected navigation cost under semantic constraints.
- Graph-Aware Low-Level Control: A graph-aware RL policy encodes visual features, local subgraph embeddings, pose, and the next subgoal before producing action probabilities.
4 Experiments
HSAN is evaluated on standard and specialized VLN-CE benchmarks, where it achieves state-of-the-art navigation performance and generalization. Ablations and temporal graph analysis examine the contributions of its hierarchical representation, optimal-transport planning, and graph-aware control.
- Experimental Setup: Experiments evaluate HSAN on R2R-CE and RxR-CE validation-unseen splits using SR, SPL, NE, and OSR.The evaluation also includes multilingual, high-clutter, temporal-dynamics, and ablation analyses.
- Main Results: HSAN achieves state-of-the-art results across all reported metrics on the R2R-CE and RxR-CE validation-unseen splits.The results indicate improvements in navigation success and efficiency over the evaluated baselines.
- Main Results: 64% SR and 0.59 SPL on R2R-CE surpass LLaVA-Nav by 6% absolute SR while indicating efficient path execution.HSAN also records 3.28m NE, 9.4% below LLaVA-Nav’s 3.62m, and 71% OSR.
- Main Results: 59% SR and 0.54 SPL on RxR-CE outperform LLaVA-Nav by 6% SR, while NE is 7.8% lower and OSR reaches 66%.These results are reported despite longer and multilingual instructions.
- Generalization: The RxR-CE multilingual subset reports 0.57 SR and 0.52 SPL, exceeding LLaVA-Nav’s 0.51 and 0.47 and GraphNav’s 0.49 and 0.45.The subset contains 2,000 validation-unseen episodes across English, Hindi, and Telugu.
- Temporal Graph Analysis: Figure 2 tracks hierarchical scene-graph node and edge updates over 200 timesteps, including object, region, and zone snapshots.Node types are colored blue, green, and red, respectively.
- Ablation Study: Removing hierarchical graph structure, optimal transport, graph-aware control, or VLM descriptions reduces performance, with SR drops of 7%, 5%, 8%, and 6%, respectively.The ablations replace the hierarchical graph with a flat graph, optimal transport with a heuristic planner, graph-aware RL with vanilla RL, and VLM descriptions with object labels.
- Generalization: HSAN reaches 61% SR on high-clutter R2R-CE episodes versus LLaVA-Nav’s 54%, while its multilingual SR is 57% versus 51% for LLaVA-Nav and 49% for GraphNav.These evaluations assess robustness across linguistic diversity and obstacle-rich environments.
5 Conclusion
HSAN addresses long-horizon VLN-CE in complex indoor settings by combining hierarchical semantic understanding, optimal-transport goal selection, and graph-aware low-level control. Experiments on R2R-CE and RxR-CE report state-of-the-art performance, improved efficiency, and generalization to unseen environments.
- HSAN integrates a hierarchical semantic scene graph, an optimal transport-based topological planner, and a graph-aware reinforcement learning policy.These components support multi-level environmental understanding, mathematically rigorous goal selection, and robust low-level control.
- HSAN uses vision-language models, spectral graph theory, and optimal transport to address limitations of static maps, heuristic planners, and flat scene representations.
- Experiments on R2R-CE and RxR-CE demonstrate state-of-the-art performance with improvements in success rate, path efficiency, and generalization to unseen environments.
- Qualitative analyses and ablation studies validate the synergistic contributions of HSAN’s components for navigating challenging instructions and cluttered spaces.
NeurIPS Paper Checklist
The checklist records affirmative assessments of the paper’s claim alignment, reproducibility information, experimental detail, statistical reporting, theoretical assumptions and proofs, and societal-impact discussion, while noting that code and data were not released at submission.
- Claims and scope: The abstract and introduction accurately reflect the paper’s contributions, scope, methodologies, and subsequent findings.
- Limitations and societal impact: The checklist states that the paper discusses its limitations and potential positive and negative societal impacts.
- Theory assumptions and proofs: Theoretical results state necessary assumptions and provide complete, logically sound proofs in the main text or appendix.
- Reproducibility: The paper fully discloses methodology, settings, and parameters needed to reproduce its main experimental results.
- Open access to data and code: Code and data were not released at submission time to preserve anonymity, despite the paper’s stated reproducibility information.
- Experimental setting: Training and test details, including data splits, hyperparameters, selection rationale, and optimizer type, are specified.
- Statistical significance: The paper reports appropriate information about experimental statistical significance.