General Evaluation for Instruction Conditioned Navigation using Dynamic Time Warping
1. Paper overview
In one sentence: Ordered, distance-aware trajectory alignment makes route fidelity measurable, while success gating and reward design determine how that fidelity affects navigation evaluation. E02E03E04E05E06E08E09E10
| At a glance | What to know |
|---|---|
| Research problem | Source description Reaching the instructed destination can conceal taking the wrong route. Endpoint metrics omit intermediate reference states, while CLS can reward visiting the correct locations in the wrong order. The paper evaluates trajectory fidelity using a reference path as the proxy for an instruction; the metric itself does not interpret language. E02E03E12 |
| Core mechanism | |
| A key reported result | R4R navigation on Validation Unseen: Fidelity-oriented: 30.4 / 12.6 / 28.5. nDTW / SDTW / SR, reported as percentages. Matterport3D; author-implemented agents following cited prior settings; goal-oriented versus fidelity-oriented reward packages. Goal-oriented: 26.9 / 11.4 / 28.7; differences are +3.5 / +1.2 / −0.2 percentage points. The gain concerns reference-path fidelity with essentially unchanged goal success. Both transition and terminal rewards change, so this comparison does not isolate nDTW shaping alone. E09E10 |
| Reading caution |
Core contributions
Figure 1. DTW matches trajectories in order while allowing unequal numbers of samples. Original paper, p. 2 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Begin at the shared first-point label in each panel and follow each solid series toward its labeled final node. The dashed segments connect matched reference and query elements; they are neither traversable shortcuts nor predicted robot movements. Section 2 constrains an alignment to advance one index, the other, or both, and to include both endpoint pairs. Multiple correspondences can therefore involve the same node. Compare the relatively close pair at left with the more separated pair at right: the graphic illustrates the distances accumulated by a warping, while Eq. (1), rather than a visual estimate, defines which alignment is optimal. E03E04
What it supports. An ordered alignment can accommodate different trajectory sampling patterns without reducing similarity to endpoint distance or exact edge matches. Each deviation contributes through a navigational distance. This supplies the mechanism behind nDTW's route-sensitive evaluation, before reference-length normalization and the exponential conversion turn the accumulated cost into a score.
Where the evidence stops. This is an alignment illustration, not a learned architecture or a benchmark result. The drawing provides no numeric scores or environment distance graph; apparent straight-line separations should not be used to reconstruct the reported navigation costs.
2. Motivation
2.1 The problem and the proposed response
Reaching the instructed destination can conceal taking the wrong route. Endpoint metrics omit intermediate reference states, while CLS can reward visiting the correct locations in the wrong order. The paper evaluates trajectory fidelity using a reference path as the proxy for an instruction; the metric itself does not interpret language. E02E03E12
2.2 What this reading follows
A navigation agent can reach the right room after following the wrong route. This paper asks how to evaluate the route itself when a reference trajectory represents the instruction. Its answer adapts dynamic time warping: align the reference and executed paths in order, accumulate navigational distance, and convert that cost into nDTW. SDTW adds a goal-success gate. The visuals below connect that definition to executable pseudocode, human preference tests, and navigation results. They also expose boundaries that matter for reproduction: the reward comparison changes two ingredients, and the printed implementation notation is not fully consistent. E02E03E04E05E06E08E09E10
3. Research context
We place the paper in the collection through its world–action interface. The catalog labels and the reading’s assessment are shown separately.
| Catalog dimension | Recorded classification |
|---|---|
| Major category | Evaluation metrics |
| Architecture | Not applicable |
| Prediction paradigm | Not applicable |
| Quadrant | Not applicable |
3.1 Evidence-based assessment
Supports the recorded classification
The recorded Evaluation metrics category is supported. nDTW/SDTW are deterministic trajectory-scoring functions; using their outputs as rewards does not establish a world-action model. Architecture, prediction paradigm and quadrant are appropriately not applicable. E02E03E05E09
This is the collection’s architectural analysis, not a new related-work survey. Benchmark comparisons and their protocols appear in Section 6.
4. Problem formulation
4.1 Inputs and outputs
| Inputs | Outputs |
|---|---|
|
|
4.2 Equations and their role
5. Method in detail
5.1 Why visiting the right places is insufficient
Start with the loop example in Appendix A: the reference visits a, b, c, and returns to a, while a competing route visits a, c, b, and returns. CLS gives the two routes the same score in the example because its coverage ignores order and their lengths coincide. An instruction with an ordered pickup-and-delivery sequence can distinguish them. DTW addresses this problem by aligning ordered prefixes, rather than finding a nearest point anywhere on the other path independently. Figure 1's dashed links visualize that constraint, and Algorithm 1 enforces it through predecessor choices. As reader analysis, the important conceptual change is from matching a collection of visited places to comparing progress through an intended sequence; success alone cannot supply that information. E02E03E06E12
Algorithms 1–2. The metric is a dynamic program followed by normalization and an optional success gate. Original paper, p. 8 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Read Algorithm 1 from initialization to return: all costs start at infinity except the origin, the nested loops fill reference/query prefix costs, and each cell adds its local distance to the minimum of three predecessors. The return line divides the final cost by reference length times the success threshold before exponentiation. Algorithm 2 then applies a threshold gate. Its printed condition uses R[i] and Q[j] without defining i or j. Section 2 and Table 3 define success using the final nodes, so those locations support the endpoint interpretation; the crop faithfully preserves the incomplete pseudocode. The greater-than branch returns zero, consistent with success including equality. E03E04E05E06E09
What it supports. The principal computation is small enough to inspect directly: there are no learned metric weights or neural inference stages. Algorithm 1 makes the O(|R||Q|) matrix computation explicit, while SDTW adds a binary gate. A reproduction can verify these operations separately before embedding nDTW in a navigation reward.
Where the evidence stops. Do not silently copy the undefined indices in Algorithm 2. The training paragraph also reverses nDTW's argument order relative to Eq. (2); reference-length normalization makes that a substantive implementation ambiguity, unresolved by the supplied source.
5.2 From accumulated distance to an interpretable score
Once DTW has accumulated the matched-point distances, Eq. (2) divides that cost by the number of reference nodes and the distance threshold used for success. The negative exponential converts the result into a bounded score whose larger values mean closer agreement. This also explains why argument order deserves attention: even with a symmetric point-distance function, exchanging reference and query can change the normalization when their lengths differ. SDTW adds a separate operation, multiplying by the final-node success indicator. It therefore assigns zero to a failed episode even if much of the route was followed closely. As reader analysis, reporting nDTW beside SDTW helps distinguish a route-following improvement from the threshold decision that determines whether that fidelity contributes to the success-weighted summary. E03E04E05
5.3 Separate metric validation from reward attribution
The experiments answer two related questions with different evidence. Human raters rank alternative orange paths relative to a fixed blue reference, and Table 1 asks which metric better follows those preferences. Table 2 then asks whether a navigation agent benefits from a reward based on improvements in nDTW. The R4R results are informative because an indirect reference can require more than simply moving toward the final destination. However, the fidelity-oriented agent changes both transition shaping and its completion bonus. As reader analysis, the reported gain establishes the performance of that combined reward design, while a claim specifically attributing it to nDTW increments requires another control. Keeping these questions separate also prevents the human study's sign-test significance from being mistaken for statistical uncertainty on the trained-agent results. E07E08E09E10E14
5.4 Training and inference
During training
The metric has no learned parameters. For agent training, the goal-oriented reward is distance-to-goal progress with terminal +1/−1 for success/failure. The fidelity-oriented reward is proportional to the increase in nDTW for successive query prefixes, with terminal 1−d(q_f,g)/d_th on success and zero otherwise; Matterport3D uses d_th=3 m. E03E09
Section 3.2 writes the query prefix before R in nDTW, whereas Eq. (2) normalizes by the first, reference argument. This matters because that normalization is asymmetric. The supplied text does not resolve which convention the implementation used. E04E09
During inference
Given a completed trajectory and reference, compute the dynamic-programming cost and optionally apply success gating. This is evaluation, not an action policy, predicted world state, or execution controller. The navigation-agent architecture and test-time policy details are not supplied here. E03E05E06E14
5.5 Implementation flow
- Choose a navigational distance
Use shortest-path distance between graph nodes. Euclidean distance is appropriate where obstructions do not invalidate it; continuous environments with obstacles can use precomputed grid distances and nearest-grid approximation. E03
- Align the complete sequences
Warping starts at the first pair and ends at the last pair. Each step advances the reference index, query index, or both. Minimizing cumulative distance permits unequal sampling while preserving order; dashed links in Figure 1 are correspondences, not robot actions. E03
- Normalize and gate
Divide accumulated cost by reference node count and success-distance threshold, then apply the negative exponential. SDTW retains this score only when the final query node is within the goal threshold. Its success gate can discard substantial fidelity on a failed episode. E04E05
6. Experiments & results
nDTW scores how closely an agent follows an ordered reference trajectory using distance-aware dynamic time warping. SDTW additionally requires goal success. Human path rankings and R2R/R4R reward comparisons support their usefulness, while implementation ambiguities and limited experimental reporting constrain reproduction (E02–E10, E14).
This metric paper contains no neural architecture diagram or controlled component-ablation experiment. Figure 1 and Algorithms 1–2 provide the original method visuals; Figure 3 provides illustrative diagnostics. Table 2 compares reward packages that differ in both transition and terminal rewards, so it is not a clean ablation of nDTW shaping. The diagnostic visual is placed in the ablation section with that boundary explicit. E03E06E09E10E13
6.1 Read the original evidence
Table 1. Human rankings favor nDTW and SDTW across the tested competitor groups. Original paper, p. 3 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Keep the two column groups separate. UC compares nDTW against path length, endpoint/oracle errors, CLS, and average/maximum deviation. SC compares SDTW against success-based alternatives. In each column, the positive/negative row counts human-ranking comparisons where the proposed metric had higher/lower correlation than the competitor. Ties are discarded. The sign-test row uses the sum of those counts as n, positives as k, and a null probability of 0.5, as specified in the original caption. For example, the CLS column contains 162 positives and 46 negatives. These are counts of correlation comparisons, not numbers of successful robot episodes or values of the correlations themselves. E07E08
What it supports. Against CLS, the unconstrained comparison reports 162/46 and p=2.4×10^−16; against SPL, the success-constrained comparison reports 219/17 and p=6.7×10^−46. This supports alignment with human path preferences within the study. It is evidence about metric validation that is separate from the reward-training results in Table 2.
Where the evidence stops. The study uses synthetic path drawings, nine raters, and distinct UC/SC groups. The paper does not identify the correlation coefficient or report correlation effect sizes. Small sign-test p-values do not quantify how much better the rankings are.
Table 2. The fidelity-oriented reward improves path scores on both datasets; R4R success stays nearly unchanged. Original paper, p. 4 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Read the two dataset blocks independently and compare the goal-oriented and fidelity-oriented rows within each. The paper reports all entries as percentages on Validation Unseen and labels higher as better. R4R is especially informative because its reference paths can be indirect or return toward their starting point. There, nDTW rises from 26.9 to 30.4 and SDTW from 11.4 to 12.6, while SR changes from 28.7 to 28.5. On R2R, the corresponding nDTW comparison is 54.4 to 58.3. Section 3.2 specifies different transition rewards and different terminal bonuses for the two agents, so the rows represent complete reward packages. E09E10E11E14
What it supports. The R4R comparison separates route fidelity from merely reaching the destination: the reported improvements are 3.5 percentage points in nDTW and 1.2 points in SDTW, accompanied by a 0.2-point SR decrease. The results support the usefulness of the fidelity-oriented reward package, without establishing which changed reward component produced the gain.
Where the evidence stops. No seed uncertainty is reported. Also, random-agent SED exceeds SR in both blocks, conflicting with Table 3's bounded success-weighted definition. Those printed cells remain unresolved and should not be treated as an independently verified SED implementation.
6.2 Results and evaluation conditions
| Task & protocol | Reported result | Comparison & interpretation |
|---|---|---|
| Agreement with human trajectory rankings Synthetic perturbed 15×15 graphs; nine raters, 505 sets of five path pairs. Unconstrained nDTW and success-constrained SDTW comparisons use separate sample groups; ties are discarded. | nDTW vs CLS: 162/46, p=2.4×10^−16. SDTW vs SPL: 219/17, p=6.7×10^−46. Positive/negative correlation comparisons; binomial sign-test p-value | Each sign compares the proposed metric's correlation with a human ranking against the named competitor, rather than comparing raw navigation scores. These tests favor the proposed metrics on the simulated preference task. They do not report the size of the correlation improvement or validate language understanding. E07E08 |
| R4R navigation on Validation Unseen Matterport3D; author-implemented agents following cited prior settings; goal-oriented versus fidelity-oriented reward packages. | Fidelity-oriented: 30.4 / 12.6 / 28.5. nDTW / SDTW / SR, reported as percentages | Goal-oriented: 26.9 / 11.4 / 28.7; differences are +3.5 / +1.2 / −0.2 percentage points. The gain concerns reference-path fidelity with essentially unchanged goal success. Both transition and terminal rewards change, so this comparison does not isolate nDTW shaping alone. E09E10 |
| R2R navigation on Validation Unseen Same reported agent comparison, on direct-to-goal R2R reference paths. | Fidelity-oriented: 58.3 / 38.3. nDTW / SDTW, reported as percentages | Goal-oriented: 54.4 / 36.1; differences are +3.9 / +2.2 percentage points. The fidelity reward also improves these metrics on R2R. No seed variance or confidence intervals are provided, limiting claims about robustness. E09E10E14 |
6.3 Ablations and diagnostic examples
Read component removals and qualitative examples within their stated evaluation conditions.
Figure 3. Example trajectories make the score's range concrete, without constituting a controlled ablation. Original paper, p. 9 ↗
Excerpt from the authors’ paper; cropped without altering the figure or table.
How to read it. Within each small panel, trace the blue reference and orange query in their arrow directions, then read the nDTW label above them. The gray network provides spatial context, and the short bar marked d_th anchors the distance scale. Closely matching examples appear toward the upper left, while examples with larger departures appear toward the lower right. The caption describes the examples as sorted, but the displayed order is not strictly descending: 0.739 precedes 0.740, and further row boundaries contain inversions. Use each printed label directly instead of inferring an ordering from position. The panels show nDTW, so their labels do not by themselves indicate binary success or SDTW. E03E04E05E13
What it supports. The examples provide an interpretable span of similarity, from the pair labeled 1.000 to the pair labeled 0.036. They illustrate graded penalties for different route departures rather than a single pass/fail judgment. Together with the alignment definition, they help a reader understand what a scalar trajectory score is summarizing.
Where the evidence stops. These are random illustrative pairs, not matched interventions isolating order, length, sampling density, or endpoint error. The source provides no per-panel coordinates for exact recomputation here, and the minor sorting inconsistency should remain visible rather than be corrected in the asset.
7. Analysis & limitations
7.1 What the evidence leaves open
Human validation uses generated path drawings and preferences for following a blue route. It does not directly establish agreement on natural-language ambiguity, real-robot safety, or all continuous environments; the particular correlation coefficient is not specified. E07E08
Normalization is motivated as scale/density insensitive, but arbitrary nonuniform resampling is not empirically isolated. Distance quality, reference sampling, and threshold choice remain consequential evaluation assumptions. E03E04E07E10
Table 2 reports random-agent SED above SR on both datasets, although Table 3 defines SED as success times a bounded edit-similarity factor. This internal inconsistency is unresolved; preserve the printed values without treating them as a verified metric implementation. E11
7.2 Questions for discussion
- Would nDTW still track human preferences when several routes equally satisfy an instruction?
- How much of the reported reward benefit comes from trajectory shaping versus the changed terminal bonus?
8. Reproducibility audit
8.1 Requirements and known gaps
Reimplement the small dynamic program with explicit reference-first argument order and endpoint success checks. Verify zero cost for identical paths, ordered-loop sensitivity, and failure gating before using it as a reward; document how the two printed pseudocode/reward ambiguities were resolved. E03E04E05E06E09E12
For human-study regeneration, use 15×15 nodes with independent coordinate jitter ±0.3, connect pairs within Euclidean distance 1.4, and join sampled waypoints two or three edges apart by shortest paths. Success uses 1.33 times average edge length. Path-generation stopping rules and the correlation estimator require clarification. E07E08
Agent reproduction requires the cited training setup and R2R/R4R data. The random baseline averages one million neighbor-uniform walks with step counts sampled from reference lengths. Optimizer, full architecture, seeds, compute and reward proportionality are not specified locally; the trained comparison also changes terminal rewards. E09E14
8.2 Proposed reproduction checks
The following checks are proposals motivated by the paper. They have not been run as part of this reading.
Check 1: Check order sensitivity, normalization, and endpoint gating
Reader-proposed, not executed: implement Eq. (2) and Algorithm 1 on a small symmetric graph containing the Appendix A loop. Compare the reference with itself and with the reversed loop, holding visited nodes, endpoint and path length fixed; compare nDTW with CLS. Identical paths should score one, while a distinct ordered loop should have positive DTW cost even when CLS ties. Next use unequal-length paths to test both argument orders, and place final nodes just inside, at, and outside the success threshold to verify SDTW's gate. Record the endpoint convention explicitly. A reversed-loop tie in nDTW or a nonzero SDTW outside the threshold would falsify the intended implementation. E03E04E05E06E12
Check 2: Isolate the two reward changes on R4R
Reader-proposed, not executed: reproduce the R4R Validation Unseen comparison with a two-by-two design crossing goal-progress versus nDTW-gain transition rewards with binary versus distance-shaped terminal bonuses. Hold architecture, data, optimizer, training budget and seeds matched, document the reward scale and nDTW argument convention, and evaluate SR, nDTW and SDTW across repeated runs. The specific shaping claim would be supported if nDTW increments improve fidelity under the same terminal bonus. If gains occur only with the changed completion reward, Table 2's combined improvement cannot be attributed to nDTW shaping alone. Report variability and any SR tradeoff. E04E09E10E14
8.3 Reading coverage
Visual audit: Visually inspected the title, authors, affiliations and v2/date on p. 1; Figure 1 and alignment/normalization equations on p. 2; Figure 2, Table 1, human protocol and SDTW definition on p. 3; all Table 2 cells, statistical-test discussion and reward definitions on p. 4; Table 3 and metric definitions on p. 7; CLS diagnostic, Algorithms 1–2 and implementation discussion on p. 8; and all Figure 3 panels on p. 9. Every final crop was opened and inspected. Reference-only pp. 5–6 were read in text. No separate supplement, code or execution was reviewed. These declared pages cover all retained method, numerical, training, evaluation and proposed-reproduction source facts.
PDF pages inspected for this edition: 1, 2, 3, 4, 7, 8, 9. Appendix coverage: reviewed.
Original figures and tables remain the work of the source’s authors. Extractions preserve their scientific content; any HTML wrapper layout is disclosed with each figure. The surrounding reading notes are our own.
Text reading scope & known omissions
- Abstract
- 1 Introduction
- 2 Dynamic Time Warping for Navigation
- 3 Evaluation
- 3.1 Human evaluations
- 3.2 Evaluation on VLN Tasks
- 4 Conclusion
- References
- Appendix A: Evaluation metrics in instruction conditioned navigation
- Appendix B: Implementing of proposed metrics
- Appendix C: Visualizing nDTW scores
Outside the original text pass
- Text extraction does not reconstruct figure images; inspect the retained PDF for figures and equation/table layout.
- Separate supplemental material availability has not been fully verified.
- The supplied nine-page paper and all three text chunks were read. The observed source is arXiv:1907.05446v2, dated 28 November 2019, later than the catalog's 11 July 2019 submission date. Title and all five authors agree; v1 was not supplied, so revision differences cannot be compared (E01).
- The manifest notes that text extraction does not reconstruct figure images; this edition supplements it with inspected PDF pages and original crops. Pages 1–4 and 7–9 were visually inspected; reference-only pages 5–6 were read as text.
- Separate supplemental material availability has not been fully verified. No separate supplement was supplied.
- Code and cited external resources were not inspected; no experiments were reproduced.
The visual audit above records the subsequent illustrated pass.
8.4 Traceable evidence
E01PDF p. 1, title, author/affiliation block, arXiv margin and conference footer
The exact catalog title and five authors appear on arXiv:1907.05446v2, dated 28 November 2019. Affiliations are the University of Washington's Paul G. Allen School and Google Research; the footer names NeurIPS 2019.
Go to primary source ↓E02PDF p. 1, Abstract and Section 1; p. 7, Appendix A
Goal arrival and trajectory efficiency do not establish fidelity to intermediate reference states; the proposed contribution is evaluation of navigation paths.
Go to primary source ↓E03PDF p. 2, Figure 1 and Section 2, Eq. (1) and following distance paragraph
DTW minimizes cumulative distance under monotone warping steps and endpoint constraints. Navigation costs can use graph shortest paths or appropriate continuous-space distances.
Go to primary source ↓E04PDF p. 2, Section 2, Eq. (2) and normalization discussion
nDTW exponentiates negative DTW divided by reference node count times the success-distance threshold; higher scores indicate greater similarity.
Go to primary source ↓E05PDF p. 3, Section 2, SDTW definition; p. 7, Table 3, SR and SDTW rows
SDTW is SR multiplied by nDTW. SR tests final-node distance against the success threshold with a less-than-or-equal inequality.
Go to primary source ↓E06PDF p. 8, Appendix B, Algorithms 1–2, Eq. (3) and complexity discussion
Algorithm 1 gives the dynamic program and exponential normalization. Algorithm 2 prints a threshold test using undefined i and j. Exact computation is quadratic; linear approximation is referred to prior work.
Go to primary source ↓E07PDF p. 3, Figure 2 and Section 3.1
Nine raters annotated 2,525 path pairs in 505 five-query sets, split into 1,325 unconstrained and 1,200 success-constrained samples on randomly generated perturbed grids.
Go to primary source ↓E08PDF p. 3, Table 1, CLS and SPL columns and caption; p. 4, first paragraph
After discarding ties, nDTW versus CLS has 162/46 positive/negative correlation comparisons and sign-test p=2.4e-16; SDTW versus SPL has 219/17 and p=6.7e-46.
Go to primary source ↓E09PDF p. 4, Section 3.2, environment, random baseline and reward definitions
The authors train their own agents following Jain et al.'s settings, compare goal-progress and nDTW-gain rewards with different terminal bonuses, and use a 3 m success threshold. The nDTW reward expression places the query prefix first.
Go to primary source ↓E10PDF p. 4, Table 2, R2R and R4R Validation Unseen columns, all agent rows
All scores are reported as percentages. Fidelity-oriented versus goal-oriented R4R nDTW is 30.4 versus 26.9, SDTW 12.6 versus 11.4, and SR 28.5 versus 28.7. R2R nDTW is 58.3 versus 54.4 and SDTW 38.3 versus 36.1.
Go to primary source ↓E11PDF p. 7, Table 3, SED definition; p. 4, Table 2, random-agent SR and SED columns
SED multiplies SR by a normalized edit-similarity term. Table 2 nevertheless reports random-agent SED above SR: 5.8 versus 5.1 on R2R and 16.5 versus 13.7 on R4R.
Go to primary source ↓E12PDF p. 8, Appendix A, CLS loop example and AD/MD discussion
CLS assigns the same score to the illustrated forward and reversed loops; its coverage ignores visit order. AD and MD also ignore node order.
Go to primary source ↓E13PDF p. 9, Figure 3 and Appendix C
Twenty blue-reference/orange-query examples display nDTW values. The caption calls them sorted, although the printed sequence includes local inversions, including 0.739 then 0.740.
Go to primary source ↓E14PDF p. 4, Section 3.2 and Table 2; p. 8, Appendix B
The supplied experiment description delegates settings to prior work and omits optimizer, architecture details, seeds, uncertainty and hardware. The appendix supplies metric pseudocode, rather than a complete agent-training specification.
Go to primary source ↓8.5 Primary sources
General Evaluation for Instruction Conditioned Navigation using Dynamic Time Warping ↗
PDF · 4,584 extracted words
Source fingerprint
893f1c3f971d8a7f6694734bc2a33d25cc2d58b97be22a40eec94cd9988c88c8