# Reinforced Structured State-Evolution for Vision-Language Navigation

arXiv: https://arxiv.org/abs/2204.09280 · HTML: https://mlsanity.com/paper/2204.09280/

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 45 references that are in the map.
- First posted on arXiv 20 Apr 2022.

## Builds on (most cited first, 30 of 41)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks](https://mlsanity.com/paper/1506.01497/) (2015)
- [Visual Genome: Connecting Language and Vision Using Crowdsourced Dense Image Annotations](https://mlsanity.com/paper/1602.07332/) (2016)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Matterport3D: Learning from RGB-D Data in Indoor Environments](https://mlsanity.com/paper/1709.06158/) (2017)
- [Habitat: A Platform for Embodied AI Research](https://mlsanity.com/paper/1904.01201/) (2019)
- [Vision-and-Language Navigation: Interpreting visually-grounded navigation instructions in real environments](https://mlsanity.com/paper/1711.07280/) (2017)
- [ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks](https://mlsanity.com/paper/1912.01734/) (2019)
- [Bidirectional LSTM-CRF Models for Sequence Tagging](https://mlsanity.com/paper/1508.01991/) (2015)
- [Gibson Env: Real-World Perception for Embodied Agents](https://mlsanity.com/paper/1808.10654/) (2018)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Speaker-Follower Models for Vision-and-Language Navigation](https://mlsanity.com/paper/1806.02724/) (2018)
- [Reinforced Cross-Modal Matching and Self-Supervised Imitation Learning for Vision-Language Navigation](https://mlsanity.com/paper/1811.10092/) (2018)
- [A Recurrent Vision-and-Language BERT for Navigation](https://mlsanity.com/paper/2011.13922/) (2020)
- [Emergence of Grounded Compositional Language in Multi-Agent Populations](https://mlsanity.com/paper/1703.04908/) (2017)
- [Learning to Navigate Unseen Environments: Back Translation with Environmental Dropout](https://mlsanity.com/paper/1904.04195/) (2019)
- [Towards Learning a Generic Agent for Vision-and-Language Navigation via Pre-training](https://mlsanity.com/paper/2002.10638/) (2020)
- [RoboTHOR: An Open Simulation-to-Real Embodied AI Platform](https://mlsanity.com/paper/2004.06799/) (2020)
- [Vision-Language Navigation with Self-Supervised Auxiliary Reasoning Tasks](https://mlsanity.com/paper/1911.07883/) (2019)
- [Improving Vision-and-Language Navigation with Image-Text Pairs from the Web](https://mlsanity.com/paper/2004.14973/) (2020)
- [Self-Monitoring Navigation Agent via Auxiliary Progress Estimation](https://mlsanity.com/paper/1901.03035/) (2019)
- [Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs](https://mlsanity.com/paper/1705.05742/) (2017)
- [Stay on the Path: Instruction Fidelity in Vision-and-Language Navigation](https://mlsanity.com/paper/1905.12255/) (2019)
- [Airbert: In-domain Pretraining for Vision-and-Language Navigation](https://mlsanity.com/paper/2108.09105/) (2021)
- [The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation](https://mlsanity.com/paper/1903.01602/) (2019)
- [General Evaluation for Instruction Conditioned Navigation using Dynamic Time Warping](https://mlsanity.com/paper/1907.05446/) (2019)
- [Language and Visual Entity Relationship Graph for Agent Navigation](https://mlsanity.com/paper/2010.09304/) (2020)
- [Structured Scene Memory for Vision-Language Navigation](https://mlsanity.com/paper/2103.03454/) (2021)

## Built on by (most cited first, 30 of 37)

- [GridMM: Grid Memory Map for Vision-and-Language Navigation](https://mlsanity.com/paper/2307.12907/) (2023)
- [BEVBert: Multimodal Map Pre-training for Language-guided Navigation](https://mlsanity.com/paper/2212.04385/) (2022)
- [Scaling Data Generation in Vision-and-Language Navigation](https://mlsanity.com/paper/2307.15644/) (2023)
- [PanoGen: Text-Conditioned Panoramic Environment Generation for Vision-and-Language Navigation](https://mlsanity.com/paper/2305.19195/) (2023)
- [Target-Driven Structured Transformer Planner for Vision-Language Navigation](https://mlsanity.com/paper/2207.11201/) (2022)
- [A Survey on Graph Neural Networks and Graph Transformers in Computer Vision: A Task-Oriented Perspective](https://mlsanity.com/paper/2209.13232/) (2022)
- [NavMorph: A Self-Evolving World Model for Vision-and-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2506.23468/) (2025)
- [Multimodal Fusion and Vision-Language Models: A Survey for Robot Vision](https://mlsanity.com/paper/2504.02477/) (2025)
- [OctoNav: Towards Generalist Embodied Navigation](https://mlsanity.com/paper/2506.09839/) (2025)
- [Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing](https://mlsanity.com/paper/2208.08302/) (2022)
- [Grounded Entity-Landmark Adaptive Pre-training for Vision-and-Language Navigation](https://mlsanity.com/paper/2308.12587/) (2023)
- [Fast-Slow Test-Time Adaptation for Online Vision-and-Language Navigation](https://mlsanity.com/paper/2311.13209/) (2023)
- [Controllable Navigation Instruction Generation with Chain of Thought Prompting](https://mlsanity.com/paper/2407.07433/) (2024)
- [Bootstrapping Language-Guided Navigation Learning with Self-Refining Data Flywheel](https://mlsanity.com/paper/2412.08467/) (2024)
- [Omnidirectional Information Gathering for Knowledge Transfer-based Audio-Visual Navigation](https://mlsanity.com/paper/2308.10306/) (2023)
- [A Dual Semantic-Aware Recurrent Global-Adaptive Network For Vision-and-Language Navigation](https://mlsanity.com/paper/2305.03602/) (2023)
- [TopV-Nav: Unlocking the Top-View Spatial Reasoning Potential of MLLM for Zero-shot Object Navigation](https://mlsanity.com/paper/2411.16425/) (2024)
- [COSMO: Combination of Selective Memorization for Low-cost Vision-and-Language Navigation](https://mlsanity.com/paper/2503.24065/) (2025)
- [DOPE: Dual Object Perception-Enhancement Network for Vision-and-Language Navigation](https://mlsanity.com/paper/2505.00743/) (2025)
- [Advancing Audio-Visual Navigation Through Multi-Agent Collaboration in 3D Environments](https://mlsanity.com/paper/2509.22698/) (2025)
- [AeroDuo: Aerial Duo for UAV-based Vision and Language Navigation](https://mlsanity.com/paper/2508.15232/) (2025)
- [ESceme: Vision-and-Language Navigation with Episodic Scene Memory](https://mlsanity.com/paper/2303.01032/) (2023)
- [Graph based Environment Representation for Vision-and-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2301.04352/) (2023)
- [PASTS: Progress-Aware Spatio-Temporal Transformer Speaker For Vision-and-Language Navigation](https://mlsanity.com/paper/2305.11918/) (2023)
- [CogDDN: A Cognitive Demand-Driven Navigation with Decision Optimization and Dual-Process Thinking](https://mlsanity.com/paper/2507.11334/) (2025)
- [NavQ: Learning a Q-Model for Foresighted Vision-and-Language Navigation](https://mlsanity.com/paper/2510.16457/) (2025)
- [VISTAv2: World Imagination for Indoor Vision-and-Language Navigation](https://mlsanity.com/paper/2512.00041/) (2025)
- [Learning-To-Rank Approach for Identifying Everyday Objects Using a Physical-World Search Engine](https://mlsanity.com/paper/2312.15844/) (2023)
- [Trajectory-Diversity-Driven Robust Vision-and-Language Navigation](https://mlsanity.com/paper/2603.15370/) (2026)
- [CoMaTrack: Competitive Multi-Agent Game-Theoretic Tracking with Vision-Language-Action Models](https://mlsanity.com/paper/2603.22846/) (2026)

## Abstract (arXiv)

Vision-and-language Navigation (VLN) task requires an embodied agent to navigate to a remote location following a natural language instruction. Previous methods usually adopt a sequence model (e.g., Transformer and LSTM) as the navigator. In such a paradigm, the sequence model predicts action at each step through a maintained navigation state, which is generally represented as a one-dimensional vector. However, the crucial navigation clues (i.e., object-level environment layout) for embodied navigation task is discarded since the maintained vector is essentially unstructured. In this paper, we propose a novel Structured state-Evolution (SEvol) model to effectively maintain the environment layout clues for VLN. Specifically, we utilise the graph-based feature to represent the navigation state instead of the vector-based state. Accordingly, we devise a Reinforced Layout clues Miner (RLM) to mine and detect the most crucial layout graph for long-term navigation via a customised reinforcement learning strategy. Moreover, the Structured Evolving Module (SEM) is proposed to maintain the structured graph-based state during navigation, where the state is gradually evolved to learn the object-level spatial-temporal relationship. The experiments on the R2R and R4R datasets show that the proposed SEvol model improves VLN models' performance by large margins, e.g., +3% absolute SPL accuracy for NvEM and +8% for EnvDrop on the R2R test set.