Tree-Structured Trajectory Encoding for Vision-and-Language Navigation

Xinzhe Zhou, Yadong MuAAAI 2023 · DOI

Introduction

Vision-and-Language Navigation (VLN) tasks challenge agents to reach a target location by following natural language instructions in complex, photo-realistic environments. A core difficulty in VLN is maintaining an effective memory of the agent's trajectory. Most existing models treat navigation history as a simple chronological sequence. However, this "flat" representation conflates productive steps with erroneous detours, making it difficult for agents to recover from mistakes or understand their current state relative to the goal.

The Problem with Sequential Memory

When an agent using a sequential encoder (like an LSTM or standard Transformer) makes a mistake and backtracks, its memory grows linearly: $A \rightarrow B \rightarrow C \rightarrow B \rightarrow D$. In this sequence, the "correction" ($B \rightarrow D$) is indistinguishable from the "error" ($B \rightarrow C$). This lack of structural hierarchy prevents the agent from clearly identifying which parts of its history are relevant to the current path and which are failed explorations.

Proposed Method: Tree-Structured Encoding

To address these limitations, the authors introduce a tree-structured trajectory encoding. Instead of a list, the navigation history is organized as a tree rooted at the starting point.

Overview of the tree-structured approach, including encoding comparison, high-level architecture, and robustness results.

1. Tree-Structured Trajectory

In this framework, moving to a new location adds a child node, while backtracking moves the active pointer up the tree. New movements from a previous node create a new branch, effectively isolating erroneous paths into deprecated branches. This structural isolation allows the agent to "forget" the noise of a mistake while still retaining the visual information gathered during that exploration.

2. The Tree-Transformer

The authors adapt the Transformer architecture to this tree structure. They replace standard positional embeddings with Depth Embeddings, which represent a node's distance from the root. Furthermore, a Tree-based Attention Mask restricts each node's attention to its ancestors and descendants, preventing information leakage between unrelated branches of exploration.

Technical details of the Tree-Transformer, showing depth embeddings and the tree-attention mask.

3. Action Space and Rewards

The model utilizes a tree-based action space that allows "jumping" to any previously visited node, facilitating long-range error correction. To manage complexity, Dynamic Filtering limits backtracking candidates to the $k$ most recently visited nodes. Additionally, a Tree-nDTW Reward is used during Reinforcement Learning, focusing only on the current active path and ignoring "dead" branches.

Experimental Results

The model was evaluated on the Room-to-Room (R2R) and Room-Across-Room (RxR) benchmarks, achieving state-of-the-art results.

  • Performance Benchmarks: On R2R, the model achieved a 68% Success Rate (SR) on the val-unseen split, outperforming models like VLN-HAMT and RecBert. On the multi-lingual RxR dataset, it reached a 58.7% SR.
  • Robustness to Errors: A key finding was the agent's resilience to early mistakes. When manually forced to take wrong steps at the start, the Tree-Structured agent maintained a stable success rate, whereas sequential models saw significant performance drops.
  • Path Quality: The model scored 0.74 on the "Identified nDTW" metric, indicating a superior ability to identify the correct path amidst navigation noise compared to RecBert (0.67).

Conclusion

By moving from sequential to tree-structured memory, the proposed model effectively separates exploration noise from navigational intent. While this approach increases implementation complexity and can lead to longer trajectory lengths due to increased exploration, it provides a robust framework for error correction in complex embodied AI tasks. Future work may extend this structural approach to broader domains like robotic manipulation and task planning.

Summary updated

BibTeX
@inproceedings{zhou2023tree,
  author = {Xinzhe Zhou and Yadong Mu},
  title = {{Tree-Structured Trajectory Encoding for Vision-and-Language Navigation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i3.25494},
}
Figure