# General Evaluation for Instruction Conditioned Navigation using Dynamic Time Warping

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

## Key facts

- Cited by 105 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2019.

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

- [History Aware Multimodal Transformer for Vision-and-Language Navigation](https://mlsanity.com/paper/2110.13309/) (2021)
- [Think Global, Act Local: Dual-scale Graph Transformer for Vision-and-Language Navigation](https://mlsanity.com/paper/2202.11742/) (2022)
- [ETPNav: Evolving Topological Planning for Vision-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2304.03047/) (2023)
- [Genie Envisioner: A Unified World Foundation Platform for Robotic Manipulation](https://mlsanity.com/paper/2508.05635/) (2025)
- [Bridging the Gap Between Learning in Discrete and Continuous Environments for Vision-and-Language Navigation](https://mlsanity.com/paper/2203.02764/) (2022)
- [BEVBert: Multimodal Map Pre-training for Language-guided Navigation](https://mlsanity.com/paper/2212.04385/) (2022)
- [AerialVLN: Vision-and-Language Navigation for UAVs](https://mlsanity.com/paper/2308.06735/) (2023)
- [SOON: Scenario Oriented Object Navigation with Graph-based Exploration](https://mlsanity.com/paper/2103.17138/) (2021)
- [Pathdreamer: A World Model for Indoor Navigation](https://mlsanity.com/paper/2105.08756/) (2021)
- [Vision-and-Language Navigation: A Survey of Tasks, Methods, and Future Directions](https://mlsanity.com/paper/2203.12667/) (2022)
- [Scaling Data Generation in Vision-and-Language Navigation](https://mlsanity.com/paper/2307.15644/) (2023)
- [NavGPT-2: Unleashing Navigational Reasoning Capability for Large Vision-Language Models](https://mlsanity.com/paper/2407.12366/) (2024)
- [Language-Aligned Waypoint (LAW) Supervision for Vision-and-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2109.15207/) (2021)
- [EnvEdit: Environment Editing for Vision-and-Language Navigation](https://mlsanity.com/paper/2203.15685/) (2022)
- [NavCoT: Boosting LLM-Based Vision-and-Language Navigation via Learning Disentangled Reasoning](https://mlsanity.com/paper/2403.07376/) (2024)
- [Vision-and-Language Navigation Today and Tomorrow: A Survey in the Era of Foundation Models](https://mlsanity.com/paper/2407.07035/) (2024)
- [Vision-Language Navigation with Random Environmental Mixup](https://mlsanity.com/paper/2106.07876/) (2021)
- [HOP: History-and-Order Aware Pre-training for Vision-and-Language Navigation](https://mlsanity.com/paper/2203.11591/) (2022)
- [Neighbor-view Enhanced Model for Vision and Language Navigation](https://mlsanity.com/paper/2107.07201/) (2021)
- [SASRA: Semantically-aware Spatio-temporal Reasoning Agent for Vision-and-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2108.11945/) (2021)
- [Retrospectives on the Embodied AI Workshop](https://mlsanity.com/paper/2210.06849/) (2022)
- [Improving Vision-and-Language Navigation by Generating Future-View Image Semantics](https://mlsanity.com/paper/2304.04907/) (2023)
- [NavMorph: A Self-Evolving World Model for Vision-and-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2506.23468/) (2025)
- [Learning Navigational Visual Representations with Semantic Map Supervision](https://mlsanity.com/paper/2307.12335/) (2023)
- [When LLMs step into the 3D World: A Survey and Meta-Analysis of 3D Tasks via Multi-modal Large Language Models](https://mlsanity.com/paper/2405.10255/) (2024)
- [Reinforced Structured State-Evolution for Vision-Language Navigation](https://mlsanity.com/paper/2204.09280/) (2022)
- [Iterative Vision-and-Language Navigation](https://mlsanity.com/paper/2210.03087/) (2022)
- [Vision-Language Navigation: A Survey and Taxonomy](https://mlsanity.com/paper/2108.11544/) (2021)
- [1st Place Solutions for RxR-Habitat Vision-and-Language Navigation Competition (CVPR 2022)](https://mlsanity.com/paper/2206.11610/) (2022)
- [UAV-Flow Colosseo: A Real-World Benchmark for Flying-on-a-Word UAV Imitation Learning](https://mlsanity.com/paper/2505.15725/) (2025)

## Abstract (arXiv)

In instruction conditioned navigation, agents interpret natural language and their surroundings to navigate through an environment. Datasets for studying this task typically contain pairs of these instructions and reference trajectories. Yet, most evaluation metrics used thus far fail to properly account for the latter, relying instead on insufficient similarity comparisons. We address fundamental flaws in previously used metrics and show how Dynamic Time Warping (DTW), a long known method of measuring similarity between two time series, can be used for evaluation of navigation agents. For such, we define the normalized Dynamic Time Warping (nDTW) metric, that softly penalizes deviations from the reference path, is naturally sensitive to the order of the nodes composing each path, is suited for both continuous and graph-based evaluations, and can be efficiently calculated. Further, we define SDTW, which constrains nDTW to only successful paths. We collect human similarity judgments for simulated paths and find nDTW correlates better with human rankings than all other metrics. We also demonstrate that using nDTW as a reward signal for Reinforcement Learning navigation agents improves their performance on both the Room-to-Room (R2R) and Room-for-Room (R4R) datasets. The R4R results in particular highlight the superiority of SDTW over previous success-constrained metrics.