Source-linked AI summary
Tactical Rewind: Self-Correction via Backtracking in Vision-and-Language Navigation
Liyiming Ke, Xiujun Li, Yonatan Bisk, Ari Holtzman, Zhe Gan, Jingjing Liu, Jianfeng Gao, Yejin Choi, Siddhartha Srinivasa
TL;DR
Vision-and-Language Navigation must map language instructions to actions in unseen visual environments while coping with exposure bias and inefficient global search. FAST combines local and global signals to compare partial trajectories and backtrack when needed. On Room-to-Room navigation, it achieves state-of-the-art success rates and SPLs, while improving the efficiency of existing models.
Problem
VLN decoding is challenged by exposure bias and by beam search's potentially prohibitive cost from scoring many global trajectories.
Method
FAST uses asynchronous search to compare partial trajectories of different lengths with local and global information, backtracking when the agent detects a mistake.
Results
FAST achieves state-of-the-art success rates and SPLs on Room-to-Room navigation and improves the efficiency of existing models.
Takeaways & Limitations
FAST can be plugged into advanced VLN agents to improve efficiency and enable explicit recovery when an agent becomes lost.
Takeaways & Limitations
Closing the gap between current global information providers and oracle performance remains an important direction for future work.
Abstract
from arXiv · showhide
We present the Frontier Aware Search with backTracking (FAST) Navigator, a general framework for action decoding, that achieves state-of-the-art results on the Room-to-Room (R2R) Vision-and-Language navigation challenge of Anderson et. al. (2018). Given a natural language instruction and photo-realistic image views of a previously unseen environment, the agent was tasked with navigating from source to target location as quickly as possible. While all current approaches make local action decisions or score entire trajectories using beam search, ours balances local and global signals when exploring an unobserved environment. Importantly, this lets us act greedily but use global signals to backtrack when necessary. Applying FAST framework to existing state-of-the-art models achieved a 17% relative gain, an absolute 6% gain on Success rate weighted by Path Length (SPL).
1. Introduction
Vision-and-Language Navigation requires agents to follow language instructions through unseen visual environments despite exposure bias and the costs of broad beam-search exploration. FAST addresses these challenges by combining local and global trajectory information with backtracking.
- Motivation: VLN agents must build rich multimodal representations from limited data while navigating photo-realistic environments using ego-centric vision and supervised actions.Instructions refer to landmarks and spatial markers that support a mental map of the route.
- Challenges: Exposure bias arises because models trained on ground-truth histories may perform inaccurately on their own self-generated sequences.Student forcing exposes models to generated sequences, but the original instruction may no longer apply after deviation.
- Challenges: Beam search scores multiple global trajectories but can incur prohibitively high costs and produce long paths with poor SPL.The approach may require broad exploration before acting, conflicting with efficient navigation.
- FAST Navigator: FAST compares partial paths of different lengths using local and global information, then backtracks when it detects a mistake.The framework is designed to alleviate both exposure bias and expensive beam-search decoding.
- FAST Navigator: FAST is an asynchronous-search framework that converts local action knowledge and history into progress scores for choosing actions and deciding whether to backtrack.It is presented as an extensible framework that can be applied to existing models to improve SPL.
2. Method
FAST models VLN as graph search that combines local action scores with global trajectory signals, allowing adaptive expansion and backtracking. It organizes partial and completed trajectories in separate queues to balance efficient greedy decisions with broader search.
- Task formulation: VLN agents search over trajectories in photo-realistic environments using panoramic observations and actions that include movement toward views and stopping.The environment provides 36 views at each step, and the action space uses view-directed movements rather than primitive turns.
- Learning signals: FAST combines local action logits, a global progress monitor, and speaker-based global scoring to evaluate how trajectories align with instructions.The progress monitor estimates normalized instruction completion, while the speaker scores whether a trajectory corresponds to the original instruction.
- Algorithm: FAST expands partial trajectories while proposed actions remain unevaluated, then executes an action only after selecting which trajectory to extend or stop.Expanding a trajectory moves to its last node, executes its last action, and adds available next actions to the frontier while adding the current location to the candidate queue.
- Framework: FAST maintains a frontier queue for partial trajectories and a candidate queue for completed trajectories, sorted by local and global scores respectively.The framework can use trainable functions to define these scores from signals extracted from partial trajectories.
- Search decisions: The framework answers whether and where to backtrack, which visited node is the goal, and when to terminate by comparing partial and completed trajectories.Unlike greedy decoding or fixed beam search, FAST supports adaptive decisions about graph traversal and backtracking.
- Algorithm: Normalizing low-value logits can produce comparatively high probabilities when an agent is lost, motivating experiments with alternative aggregation strategies.The authors also examine means instead of sums for these signals.
3. Experiments
Experiments evaluate FAST on R2R using navigation efficiency and success metrics, comparing short and long variants with published baselines. FAST achieves strong efficiency and plug-in gains while recovering from early divergences.
- Evaluation setting: FAST is evaluated on R2R using trajectory length, navigation error, success rate, and success weighted by path length.SPL trades off success rate against trajectory length, with higher scores indicating more efficient navigation.
- Model variants: FAST(short) uses exploit-based stopping with sum-of-logits fusion, while FAST(long) uses exploration, fixed node expansion, and a neural reranker.The two versions compare different stopping and search strategies against greedy and beam-search approaches.
- Main results: FAST matches the best overall success rate while taking 150–1,000 fewer steps, and matches peak success rates in half the steps, 196 versus 373.The short-trajectory model also outperforms current approaches in both success rate and SPL.
- Plug-in gains: Replacing greedy decoders with FAST yields immediate success-rate gains of 6 and 9 points for SPEAKER-FOLLOWER and SMNA, respectively.These gains require no added global information or reranking; trajectory lengths increase slightly, while SPL also increases.
4. Analysis
The analysis examines how FAST balances exploration, stopping, trajectory scoring, and backtracking. Results show gains from backtracking and learned global scoring, while exploration introduces an SR–SPL trade-off and a remaining oracle gap.
- Fixing Your Mistakes: FAST’s backtracking raises success after early mistakes, whereas greedy decoding has under a 30% completion chance after a first-step error.FAST’s one-step backtracking increases success likelihood by over 10%.
- Knowing When To Stop Exploring: At 40 expanded nodes, the agent visits the true target more than 90% of the time but often fails to recognize it as the destination.This gap motivates testing whether global information is predictive.
- Local and Global Scoring: Summing unnormalized logits performs best among local fusion methods, achieving an SR score of 56.66.The analysis suggests normalization discards useful activation information.
- Knowing When To Stop Exploring: The stopping criterion trades exploration for efficiency: SR increases before plateauing, while SPL continually decreases as more nodes are explored.SPL is especially sensitive to added path length.
- Local and Global Scoring: Directly integrating the normalized progress monitor performs poorly because local and global signals differ substantially in scale.The authors note that future signals may combine more effectively.
- Local and Global Scoring: Combining all signals with a multilayer perceptron significantly improves performance on unseen trajectories, while current global information remains below oracle performance.The oracle gap is identified as an important direction for future work.
- Intuitive Behavior: Qualitative examples show greedy decoding entering behavioral loops, while a single FAST backtracking step can free the agent from poor choices.These examples compare FAST with the SMNA greedy decoder.
5. Related Work
Related work spans instruction following in mapped and rendered environments, multimodal VLN architectures, reinforcement-learning-based grounding, panoramic action spaces, and speaker models.
- Prior Instruction Following: Instruction-following research has used 2D maps and computer-rendered 3D environments before photo-realistic VLN.VLN also draws on referring expressions, visual question answering, and egocentric question answering.
- Vision-and-Language Navigation: VLN work introduced student forcing, planning with model-based and model-free reinforcement learning, and cross-modal matching for local and global grounding.These methods target generalization and multimodal alignment.
- Vision-and-Language Navigation: Panoramic action spaces and speaker models were major subsequent improvements in VLN.The supplied passage introduces these advances alongside earlier planning and grounding methods.
6. Conclusion
FAST Navigator uses asynchronous search to add explicit backtracking to VLN agents and reports state-of-the-art Success Rates and SPLs on Room-to-Room.
- Conclusion: FAST Navigator is a plug-in asynchronous-search framework that enables an agent to backtrack when it detects that it is lost.The framework is intended to boost existing VLN navigators.
- Conclusion: On the Room-to-Room dataset, FAST achieves state-of-the-art Success Rates and SPLs.The authors also describe the search-based method as extendible to more challenging settings.
A.1. Qualitative comparison
The qualitative comparison presents three examples contrasting FAST with the previous state-of-the-art and provides a video of agents navigating with corresponding bird’s-eye-view maps.
- Qualitative comparison: Figures A1–A3 compare FAST with the previous state-of-the-art using three qualitative navigation examples.A linked 90-second video shows first-person agent views alongside bird’s-eye-view maps.
A.2. Candidate Reranker
FAST’s candidate reranker scores partial trajectories using aggregated action and model signals, then selects the highest-scoring trajectory for the next step. It is trained with pairwise supervision distinguishing trajectories that finish within 3 meters of the destination from those that do not.
- Candidate scoring: The reranker assigns scores to candidate trajectories, and FAST selects the highest-scoring trajectory for its next step.The implementation uses a 2-layer MLP trained with pairwise cross-entropy loss.
- Candidate scoring: The reranker input is a 6-dimensional vector combining action-score logits, action log probabilities, progress-monitor scores, and speaker scores.The features use both aggregate statistics over the trajectory and scores for the completed trajectory.
- Reranker architecture: The MLP maps the 6-dimensional input through batch normalization, fully connected layers, and Tanh to produce one floating-point score for each partial trajectory.The first fully connected layer preserves six dimensions; the second projects to a scalar.
- Training: Training uses cached candidate queues after 40 FAST steps and pairwise comparisons between qualified and unqualified trajectories.Qualified trajectories end within 3 meters of the ground-truth destination; the cached set contains 4,378,729 training pairs.
- Qualitative comparison: In example trajectories, SMNA retraces its steps multiple times, attributed to its lack of global information.The comparison uses FAST as the alternative method and ground truth as the reference across three R2R examples.