GROKE: Vision-Free Navigation Instruction Evaluation via Graph Reasoning on OpenStreetMap

• URL: http://arxiv.org/abs/2601.07375v1
• Date: Mon, 12 Jan 2026 09:56:47 GMT
• Title: GROKE: Vision-Free Navigation Instruction Evaluation via Graph Reasoning on OpenStreetMap
• Authors: Farzad Shami, Subhrasankha Dey, Nico Van de Weghe, Henrikki Tenkanen,
• Abstract summary: This paper introduces GROKE(Graph-based Reasoning over OSM Knowledge for instruction Evaluation), a vision-free training framework for evaluating OpenStreetMap data.<n>Our hierarchical architecture combines sub-instruction planning with topological graph navigation, reducing navigation error by 68.5% compared to sampling baselines on the Map2Seq dataset.
• Score: 2.4382430407654767
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The evaluation of navigation instructions remains a persistent challenge in Vision-and-Language Navigation (VLN) research. Traditional reference-based metrics such as BLEU and ROUGE fail to capture the functional utility of spatial directives, specifically whether an instruction successfully guides a navigator to the intended destination. Although existing VLN agents could serve as evaluators, their reliance on high-fidelity visual simulators introduces licensing constraints and computational costs, and perception errors further confound linguistic quality assessment. This paper introduces GROKE(Graph-based Reasoning over OSM Knowledge for instruction Evaluation), a vision-free training-free hierarchical LLM-based framework for evaluating navigation instructions using OpenStreetMap data. Through systematic ablation studies, we demonstrate that structured JSON and textual formats for spatial information substantially outperform grid-based and visual graph representations. Our hierarchical architecture combines sub-instruction planning with topological graph navigation, reducing navigation error by 68.5% compared to heuristic and sampling baselines on the Map2Seq dataset. The agent's execution success, trajectory fidelity, and decision patterns serve as proxy metrics for functional navigability given OSM-visible landmarks and topology, establishing a scalable and interpretable evaluation paradigm without visual dependencies. Code and data are available at https://anonymous.4open.science/r/groke.

Related papers

• TagaVLM: Topology-Aware Global Action Reasoning for Vision-Language Navigation [70.23578202012048]
  Vision-Language Navigation (VLN) presents a unique challenge for Large Vision-Language Models (VLMs) due to their inherent architectural mismatch.<n>We propose TagaVLM (Topology-Aware Global Action reasoning), an end-to-end framework that explicitly injects topological structures into the VLM backbone.<n>To enhance topological node information, an Interleaved Navigation Prompt strengthens node-level visual-text alignment.<n>With the embedded topological graph, the model is capable of global action reasoning, allowing for robust path correction.
  arXiv  Detail & Related papers  (2026-03-03T13:28:07Z)
• RSRNav: Reasoning Spatial Relationship for Image-Goal Navigation [57.197881161006904]
  Recent image-goal navigation (ImageNav) methods learn a perception-action policy by separately capturing semantic features of the goal and egocentric images.<n>We propose RSRNav, a simple yet effective method that reasons spatial relationships between the goal and current observations as navigation guidance.
  arXiv  Detail & Related papers  (2025-04-25T00:22:17Z)
• TopV-Nav: Unlocking the Top-View Spatial Reasoning Potential of MLLM for Zero-shot Object Navigation [52.422619828854984]
  We introduce TopV-Nav, an MLLM-based method that directly reasons on the top-view map with sufficient spatial information.<n>To fully unlock the MLLM's spatial reasoning potential in top-view perspective, we propose the Adaptive Visual Prompt Generation (AVPG) method.
  arXiv  Detail & Related papers  (2024-11-25T14:27:55Z)
• PRET: Planning with Directed Fidelity Trajectory for Vision and Language Navigation [30.710806048991923]
  Vision and language navigation is a task that requires an agent to navigate according to a natural language instruction. Recent methods predict sub-goals on constructed topology map at each step to enable long-term action planning. We propose an alternative method that facilitates navigation planning by considering the alignment between instructions and directed fidelity trajectories.
  arXiv  Detail & Related papers  (2024-07-16T08:22:18Z)
• Into the Unknown: Generating Geospatial Descriptions for New Environments [18.736071151303726]
  Rendezvous task requires reasoning over allocentric spatial relationships. Using opensource descriptions paired with coordinates (e.g., Wikipedia) provides training data but suffers from limited spatially-oriented text. We propose a large-scale augmentation method for generating high-quality synthetic data for new environments.
  arXiv  Detail & Related papers  (2024-06-28T14:56:21Z)
• TAS: A Transit-Aware Strategy for Embodied Navigation with Non-Stationary Targets [55.09248760290918]
  We present a novel algorithm for navigation in dynamic scenarios with non-stationary targets.<n>Our novel Transit-Aware Strategy (TAS) enriches embodied navigation policies with object path information.<n> TAS improves performance in non-stationary environments by rewarding agents for synchronizing their routes with target routes.
  arXiv  Detail & Related papers  (2024-03-14T22:33:22Z)
• NavCoT: Boosting LLM-Based Vision-and-Language Navigation via Learning Disentangled Reasoning [97.88246428240872]
  Vision-and-Language Navigation (VLN), as a crucial research problem of Embodied AI, requires an embodied agent to navigate through complex 3D environments following natural language instructions.<n>Recent research has highlighted the promising capacity of large language models (LLMs) in VLN by improving navigational reasoning accuracy and interpretability.<n>This paper introduces a novel strategy called Navigational Chain-of-Thought (NavCoT), where we fulfill parameter-efficient in-domain training to enable self-guided navigational decision.
  arXiv  Detail & Related papers  (2024-03-12T07:27:02Z)
• Aligning Knowledge Graph with Visual Perception for Object-goal Navigation [16.32780793344835]
  We propose the Aligning Knowledge Graph with Visual Perception (AKGVP) method for object-goal navigation. Our approach introduces continuous modeling of the hierarchical scene architecture and leverages visual-language pre-training to align natural language description with visual perception. The integration of a continuous knowledge graph architecture and multimodal feature alignment empowers the navigator with a remarkable zero-shot navigation capability.
  arXiv  Detail & Related papers  (2024-02-29T06:31:18Z)
• Learning Navigational Visual Representations with Semantic Map Supervision [85.91625020847358]
  We propose a navigational-specific visual representation learning method by contrasting the agent's egocentric views and semantic maps. Ego$2$-Map learning transfers the compact and rich information from a map, such as objects, structure and transition, to the agent's egocentric representations for navigation.
  arXiv  Detail & Related papers  (2023-07-23T14:01:05Z)
• NavGPT: Explicit Reasoning in Vision-and-Language Navigation with Large Language Models [17.495162643127003]
  We introduce the NavGPT to reveal the reasoning capability of GPT models in complex embodied scenes. NavGPT takes the textual descriptions of visual observations, navigation history, and future explorable directions as inputs to reason the agent's current status. We show that NavGPT is capable of generating high-quality navigational instructions from observations and actions along a path.
  arXiv  Detail & Related papers  (2023-05-26T14:41:06Z)
• BEVBert: Multimodal Map Pre-training for Language-guided Navigation [75.23388288113817]
  We propose a new map-based pre-training paradigm that is spatial-aware for use in vision-and-language navigation (VLN) We build a local metric map to explicitly aggregate incomplete observations and remove duplicates, while modeling navigation dependency in a global topological map. Based on the hybrid map, we devise a pre-training framework to learn a multimodal map representation, which enhances spatial-aware cross-modal reasoning thereby facilitating the language-guided navigation goal.
  arXiv  Detail & Related papers  (2022-12-08T16:27:54Z)
• Lifelong Topological Visual Navigation [16.41858724205884]
  We propose a learning-based visual navigation method with graph update strategies that improve lifelong navigation performance over time. We take inspiration from sampling-based planning algorithms to build image-based topological graphs, resulting in sparser graphs yet with higher navigation performance compared to baseline methods. Unlike controllers that learn from fixed training environments, we show that our model can be finetuned using a relatively small dataset from the real-world environment where the robot is deployed.
  arXiv  Detail & Related papers  (2021-10-16T06:16:14Z)
• SOON: Scenario Oriented Object Navigation with Graph-based Exploration [102.74649829684617]
  The ability to navigate like a human towards a language-guided target from anywhere in a 3D embodied environment is one of the 'holy grail' goals of intelligent robots. Most visual navigation benchmarks focus on navigating toward a target from a fixed starting point, guided by an elaborate set of instructions that depicts step-by-step. This approach deviates from real-world problems in which human-only describes what the object and its surrounding look like and asks the robot to start navigation from anywhere.
  arXiv  Detail & Related papers  (2021-03-31T15:01:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.