PaperlayerView exact revision on arXiv

Source-linked AI summary

The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation

Chih-Yao Ma, Zuxuan Wu, Ghassan AlRegib, Caiming Xiong, Zsolt Kira

arXiv:1903.01602v1cs.AIcs.CVcs.RO

TL;DR

VLN asks agents to reach implicit goals from language and vision, while effective beam-search methods are unrealistic for robotics. The paper uses a progress monitor as a learned graph-search heuristic, adding learned rollback and visit-aware action selection. The resulting agent achieves state-of-the-art results without beam search, including reported gains in success and path-length-normalized success.

  • Problem

    VLN requires reaching an unspecified goal from language instructions and visual input, but strong success rates often rely on beam search that explores many trajectories and is unrealistic for robotics.

  • Method

    The agent uses a progress monitor as a learned heuristic and adds a Regret Module for backtracking plus a Progress Marker for using visited directions and their progress estimates.

  • Results

    The framework achieves state-of-the-art success-rate and SPL results among published works without beam search, with short trajectories supporting its SPL performance.

  • Takeaways & Limitations

    Learned rollback and progress-based reasoning enable greedy navigation that avoids beam search while maintaining state-of-the-art results on VLN.

Abstract

from arXiv · show

As deep learning continues to make progress for challenging perception tasks, there is increased interest in combining vision, language, and decision-making. Specifically, the Vision and Language Navigation (VLN) task involves navigating to a goal purely from language instructions and visual information without explicit knowledge of the goal. Recent successful approaches have made in-roads in achieving good success rates for this task but rely on beam search, which thoroughly explores a large number of trajectories and is unrealistic for applications such as robotics. In this paper, inspired by the intuition of viewing the problem as search on a navigation graph, we propose to use a progress monitor developed in prior work as a learnable heuristic for search. We then propose two modules incorporated into an end-to-end architecture: 1) A learned mechanism to perform backtracking, which decides whether to continue moving forward or roll back to a previous state (Regret Module) and 2) A mechanism to help the agent decide which direction to go next by showing directions that are visited and their associated progress estimate (Progress Marker). Combined, the proposed approach significantly outperforms current state-of-the-art methods using greedy action selection, with 5% absolute improvement on the test server in success rates, and more importantly 8% on success rates normalized by the path length. Our code is available at https://github.com/chihyaoma/regretful-agent .

1. Introduction

VLN requires agents to follow language instructions using visual input without explicit goal knowledge, but beam search is costly for robotics. The paper frames navigation as graph search and adds learned backtracking and visit-aware progress mechanisms to improve greedy action selection.

  • VLN requires navigating to an unspecified goal using language instructions and visual input, with potential applications in service robotics.
  • Beam-search methods achieve good success rates but produce longer trajectories, whereas greedy methods use shorter trajectories but have much lower success rates.
  • For robotics, beam search is unrealistic because it requires exploring many possible trajectories.
  • The proposed agent treats navigation as graph search and uses a learned progress monitor as a heuristic instead of exhaustive search.
  • The Regret Module learns when to backtrack, while the Progress Marker uses previous visits and progress estimates to select later actions.
  • The agent achieves state-of-the-art success rate and SPL results among published works without beam search, with short trajectory lengths supporting SPL.

2. Related Work

Related work spans vision-and-language navigation, learning-based planning heuristics, and reinforcement learning. This paper distinguishes its approach by using learned progress estimates directly during inference and by learning rollback behavior.

  • Vision and language navigation: VLN is situated among benchmarks combining vision, language, and decision-making, including House3D, Embodied QA, and AI2-THOR.
  • Navigation and learned heuristics: Robotic planning commonly uses heuristics to select which state to expand, but static distance heuristics require known goal locations and support optimal A*-style search.
  • Navigation and learned heuristics: Learning-based alternatives include heuristic residuals, heuristic ranking, and policies that optimize search effort using history and context.
  • Modern Reinforcement Learning: The baseline progress monitor resembles an RL value function, while progress-marker differences are conceptually similar to an advantage function.
  • Modern Reinforcement Learning: Unlike RL advantage functions used to regularize policy training, the progress-marker difference directly affects action selection during inference.
  • Modern Reinforcement Learning: The learned regret module relates to reset-policy work, but this paper learns rollback behavior within its navigation agent.

3. Baseline

The Self-Monitoring baseline grounds language instructions and panoramic visual inputs, then uses historical context to score navigable directions. Its progress monitor estimates instruction-following progress and primarily regularizes textual grounding.

  • The baseline combines visual-textual co-grounding with a progress monitor for instruction-following navigation.
  • Language instructions are encoded word-by-word with an LSTM language encoder.
  • At each timestep, the agent receives panoramic images representing navigable viewpoints.
  • Each navigable direction is represented by an ImageNet-pretrained ResNet-152 feature, with K denoting the maximum number of directions.
  • Soft attention produces grounded visual and textual features, which are combined with historical context to form the current hidden state.
  • The baseline scores each viewpoint by correlating its visual feature with the hidden state concatenated with grounded instructions.
  • The progress monitor uses textual-grounding attention to estimate distance from the goal and regularize attention toward relevant instructions.

4. Regretful Navigation Agent

The agent treats navigation as graph search, using progress estimates to learn when to backtrack and which directions to select without beam search. A memory-based Progress Marker records visited locations and their estimated progress, while training combines action, progress, and entropy losses.

  • Regret Module: The Regret Module compares progress-monitor outputs across time to learn whether the agent should move forward or roll back.Its attention-weighted forward and rollback embeddings bias action selection toward the previous location when rollback is favored.
  • Progress Marker: After rollback, the agent uses visited-direction information and associated progress estimates to choose a new forward direction while blocking oscillatory actions.The Progress Marker distinguishes previously visited directions from unexplored alternatives.
  • Progress Marker: The Progress Marker stores each visited location’s progress-monitor output and assigns unvisited directions a marker value of 1 to encourage exploration.Markers can be updated whenever the agent revisits a location.
  • Progress Marker: The agent concatenates the difference between current progress and each direction’s marker with that direction’s visual feature before action selection.Lower marker differences correspond to higher action-selection chances in the described design.
  • Training and Inference: Training uses cross-entropy for action selection, MSE for progress monitoring, and entropy regularization, while inference greedily selects the highest-probability action.The loss weights are λ = 0.5 for cross-entropy and MSE and β = 0.01 for entropy loss.
  • Training and Inference: The approach is evaluated against greedy-decoding state-of-the-art methods in Table 1.The table caption specifies comparisons using greedy action selection, with a data-augmentation marker.

5. Dataset and Implementations

The evaluation uses the Room-to-Room benchmark and reports navigation error, success, oracle success, and path-length-weighted success. Implementation follows prior work’s visual features and includes a greedy inference setting for comparison.

  • Dataset: The Room-to-Room dataset contains 10,800 panoramic views from 90 buildings, 7,189 navigation paths, and three human instructions per path.Its scenes are split into 61 training and validation-seen, 11 validation-unseen, and 18 test-unseen scenes.
  • Evaluation metrics: Evaluation reports Navigation Error, Success Rate, Oracle Success Rate, and Success rate weighted by normalized inverse Path Length.SPL incorporates trajectory length and is highlighted as important for robotics applications.
  • Implementation Details: Image features use pretrained ImageNet ResNet-152 appearance features concatenated with four-dimensional orientation features.The orientation vector is [sinφ; cosφ; sinθ; cosθ], using heading and elevation angles.
  • Implementation Details: The compared Speaker-Follower and Self-Monitoring systems were originally designed to optimize success rate through beam search.The cited note distinguishes those original settings from the greedy-decoding comparison.

6. Evaluation

The evaluation shows that rollback is a key source of the regretful agent’s gains, improving performance over greedy and prior methods, especially on unseen environments. Ablations and qualitative examples indicate that learned backtracking, supported by progress estimates, helps recover from mistaken or uncertain actions.

  • 6.1. Comparison with Prior Art: 37% SPL and 48% SR were achieved on the validation unseen set, exceeding existing work; the best model reached 41% SPL and 50% SR with synthetic Speaker data.On the test server, the method improved SPL by 8% and SR by 5% over the current state of the art.
  • 6.2. Ablation Study: The Regret Module produced 47% SR, compared with 44% for Progress Marker features alone and 45% when progress estimates were attached to the forward embedding.Adding the Progress Marker increased SR further to 48%, while the ablation attributes the key improvement to learned backtracking.
  • 6.3. Rollback Analysis: Blocking rollback significantly reduced NE, SR, and OSR for the proposed agent, especially in unseen environments.The same intervention left SR unchanged for Self-Monitoring, although its NE worsened and OSR improved.
  • 6.3. Rollback Analysis: The proposed agent reduced unsuccessful examples involving rollback from around 43% to 38%, correlating with a 4–5% SR improvement.The analysis measures unsuccessful examples that involve rollback for Self-Monitoring and the proposed agent.
  • 6.3. Rollback Analysis: When trained only on synthetic data and tested on unseen real data, the method significantly outperformed Self-Monitoring across all metrics.Against Self-Monitoring trained with real data, it was slightly better on ONE, the same on OSR, and marginally lower on SR.
  • 6.4. Qualitative Results: Qualitative trajectories show rollback following small or decreasing progress estimates, after which progress increased and the agent reached the instructed goal.Examples include recovering from an initial mistake, repeating the wrong stair movement, and missing the stairs.

7. Conclusion

The paper presents an end-to-end regretful navigation agent that uses a progress monitor as a learned heuristic, with modules for backtracking and reasoning about previous visits. The framework achieves state-of-the-art success rates without beam search, while analyses attribute improvement to learned rollback.

  • The agent uses a progress monitor as a learned heuristic to greedily select the next best action during inference.The monitor integrates grounded language and visual information across time with LSTMs.
  • The Regret Module learns when to backtrack based on progress and the agent’s state.It provides an end-to-end trainable mechanism for deciding when to roll back to a previous location.
  • The Progress Marker uses previous visits and unvisited directions to reduce action probabilities for visited locations with lower progress estimates.
  • The framework achieves state-of-the-art success rates on the public leaderboard without using beam search.The paper’s analyses identify the learned rollback mechanism as the source of performance improvement.

A. Network Architecture

The architecture combines instruction encoding, visual-feature projection, temporal integration, progress monitoring, and mechanisms for rollback and visit-aware action selection. A successful example shows rollback after insufficient progress, followed by correct instruction following.

  • Network Architecture: The instruction encoder uses a regular LSTM with a 256-dimensional embedding, 512-dimensional hidden state, and dropout ratio 0.5.
  • Network Architecture: Raw 2176-dimensional image features are projected to 1024 dimensions through BN → FC → BN → Dropout → ReLU, with dropout ratio 0.5.
  • Network Architecture: The temporal LSTM integrates information across time using a 512-dimensional hidden state.
  • Network Architecture: In a successful unseen-environment example, the agent rolls back after its progress-monitor output fails to increase significantly, then follows the instruction correctly.

B. Comparison with Beam Search Methods

The comparison contrasts greedy action selection with beam-search methods, emphasizing the trade-off between success rate and trajectory length. Beam search performs well on SR but has longer trajectories and lower SPL, making it impractical for real-world applications.

  • Comparison with Beam Search Methods: Beam-search methods perform well on success rate (SR) but produce significantly longer trajectories.
  • Comparison with Beam Search Methods: Their longer trajectories result in low success rate weighted by Path Length (SPL) scores.
  • Comparison with Beam Search Methods: The comparison frames trajectory length as the practical distinction between beam search and greedy action selection.The passage states that beam-search methods are impractical for real-world applications because of their trajectory lengths.

C.1. Successful examples

Successful examples show the agent using progress estimates to search locally, backtrack from ambiguous or incorrect directions, and stop after reaching high estimated progress. These behaviors occur across several unseen environments and navigation scenarios.

  • Successful examples: The examples demonstrate successful decisions to roll back and reach goals in unseen environments.
  • Successful examples: In Figure 6, the agent searches two directions locally before choosing one and continues after its progress estimate increases to 45%.
  • Successful examples: In Figure 7, the agent rolls back after an ambiguous living-room choice, then follows the instruction successfully and stops at a 99% progress estimate.
  • Successful examples: In Figure 8, the agent backs down from an ambiguous second staircase and reaches the goal after progress estimates rise from 51% to 66%, then 82% and 95%.
  • Successful examples: In Figure 9, the agent discovers the correct downstairs path, with progress increasing to 39% immediately and reaching 98% at the bottom before stopping at 99%.

C.2. Failed examples

The failed examples show that rollback can recover the correct route, but failures still arise when the agent does not stop at the goal or chooses rollback incorrectly.

  • Stopping failures: Rollback recovered the correct path in two failed runs, but both agents continued moving instead of stopping at the goal.These failures occurred despite successful backtracking toward the goal.
  • Stopping failures: In one run, the agent reached the instructed room, moved forward, and rolled back, but still failed to stop at the goal.The rollback returned the agent to the room without producing a successful termination.
  • Stopping failures: In another run, a 21% progress-estimate drop triggered correct rollback, but continued movement after reaching the refrigerator caused failure.The agent reached the refrigerator at step 8 and then took additional forward steps.
  • Rollback errors: A separate failure involved incorrect rollback decisions: the agent eventually escaped a hallway dead end but still ended unsuccessfully.The agent rolled back at steps 4 and 7 while searching for the intended turn.
  • Successful behavior: Successful examples show the agent can use progress changes to backtrack, select better directions, and stop near the goal.Examples include stopping with progress estimates of 99% after correcting navigation errors.
Loading 1903.01602v1…