Source-linked AI summary
General Evaluation for Instruction Conditioned Navigation using Dynamic Time Warping
Gabriel Ilharco, Vihan Jain, Alexander Ku, Eugene Ie, Jason Baldridge
TL;DR
Instruction-conditioned navigation needs metrics that evaluate both reaching the goal and following the instructed reference trajectory, whereas prior metrics have important limitations. The paper adapts Dynamic Time Warping into nDTW, introduces success-constrained SDTW, and finds stronger agreement with human judgments plus improved reinforcement-learning performance on R2R and R4R.
Problem
Existing navigation metrics do not adequately account for similarity between an agent’s trajectory and the reference trajectory accompanying an instruction.
Method
The paper adapts Dynamic Time Warping into normalized nDTW for navigation and defines SDTW by restricting nDTW to successful paths.
Results
nDTW and SDTW correlate substantially better with human path rankings than competing metrics, while using nDTW as an RL reward improves results on R2R and R4R.
Takeaways & Limitations
SDTW captures both task success and similarity between intended and observed trajectories for evaluating instruction-conditioned navigation agents.
Abstract
from arXiv · showhide
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.
1 Introduction
Instruction-conditioned navigation requires evaluation that reflects both goal achievement and similarity to the instructed reference trajectory. The paper adapts Dynamic Time Warping to address limitations in existing metrics and use it for navigation-agent training.
- 1 Introduction: Evaluation metrics for language-conditioned behavior should be sensitive to both the navigation task and how instructions inform the resulting behavior.This requirement motivates evaluating trajectories against reference paths rather than relying only on goal attainment.
- 1 Introduction: Existing metrics such as SR, SPL, SED, and CLS have limitations that leave a gap in evaluating path-oriented navigation agents.These metrics differ in whether they emphasize goal attainment, efficiency, or intermediary states, but the cited analysis identifies shortcomings across them.
- 1 Introduction: Dynamic Time Warping aligns reference and query series by minimizing cumulative distance while preserving element order.Figure 1 illustrates the optimal warping between reference and query series.
- 1 Introduction: The paper adapts DTW for instruction-conditioned navigation and demonstrates its use both as an evaluation measure and as a reinforcement-learning reward signal.The adaptation is intended to compare agent trajectories with reference paths and improve training.
2 Dynamic Time Warping for Navigation
The paper defines nDTW by adapting DTW to navigation distances, normalizing for trajectory sampling, and transforming the result into an interpretable score. It also introduces SDTW to combine trajectory similarity with success.
- 2 Dynamic Time Warping for Navigation: DTW finds an ordered alignment between reference and query paths by minimizing cumulative element-wise distance.The alignment preserves node order and can use shortest graph distance, Euclidean distance, or approximated distances from fixed grid points.
- 2 Dynamic Time Warping for Navigation: nDTW normalizes DTW by |R|·d_th and applies a negative exponential, producing a score from 0 to 1 with higher values indicating better performance.The normalization reduces sensitivity to trajectory scale and node density, while d_th is the success-threshold distance.
- 2 Dynamic Time Warping for Navigation: nDTW can be computed exactly in quadratic time and space or approximately in linear time and space.The paper notes that sampling nodes can adapt FastDTW-style interpolation to discrete environments.
- 2 Dynamic Time Warping for Navigation: nDTW compares entire trajectories, softly penalizes deviations, forces final-node alignment, and supports both continuous and graph-based path evaluation.It is also insensitive to changes in node scale and density while remaining sensitive to trajectory order.
- 2 Dynamic Time Warping for Navigation: SDTW multiplies nDTW by success rate, making the similarity score zero for unsuccessful episodes.Success is commonly determined using the threshold distance d_th.
3 Evaluation
The evaluation combines human path-similarity judgments with reinforcement-learning experiments on R2R and R4R to test nDTW and SDTW. Both metrics outperform competing measures, while fidelity-oriented rewards provide the clearest success-and-fidelity signal.
- 3.1 Human evaluations: Human raters rank five simulated query paths against a fixed reference path, judging which trajectory they would prefer a robot to follow.The environments contain randomly generated approximate 15×15 grids, with paths sampled through nodes two or three edges apart.
- 3.1 Human evaluations: nDTW and SDTW correlate substantially better with human path rankings than competing metrics in their respective unconstrained and success-constrained studies.The comparison uses annotations from 2,525 samples collected from 9 human raters and analyzes differences with a sign test.
- 3.2 Evaluation on VLN Tasks: Fidelity-oriented agents receive transition rewards from gains in nDTW relative to the reference path, whereas goal-oriented agents are rewarded for reducing distance to the goal.The fidelity-oriented agent also receives a success-conditioned terminal reward based on navigation error.
- 3.2 Evaluation on VLN Tasks: Using nDTW as a reward improves nDTW, SDTW, CLS, and SPL over goal-oriented rewards, with SDTW most clearly distinguishing success and trajectory fidelity.On R4R, prior metrics can fail to distinguish reward strategies or reward path length rather than fidelity to the reference.
4 Conclusion
The paper introduces nDTW and SDTW to evaluate both path similarity and task success in instruction-conditioned navigation. Human judgments and VLN-agent experiments support their usefulness, especially SDTW as a combined summary measure.
- 4 Conclusion: SDTW captures both whether an agent succeeds and how closely its trajectory matches the intended path.The authors propose SDTW as a single summary measure, while noting that path length and navigation error remain useful for understanding distinct behaviors.
- 4 Conclusion: nDTW is preferred by human evaluations and improves VLN-agent performance when used as a reward signal.The conclusion summarizes evidence from qualitative human evaluations and practical experiments on navigation agents.
- 4 Conclusion: The authors hope the community adopts SDTW for future evaluation and leaderboard rankings.
A Evaluation metrics in instruction conditioned navigation
Existing navigation metrics often measure endpoint success, path length, or partial similarity rather than ordered fidelity between complete reference and query paths. The appendix describes shortcomings in endpoint-based, edit-distance, coverage, and deviation metrics.
- A Evaluation metrics in instruction conditioned navigation: Endpoint-based metrics such as NE, ONE, SR, OSR, and SPL ignore much of the reference path and therefore tolerate intermediary deviations.These measures focus primarily on the final node or endpoint success, making them less suitable for complete path similarity.
- A Evaluation metrics in instruction conditioned navigation: SED compares action sequences using exact edit matches, so it can severely penalize trajectories that remain very close to the reference in continuous environments.
- A Evaluation metrics in instruction conditioned navigation: CLS is order-invariant, assigning the same score to paths that visit the same locations in different orders despite potentially different task behavior.For a reference path (a, b, c, a), the reversed-order path (a, c, b, a) receives the same CLS score as the intended path.
- A Evaluation metrics in instruction conditioned navigation: Average Deviation and Max Deviation consider complete paths but fail to account for the order of their nodes.
B Implementing of proposed metrics
The proposed procedures compute nDTW and SDTW from reference and query paths using dynamic programming, with nDTW returned as a normalized terminal DTW score. DTW-based metrics can also be approximated efficiently enough for evaluation and reinforcement-learning rewards.
- nDTW: The nDTW procedure takes reference path R, query path Q, and success distance threshold dth, then outputs the nDTW score.
- nDTW: nDTW returns exp(-C[|R|][|Q|] / (|R| · dth)) from the terminal dynamic-programming cost between reference path R and query path Q.The success distance threshold dth normalizes the final DTW cost by reference-path length.
- SDTW: SDTW uses the same path inputs and success threshold as nDTW but returns an SDTW score through its own procedure.
- Dynamic programming: DTW costs are computed in O(|R||Q|) by filling matrix C sequentially, because each C_i,j depends on three previously computed neighboring entries.The terminal entry C_|R||Q| is DTW(R,Q).
- Efficiency: DTW, nDTW, and SDTW can be approximated in linear time and space, enabling their use as evaluation functions and reinforcement-learning reward signals for long paths.
C Visualizing nDTW scores
Figure 3 visualizes reference and query path pairs arranged according to their nDTW scores.
- Path examples: Figure 3 shows random reference paths in blue paired with query paths in orange.
- Score ordering: The path pairs are sorted by their nDTW values, allowing visual comparison across the score ordering.
- Score interpretation: The figure provides examples of how different reference–query path pairs correspond to different nDTW scores.