ETPNav: Evolving Topological Planning for Vision-Language Navigation in Continuous Environments

In plain words

Imagine a robot in a house that receives a spoken-style direction such as "go past the sofa, then turn left at the kitchen door, and stop by the sink." It has to work out where to go and also how to move its wheels around furniture, not just pick a place on a floor plan.

ETPNav splits that job into two parts. As the robot walks, it sketches a simple map of the places it has been and the nearby spots it could go next, linking them as a graph with no prior knowledge of the house. A language-aware planner then looks at that graph and the instruction and picks which spot to head for, even one far back along the path, so the robot can return to a junction it passed earlier. A separate low-level controller drives it there. The controller is built to stop the robot from getting stuck against walls when it is not allowed to slide along them. When it is stuck, it wiggles to the side and tries again.

The authors report that this beats earlier methods on two benchmarks for following instructions in simulated continuous rooms, and that it won a 2022 challenge on one of them.

TL;DR

• ETPNav is a hierarchical navigation system for vision-language navigation in continuous (not grid or graph) indoor scenes.
• It builds an online topological map from predicted waypoints, plans over that map with a cross-modal transformer, and executes plans with a rotate-then-forward controller.
• The controller adds a "Tryout" escape for deadlocks, which matters when sliding along walls is forbidden (RxR-CE).
• Author-reported results: 55 SR and 48 SPL on R2R-CE test unseen; 51.21 SR, 39.86 SPL and 41.30 SDTW on RxR-CE test unseen tab. 2 tab. 4.
• Relevant if you build an instruction-following agent in Habitat. The code is MIT-licensed, but it does not reproduce every hyperparameter in the paper (see Paper vs code).

Problem

VLN-CE asks an agent to follow a natural-language instruction while moving with low-level actions (FORWARD 0.25 m, ROTATE 15°, STOP) on a 3D mesh, not on a predefined navigation graph §3 §2. End-to-end policies that predict actions directly perform well below discrete VLN §1. Modular waypoint methods decouple waypoint generation, subgoal selection and control, but the waypoints are local, so the agent struggles to capture global layout and to backtrack to a remote location; the controllers used with them also ignore obstacles §1 §2.

The problem is most acute when sliding along obstacles is forbidden, as in RxR-CE with a 0.18 m chassis radius. Under that setting the authors report that the common controllers get stuck frequently and cause a severe performance drop §1 §4.1.1.

The method assumes the agent knows its ground-truth pose from the simulator; noisy pose estimation is left to future work §3 §5.

Method

Setup §3. At each location the agent receives 12 RGB and 12 depth images at 12 equally spaced headings (0°, 30°, …, 330°) plus an instruction of L word embeddings. The action space is FORWARD (0.25 m), ROTATE LEFT/RIGHT (15°) and STOP. Each decision loop runs three modules: topological mapping, cross-modal planning and control fig. 1.

Topological mapping §3.1 fig. 2. The map is a graph G_t = (N_t, E_t). Nodes are visited nodes, the current node, or ghost nodes (observed but not yet visited). Edges connect nodes that are directly reachable and store Euclidean distance.

1. A waypoint predictor, pre-trained on the MP3D graph dataset and frozen, takes only the depth features and the heading features, runs a two-layer transformer over views and outputs a heatmap over candidate relative poses. K waypoints are sampled from it with non-maximum suppression. The paper does not state K §3.1.
2. RGB, depth and orientation features are fused with a linear layer and passed through a panorama encoder. The current node is the average of the panorama embeddings. A waypoint is represented by the embedding of the view it lies in (for example, the first view for headings 0° to 30°) §3.1.
3. Each waypoint is localised with F_L: if the nearest existing node is within γ, the rule below applies; otherwise a new ghost is created §3.1.
   • Nearest is a visited node: discard the waypoint and add an edge from the current node to that visited node.
   • Nearest is a ghost: add the waypoint to that ghost, whose position and embedding become the mean of its accumulated waypoints.
   • Nothing within γ: make the waypoint a new ghost.

Cross-modal planning §3.2 fig. 3. The instruction goes through a BERT-style text encoder (word embedding, positional embedding and a text type embedding, then transformer layers). The topological map and the instruction then go through a cross-modal graph encoder, similar to LXMERT, where every layer pairs a bidirectional cross-attention step with two self-attention steps and two feed-forward steps §3.2.

• Node encoding. Each node's visual feature gets a pose encoding (relative orientation and distance to the current node) and a step encoding (the last visited time step, or 0 for ghosts). A STOP node is connected to every other node §3.2.
• Graph-aware self-attention (GASA) adds a learned term computed from all-pairs shortest-path distances on the graph to the attention logits, so that the attention reflects graph topology as well as visual similarity eq. 1 §3.2.
• Goal scores are a feed-forward head over each node's output eq. 2. Visited nodes and the current node are masked. The chosen goal is the best-scoring ghost or the STOP node §3.2.
• If a ghost is chosen, the agent computes a shortest path on the graph with Dijkstra's algorithm; the resulting plan is a sequence of subgoal node positions §3.2.

Control §3.3. The rotate-then-forward controller (RF) computes the relative heading and distance to each subgoal, quantises the heading into 15° rotations and then issues 0.25 m forward steps. Each subgoal is consumed in turn §3.3.

• Unreachable goals. Because a ghost may sit off the navigable mesh, the selected ghost is deleted from the map before the controller tries to reach it, so the same goal is not chosen repeatedly §3.3.
• Tryout (obstacle avoidance, active only when sliding is forbidden). When a FORWARD step does not change the agent's position, Tryout rotates to a set of predefined headings Δθ^try and attempts a single forward step at each. If the agent moves, it has left the dead end and returns to its original heading to continue RF. The paper gives seven equally spaced headings from −90° to 90° §3.3 §4.3.3.

Training and inference §3.4.

• Pre-training. The planner is pre-trained with two proxy tasks, masked language modelling (MLM) and single-action prediction (SAP), on offline topological maps built from the discrete VLN graphs (R2R and RxR), with synthetic instructions from Prevalent and Marky-mT5 §3.4 §4.1.3. Visual features are aligned from Habitat renders onto the predefined graph §3.4.
• Fine-tuning. The model runs online in Habitat with student forcing: at each decision the next node is sampled from the predicted scores, with teacher supervision from a DAgger-style interactive demonstrator. On R2R-CE the teacher is the ghost with the shortest geodesic distance to the goal. On RxR-CE, which has no shortest-path prior, the teacher is the ghost closest to the next unvisited subgoal of the annotated reference path §3.4.
• Loss: the summed negative log-likelihood of the teacher node over decision steps eq. 3.
• Inference. The agent picks the highest-scoring ghost greedily and runs the same map–plan–control cycle. An episode ends on a STOP decision or when the maximum number of goal predictions is reached: 15 for R2R-CE and 25 for RxR-CE §3.4.

# ETPNav decision loop at inference  [§3] [§3.1] [§3.2] [§3.3]
# Input:  instruction word embeddings; max_predictions (15 R2R, 25 RxR)
# Output: a low-level action sequence ending in STOP

def navigate(instruction_words, max_predictions):
    # Encode the instruction once  [§3.2]
    text_embeds = text_encoder(instruction_words)           # (L, d)
    graph = empty_topological_map()
    for step in range(max_predictions):
        # Predict waypoints from depth features only  [§3.1]
        waypoints = waypoint_predictor(depth_views)          # K waypoints
        # Fuse RGB, depth and heading per view  [§3.1]
        views = panorama_encoder(rgb_views, depth_views, headings)
        # The current node is the mean of its panorama embeddings  [§3.1]
        current_embed = mean(views)
        # Localise each waypoint against nodes and ghosts  [§3.1]
        graph = update_graph(graph, current_embed, waypoints)
        # Score ghosts and STOP; visited and current nodes are masked  [§3.2]
        scores = cross_modal_graph_encoder(text_embeds, graph)
        if argmax(scores) is STOP:
            return stop_action()
        # Plan a shortest graph path to the chosen ghost, then drive it  [§3.3]
        goal = argmax(scores)
        remove_ghost(graph, goal)     # so an unreachable goal is not reselected
        rotate_forward_along(shortest_path(graph, goal))
    return stop_action()

# Tryout: escape a deadlock while sliding is forbidden  [§3.3]
# Triggered when a FORWARD step does not move the agent

def tryout(original_heading, headings):
    # Try each predefined heading with one forward step  [§3.3]
    for heading in headings:              # 7 headings from -90 to 90 deg
        rotate_to(heading)
        before = agent_position()
        forward_one_step()
        if agent_position() != before:
            # Dead end left: restore the heading and resume RF  [§3.3]
            rotate_to(original_heading)
            return True
    return False

# Fine-tuning loss with student forcing  [§3.4] [eq. 3]
# Input:  episode (instruction, graph, teacher rule); sample_ratio

def fine_tune_loss(episode, sample_ratio):
    loss = 0.0
    for step in range(max_predictions):
        scores = cross_modal_graph_encoder(text_embeds, graph)
        teacher = teacher_ghost(graph, episode)  # goal or next subgoal
        # Accumulate the negative log-likelihood of the teacher  [eq. 3]
        loss = loss + cross_entropy(scores, teacher)
        # Follow the teacher with probability sample_ratio  [§3.4]
        sampled = sample(scores)
        action = teacher if random() <= sample_ratio else sampled
        advance_simulator(action)
    return loss

Key equations, as numbered in the source:

\textrm{GASA}(\bm{X}) = \textrm{softmax}\left(\frac{\bm{X}\bm{W}_q(\bm{X}\bm{W}_k)^\top}{\sqrt{d}} + \bm{E}\bm{W}_e\right)\bm{X}\bm{W}_v eq. 1

where X stacks the node encodings and E holds all-pairs shortest distances on the graph §3.2.

\bm{s}_i = \textrm{FFN}(\tilde{\bm{n}}_i) eq. 2

where ñ_i is the multimodal representation of node i and s_0 is the STOP score §3.2.

L = \sum_{t=1}^{T} -\log p(a_t^{*} \mid W, G_t) eq. 3

where a_t* is the teacher node at step t §3.4.

Hyperparameters

Values in the first block are stated in the paper. Values in the second block come from the official code only and are marked as such.

Results

Author-reported. Setup: Habitat simulator on R2R-CE and RxR-CE; two RTX 3090 GPUs; the baseline set is each paper's own reported numbers §4.1 §4.2. Every number below is taken from the paper's tables. Columns: TL = trajectory length (m), NE = navigation error (m), OSR = oracle success rate, SR = success rate, SPL = success weighted by path length.

R2R-CE tab. 2:

Rows with "-" are not reported in the source table. The SASRA, CMTP and LAW rows keep the paper's blanks.

Planner comparison on R2R-CE Val-Unseen, with controllers aligned to ETPNav's tab. 3: RecBERT 12.46 TL, 5.66 NE, 54.13 OSR, 45.14 SR, 39.87 SPL; HAMT 10.23, 5.41, 57.09, 49.97, 45.72; DUET 13.08, 5.16, 62.21, 53.71, 46.43; ETPNav 11.99, 4.71, 64.71, 57.21, 49.15 §4.2.1.

RxR-CE tab. 4. Columns: NE, SR, SPL, NDTW, SDTW. Rows marked † are without Marky-mT5 synthetic instructions.

RxR-CE runs use the Marky-mT5 augmentation in the main rows §4.2.2. The paper names Reborn as the authors' winning entry in the 2022 RxR-Habitat Challenge, and says the algorithm described in this paper was used to win that challenge §1 §4.2.2.

Headline claims in the paper. On R2R-CE test unseen, ETPNav beats Sim2Sim by 11 SR and 11 SPL and beats Reborn by 6 SR and 3 SPL §4.2.1. On RxR-CE val unseen, it beats CWP-RecBERT by 27.71 SR, 22.24 SPL and 15.19 NDTW §4.2.2.

Ablations (R2R-CE Val-Unseen unless noted).

• Waypoint predictor inputs tab. 5: RGBD 56.44 SR / 48.53 SPL; RGB only 51.66 SR / 42.21 SPL; depth only 57.21 SR / 49.15 SPL. Depth-only has the best %Open (84.05) and Chamfer distance (1.04).
• Map construction tab. 6: the default row (γ = 0.5 m, with waypoint accumulation and ghost deletion) gives 23.76 nodes, 57.21 SR, 49.15 SPL. Removing accumulation (row 5) drops SR to 55.89. Removing ghost deletion (row 6) drops SR to 52.41. Other γ values are in the table; γ = 1.00 m gives the fewest nodes and the lowest SR of the γ settings tested.
• Planning space tab. 7: local 53.15 SR; global 55.97 SR; global with GASA 57.21 SR / 49.15 SPL. GASA adds about 1 SR in both settings.
• Pre-training tab. 8: from scratch 37.41 SR; MLM 48.23; SAP 52.37; MLM + SAP 57.21 SR / 49.15 SPL.
• Pre-training visuals tab. 9: MP3D RGB 53.24 SR; MP3D RGB + depth 55.74; Habitat RGB 55.92; Habitat RGB + depth 57.21 SR / 49.15 SPL.
• Controllers tab. 10: R2R-CE SR/SPL: teleportation upper bound 57.97 / 49.76; PointGoal 54.86 / 44.05; FMM 52.64 / 44.34; FMM with collision map 53.62 / 44.96; RF without Tryout 57.21 / 49.15. RxR-CE SDTW: teleportation 46.04; PointGoal 43.79; FMM 21.73; FMM with collision map 41.09; RF without Tryout 18.64; RF with Tryout 45.33.
• Oracle planner tab. 11: with an oracle planner on RxR-CE Val-Unseen, RF with Tryout reaches 88.85 SR and 82.34 NDTW, against 35.92 SR for RF without Tryout, and it has 17.22 collisions per episode against 70.04 without Tryout. On R2R-CE, RF without Tryout reaches 97.61 SR and 93.27 SPL.

Dataset statistics tab. 1. R2R-CE: English only; mean path 9.89 m; mean instruction 32 words; splits 61 / 53 / 11 / 18 houses (train, val seen, val unseen, test unseen); 10,819 / 778 / 1,839 / 3,408 instructions; chassis 0.10 m; sliding allowed. RxR-CE: English, Hindi, Telugu; mean path 15.23 m; mean instruction 120 words; 59 / 57 / 11 / 17 houses; 60,300 / 6,746 / 11,006 / 9,557 instructions; chassis 0.18 m; sliding forbidden.

Paper vs code

Code: official repository MarSaKi/ETPNav at commit 160e65fe5d23ad83d024d57d710e47be6892fc68, linked from the paper's abstract. The copyright line in its MIT LICENSE names the first author. Shallow clone, raw/code/2304.03047.

Differences between the paper and the code, each with both citations:

1. Loss normalisation. The paper's loss is an unnormalised sum over steps eq. 3. The code sums the cross-entropy over steps and then divides by the total number of decision steps in the batch, so the loss is a per-step mean ss_trainer_ETP.py ss_trainer_ETP.py. Steps with no ghost left use an ignore index of −100 ss_trainer_ETP.py.
2. Teacher STOP rule. The code makes the teacher output STOP whenever the agent is within 1.5 m of the goal. The paper does not state this rule ss_trainer_ETP.py.
3. What STOP does. The paper says the episode terminates on STOP §3.4. The code, on a STOP decision or at the step limit, first moves the agent to the node with the highest stop probability among the nodes it has stood on, then issues the stop ss_trainer_ETP.py.
4. Back-path execution during training. The paper says each planned path is executed by the RF controller §3.3. In the training configs IL.back_algo defaults to teleport, and the training run script does not override it. Teleport moves the agent straight to the front node, skipping the controller iter_train.yaml main.bash ss_trainer_ETP.py environments.py. Evaluation and inference scripts set IL.back_algo control main.bash main.bash. Training and evaluation therefore use different back-path execution.
5. Teacher-forcing schedule. The paper says the teacher is used with a decaying probability (decay every 3,000 iterations, ratio 0.75) §4.1.3. The code uses the teacher with probability 0.75 raised to (⌊iteration / 3,000⌋ + 1), so the first 3,000 iterations use probability 0.75 ss_trainer_ETP.py ss_trainer_ETP.py.
6. Tryout headings. The paper describes seven equally spaced headings from −90° to 90° §3.3. The code draws a random side (±90°) for the first turn, then tries six head-and-tail turn sequences, and after a successful try it finishes the remaining forward steps environments.py. The collision check for the first forward step uses the simulator's collision flag, not a position change environments.py.
7. Tryout activation. The code enables Tryout only when ALLOW_SLIDING is false ss_trainer_ETP.py. The R2R-CE configs set sliding to true, so Tryout is off there r2r_vlnce.yaml. The paper agrees §3.3.
8. GASA implementation. The paper's graph bias is a learned matrix W_e applied to the shortest-path matrix eq. 1. The code uses a single learned linear map with one input and one output (a scalar weight and bias) applied to the normalised shortest-path distance (divided by 30 m), added to the attention mask of the visual self-attention in each cross-modal layer vilmodel_cmt.py vilmodel_cmt.py vilmodel_cmt.py ss_trainer_ETP.py. Pair distances for the STOP row are left at zero, because the loop starts at index 1 ss_trainer_ETP.py.
9. Masking. Visited nodes are masked from the logits, including the current node. The STOP node has index 0 and is not masked ss_trainer_ETP.py vilmodel_cmt.py.
10. Waypoint count and augmentation. The paper leaves K unstated. The code keeps at most five waypoints with NMS Policy_ViewSelection_ETP.py. During training with waypoint augmentation, the code samples waypoints from the heatmap Policy_ViewSelection_ETP.py.
11. Waypoint predictor input. The paper says the predictor is depth-only §3.1. The code passes RGB features to the predictor, but the RGB branch is commented out, so only depth is used TRM_net.py Policy_ViewSelection_ETP.py. This agrees with the paper.
12. RxR text encoder. The paper says it pre-trains with RoBERTa for RxR-CE §4.1.3. The code loads XLM-RoBERTa base for RxR and for any run with the xlm tokenizer vlnbert_init.py rxr_vlnce.yaml.
13. RxR fine-tuning hyperparameters. The paper gives one set of fine-tuning values, which matches the R2R-CE run. The RxR run script uses 20,000 iterations, learning rate 1.5e-5, decay interval 4,000, four GPUs and the NDTW teacher main.bash. The RxR config file itself lists 15,000 iterations and 1e-5 iter_train.yaml. The command-line overrides win at run time.
14. Pre-training configuration. The paper states batch size 64, 100,000 iterations and learning rate 5e-5 §4.1.3. The config file has per-process batch size 32, 100,000 steps, learning rate 5e-5, 10,000 warmup steps, weight decay 0.01, betas (0.9, 0.98), gradient clip 5.0 and dropout 0.1 r2r_pretrain_habitat.json. The effective batch size on two GPUs was not verified. Only an R2R-CE pre-training config is in the repository.
15. Initialisation checkpoints. The paper says the pre-training stage starts from LXMERT on R2R-CE and from RoBERTa for RxR-CE §4.1.3. The released run scripts load pre-trained weights from step 82,500 (R2R-CE) and step 90,000 (RxR-CE) main.bash main.bash.
16. Evaluation checkpoints. The release run scripts evaluate the checkpoint at iteration 12,000 (R2R-CE) and 19,600 (RxR-CE) main.bash main.bash. The paper says the best iteration on val-unseen is used §4.1.3.
17. RxR teacher. The paper describes a subgoal-tracking teacher based on the annotated reference path §3.4. The code marks reference points as reached within 3.0 m and advances a progress pointer environments.py. The 3.0 m radius is not stated in the paper.
18. Paper-internal inconsistencies. The text says RF without Tryout reaches 64.43 NDTW on RxR-CE Val-Unseen for the teleport upper bound, but the table gives 64.33 §4.3.3 tab. 10. The text gives Reborn's test SDTW as 38.43, but the table gives 38.42 §4.2.2 tab. 4.

Pitfalls

• Ground-truth pose. Mapping and control both rely on the simulator's pose §3. The paper says estimating pose from noisy sensors is future work §5, and the ablations were run with simulator poses. Replacing pose with odometry is not evaluated in the paper.
• Map size and cost. The average node count is sensitive to γ. At the default, it is about 24 nodes per episode tab. 6. Pair distances are rebuilt with all-pairs shortest paths at every step graph_utils.py, so cost grows with the number of nodes and ghosts. Larger γ reduces nodes but hurts SR sharply tab. 6.
• Ghost deletion is load-bearing. Removing deletion costs about 4.8 SR with accumulation on tab. 6 §4.3.1. The paper's own explanation is that unreachable ghosts can be picked repeatedly.
• Tryout is not a general obstacle avoider. It only runs on forward steps that fail to move, and only in sliding-forbidden settings. In the oracle study, RF without Tryout had 70.04 collisions per episode on RxR-CE tab. 11.
• Teleport in training. Training teleports along back-paths, while evaluation drives them with the controller (see Paper vs code, item 4). The paper does not discuss this difference. Expect a train/eval gap if you change one without the other.
• Dataset-dependent teacher. The R2R-CE and RxR-CE teachers differ §3.4. Changing a dataset also changes the teacher rule, the max step count and the text length.
• Synthetic instructions. The RxR-CE main results use Marky-mT5 augmentation. Without it, the paper reports lower numbers (†) §4.2.2 tab. 4. Compare like with like.
• Pre-training source. Pre-training uses discrete-graph data, not continuous environments §3.4. The Habitat-rendered visuals and depth help (tab. 9), but a visual domain gap is reported between MP3D and Habitat renders §4.3.2.
• Results are single-setting. All numbers are author-reported on the paper's splits with a fixed simulator setup. The tables show no seed or variance statistics.
• Chassis-radius plot. fig. 4 shows SR against chassis radius. The text gives only the trend and an RxR-CE gap of about 3 SR for RF over PointGoal across radii §4.3.3.

Lineage

• Builds on: the CWP / RecBERT waypoint-based VLN-CE agent, for the depth-based waypoint predictor and the panoramic setting §3.1; the LXMERT-style cross-modal encoder §3.2; the topological-map structure from prior navigation work §3.1; the VLN-CE setup and student forcing §3.4; and DAgger-style interactive teaching §3.4.
• Compared against: Seq2Seq, SASRA, CMTP, LAW, HPN, CM2, WS-MGMAP, CWP-CMA, CWP-RecBERT, Sim2Sim, Reborn, RecBERT, HAMT and DUET tab. 2 tab. 3 tab. 4.
• Superseded by: not stated in wiki content.