# The Regretful Agent: Heuristic-Aided Navigation through Progress Estimation

arXiv: https://arxiv.org/abs/1903.01602 · HTML: https://mlsanity.com/paper/1903.01602/

## Key facts

- Cited by 105 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2019.

## Built on by (most cited first, 30 of 105)

- [How Much Can CLIP Benefit Vision-and-Language Tasks?](https://mlsanity.com/paper/2107.06383/) (2021)
- [Think Global, Act Local: Dual-scale Graph Transformer for Vision-and-Language Navigation](https://mlsanity.com/paper/2202.11742/) (2022)
- [Agent AI: Surveying the Horizons of Multimodal Interaction](https://mlsanity.com/paper/2401.03568/) (2024)
- [Episodic Transformer for Vision-and-Language Navigation](https://mlsanity.com/paper/2105.06453/) (2021)
- [Bridging the Gap Between Learning in Discrete and Continuous Environments for Vision-and-Language Navigation](https://mlsanity.com/paper/2203.02764/) (2022)
- [Airbert: In-domain Pretraining for Vision-and-Language Navigation](https://mlsanity.com/paper/2108.09105/) (2021)
- [FILM: Following Instructions in Language with Modular Methods](https://mlsanity.com/paper/2110.07342/) (2021)
- [SOON: Scenario Oriented Object Navigation with Graph-based Exploration](https://mlsanity.com/paper/2103.17138/) (2021)
- [Pathdreamer: A World Model for Indoor Navigation](https://mlsanity.com/paper/2105.08756/) (2021)
- [Vision-and-Language Navigation: A Survey of Tasks, Methods, and Future Directions](https://mlsanity.com/paper/2203.12667/) (2022)
- [Cross-Modal Progressive Comprehension for Referring Segmentation](https://mlsanity.com/paper/2105.07175/) (2021)
- [Help, Anna! Visual Navigation with Natural Multimodal Assistance via Retrospective Curiosity-Encouraging Imitation Learning](https://mlsanity.com/paper/1909.01871/) (2019)
- [NavGPT-2: Unleashing Navigational Reasoning Capability for Large Vision-Language Models](https://mlsanity.com/paper/2407.12366/) (2024)
- [Structured Scene Memory for Vision-Language Navigation](https://mlsanity.com/paper/2103.03454/) (2021)
- [Cross-modal Map Learning for Vision and Language Navigation](https://mlsanity.com/paper/2203.05137/) (2022)
- [DREAMWALKER: Mental Planning for Continuous Vision-Language Navigation](https://mlsanity.com/paper/2308.07498/) (2023)
- [Bird's-Eye-View Scene Graph for Vision-Language Navigation](https://mlsanity.com/paper/2308.04758/) (2023)
- [Vision-Language Navigation with Random Environmental Mixup](https://mlsanity.com/paper/2106.07876/) (2021)
- [HOP: History-and-Order Aware Pre-training for Vision-and-Language Navigation](https://mlsanity.com/paper/2203.11591/) (2022)
- [Open-Nav: Exploring Zero-Shot Vision-and-Language Navigation in Continuous Environment with Open-Source LLMs](https://mlsanity.com/paper/2409.18794/) (2024)
- [The Road to Know-Where: An Object-and-Room Informed Sequential BERT for Indoor Vision-Language Navigation](https://mlsanity.com/paper/2104.04167/) (2021)
- [Target-Driven Structured Transformer Planner for Vision-Language Navigation](https://mlsanity.com/paper/2207.11201/) (2022)
- [Semantics for Robotic Mapping, Perception and Interaction: A Survey](https://mlsanity.com/paper/2101.00443/) (2021)
- [Hierarchical Task Learning from Language Instructions with Unified Transformers and Self-Monitoring](https://mlsanity.com/paper/2106.03427/) (2021)
- [SOAT: A Scene- and Object-Aware Transformer for Vision-and-Language Navigation](https://mlsanity.com/paper/2110.14143/) (2021)
- [Counterfactual Cycle-Consistent Learning for Instruction Following and Generation in Vision-Language Navigation](https://mlsanity.com/paper/2203.16586/) (2022)
- [Neighbor-view Enhanced Model for Vision and Language Navigation](https://mlsanity.com/paper/2107.07201/) (2021)
- [Learning from Unlabeled 3D Environments for Vision-and-Language Navigation](https://mlsanity.com/paper/2208.11781/) (2022)
- [Constraint-Aware Zero-Shot Vision-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2412.10137/) (2024)
- [SASRA: Semantically-aware Spatio-temporal Reasoning Agent for Vision-and-Language Navigation in Continuous Environments](https://mlsanity.com/paper/2108.11945/) (2021)

## Abstract (arXiv)

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 .