Vision-and-Language Navigation

Vision-and-language navigation (VLN) is the task of following directions given in ordinary language, such as “walk past the sofa, go through the kitchen and stop at the bedroom door”, from a starting point to a goal in a building the agent has usually never seen, using only what its cameras show along the way. Natural-language navigation instructions had been studied before, mostly in rendered, symbolic or otherwise visually restricted environments (Anderson et al., 2018). Anderson et al. gave the name to the version set in real images and released its first benchmark, Room-to-Room (R2R), together with the Matterport3D Simulator, in which an agent moves between panoramic photographs of 90 real buildings. They framed it as a vision-and-language problem: like visual question answering, it maps an image stream and a sentence to an output, but the output is a sequence of actions that changes what the agent sees next. The task sits at the meeting point of visual navigation, which moves an agent to goals given as coordinates, object categories or images, and vision–language models, which relate words to pixels. What VLN adds is that the instruction describes a route, with landmarks, turns and a stopping point, so the agent must ground phrases in what it sees, keep track of how much of the instruction it has carried out, and decide for itself where to stop.

In outline (our summary of the methods below), the field has gone through three phases: recurrent sequence-to-sequence agents trained by imitation and reinforcement learning on R2R (2018–2019), agents built on transformers pretrained on image–text and instruction–path data (2020–2022), and agents that hand the decision to a large language model working from text descriptions of the views (NavGPT, 2024). Alongside these, the benchmarks were revised to measure whether agents follow the described path rather than only reach its end, and to drop simplifications of the original simulator.

Problem Definition

In R2R, an episode gives the agent an instruction $\bar{x} = \langle x_1, \dots, x_L \rangle$ of $L$ word tokens and an initial pose $s_0 = \langle v_0, \psi_0, \theta_0 \rangle$: a viewpoint $v_0$, a heading $\psi_0$ and a camera elevation $\theta_0$ (Anderson et al., 2018). The agent executes a sequence of actions $\langle s_0, a_0, s_1, a_1, \dots, s_T, a_T \rangle$, each producing a new pose and a new image, and ends the episode with a special stop action. It succeeds if it stops close to the intended goal location $v^*$.

Movement is defined by a navigation graph $G = \langle V, E \rangle$ for each building, whose vertices are the panorama locations and whose edges, weighted by straight-line distance, mark transitions a robot could make. Anderson et al. built the graphs by ray-tracing between viewpoints in the building meshes, removed edges longer than 5 m and checked every graph by hand for obstacles the meshes miss, such as windows and mirrors. From viewpoint $v_t$ the agent may move to

$$W_{t+1} = \{ v_t \} \cup \{ v_i \in V \mid \langle v_t, v_i \rangle \in E \wedge v_i \in P_t \},$$

where $P_t$ is the region inside the left and right extent of the camera frustum: it may follow any edge whose end it can see, or stay and turn the camera. A graph has 117 viewpoints on average, with average degree 4.1, and Matterport3D’s panoramas lie about 2.25 m apart (Anderson et al., 2018).

Three things distinguish this from point-goal navigation, where the goal is given as a displacement. First, the goal must be inferred from language, which may describe it only by what is near it (stop beside a particular picture on a wall). Second, the instruction describes a particular route, so in principle the path matters and not only its end, although R2R itself scores only where the agent stops. Third, the agent must recognise the goal and stop: Anderson et al. treat stopping as part of understanding the instruction, and report an oracle stopping rule separately to disentangle it.

Input and Output

The original simulator gives the agent a single perspective RGB image per step, 640 × 480 pixels with a 60° vertical field of view in the baseline experiments (Anderson et al., 2018). Fried et al. (2018) replaced this with a panoramic observation: at each viewpoint the agent receives 36 views (12 headings × 3 elevations at 30° intervals), each encoded as a CNN feature concatenated with the orientation feature $[\sin\psi; \cos\psi; \sin\theta; \cos\theta]$, and the navigable directions are encoded the same way. Krantz et al. (2020) note that nearly all follow-up work adopted this panoramic observation space.

The output differs by action space:

• Low-level camera actions (Anderson et al., 2018): left, right, up and down by 30°, forward to the reachable viewpoint closest to the centre of the view, and stop.
• Panoramic actions (Fried et al., 2018): choose one of the navigable neighbouring viewpoints, or stop. The simulator translates the choice into turning and moving.
• Continuous control in VLN-CE (Krantz et al., 2020): move forward 0.25 m, turn left or right 15°, or stop, with a 256 × 256 RGB-D egocentric camera of 90° horizontal field of view, emulating a ground robot with zero turning radius.
• Navigation plus grounding in REVERIE (Qi et al., 2020): the agent must also output a bounding box around the target object, or choose it from candidate boxes the simulator provides.

What is evaluated is the trajectory, the sequence of viewpoints (or positions, in VLN-CE) the agent visits. The R2R evaluation code expects, for each instruction, a list of (viewpoint, heading, elevation) triples starting at the start viewpoint, and rejects a trajectory that moves between viewpoints the graph does not connect (Anderson et al., eval.py).

Variants

Room-to-Room (R2R). Start and goal pairs were sampled mostly in different rooms, and the path between them is the shortest path in the navigation graph, kept only if it is at least 5 m long and has four to six edges (Anderson et al., 2018). The 7,189 paths average 10 m. Over 400 Amazon Mechanical Turk workers, all US-based, wrote three instructions per path after watching a fly-through, 21,567 instructions in total with an average of 29 words and a vocabulary of about 3,100 words. Workers were told that it was not necessary to follow the indicated path exactly, merely to reach the goal.

Room-for-Room (R4R). Because every R2R path is a shortest path to the goal, following the instruction and heading straight for the goal coincide. Jain et al. (2019) joined pairs of R2R paths: paths $A$ and $B$ are joined if the end of $A$ lies within $d_{th}$ of the start of $B$, with the shortest path between them inserted, and every combination of their instructions is kept. With the conventional 3 m threshold this gives 233,613 training instructions; reference paths average 20.6 m against 10.5 m for the shortest path to the same goal (Table 1). The paper writes the joining condition with a strict inequality; the generator script drops a pair only when the distance exceeds the threshold, so pairs exactly at it are kept (google-research r4r code).

Room-across-Room (RxR). Ku et al. (2020) collected 126,069 instructions in English, Hindi and Telugu for 16,522 paths, written from scratch by native speakers rather than translated. Paths visit a sequence of rooms and are the shortest panorama path constrained to those rooms, so 44.5% are not shortest paths to the goal and they average 14.9 m and 8 edges against 9.4 m and 5 edges in R2R. Instructions are spoken, transcribed by the annotators and average 78 words. Each word is time-aligned with the annotator’s virtual camera pose, and a second annotator followed each instruction, which both validated it (success meant reaching within 3 m of the last panorama) and recorded a follower pose trace. Human followers reached a 93.9% success rate.

REVERIE. Qi et al. (2020) replaced step-by-step directions with short, high-level commands that refer to a remote object, such as asking for a particular picture near the top of the stairs to be brought: 21,702 instructions averaging 18 words, for 4,140 target objects in 86 buildings. The agent must navigate to the object’s room and localize the object, which visual grounding addresses in single images; here the object is not visible from the start.

Continuous environments (VLN-CE). Krantz et al. (2020) argue that the navigation graph builds three assumptions into VLN: known topology (the graph itself is prior knowledge about the layout, even in unseen buildings), oracle navigation (a hop of several metres between panoramas abstracts away obstacle avoidance) and perfect localization. They transferred R2R paths to the Matterport3D meshes in the Habitat simulator: each panorama location was projected to the nearest navigable floor point for an agent modelled as a cylinder 1.5 m tall and 0.2 m in diameter, which succeeded for 98.3% of nodes, and a path was kept if an agent could follow shortest paths between consecutive waypoints to within 0.5 m. Of the R2R trajectories, 77% were navigable, giving 4,475 trajectories from the training and validation splits; shortest paths need 55.88 low-level actions on average against 4–6 hops in R2R.

Other formulations share the evaluation machinery: outdoor navigation in street panoramas (Touchdown), navigation from dialogue (CVDN) and the household instructions of ALFRED, which Embodied AI describes.

Challenges

Generalization to unseen buildings. The first R2R baseline succeeded in 38.6% of validation episodes in training buildings and in 21.8% in unseen ones (Anderson et al., 2018, Table 1). Its validation curves showed performance in unseen buildings plateauing early while performance in training buildings kept rising, despite dropout and weight decay, which the authors read as visual groundings specific to the training environments. Tan et al. (2019) found the same bottleneck from the data side: with equal amounts of data, adding environments raised success rate faster than adding instructions spread over all training environments (their Figure 5).

Scarce data. R2R has 14,025 training instructions. Tan et al. counted about 190,000 possible shortest-path routes in the training environments, of which R2R labels about 7%. Augmentation with machine-written instructions, pretraining on other data and multilingual collection (RxR) are all responses to this.

Grounding. Instructions refer to objects, rooms and spatial relations (a closet door on the left, a bathroom straight ahead), whose appearance changes with viewpoint, and the level of abstraction varies widely between annotators (Anderson et al., 2018). Krantz et al. (2020) observed failures in VLN-CE when the agent never looked at the referenced object, since a narrow egocentric camera must actively turn to see it: the active perception problem inside VLN.

Path biases. R2R’s paths are short, of narrow length range and always shortest to the goal. Ku et al. (2020) report that baselines which go straight for the average number of training steps do worse on RxR than on R2R, most clearly when given the correct first step (27.2% against 13.7% success on val unseen, their Table 4), and Jain et al. (2019) found that an R4R agent trained with goal rewards scored the same path-fidelity score whether given the full instruction or only its last five tokens.

Simulator assumptions. Krantz et al. (2020) show how much the navigation graph helps. A hand-crafted agent that picks a random heading and walks 37 forward steps (the dataset average) succeeds in about 3% of unseen VLN-CE episodes; a similar agent in the nav-graph setting succeeded in 16.3%, a comparison the authors call not directly comparable but indicative of the graph’s prior. Removing depth from their sequence-to-sequence agent left success at 3–4% (RGB only) and 0% (no vision) in their Table 2, while the text says these ablations reach at most 1%; the authors believe depth lets an agent learn to move without collisions, without which it is hard to start following instructions at all.

Approaches

Sequence-to-sequence agents and exposure bias

Anderson et al. (2018) modelled the agent as an LSTM encoder–decoder with attention: the encoder reads the instruction with the word order reversed, and the decoder takes the ResNet-152 feature of the current image and the previous action, attends over the encoded instruction and outputs a distribution over the six low-level actions. Training minimized cross-entropy against the next action on the shortest path from the agent’s current pose to the goal. Under teacher forcing the agent always took that action, so it only ever saw states on the shortest path, a distribution shift between training and testing; under student forcing it sampled its next action from its own output distribution and was still supervised with the shortest-path action. The authors note that student forcing is equivalent to an online version of DAgger, and that in initial experiments scheduled sampling did worse; visuomotor policy learning explains the compounding error behind both. Student forcing raised unseen-validation success from 19.6% to 21.8%.

Speaker–follower models and the panoramic action space

Fried et al. (2018) added a speaker, a model of how people describe routes, trained on the same data in the opposite direction: it encodes the sequence of views and actions of a route and generates an instruction word by word. The speaker helps the follower twice. For training, it wrote instructions for 178,000 routes sampled in the training environments; the follower was trained on the augmented set and then fine-tuned on the human data. At test time the follower generates up to $K = 40$ candidate routes by a state-factored search, and the speaker rescores them by how well each explains the instruction:

$$\hat{r} = \arg\max_{r \in R(d)} P_S(d \mid r)^{\lambda} \, P_F(r \mid d)^{1-\lambda},$$

with $\lambda = 0.95$, so the speaker dominates. The authors call this pragmatic inference, following the Rational Speech Acts framework. With the panoramic action space described above, the three components raised unseen-validation success from 19.9% for the student-forcing baseline to 54.6% (Table 1, rows 1 and 8), and the full model reached 53.5% on the unseen test set.

That test figure came from search: for the leaderboard submission the authors modified the search to keep the trajectory physically plausible, and the resulting trajectory had a length of 1,257 m and an oracle success rate of 96.0% (Fried et al., 2018, Table 2). Results on the R2R leaderboard are reported under separate settings (Tan et al., 2019): single run (one pass, no exploration of the test building), beam search, and pre-exploration, in which the agent may adapt to the test environment first. In the single-run setting, Tan et al.’s leaderboard table lists the speaker–follower agent at 35.0% success and an SPL of 0.28; with beam search, 53.5% success and an SPL of 0.01.

Progress monitoring

Ma et al. (2019) introduced a self-monitoring agent with an auxiliary progress estimate. Their paper (ICLR 2019) was not read here; later papers describe it as a visual–textual co-grounding module with a progress monitor on the panoramic action space (Hao et al., 2020), trained to predict at each step the fraction of the trajectory already covered (Krantz et al., 2020). Tan et al. (2019, Table 1) list it at 48.0% success and an SPL of 0.35 in the single-run test setting. Krantz et al. found the progress-monitor loss harmful on its own in VLN-CE but useful combined with augmented data, and saw it overfit without augmentation.

Imitation plus reinforcement learning, back translation and environmental dropout

Tan et al. (2019) trained a panoramic encoder–decoder agent with a mixture of imitation learning (behavioural cloning of the shortest-path action) and advantage actor-critic reinforcement learning, with a reward of +3 for stopping within 3 m of the goal, −3 otherwise, and the decrease in distance to the goal at each step. The two share weights but navigate separate routes, and the loss is $L_{RL} + \lambda_{IL} L_{IL}$. Imitation alone reached 43.6% unseen-validation success, reinforcement learning alone 24.0%, and the mixture 46.5% (Table 2).

Their second stage uses a speaker for back translation, as Fried et al. did, but targets the shortage of environments. Environmental dropout multiplies the image features of every view at every viewpoint of a training environment by the same dropout mask, keeping the orientation features, so that whatever a dropped feature dimension encodes disappears consistently throughout the “new” environment; the authors describe the idea as mimicking the removal of one kind of object, such as chairs. The speaker then writes instructions for routes in the altered environment, and the follower, using the same mask, is fine-tuned on them. On unseen validation, back translation alone gave 48.2%, adding ordinary feature dropout (independent masks per view) 48.4%, environmental dropout with separate masks for speaker and follower 49.0%, and with the masks tied 52.2% (Table 2). On the unseen test set the agent reached 51.5% success and an SPL of 0.47 in the single-run setting (Table 1).

Rewards for following the path

Jain et al. (2019) reimplemented the reinforced cross-modal matching agent of Wang et al. and trained it on R4R with either a goal-oriented reward or a fidelity-oriented one that adds CLS (defined below) at the end of the episode. On R4R unseen validation the fidelity reward raised CLS from 20.4 to 34.6 and lowered navigation error from 8.45 m to 8.08 m. Ilharco et al. (2019) used the gain in nDTW at each step as the reward, plus an end reward linear in navigation error for successful episodes. On R4R unseen validation the fidelity-oriented agent scored nDTW 30.4 and SDTW 12.6 against 26.9 and 11.4 for the goal-oriented one, while success rates were nearly equal (28.5% and 28.7%). Its SPL was also higher (21.4 against 15.0), which the authors attribute to paths closer in length to the references, not to fidelity.

Pretrained transformers

The next step reused pretraining from vision–language pretraining and BERT-style objectives.

• PREVALENT (Hao et al., 2020) pretrains a cross-modal encoder on image–text–action triplets with two objectives: masked language modelling in which masked words are predicted from the remaining words and the images, and prediction of the next action. Triplets come from R2R’s training data (104K) and from 1,020K instructions written by the Fried et al. speaker for shortest paths in the training environments. The paper gives the resulting count as 6,482K triplets and the total pretraining set as 6,582K, figures that do not add up as printed. Only the language features are used when fine-tuning, as a drop-in component of an existing agent fine-tuned on Tan et al.’s schedule (cited by PREVALENT as EMNLP 2019; the paper appeared at NAACL). It reached 54% success and an SPL of 0.51 on the R2R unseen test set in the single-instruction setting (Table 1).
• VLN-BERT (Majumdar et al., 2020) scores the compatibility between an instruction and a whole path of panoramas. It was pretrained in stages on text (as BERT), on web image–caption pairs from Conceptual Captions (as ViLBERT) and on R2R path–instruction pairs, and is used to rank candidate paths from beam search in the fully observed setting, where an ensemble of a speaker, a follower and VLN-BERT reached 73% leaderboard success, 4 percentage points above the previous published best.
• VLN↻BERT (recurrent VLN BERT, called RecBERT by later papers; Hong et al., 2021) makes a single-stream transformer recurrent: a state token, initialized from the [CLS] token, is fed back at each step together with the language and visual tokens, so no separate LSTM is needed, and during navigation language tokens act only as keys and values, which saves memory. Initialized from PREVALENT, it reached 63% success and an SPL of 0.57 on the R2R unseen test set (single run); from random initialization it reached 51% and 0.47 (Table 1).
• HAMT (Chen et al., 2021) keeps the whole history of panoramas instead of a recurrent state. A hierarchical vision transformer encodes each view, then the spatial relations among views in a panorama, then the sequence of panoramas, and a cross-modal transformer combines history, current observation and instruction. It is trained end to end with proxy tasks (single-step action prediction, spatial relation prediction, masked language and image prediction, instruction–trajectory matching) and then fine-tuned with imitation and reinforcement learning. It reached 65% success and an SPL of 0.60 on the R2R unseen test set (Table 5), and on R4R unseen validation an nDTW of 50.3 against 45.1 for VLN↻BERT, which HAMT’s authors ran from the original implementation (Table 6).
• DUET (Chen et al., 2022) builds a topological map on the fly from visited and observed navigable nodes and chooses among all nodes on the map, not only the neighbours; a planner then moves the agent along the shortest path in the map to the chosen node. It encodes the map coarsely and the current panorama finely and fuses the two. On REVERIE’s unseen test split it reached 52.51% success and an SPL of 36.06 against 30.40% and 26.67 for HAMT (Table 6). On R2R test unseen it raised success to 69% from HAMT’s 65% at a comparable SPL (0.59 against 0.60, Table 7), which the authors attribute to backtracking: a global action space encourages returning along the map, which lengthens paths.

LLM-based agents

NavGPT (Zhou et al., 2024) uses GPT-4 or GPT-3.5 without any training on VLN data; the authors evaluate both and use GPT-3.5 for their ablations. At each viewpoint, BLIP-2 describes each of 24 views in words, an object detector the authors cite as Fast-RCNN lists objects, and the simulator’s depth gives their distances; a prompt manager combines these descriptions, a history summarized by GPT-3.5 and the navigable directions, and the LLM writes its reasoning and chooses the next viewpoint. On R2R unseen validation (the 783 trajectories of the 11 unseen buildings) NavGPT reached 34% success and an SPL of 0.29 (the table does not say which of the two LLMs produced this row), against 72% and 0.60 for the trained DUET and 1% for DUET without training (Table 1). The authors locate the bottleneck in the information lost when views are turned into text and when the history is summarized, and show with GPT-4 reasoning traces that the model decomposes instructions into sub-goals, identifies landmarks and tracks its progress. BLIP describes the captioner’s family. Vision-language-action models take a different route to using pretrained models: they fine-tune a vision–language model on robot demonstrations so that it outputs the robot’s actions itself, as tokens or through an action head.

Agents in continuous environments

Krantz et al. (2020) built a sequence-to-sequence agent and a cross-modal attention agent for VLN-CE, both using ImageNet ResNet-50 RGB features and a depth encoder from a point-goal navigation agent. Training used teacher forcing with inflection weighting, DAgger, the progress monitor and the EnvDrop augmentation paths converted to continuous environments. The best model, cross-modal attention pretrained with augmentation and the progress monitor and then fine-tuned with DAgger, reached 32% success and an SPL of 0.30 on unseen validation (Table 3). Converted back to the navigation graph and submitted to the R2R leaderboard, it scored an SPL of 0.21 on the test set, against 0.38 for a nav-graph agent with a similar architecture (Table 4). About 20% of R2R trajectories cannot be completed in VLN-CE, and continuous paths translate poorly to the graph where panoramas are sparse; the authors estimate that these two effects together cost about 0.10 SPL, which still leaves nav-graph agents clearly ahead.

Datasets and Benchmarks

Benchmark	Environment	Instructions	Paths	Language	Main scores
R2R (2018)	Matterport3D nav-graph, 90 buildings	21,567, avg. 29 words	7,189 shortest paths, 4–6 edges	English	SR, SPL, NE, OSR, TL
R4R (2019)	as R2R	joined R2R instructions	joined paths, avg. 20.6 m (train)	English	CLS, nDTW, SDTW
RxR (2020)	as R2R	126,069, avg. 78 words	16,522; 44.5% not shortest	English, Hindi, Telugu	nDTW, SDTW
REVERIE (2020)	as R2R, with object boxes	21,702, avg. 18 words	4,140 target objects	English	RGS, RGSPL, SR, SPL
VLN-CE (2020)	Matterport3D meshes in Habitat	R2R’s	4,475 converted trajectories	English	SR, SPL, nDTW

Seen and unseen splits. R2R follows the building split of Matterport3D (Anderson et al., 2018): 18 buildings and 4,173 instructions for test; 11 buildings and 2,349 instructions for validation in unseen environments (val unseen); and 61 buildings whose instructions are split into 14,025 for training and 1,020 for validation in seen environments (val seen). Val seen therefore tests new instructions in buildings whose images the agent was trained on, and val unseen tests new buildings. Test goals are withheld and scored by an evaluation server. Later papers print slightly different counts for the same splits: Jain et al. (2019, Table 1) give 14,039, 1,021 and 2,249. RxR keeps the same environment splits, with 11,089 training, 1,232 val-seen, 1,517 val-unseen and 2,684 test paths (Ku et al., 2020). The gap between seen and unseen splits is the field’s measure of overfitting to environments, and results are compared on val unseen or test unseen.

Biases of the data. Anderson et al. (2018) note selection biases in Matterport3D: most living spaces are clean, tidy and often luxurious, there are very few people or animals, and capture positions tend to give commanding views of a room, not the positions a robot might find itself in.

Evaluation Metrics

Let the agent’s path be the sequence of nodes $P = (p_1, \dots, p_{|P|})$, the reference path $R = (r_1, \dots, r_{|R|})$, $d(\cdot, \cdot)$ the shortest-path distance along the navigation graph, and $d_{th} = 3$ m.

Goal metrics (R2R). Navigation error is the graph distance from the stopping node to the goal, $\mathrm{NE} = d(p_{|P|}, r_{|R|})$, ignoring heading and elevation. An episode succeeds if NE is less than 3 m, a margin of about one viewpoint and below R2R’s minimum starting distance of 5 m (Anderson et al., 2018). Oracle success applies the same test to the node of the path closest to the goal, as if the agent had stopped there. Trajectory length (TL, also called path length) sums the edge lengths travelled. SPL, proposed by the navigation working group of Anderson, Chang, Chaplot and colleagues (2018) and defined in Visual Navigation, weights each success by $\ell / \max(\mathrm{PL}, \ell)$, where $\ell = d(p_1, r_{|R|})$ is the shortest-path distance from start to goal, not the length of the reference path. The official evaluation code makes these choices concrete (Anderson et al., eval.py): success and oracle success use a strict < 3.0, the oracle node is the path node nearest the goal by graph distance, and SPL averages $\ell / \max(\mathrm{TL}, \ell)$ over successes and 0 over failures. Anderson et al. (2018) deliberately did not score the trajectory, “as many instructions do not specify the path that should be taken” in their words.

Coverage weighted by Length Score (CLS). Jain et al. (2019) list desiderata for a fidelity metric: it should depend on every node of both paths, penalize deviations softly by distance, have a unique optimum at the reference path, be invariant to the scale of the graph and be cheap to compute. CLS multiplies path coverage by a length score:

$$\mathrm{PC}(P, R) = \frac{1}{|R|} \sum_{r \in R} \exp\left( -\frac{d(r, P)}{d_{th}} \right), \qquad \mathrm{EPL} = \mathrm{PC} \cdot \mathrm{PL}(R),$$ $$\mathrm{LS}(P, R) = \frac{\mathrm{EPL}}{\mathrm{EPL} + |\mathrm{EPL} - \mathrm{PL}(P)|}, \qquad \mathrm{CLS} = \mathrm{PC} \cdot \mathrm{LS},$$

with $d(r, P) = \min_{p \in P} d(r, p)$. Coverage replaces success with a soft measure of how closely the agent passed each reference node, and the length score compares the agent’s path length with the length expected for that coverage. The reference implementation in google-research’s r4r folder computes exactly this; its doctest, however, calls the function with the two paths in the opposite order to its signature, so the third doctest value (0.442) corresponds to scoring the reference against the agent’s path.

Normalized Dynamic Time Warping (nDTW). Ilharco et al. (2019) pointed out that coverage is blind to order: for a reference path $(a, b, c, a)$, the paths $(a, c, b, a)$ and $(a, b, c, a)$ have the same coverage. Dynamic time warping aligns the two sequences monotonically, matching every node of each path to at least one node of the other, with first nodes matched to each other and last nodes to each other, and minimizes the summed distance. With $C_{0,0} = 0$, $C_{i,0} = C_{0,j} = \infty$ and

$$C_{i,j} = d(r_i, q_j) + \min(C_{i-1,j},\, C_{i,j-1},\, C_{i-1,j-1}),$$

$\mathrm{DTW}(R, Q) = C_{|R|,|Q|}$ for the query path $Q$, computed exactly in $O(|R||Q|)$ time, and

$$\mathrm{nDTW}(R, Q) = \exp\left( -\frac{\mathrm{DTW}(R, Q)}{|R| \cdot d_{th}} \right), \qquad \mathrm{SDTW} = \mathrm{SR} \cdot \mathrm{nDTW}.$$

Dividing by $|R| \cdot d_{th}$ makes the score comparable across graphs of different density, since DTW is a sum of at least $|R|$ terms; the exponential maps it to $(0, 1]$, reaching 1 only when DTW is zero, that is, when the path visits exactly the reference nodes in order (repetitions aside). The distance can be the graph distance in discrete environments or a Euclidean or precomputed grid distance in continuous ones. In a human study with 2,525 rated pairs of synthetic paths from nine raters, sign tests over the sets of ranked paths found that nDTW correlated better with the human rankings than path length, navigation error, oracle navigation error, CLS and average or maximum deviation, and SDTW better than success, oracle success, SPL and success weighted by edit distance (Ilharco et al., 2019, Table 1).

The implementations differ in details that matter at the margin. The r4r dtw.py uses graph distances and counts success as $\mathrm{NE} \le d_{th}$, as does the nDTW paper’s table of metric definitions, while R2R’s eval.py uses $<$. VLN-CE’s code computes nDTW over the agent’s recorded positions with Euclidean distance, by default with the approximate FastDTW algorithm (Krantz et al., measures.py, at the commit cited), and uses a 3.0 m success distance and a 500-step episode limit in its task configuration.

REVERIE’s grounding metrics. Remote grounding success (RGS) counts an episode as solved if the agent selects the correct box from the candidates, or predicts a box with IoU of at least 0.5 when no candidates are given, for the target seen within 3 m (Qi et al., 2020); RGSPL, reported by later papers, weights it by path length as SPL does (Hong et al., 2021). Navigation success requires stopping within 3 m of the object.

Example: grounding instructions and scoring path fidelity

The example below builds small buildings as navigation graphs, renders the view at every node as an image, and follows templated instructions with a rule-based parser and a learned landmark detector. It then scores five agents with the goal metrics of R2R’s eval.py and the fidelity metrics of the r4r code, on new instructions in the training layouts (val seen) and in new layouts with unseen colour casts (val unseen). Visual Navigation has a point-goal grid example scored by SPL; here the goal is given in words and the reference path is not the shortest path, so the metrics can disagree.

Each layout is an 8 × 8 lattice of viewpoints 2.25 m apart, R2R’s average spacing, connected to their four neighbours and split into four rooms by walls with one door gap each. Twelve of the 20 landmark classes (five shapes in four colours) are placed on random nodes; every node’s view is a 24 × 24 RGB image of the floor texture of the layout’s style, with the landmark drawn at random scale and offset, plus noise. Four floor styles appear in the 30 training layouts and two others, with warm and cool colour casts, only in the 10 unseen layouts. An instruction reads “go past the red door, then past the green lamp, and stop at the blue chair”; its reference path joins the shortest paths through the three landmarks, as R4R joins R2R paths, and the start lies at least three edges (6.75 m) from the goal. A logistic-regression detector is trained on every node view of the training layouts. Grounding a phrase means choosing the node whose view gives the highest probability for the named class, with every view available in advance, a fully observed setting that isolates grounding from exploration.

The agents are: the reference path itself; the shortest path to the true goal; the follower, which visits the grounded landmarks in the order given; a goal-only agent, which grounds only the last phrase; and an order-ignoring agent, which visits the two intermediate landmarks nearest-first. Success is printed with both < and ≤, and nDTW with graph and with Euclidean distances, since the sources use both. The script runs seeds 0, 1 and 2 (each regenerates the layouts, renderings and episodes and retrains the detector) and prints means over the seeds. It uses NumPy 2.3.5 and scikit-learn 1.7.2 and takes about 40 seconds.

import numpy as np
from collections import deque
from sklearn.linear_model import LogisticRegression

N, STEP, TH = 8, 2.25, 3.0          # 8x8 viewpoints, 2.25 m apart, 3 m threshold
SHAPES = ["door", "chair", "lamp", "table", "plant"]
COLOURS = {"red": (0.85, 0.15, 0.15), "green": (0.15, 0.70, 0.20),
           "blue": (0.15, 0.25, 0.85), "yellow": (0.90, 0.85, 0.15)}
CLASSES = [(c, s) for s in SHAPES for c in COLOURS]          # 20 landmark classes
STYLES = [  # floor colour, texture, colour cast; styles 4-5 only in unseen layouts
    ((0.55, 0.50, 0.45), "stripes", (1.00, 1.00, 1.00)),
    ((0.40, 0.42, 0.45), "checker", (1.00, 1.00, 1.00)),
    ((0.60, 0.60, 0.58), "speckle", (1.00, 1.00, 1.00)),
    ((0.45, 0.38, 0.32), "stripes", (1.00, 1.00, 1.00)),
    ((0.50, 0.50, 0.50), "checker", (1.15, 1.00, 0.80)),
    ((0.52, 0.48, 0.44), "speckle", (0.85, 1.00, 1.15))]
XY = np.array([(i % N * STEP, i // N * STEP) for i in range(N * N)])

def make_layout(rng):
    """Nav-graph with a cross of walls (one door gap per wall segment)."""
    gaps_h = {rng.integers(0, 4), rng.integers(4, 8)}      # columns crossing row 3|4
    gaps_v = {rng.integers(0, 4), rng.integers(4, 8)}      # rows crossing column 3|4
    nbrs = [[] for _ in range(N * N)]
    for r in range(N):
        for c in range(N):
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                rr, cc = r + dr, c + dc
                if not (0 <= rr < N and 0 <= cc < N):
                    continue
                if {r, rr} == {3, 4} and c not in gaps_h:
                    continue
                if {c, cc} == {3, 4} and r not in gaps_v:
                    continue
                nbrs[r * N + c].append(rr * N + cc)
    nodes = rng.choice(N * N, 12, replace=False)
    classes = rng.choice(len(CLASSES), 12, replace=False)
    label = np.full(N * N, len(CLASSES))                   # 20 = no landmark
    label[nodes] = classes
    return nbrs, label

def bfs(nbrs, s):
    dist, prev, q = {s: 0}, {s: None}, deque([s])
    while q:
        u = q.popleft()
        for v in nbrs[u]:
            if v not in dist:
                dist[v], prev[v] = dist[u] + 1, u
                q.append(v)
    return dist, prev

def all_pairs(nbrs):
    D, P = np.zeros((N * N, N * N)), []
    for s in range(N * N):
        dist, prev = bfs(nbrs, s)
        D[s] = [dist[t] * STEP for t in range(N * N)]
        P.append(prev)
    return D, P

def route(P, stops):
    """Concatenated shortest paths through a list of stops."""
    path = [stops[0]]
    for a, b in zip(stops[:-1], stops[1:]):
        seg, u = [], b
        while u != a:
            seg.append(u)
            u = P[a][u]
        path += seg[::-1]
    return path

def render(cls, style, rng):
    floor, texture, cast = STYLES[style]
    yy, xx = np.mgrid[0:24, 0:24]
    pat = {"stripes": (xx // 3) % 2, "checker": ((xx // 4) + (yy // 4)) % 2,
           "speckle": rng.random((24, 24)) > 0.7}[texture]
    img = np.array(floor) + 0.08 * (pat[..., None] - 0.5)
    if cls < len(CLASSES):
        colour, shape = CLASSES[cls]
        s = rng.uniform(0.6, 0.9) * 24
        cx, cy = 12 + rng.integers(-2, 3), 12 + rng.integers(-2, 3)
        u, v = (xx - cx) / s, (yy - cy) / s
        mask = {"door": (abs(u) < 0.18) & (abs(v) < 0.45),
                "table": (abs(u) < 0.45) & (abs(v) < 0.18),
                "chair": ((u > -0.3) & (u < -0.12) & (abs(v) < 0.4)) |
                         ((abs(u) < 0.3) & (v > 0.0) & (v < 0.15)),
                "lamp": (v < 0.4) & (abs(u) < (v + 0.4) * 0.55) & (v > -0.4),
                "plant": u ** 2 + v ** 2 < 0.38 ** 2}[shape]
        img[mask] = COLOURS[colour]
    img = img * np.array(cast) + rng.normal(0, 0.05, img.shape)
    return np.clip(img, 0, 1)

def make_episode(rng, label, D, P):
    marks = np.flatnonzero(label < len(CLASSES))
    empty = np.flatnonzero(label == len(CLASSES))
    while True:
        start = rng.choice(empty)
        l1, l2, goal = rng.choice(marks, 3, replace=False)
        if D[start, goal] >= 3 * STEP:
            break
    words = [" ".join(CLASSES[label[n]]) for n in (l1, l2, goal)]
    text = f"go past the {words[0]}, then past the {words[1]}, and stop at the {words[2]}"
    return text, start, route(P, [start, l1, l2, goal])

def parse(text):
    """Rule-based parser: the ordered (colour, shape) mentions."""
    toks = text.replace(",", "").split()
    return [CLASSES.index((toks[i], toks[i + 1])) for i in range(len(toks) - 1)
            if toks[i] in COLOURS and toks[i + 1] in SHAPES]

def dtw(pred, ref, dist):
    C = np.full((len(pred) + 1, len(ref) + 1), np.inf)
    C[0, 0] = 0
    for i in range(1, len(pred) + 1):
        for j in range(1, len(ref) + 1):
            C[i, j] = dist(pred[i - 1], ref[j - 1]) + min(C[i - 1, j], C[i, j - 1], C[i - 1, j - 1])
    return C[-1, -1]

def scores(pred, ref, D):
    geo = lambda a, b: D[a, b]
    euc = lambda a, b: np.linalg.norm(XY[a] - XY[b])
    goal, start = ref[-1], ref[0]
    ne = D[pred[-1], goal]
    pl = sum(D[a, b] for a, b in zip(pred[:-1], pred[1:]))
    sp = D[start, goal]
    succ = ne < TH                                       # R2R eval.py
    ndtw = np.exp(-dtw(pred, ref, geo) / (len(ref) * TH))
    ndtw_e = np.exp(-dtw(pred, ref, euc) / (len(ref) * TH))
    pc = np.mean([np.exp(-min(D[r, p] for p in pred) / TH) for r in ref])
    epl = pc * sum(D[a, b] for a, b in zip(ref[:-1], ref[1:]))
    cls = pc * epl / (epl + abs(epl - pl))
    return dict(SR=succ, SRle=ne <= TH, OSR=min(D[p, goal] for p in pred) < TH,
                NE=ne, PL=pl, SPL=succ * sp / max(pl, sp), nDTW=ndtw,
                nDTWe=ndtw_e, SDTW=(ne <= TH) * ndtw, CLS=cls)

def run(seed):
    rng = np.random.default_rng(seed)
    envs = []
    for i in range(40):                                  # 30 training, 10 unseen
        nbrs, label = make_layout(rng)
        style = i % 4 if i < 30 else 4 + i % 2
        views = np.array([render(c, style, rng) for c in label])
        envs.append((label, views, *all_pairs(nbrs)))
    X = np.concatenate([e[1] for e in envs[:30]]).reshape(30 * N * N, -1)
    y = np.concatenate([e[0] for e in envs[:30]])
    det = LogisticRegression(C=1.0, max_iter=2000).fit(X, y)
    out = {}
    for split, pool in (("val_seen", envs[:30]), ("val_unseen", envs[30:])):
        prob = [det.predict_proba(e[1].reshape(N * N, -1)) for e in pool]
        view_acc = np.mean([np.mean(p.argmax(1) == e[0]) for p, e in zip(prob, pool)])
        rows, hits = {a: [] for a in "ABCDE"}, []
        for _ in range(100):
            k = rng.integers(len(pool))
            label, _, D, P = pool[k]
            text, start, ref = make_episode(rng, label, D, P)
            found = [int(prob[k][:, c].argmax()) for c in parse(text)]
            hits += [label[n] == c for n, c in zip(found, parse(text))]
            l1, l2, g = found
            near, far = sorted((l1, l2), key=lambda n: D[start, n])
            paths = {"A": ref, "B": route(P, [start, ref[-1]]),
                     "C": route(P, [start, l1, l2, g]), "D": route(P, [start, g]),
                     "E": route(P, [start, near, far, g])}
            for a, p in paths.items():
                rows[a].append(scores(p, ref, D))
        out[split] = (view_acc, np.mean(hits),
                      {a: {m: np.mean([r[m] for r in v]) for m in v[0]} for a, v in rows.items()})
    return out

names = {"A": "reference", "B": "shortest-to-goal", "C": "follower",
         "D": "goal-only", "E": "order-ignoring"}
res = [run(s) for s in (0, 1, 2)]
cols = ["SR", "SRle", "OSR", "NE", "PL", "SPL", "nDTW", "nDTWe", "SDTW", "CLS"]
for split in ("val_seen", "val_unseen"):
    print(f"{split}: view accuracy " + " ".join(f"{r[split][0]:.3f}" for r in res)
          + " | landmark grounding " + " ".join(f"{r[split][1]:.3f}" for r in res))
    print(f"  {'agent':17s}" + "".join(f"{c:>7s}" for c in cols))
    for a in "ABCDE":
        m = [np.mean([r[split][2][a][c] for r in res]) for c in cols]
        print(f"  {names[a]:17s}" + "".join(f"{v:7.2f}" for v in m))
    for c in ("SR", "nDTW"):
        v = [r[split][2]["C"][c] for r in res]
        print(f"  follower {c} over seeds 0-2: {min(v):.2f}-{max(v):.2f}")

val_seen: view accuracy 1.000 1.000 1.000 | landmark grounding 1.000 1.000 1.000
  agent                 SR   SRle    OSR     NE     PL    SPL   nDTW  nDTWe   SDTW    CLS
  reference           1.00   1.00   1.00   0.00  41.23   0.41   1.00   1.00   1.00   1.00
  shortest-to-goal    1.00   1.00   1.00   0.00  15.59   1.00   0.30   0.37   0.30   0.38
  follower            1.00   1.00   1.00   0.00  41.23   0.41   1.00   1.00   1.00   1.00
  goal-only           1.00   1.00   1.00   0.00  15.59   1.00   0.30   0.37   0.30   0.38
  order-ignoring      1.00   1.00   1.00   0.00  38.02   0.45   0.77   0.80   0.77   0.90
  follower SR over seeds 0-2: 1.00-1.00
  follower nDTW over seeds 0-2: 1.00-1.00
val_unseen: view accuracy 0.961 0.967 0.961 | landmark grounding 0.963 0.967 0.937
  agent                 SR   SRle    OSR     NE     PL    SPL   nDTW  nDTWe   SDTW    CLS
  reference           1.00   1.00   1.00   0.00  41.15   0.40   1.00   1.00   1.00   1.00
  shortest-to-goal    1.00   1.00   1.00   0.00  15.10   1.00   0.28   0.36   0.28   0.38
  follower            0.95   0.95   0.96   0.78  40.75   0.39   0.92   0.93   0.90   0.96
  goal-only           0.95   0.95   0.96   0.78  15.10   0.95   0.27   0.35   0.27   0.37
  order-ignoring      0.95   0.95   0.96   0.78  37.16   0.42   0.71   0.74   0.69   0.87
  follower SR over seeds 0-2: 0.93-0.97
  follower nDTW over seeds 0-2: 0.90-0.96

The reference agent checks the metrics: nDTW, SDTW and CLS equal 1 only because its path is the reference, yet its SPL is about 0.4, because SPL divides the shortest start-to-goal distance by the length walked, and the reference paths are on average about 2.6 times as long as the paths of the shortest-path oracle (41.2 m against 15.6 m on val seen). A perfectly faithful agent is penalized by SPL whenever the instruction describes a detour, the situation Jain et al. (2019) illustrate with a path that scores 0.17 SPL while following the reference closely. The shortest-path oracle shows the converse: perfect success and SPL with an nDTW near 0.3, so goal metrics cannot tell instruction following from goal seeking.

The learned agents make the same point from the other side. The follower and the goal-only agent have identical success and navigation error on both splits because, by construction, both stop at the node grounded for the last phrase: success depends only on grounding the goal. Their oracle success also agrees to two decimals, although that is not guaranteed, since the follower’s longer path can pass near the true goal after a wrong final grounding. Only the fidelity metrics separate them. The order-ignoring agent visits the same landmarks and stops at the same place, so its success is unchanged, but its nDTW falls much further than its CLS. By construction CLS cannot see order: coverage asks only how near the path comes to each reference node at any time, so the reordered path loses CLS only where it passes far from reference nodes and through its length. DTW’s monotone alignment cannot match a reversed visit order cheaply, the property Ilharco et al. (2019) designed it to have. Euclidean nDTW is higher than geodesic nDTW for every agent, as it must be: straight-line distances never exceed distances along the graph, which on a four-connected lattice are longer for any diagonal offset and longer still where walls force detours. Success with < and ≤ agrees because no graph distance on a 2.25 m lattice equals 3 m exactly.

On val seen the detector labels every view correctly because it was trained on exactly those images. Val unseen adds layouts with colour casts it has not seen, and it mislabels 3–4% of views; a wrong grounding of the last phrase sends the agent to the wrong node, which is where the navigation errors and the 0.93–0.97 range of follower success come from. In our reading this is a mild version of R2R’s seen–unseen gap, which in R2R comes from real buildings, varied language and visual groundings specific to the training environments; a colour cast on synthetic shapes cannot show how large that gap is, and the templated language, known graph and full view of every node remove the exploration, stopping and language-understanding problems that dominate real VLN.

Applications

Anderson et al. (2018) motivate VLN with robots that carry out verbal instructions in buildings they have not seen, and see stopping at the goal as freeing the agent for a further task there. REVERIE’s instructions are of that kind, such as pushing in a particular bar chair in the kitchen, although its agents only navigate and point to the object, without manipulating it (Qi et al., 2020). VLN-CE chose its observation and action spaces to emulate a ground robot with a single forward camera, similar to a LoCoBot, and actions that robots with standard motion controllers can execute (Krantz et al., 2020). Instruction following is one of the tasks of embodied AI and of robot perception more broadly. The speaker models built for data augmentation are instruction generators in their own right: Fried et al. (2018) trained theirs on human route descriptions, and RxR’s authors list training models to generate navigation instructions among the uses of their dataset.

Open Problems

• Leaving the simulator. Krantz et al. (2020) note that transferring nav-graph agents to physical robots had not been examined, and their continuous setting exists to make that possible. Moving from simulation to real robots is the subject of sim-to-real transfer.
• Generalization. Every method above narrows the gap between seen and unseen buildings without closing it, and gains from more environments outpaced gains from more instructions in Tan et al.’s (2019) analysis.
• Fidelity versus goal reaching. Agents trained with goal rewards can largely ignore the middle of the instruction (Jain et al., 2019). Fidelity metrics and rewards exist, but R2R’s reference paths are shortest paths, on which reaching the goal directly and following the route coincide, and PREVALENT’s authors, for example, treat SPL as R2R’s primary metric (Hao et al., 2020).
• Comparability. On the same test set, Tan et al.’s agent scored 51.5% success and an SPL of 0.47 in a single run, 68.9% and 0.01 with beam search, and 63.9% and 0.61 after pre-exploration (Tan et al., 2019, Table 1), and details such as < against ≤ for success, graph against Euclidean distances and exact against approximate DTW differ between official implementations.
• Language models as navigators. NavGPT’s zero-shot agent reasons in explicit text but remains far below trained agents (Zhou et al., 2024).
• Languages and people. Apart from about 1,000 instructions translated into Chinese for a game-like environment, all publicly available VLN datasets known to Ku et al. (2020) had English instructions before RxR, and the Matterport3D buildings have the selection biases described above.