REST: Receding Horizon Explorative Steiner Tree for Zero-Shot Object-Goal Navigation

arXiv:2603.18624v2 Announce Type: replace-cross Abstract: Zero-shot object-goal navigation (ZSON) requires navigating unknown environments to find a target object without task-specific training. Prior hierarchical solutions mainly focus on either scene understanding and representations (belief) or high-level decision-making and planning (policy), yet treat the option, i.e., the subgoal candidate that belief proposes and policy selects, as an interface inherited from adjacent modules rather than a design axis in its own right. In practice, options are predominantly single waypoints scored by destination utility: a lone destination hides the value gathered en route, and a flat list obscures the relationships among candidates. Our insight is that the option space should be a tree of paths. Full paths expose en-route information gain that destination-only scoring systematically neglects; a tree of shared segments enables coarse-to-fine LLM reasoning that dismisses or pursues entire branches before examining individual leaves, compressing the combinatorial path space into an efficient hierarchy. We instantiate this insight in REST (Receding Horizon Explorative Steiner Tree), a training-free framework that (1) builds an explicit open-vocabulary 3D map from online RGB-D streams; (2) grows an agent-centric tree of safe and informative paths as the option space via sampling-based planning; and (3) textualizes each branch into a spatial narrative and selects the next-best path through chain-of-thought LLM reasoning. Across the Gibson, HM3D, and HSSD benchmarks, REST consistently ranks among the top methods in success rate and path efficiency.