# GC-VLN: Instruction as Graph Constraints for Training-free Vision-and-Language Navigation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 46 references that are in the map.
- First posted on arXiv 12 Sep 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [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)
- [On Evaluation of Embodied Navigation Agents](https://mlsanity.com/paper/1807.06757/) (2018)
- [Beyond the Nav-Graph: Vision-and-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2004.02857/) (2020)
- [Room-Across-Room: Multilingual Vision-and-Language Navigation with Dense Spatiotemporal Grounding](https://mlsanity.com/paper/2010.07954/) (2020)
- [NavGPT: Explicit Reasoning in Vision-and-Language Navigation with Large Language Models](https://mlsanity.com/paper/2305.16986/) (2023)
- [NaVid: Video-based VLM Plans the Next Step for Vision-and-Language Navigation](https://mlsanity.com/paper/2402.15852/) (2024)
- [Towards Learning a Generic Agent for Vision-and-Language Navigation via Pre-training](https://mlsanity.com/paper/2002.10638/) (2020)
- [CoWs on Pasture: Baselines and Benchmarks for Language-Driven Zero-Shot Object Navigation](https://mlsanity.com/paper/2203.10421/) (2022)
- [ZSON: Zero-Shot Object-Goal Navigation using Multimodal Goal Embeddings](https://mlsanity.com/paper/2206.12403/) (2022)
- [ETPNav: Evolving Topological Planning for Vision-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2304.03047/) (2023)
- [Bridging the Gap Between Learning in Discrete and Continuous Environments for Vision-and-Language Navigation](https://mlsanity.com/paper/2203.02764/) (2022)
- [ESC: Exploration with Soft Commonsense Constraints for Zero-shot Object Navigation](https://mlsanity.com/paper/2301.13166/) (2023)
- [GridMM: Grid Memory Map for Vision-and-Language Navigation](https://mlsanity.com/paper/2307.12907/) (2023)
- [L3MVN: Leveraging Large Language Models for Visual Target Navigation](https://mlsanity.com/paper/2304.05501/) (2023)
- [Topological Planning with Transformers for Vision-and-Language Navigation](https://mlsanity.com/paper/2012.05292/) (2020)
- [Discuss Before Moving: Visual Language Navigation via Multi-expert Discussions](https://mlsanity.com/paper/2309.11382/) (2023)
- [SG-Nav: Online 3D Scene Graph Prompting for LLM-based Zero-shot Object Navigation](https://mlsanity.com/paper/2410.08189/) (2024)
- [General Evaluation for Instruction Conditioned Navigation using Dynamic Time Warping](https://mlsanity.com/paper/1907.05446/) (2019)
- [NavGPT-2: Unleashing Navigational Reasoning Capability for Large Vision-Language Models](https://mlsanity.com/paper/2407.12366/) (2024)
- [Sim-to-Real Transfer for Vision-and-Language Navigation](https://mlsanity.com/paper/2011.03807/) (2020)
- [Sim-2-Sim Transfer for Vision-and-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2204.09667/) (2022)
- [Weakly-Supervised Multi-Granularity Map Learning for Vision-and-Language Navigation](https://mlsanity.com/paper/2210.07506/) (2022)
- [MapGPT: Map-Guided Prompting with Adaptive Path Planning for Vision-and-Language Navigation](https://mlsanity.com/paper/2401.07314/) (2024)
- [DREAMWALKER: Mental Planning for Continuous Vision-Language Navigation](https://mlsanity.com/paper/2308.07498/) (2023)
- [Bridging Zero-shot Object Navigation and Foundation Models through Pixel-Guided Navigation Skill](https://mlsanity.com/paper/2309.10309/) (2023)
- [Bird's-Eye-View Scene Graph for Vision-Language Navigation](https://mlsanity.com/paper/2308.04758/) (2023)

## Built on by (most cited first, 10 of 10)

- [Qwen-RobotNav Technical Report: A Scalable Navigation Model Designed for an Agentic Navigation System](https://mlsanity.com/paper/2606.18112/) (2026)
- [UnderwaterVLA: Dual-brain Vision-Language-Action architecture for Autonomous Underwater Navigation](https://mlsanity.com/paper/2509.22441/) (2025)
- [Uni-LaViRA: Language-Vision-Robot Actions Translation for Unified Embodied Navigation](https://mlsanity.com/paper/2605.27582/) (2026)
- [SpaceVLN: A Zero-Shot Vision-and-Language Navigation Agent with Online Spatial Cognitive Memory and Reasoning](https://mlsanity.com/paper/2606.08992/) (2026)
- [A Comprehensive Survey and Systematic Real-World Evaluation of Embodied Vision-and-Language Navigation](https://mlsanity.com/paper/2607.09792/) (2026)
- [Navi-Agent: Unlocalized Monocular Navigation Agent](https://mlsanity.com/paper/2609.20388/) (2026)
- [Rule-VLN: Bridging Perception and Compliance via Semantic Reasoning and Geometric Rectification](https://mlsanity.com/paper/2604.16993/) (2026)
- [NoPA: Non-Parametric Online 3D Scene Graph Generation](https://mlsanity.com/paper/2607.00529/) (2026)
- [CGFM-Nav: Cognitive Graph-Field Memory for Semantic-Guided Lifelong Multimodal Embodied Navigation](https://mlsanity.com/paper/2608.29114/) (2026)
- [One MLLM, One Call: Efficient Zero-Shot Vision-and-Language Navigation via Spatial-Aware Waypoints](https://mlsanity.com/paper/2609.06476/) (2026)

## Abstract (arXiv)

In this paper, we propose a training-free framework for vision-and-language navigation (VLN). Existing zero-shot VLN methods are mainly designed for discrete environments or involve unsupervised training in continuous simulator environments, which makes it challenging to generalize and deploy them in real-world scenarios. To achieve a training-free framework in continuous environments, our framework formulates navigation guidance as graph constraint optimization by decomposing instructions into explicit spatial constraints. The constraint-driven paradigm decodes spatial semantics through constraint solving, enabling zero-shot adaptation to unseen environments. Specifically, we construct a spatial constraint library covering all types of spatial relationship mentioned in VLN instructions. The human instruction is decomposed into a directed acyclic graph, with waypoint nodes, object nodes and edges, which are used as queries to retrieve the library to build the graph constraints. The graph constraint optimization is solved by the constraint solver to determine the positions of waypoints, obtaining the robot's navigation path and final goal. To handle cases of no solution or multiple solutions, we construct a navigation tree and the backtracking mechanism. Extensive experiments on standard benchmarks demonstrate significant improvements in success rate and navigation efficiency compared to state-of-the-art zero-shot VLN methods. We further conduct real-world experiments to show that our framework can effectively generalize to new environments and instruction sets, paving the way for a more robust and autonomous navigation framework.