PaperlayerView exact revision on arXiv

Source-linked AI summary

VoroNav: Voronoi-based Zero-shot Object Navigation with Large Language Model

Pengying Wu, Yao Mu, Bingxian Wu, Yi Hou, Ji Ma, Shanghang Zhang, Chang Liu

arXiv:2401.02695v2cs.ROcs.CV

TL;DR

Zero-Shot Object Navigation asks agents to find objects from unfamiliar categories, while existing approaches have limitations in interpretability, movement efficiency, or planning beyond depth-camera range. VoroNav combines graph-based exploration with LLM-readable path and image descriptions. It outperforms the best-performing competitor on HM3D and HSSD in Success and SPL.

  • Problem

    ZSON requires finding unfamiliar-category objects, while existing methods can have interpretability, redundant-movement, or depth-range limits on planning.

    Source: §1 · pp. 1–2

  • Method

    VoroNav combines Voronoi-based waypoint selection with path and farsight descriptions that provide scene context for LLM reasoning.

    Source: §1 · p. 2, §3.3 · p. 5

  • Results

    +2.8% Success and +3.7% SPL on HM3D, and +2.6% Success and +3.8% SPL on HSSD over the best-performing competitor.

    Source: §4.2.1 · p. 7

  • Takeaways & Limitations

    VoroNav combines graph-structured exploration and LLM decision-making for more strategic navigation and efficient exploration in ZSON.

    Source: §5 · p. 8

    The conclusion flags safe, reliable, and intuitive behavior in domestic settings as concerns for VoroNav’s application.

    Source: Impact Statements · p. 9

Abstract

from arXiv · show

In the realm of household robotics, the Zero-Shot Object Navigation (ZSON) task empowers agents to adeptly traverse unfamiliar environments and locate objects from novel categories without prior explicit training. This paper introduces VoroNav, a novel semantic exploration framework that proposes the Reduced Voronoi Graph 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 (LLM). In particular, our approach presents a synergy of path and farsight descriptions to represent the environmental context, enabling LLM to apply commonsense reasoning to ascertain waypoints for navigation. Extensive evaluation on HM3D and HSSD validates VoroNav surpasses existing benchmarks in both success rate and exploration efficiency (absolute improvement: +2.8% Success and +3.7% SPL on HM3D, +2.6% Success and +3.8% SPL on HSSD). Additionally introduced metrics that evaluate obstacle avoidance proficiency and perceptual efficiency further corroborate the enhancements achieved by our method in ZSON planning. Project page: https://voro-nav.github.io

1. Introduction

ZSON asks household robots to find objects from unfamiliar categories through scene reasoning while limiting movement cost and accurately locating targets. VoroNav proposes informative graph waypoints and map-and-image descriptions for LLM-guided decisions.

1. Introduction

  • ZSON requires agents to reach unfamiliar-category targets through scene reasoning, with minimal movement cost and accurate target localization.The task is presented as important for diverse complex household-robot tasks.Source: §1 · p. 1
  • End-to-end methods can lack interpretability, require substantial training data, and make redundant back-and-forth movements, while map-based methods may miss informative intersection waypoints.Map-based planning can overlook intersections that reveal substantial unseen areas with one additional step.Source: §1 · p. 2
  • VoroNav extracts intersection points and viable paths from real-time maps as a Reduced Voronoi Graph, organizing planning as subtasks across graph nodes.The paper argues that intersections can provide rich observations and expose expansive unseen areas.Source: §1 · p. 2
  • VoroNav describes traversable paths and farsight images in prompts so an LLM can reason over both path scenes and egocentric views.The paper adopts an LLM as a spatial-reasoning engine and designs prompts to integrate map and image observations.Source: §1 · p. 2
  • A hierarchical reward mechanism combines map topology and LLM suggestions to assess waypoint exploration value, path efficiency, and commonsense tendencies.The mechanism addresses the LLM's difficulty handling exploration while guiding the agent toward low-cost target search.Source: §1 · p. 2
  • VoroNav reports state-of-the-art ZSON results, outperforming benchmark methods on HM3D and HSSD.The contribution summary identifies both datasets as representative benchmarks.Source: §1 · pp. 2–3

2. Related Work

Prior ZSON work spans image-driven policies and map-based hierarchies, with scene representations ranging from frontiers to topological graphs. LLM-guided navigation uses prior knowledge in several ways to estimate target locations and guide exploration.

2.1. Zero-shot Object Navigation

  • Image-based ZSON maps egocentric images and target instructions to embeddings for trained action-predicting policies, while map-based methods use hierarchical structures and zero-shot detectors.Map-based approaches may use object relationships or LLMs to inform decisions.Source: §2.1 · p. 3

2.2. Scene Representation for Navigation

  • Navigation scene representations include semantic frontiers from online grid maps and topological graphs built from RGB-D images or sparsified maps.Graph nodes integrate geographic and semantic information for waypoint navigation.Source: §2.2 · p. 3

2.3. LLM Guided Navigation

  • LLM-guided methods use object- and room-level correlations, frontier-cluster contents, or chain-of-thought to guide target localization and exploration.Other examples cluster panoramic images into scene nodes for explore-versus-exploit decisions and plan mid-term goals for multiple robots from online-map information.Source: §2.3 · p. 3

3. VoroNav Approach

VoroNav builds a semantic map from RGB-D observations and pose, then uses a Reduced Voronoi Graph and LLM reasoning to select navigation goals. A local policy plans actions toward those goals.

3.1. Task Definition of ZSON

  • VoroNav defines ZSON as finding an unfamiliar target category without purposeful training, exploring until discovery, and stopping within 0.1 meters of the target.Exceeding the maximum step count without finding the target, or stopping farther than 0.1 meters away, counts as failure.Source: §3.1 · p. 3

3.2. The Semantic Mapping Module

  • The Semantic Mapping Module builds a 2D map from RGB-D images and poses, with K categorical channels plus obstacle and explored maps.The maps represent detected object regions, obstacles, and observed regions, respectively.Source: §3.2 · pp. 3–4

3.3. The Global Decision Module

  • The Global Decision Module constructs an RVG from GVD points and classifies nodes as agent, neighbor, exploratory, or ordinary nodes.The GVD represents points equidistant from the two closest obstacles; neighbor nodes connect directly to the agent node, while exploratory nodes border unexplored areas and have one connecting edge.Source: §3.3 · p. 4
  • VoroNav describes scenes along paths to exploratory nodes using objects and their locations, and generates farsight descriptions from RGB views facing neighbor nodes.The path descriptions are generated with GPT-3.5; BLIP captions the selected neighbor-facing images.Source: §3.3 · pp. 4–5
  • Goal selection combines exploration, efficiency, and LLM-derived semantic rewards, prioritizing them in that order when choosing the neighbor node with the highest cumulative reward.The LLM estimates target presence from fused path and farsight descriptions; if the target is detected, its mapped location becomes available for direct path planning.Source: §3.3 · pp. 5–6

3.4. The Local Policy Module

  • The local policy uses the Fast Marching Method to find a shortest path to the target and selects the nearest path coordinate as the immediate navigation objective.At a Voronoi node, the agent rotates and selects a new mid-term goal.Source: §3.4 · p. 6

4. Experiments

Experiments on HM3D and HSSD compare VoroNav with navigation baselines, ablations, and planning metrics. VoroNav leads the best-performing competitor on Success and SPL, while planning analyses assess obstacle avoidance and perceptual efficiency.

4. Experiments

  • The evaluation covers 20 HM3D buildings with 2K validation episodes and 40 HSSD scenes with 1.2K validation episodes.Success measures successful episodes as a share of all episodes; SPL weights path efficiency by success rate.Source: §4.1 · p. 6

4.1. Baselines and Metrics

  • Comparisons include topological planners and semantic planners, with Success rate and Success weighted by Path Length (SPL) as the evaluation metrics.The baselines include Random Exploration, Frontier, Voronoi, L3MVN, Pixel-Nav, and ESC; semantic information is used by L3MVN, Pixel-Nav, and ESC.Source: §4.1 · p. 6

4.2.1. COMPARISON WITH SOTA METHODS

  • +2.8% Success and +3.7% SPL on HM3D, and +2.6% Success and +3.8% SPL on HSSD, separate VoroNav from the best-performing competitor.Table 1 compares ZSON baselines on both datasets; starred methods use Grounded-SAM vision modules for zero-shot capability alignment.Source: Table 1 · p. 7, §4.2.1 · p. 7

4.2.2. ABLATION STUDY

  • Both Voro-path and Voro-farsight outperform Voronoi on Success and SPL, while VoroNav performs better than all three ablations.Voro-path omits farsight descriptions, Voro-farsight omits path descriptions, and Voronoi has no semantic guidance.Source: §4.2.2 · p. 7, Table 2 · p. 7

4.2.3. PLANNING STUDY

  • Voronoi-based methods significantly surpass Frontier-based methods on SCA and SEA, and VoroNav has the highest scores on both planning metrics.SCA evaluates obstacle avoidance; SEA evaluates observed area relative to path length, weighted by success.Source: §4.2.3 · pp. 7–8, Table 3 · p. 8

5. Conclusion

VoroNav uses a structured graph-based exploration strategy to enhance zero-shot object navigation. Its Reduced Voronoi Graph module and GPT-3.5 decision-making produce informative waypoints and text-based environmental representations.

5. Conclusion

  • VoroNav uses a structured graph-based exploration strategy to substantially enhance ZSON.The framework combines RVG generation with GPT-3.5 decision-making for more strategic navigation and efficient exploration.Source: §5 · p. 8
  • VoroNav generates informative waypoints and fuses text information to represent the environment, addressing limitations of traditional end-to-end and map-based methods.Source: §5 · p. 8
  • The authors describe VoroNav’s LLM and topologically structured scene graphs as setting a new benchmark for ZSON and opening pathways for intelligent robotic systems.Source: §5 · p. 8

Impact Statements

VoroNav integrates a Reduced Voronoi Graph with LLMs to provide explicit reasoning during navigation. Its experiments use controlled simulated environments, while the reliability of generative models in practical applications remains future work.

Impact Statements

  • VoroNav integrates a Reduced Voronoi Graph with LLMs to add explicit reasoning during navigation.Source: Impact Statements · p. 9
  • Experiments use controlled, simulated environments with open-source datasets to ensure predictable and safe agent behavior.Source: Impact Statements · p. 9
  • Practical reliability of generative models remains unresolved, and real-world deployment requires improving LLM accuracy in planning and sequential action prediction.Source: Impact Statements · p. 9
  • The authors identify potential implications for household robotics and AI-driven navigation systems.Source: Impact Statements · p. 9

A.1. RVG Generation

VoroNav derives a Reduced Voronoi Graph from traversable regions in the explored map, then uses graph nodes to generate exploratory paths. The accompanying figure illustrates node filtering and a worst-case exploration sequence.

A.1. RVG Generation

  • The unoccupied map is formed by subtracting obstacles from explored areas, then morphologically processed to fill holes and smooth boundaries.Source: §A.1 · p. 12
  • Skeletonizing the traversable map yields Voronoi points for a GVD, which is converted into an RVG of intersection or endpoint nodes and connecting edges.The raw graph is further processed by merging nearby nodes and removing trivial forks.Source: §A.1 · p. 12
  • Figure 6 shows agent, neighbor, ordinary, and exploratory nodes filtered by location, with shortest GVD paths connecting the agent to exploratory nodes.Source: Figure 6 · p. 12
  • Figure 7 depicts a worst-case sequence in which LLM-only decisions can be undesirable, ending with the agent finding the target object.The panels show choices among neighbor nodes, including previously traversed nodes and nodes not on exploratory paths.Source: Figure 7 · p. 12

A.2. Reward Roles

VoroNav combines exploration, efficiency, and semantic rewards to select mid-term goals on the RVG. At each navigation step, it updates its map and graph, gathers path and image descriptions, and uses LLM reasoning alongside topological rewards to choose a goal.

A.2. Reward Roles

  • Exploration rewards prioritize neighbor nodes whose exploratory paths indicate routes toward unexplored areas.Source: §A.2 · p. 12
  • Efficiency rewards use historical decisions to discourage backtracking, continuing exploration when an extension leads to unexplored areas and revisiting prior paths otherwise.Source: §A.2 · p. 12
  • When neighbor nodes have equivalent exploration and efficiency rewards, VoroNav favors the node with higher predicted semantic probability for the target.Source: §A.2 · p. 12

A.3. Navigation Process

  • The complete process of a navigation episode is illustrated in Algorithm 1; the passage also introduces a code snippet for the LookAround procedure.Source: §A.3 · p. 12
  • At each step, the agent updates the semantic map and RVG; if the target is detected, it plans a direct route, otherwise it rotates to build a scene representation and navigate to an RVG node.Source: §A.3 · p. 13
  • At a node or mid-term goal, the agent gathers path and farsight descriptions, obtains LLM semantic rewards plus exploration and efficiency rewards, and selects the highest-reward neighbor as its next goal.Low-level motion planning targets that goal; the episode ends with a stop action near the target or after the maximum step count.Source: §A.3 · p. 13

B.1. Experiment Setup

The experiments use a LoCoBot with RGB-D sensing and evaluate VoroNav on HM3D and HSSD. Failure analysis finds different dominant failure types across the datasets, while VoroNav has the fewest planning failures.

B.1. Experiment Setup

  • Evaluations use a LoCoBot with an RGB-D camera, pose sensor, discrete movements, and six actions across six object-goal categories.The base radius is 0.18 m, camera height is 0.88 m, and movement increment is 0.25 m; HM3D and HSSD use their specified evaluation settings.Source: §B.1 · p. 13
  • With ground-truth semantic segmentation, VoroNav achieves the best performance, revealing the superiority of its planning module.Table 4 reports the ground-truth semantics experiment.Source: Table 4 · p. 14

B.2. Failure Case Study

  • VoroNav experiences the fewest planning failures across the HM3D and HSSD datasets.Figure 8 presents failure percentages for both datasets.Source: Figure 8 · p. 14
  • Most failures stem from incorrect detection on HM3D and abnormal planning on HSSD.Failures are categorized as detection, planning, or exploration failures; detection failures include false target identification or missed targets, while planning failures involve being stuck or failing to reach a detected target.Source: §B.2 · p. 14

B.3. Ground-truth Vision Experiments

In ground-truth vision experiments, VoroNav outperforms Frontier and L3MVN. The supplementary material also presents prompts for path descriptions and decisions, alongside examples of generated descriptions and LLM decisions.

B.3. Ground-truth Vision Experiments

  • With ground-truth semantic images, VoroNav outperforms Frontier on Success and SPL, and outperforms L3MVN by a large margin.The experiment replaces RGB images with ground-truth semantic images to remove detection errors and assess planning and exploration effects.Source: §B.3 · p. 14

B.4. Prompt Template

B.5. Examples of LLM Conversation

  • Examples show path descriptions naming encountered rooms and objects, including a living room with a couch, table, and TV.The supplement also includes bedroom, bathroom, and kitchen examples, plus LLM decision examples.Source: §B.5 · pp. 15–16

Related papers

Loading 2401.02695v2…