Racing the Clock: Teaching VLNs Budget-Conditioned Object Search

TL;DR The authors fine-tune the Uni-NaVid navigation model to find as many target objects as it can within a step budget stated in the instruction. It learns from a room-level planner that cannot see inside unexplored rooms. On held-out HM3D scenes it finds 72.7% of reachable targets at 2000 steps, versus 65.5% when trained on a planner that knows every target location and 44.8% for the pretrained model.
What they do
Vision-language navigation (VLN) models are usually run under a step limit they never see. This paper defines budget-conditioned object search: given a target category and a countdown of remaining steps in the instruction, find as many distinct instances as possible. It then asks which expert a VLN should imitate. An expert that knows where every target is plans near-optimal routes. But its turns depend on objects the student cannot see, so a student imitating it learns an average over scenes it cannot tell apart.
How it works
- Budget as text. Uni-NaVid sees RGB video history and an instruction such as “Find as many chairs as possible. You have b steps remaining,” with no architecture change. An object counts as found within 1.5 m and inside the camera’s field of view.
- Two Bellman experts apply one budget-indexed recursion to different scene abstractions. The object-level expert knows all target locations and solves budgeted routing. The room-level expert knows only entered rooms and objects visible through doorways. It values unexplored rooms from outcomes recorded in 181 other HM3D scenes.
- Distillation. Each expert fine-tunes a separate Uni-NaVid on matched scenes, budgets and record counts (388,199 records). A greedy frontier explorer supplies a third set of demonstrations.
Results
- With all target locations, the object-level expert collects 91.3% at B = 150 versus 45.7% for the room-level expert. The gap shrinks to 2.0 points at B = 2000.
- Students reverse this order. Room-level supervision gives the highest collection at every budget: 72.7% at B = 2000 versus 68.5% (frontier), 65.5% (object-level) and 44.8% (pretrained).
- Changing only the countdown from 150 to 2000 changed the route in all six probe pairs, after 2-11 actions.
- Zero-shot on a quadruped in a home with 14 chairs, mean chairs found rose from 3.4 at B = 50 to 9.2 at B = 2000 (5 runs each).
Limitations
At B = 2000 the student stays well below its expert (72.7% vs 98.0%). The non-learned frontier explorer beats every VLN from B = 800 on, and 92-93% of the student’s forward moves revisit cells it has already crossed. The room-level expert reads room types from simulator annotations. The two experts differ in both decision unit and information access, and the experiments do not separate the two.
Figures




Abstract
A rescue robot entering a building with thirty seconds on the clock should sprint toward the single most promising room; given ten minutes, it should instead explore a broader tour. Yet vision-language-navigation (VLN) models are typically evaluated under a fixed episode limit that the policy never observes, even though time-critical missions require behavior to adapt to the available budget. We study budget-conditioned object search: given a target category and an explicit action budget, an agent must find as many distinct target instances as possible before the budget expires. We investigate how to supervise VLNs for this task by comparing a privileged TSP expert, which plans near-optimal routes using the full map and true target locations, with a room-level Bellman expert that maximizes expected return under partial observability using high-level cross-scene semantic priors. Despite the TSP expert achieving substantially higher expert performance, its demonstrations are less effective for learning exploration: on held-out HM3D scenes, the Bellman-supervised VLN consistently outperforms the TSP-supervised VLN, with the advantage becoming more pronounced at longer budgets. At 2000 steps (500m), the Bellman-supervised VLN finds 71.4% of reachable target instances, compared with 65.5% for the TSP-supervised VLN and 44.8% for the pretrained VLN. These results highlight a distinction between optimal routing and optimal exploration: effective exploration supervision should optimize decisions under partial observability rather than imitate routes that are optimal only once the environment is fully known.
Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.
