Navigation agents stop re-running finished instructions: coupling progress estimation to decisions lifts R2R success by 3 points
Synopsis
Vision-language navigation agents previously matched a whole instruction against candidate trajectories, so already executed content kept interfering with later decisions. VLN-AIEP couples instruction-execution progress estimation with navigation decision-making: it uses the visited trajectory to suppress embeddings of executed content, then matches candidate locations only against pending content, so progress can be learned directly from navigation decision labels without explicit progress annotations. Across R2R, RxR, CVDN and R2R-CE, the method reaches competitive results on multiple metrics, including 77% success on R2R val-unseen, 3 points above PRET.
Interpretation
At each step the agent matches only the not-yet-executed part of the instruction, instead of comparing the entire instruction with a candidate trajectory. Earlier graph-based methods matched the full candidate trajectory against the whole instruction, letting executed content interfere with later decisions, for example making the agent turn left twice. On R2R, success rates are 81%, 77% and 74% on val-seen, val-unseen and test-unseen, exceeding PRET by 3, 3 and 2 percentage points.
Execution progress no longer needs separate annotations or a dedicated learning stage, because navigation decision loss supervises it directly. Traditional progress monitors used normalized goal distance as supervision, while later methods relied on human annotations, automatically generated alignment data, dedicated progress-learning stages, or repeated online inference with large models. On RxR, success rates are 85.9% and 74.5% on val-seen and val-unseen, 6.6 and 1.7 points above PRET; on R2R-CE val-unseen, navigation error is 4.39 with 68% OSR, 60% SR and 50% SPL, exceeding ETPNav by 3 points in SR and OSR under the same waypoint predictor.
The trajectory representation uses instruction-referred landmarks as spatial anchors, encoding their semantic labels and viewpoint-relative geometry into panorama features to associate the visited trajectory with executed instruction content. Earlier work used landmarks mainly as object cues, supervision targets or discrete progress states, not as trajectory evidence for progress estimation. On R2R val-unseen, adding landmarks improves success rate by 2.38 points and SPL by 1.91 points; landmark-anchored masked language modeling improves success rate by 4.08 points and SPL by 1.96 points.
Perspective
The method is validated on R2R, RxR, CVDN and R2R-CE, covering discrete graph environments and continuous environments, where R2R-CE uses the same waypoint predictor as ETPNav. It is aimed at researchers and engineers working on vision-language navigation, long-horizon instruction following and embodied agents.
On CVDN, val-unseen GP is 6.44, above NaviLLM's 6.16, but test-unseen is 6.90, below NaviLLM's 7.90. The termination rethinking strategy adds only 0.41 percentage points of success rate and is an auxiliary refinement. The zero-shot methods DiscussNav, Open-Nav and Fast-SmartWay report results only on selected splits and are listed for reference, not directly compared.