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

• URL: http://arxiv.org/abs/2603.18624v1
• Date: Thu, 19 Mar 2026 08:43:40 GMT
• Title: REST: Receding Horizon Explorative Steiner Tree for Zero-Shot Object-Goal Navigation
• Abstract summary: Zero-shot object-goal navigation (ZSON) requires navigating unknown environments to find a target object without task-specific training.<n>We instantiate this insight in textitREST (Receding Horizon Explorative Steiner Tree), a training-free framework that builds an explicit open-vocabulary 3D map from online RGB-D streams.
• Score: 31.04470860657085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Zero-shot object-goal navigation (ZSON) requires navigating unknown environments to find a target object without task-specific training. Prior hierarchical training-free solutions invest in scene understanding (\textit{belief}) and high-level decision-making (\textit{policy}), yet overlook the design of \textit{option}, i.e., a subgoal candidate proposed from evolving belief and presented to policy for selection. In practice, options are reduced to isolated waypoints scored independently: single destinations hide the value gathered along the journey; an unstructured collection obscures the relationships among candidates. Our insight is that the option space should be a \textit{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 \textbf{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 while achieving the best or second-best path efficiency, demonstrating a favorable efficiency-success balance.

Related papers

• Parse, Search, and Confirmation: Training-Free Aerial Vision-and-Dialog Navigation with Chain-of-Thought Reasoning and Structured Spatial Memory [69.51256305550844]
  We propose PSC-AVDN, a training-free framework that tightly couples a three-stage Parsing-Search-Confirmation reasoning pipeline with a Structured Spatial Memory.<n> PSC-AVDN establishes new state-of-the-art performance in the training-free setting, matching or surpassing several finetuned methods.
  arXiv  Detail & Related papers  (2026-07-13T13:14:20Z)
• FlexPath: Learned Semantic Path Priors for Image-Based Planning [2.739231894601598]
  We introduce FlexPath, a two-stage framework that decouples feasibility from preference.<n>For shortest-path planning, FlexPath reduces search effort on TMP by 14.3% compared to the state-of-the-art TransPath.<n>For obstacle clearance with minimum clearance distance 2, it achieves 96.8% full obstacle avoidance while maintaining low search cost.
  arXiv  Detail & Related papers  (2026-06-08T20:53:11Z)
• An Efficient Beam Search Algorithm for Active Perception in Mobile Robotics [10.002920418375007]
  Active perception is a fundamental problem in autonomous robotics in which the robot must decide where to move.<n>Existing approaches either solve a computationally expensive traveling problem overly selected informative nodes, or adopt a more efficient but overly constrained shortest path tree formulation.<n>We propose a node-wise beam search (NBS) algorithm, which maintains top-B candidates per node to enable more effective exploration of the solution space.<n>As a second contribution, we integrate the concept of frontiers into the path selection criterion, introducing the expected gain metric.<n>Our third contribution proposes the rapidly-exploring random annulus graph (R
  arXiv  Detail & Related papers  (2026-04-25T14:35:11Z)
• ReasonNavi: Human-Inspired Global Map Reasoning for Zero-Shot Embodied Navigation [53.95797153529148]
  Embodied agents often struggle with efficient navigation because they rely primarily on partial egocentric observations.<n>We introduce ReasonNavi, a human-inspired framework that operationalizes this reason-then-act paradigm by coupling Multimodal Large Language Models (MLLMs) with deterministic planners.
  arXiv  Detail & Related papers  (2026-01-26T19:09:20Z)
• Follow the Signs: Using Textual Cues and LLMs to Guide Efficient Robot Navigation [8.782169490089673]
  We propose a novel semantic navigation framework that infers patterns from partial observations and predicts regions where the goal is most likely located.<n>Our method combines local perceptual inputs with frontier-based exploration and periodic LLM queries.<n>We demonstrate that this approach enables more efficient navigation in sparse, partially observable grid environments by exploiting symbolic patterns.
  arXiv  Detail & Related papers  (2026-01-10T18:47:25Z)
• LLM-guided Hierarchical Retrieval [54.73080745446999]
  LATTICE is a hierarchical retrieval framework that enables an LLM to reason over and navigate large corpora with logarithmic search complexity.<n>A central challenge in such LLM-guided search is that the model's relevance judgments are noisy, context-dependent, and unaware of the hierarchy.<n>Our framework achieves state-of-the-art zero-shot performance on the reasoning-intensive BRIGHT benchmark.
  arXiv  Detail & Related papers  (2025-10-15T07:05:17Z)
• IPPON: Common Sense Guided Informative Path Planning for Object Goal Navigation [33.979481250363584]
  This paper introduces a novel informative path planning and 3D object probability mapping approach. The mapping module computes the probability of the object of interest through semantic segmentation and a Bayes filter. Although our planner follows a zero-shot approach, it achieves state-of-the-art performance as measured by the Success weighted by Path Length (SPL) and Soft SPL in the Habitat ObjectNav Challenge 2023.
  arXiv  Detail & Related papers  (2024-10-25T17:11:33Z)
• SG-Nav: Online 3D Scene Graph Prompting for LLM-based Zero-shot Object Navigation [83.4599149936183]
  Existing zero-shot object navigation methods prompt LLM with the text of spatially closed objects. We propose to represent the observed scene with 3D scene graph. We conduct extensive experiments on MP3D, HM3D and RoboTHOR environments, where SG-Nav surpasses previous state-of-the-art zero-shot methods by more than 10% SR on all benchmarks.
  arXiv  Detail & Related papers  (2024-10-10T17:57:19Z)
• LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning [91.95362946266577]
  Path planning is a fundamental scientific problem in robotics and autonomous navigation.<n>Traditional algorithms like A* and its variants are capable of ensuring path validity but suffer from significant computational and memory inefficiencies as the state space grows.<n>We propose a new LLM based route planning method that synergistically combines the precise pathfinding capabilities of A* with the global reasoning capability of LLMs.<n>This hybrid approach aims to enhance pathfinding efficiency in terms of time and space complexity while maintaining the integrity of path validity, especially in large-scale scenarios.
  arXiv  Detail & Related papers  (2024-06-20T01:24:30Z)
• Hierarchical Spatial Proximity Reasoning for Vision-and-Language Navigation [1.2473780585666772]
  Most Vision-and-Language Navigation (VLN) algorithms are prone to making inaccurate decisions due to their lack of visual common sense and limited reasoning capabilities. We propose a Hierarchical Spatial Proximity Reasoning (HSPR) method to help the agent build a knowledge base of hierarchical spatial proximity. We validate our approach with experiments on publicly available datasets including REVERIE, SOON, R2R, and R4R.
  arXiv  Detail & Related papers  (2024-03-18T07:51:22Z)
• Path Choice Matters for Clear Attribution in Path Methods [84.29092710376217]
  We introduce textbfConcentration Principle, which allocates high attributions to indispensable features. We then present textbfSAMP, a model-agnostic interpreter, which efficiently searches the near-optimal path. We also propose the infinitesimal constraint (IC) and momentum strategy (MS) to improve the rigorousness and optimality.
  arXiv  Detail & Related papers  (2024-01-19T01:11:44Z)
• VoroNav: Voronoi-based Zero-shot Object Navigation with Large Language Model [28.79971953667143]
  VoroNav is a semantic exploration framework to extract exploratory paths and planning nodes from a semantic map constructed in real time. By harnessing topological and semantic information, VoroNav designs text-based descriptions of paths and images that are readily interpretable by a large language model.
  arXiv  Detail & Related papers  (2024-01-05T08:05:07Z)
• Find a Way Forward: a Language-Guided Semantic Map Navigator [53.69229615952205]
  This paper attacks the problem of language-guided navigation in a new perspective. We use novel semantic navigation maps, which enables robots to carry out natural language instructions and move to a target position based on the map observations. The proposed approach has noticeable performance gains, especially in long-distance navigation cases.
  arXiv  Detail & Related papers  (2022-03-07T07:40:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.