RollbackNav: Program-Based Rollback for Reliable Embodied Navigation

Real-world embodied navigation differs from simulation in that robots operate under physical constraints that prevent instantaneous location reset. In practice, execution errors are inevitable, making recovery costly. However, existing approaches treat failure recovery implicitly, relying on heuristic backtracking or assumed state resets, rather than modeling recovery as an explicit execution capability. We propose RollbackNav, a program-guided navigation paradigm that elevates rollback to a first-class, physically executable operation during task execution. RollbackNav represents vision-language-navigation (VLN) behaviors as executable programs with explicit intermediate states, enabling step-level error localization, a structured rollback strategy, and validation of correctness. Based on this representation, we define a navigation-consistent rollback strategy with trajectory-aligned inverse operations, and introduce a program-guided recovery mechanism that selects rollback points based on semantic consistency and verifies rollback correctness via perceptual feature consistency. Experiments on VLN benchmarks, high-fidelity simulation, and real-world robotic deployments show that RollbackNav consistently outperforms heuristic-based rollback strategies, achieving more reliable recovery and higher rollback success.