Handle Object Navigation as Weighted Traveling Repairman Problem

Ruimeng Liu, Xinhang Xu, Shenghai Yuan, And Lihua Xie · 2025

Read Handle Object Navigation as Weighted Traveling Repairman Problem by Ruimeng Liu, Xinhang Xu, Shenghai Yuan, And Lihua Xie (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-06937.txt.

Introduction

Ruimeng Liu and co-authors send robots hunting for objects named in plain words, in a 2025 paper. The task, zero-shot object navigation, gives no fixed categories and no map in advance. Many systems lean on flat maps and greedy next-step choices, which fail in cluttered spaces. The team recasts the hunt as a weighted traveling repairman problem, cutting the total wait across candidate viewpoints.

A vision-language model scores viewpoints by how well each matches the object's description, laid over a depth-aware map. An open-vocabulary detector confirms sightings and updates goals. A 3D feature map gives the robot memory of the space. Tests show the planner beats existing methods on complex hunts.

Catalog record

CREATORRuimeng Liu, Xinhang Xu, Shenghai Yuan, And Lihua Xie
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-06937

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Handle Object Navigation as Weighted Traveling Repairman Problem Ruimeng Liu, Xinhang Xu, Shenghai Yuan, And Lihua Xie Abstract Zero-Shot Object Navigation (ZSON) requires agents to navigate to objects specified via open-ended natural language without predefined categories or prior environmental knowledge. While recent methods leverage foundation models or multi-modal maps, they often rely on 2D representations and greedy strategies or require additional training or modules with high computation load, limiting performance in complex environments and real applications. We propose WTRP-Searcher, a novel framework that formulates ZSON as a Weighted Traveling Repairman Problem (WTRP), minimizing the weighted waiting time of viewpoints. Using a Vision-Language Model (VLM), we score viewpoints based on object-description similarity, projected onto a 2D map with depth information. An open-vocabulary detector identifies targets, dynamically updating goals, while a 3D embedding feature map enhances spatial awareness and environmental recall. WTRP-Searcher outperforms existing methods, offering efficient global planning and improved performance in complex ZSON tasks. Code and more demos will be avaliable on https://github.com/lrm20011/WTRP_Searcher . I Introduction Zero-Shot Object Navigation (ZSON) is a challenging task in robotics and AI, where an agent is required to navigate to specified targets using open-ended natural language. Unlike conventional object navigation methods [ 1 , 2 , 3 , 4 ] , ZSON operates without a predefined set of object categories or prior knowledge of the environment, making it more adaptable to real-world applications, as illustrated in Fig. 1 . Object navigation has received considerable research attention in recent years. Earlier works [ 5 , 6 ] implicitly utilize the comprehension of the semantic environment through reinforcement or imitation learning but are limited to closed-set settings and certain environments. Recent training-free methods [ 7 , 8 , 9 ] leverage large language models (LLM) for planning by converting observations into language queries. However, this approach is inefficient and neglects complex 3D correspondence, leading to sub-optimal decisions. Many experiments in biology [ 10 ] and robotics [ 11 , 12 ] have shown that spatial representation and memory are significant mechanisms in human navigation, and explicit maps improve performance and efficiency over end-to-end methods in various navigation tasks. More and more researchers are using prior map-based methods [ 13 ] . They build semantic maps [ 14 , 15 , 16 , 17 ] for further inferring or decision making by close-set detector or open-vocabulary Vision-Language Model (VLM). Some works also combined this with a traditional frontier method, which marks the boundary of observed and unobserved areas for more efficient navigation [ 18 , 19 ] . Despite these advancements, several challenges [ 20 ] remain in map-based and frontier-based approaches. Many methods [ 14 , 16 ] employ top-down 2D feature maps, which struggle with overlapping objects and occluded environments (e.g., objects inside cabinets). Existing approaches [ 19 , 8 ] often rely on greedy goal selection strategies, which choose the most promising viewpoint at each step but fail to account for long-term planning. This shortsighted decision-making can lead to inefficient search behaviors in complex environments. Fig. 1 : Motivation of our work Zero-Shot Object Navigation in dealing with object-based navigation scenario without prior knowledge of the environment. To overcome these challenges, we propose WTRP-Searcher, a novel training-free navigation framework that formulates ZSON as a Weighted Traveling Repairman Problem (WTRP) to optimize search efficiency through global viewpoint selection. Our approach leverages a VLM to compute similarity scores between the environment and object descriptions, projecting them onto a 2D depth-enhanced map for improved spatial reasoning. Frontier-based viewpoint extraction assigns these similarity scores as weights in the WTRP optimization process, enabling more informed goal selection. Additionally, an open-vocabulary object detector dynamically refines candidate viewpoints and navigation targets based on detection confidence, while a 3D embedding feature map continuously updates environment memory, enhancing object localization as the agent explores. In general, the contributions of this work are as follows: • We propose WTRP-Searcher, a training-free framework for Zero-Shot Object Navigation (ZSON) that integrates open-vocabulary detection, 3D feature mapping, and a Weighted Traveling Repairman Problem (WTRP) formulation for efficient global planning for object search. • We introduce a global goal selection policy leveraging items and global associations, addressing the limitations of greedy strategies in prior work. • We develop a real-time mapping system that builds multi-modal maps, enabling efficient object localization and environment memorization. • We evaluate our method in simulated and real-world environments, showing superior performance over state-of-the-art approaches. We will open source our work for the benefit of society. Fig. 2 : Implementation of our approach in a real robot. The left image visualizes items that support the search framework. The right top image represents the detection result of a camera in the robot. The right bottom image is a third view. II RELATED WORKS II-A Frontier-based Navigation Frontier-based navigation is a widely used approach in exploration tasks, where frontiers mark the boundaries between explored and unexplored areas [ 21 ] . Classical methods often employ greedy strategies, selecting the nearest frontier at each step to maximize immediate exploration gains. More advanced strategies, such as next-best-view selection [ 22 ] , evaluate candidate viewpoints based on information gain and path cost, selecting the one with the highest utility. To improve planning efficiency, recent works [ 23 , 24 ] have reformulated frontier selection as a Traveling Salesman Problem (TSP), aiming to minimize the total travel cost across all viewpoints, which has demonstrated superior performance compared to traditional heuristic approaches [ 25 , 26 , 27 , 28 , 29 ] . Beyond general exploration, frontier-based strategies have been widely adopted in object search problems. Extensions of classical frameworks [ 30 , 31 ] integrate unknown space exploration with object-centric surface inspection, enabling more target-aware navigation. Several works focus on leveraging frontier selection for object search optimization. For example, [ 18 ] introduces a learning-based policy that generates navigation goals based on semantic maps and frontiers, while [ 32 ] employs a simpler heuristic, iteratively selecting the closest frontier until an open-vocabulary detector confirms object detection. More recent approaches, such as VLF-M [ 19 ] , combine visual-language similarity scoring with frontier selection, prioritizing viewpoints with the highest confidence to improve search efficiency. This growing body of research highlights the effectiveness of frontier-based strategies in object search, yet many existing methods still suffer from greedy selection biases, lack of global planning, and reliance on 2D representations, which limits performance in complex, occluded, or long-horizon navigation tasks. Addressing these challenges remains a key direction for improving efficient and scalable object navigation. II-B Zero-Shot Object Navigation ZSON requires an agent to navigate toward a specified target without prior training or exposure to the object or environment [ 33 ] . Traditional approaches can be broadly categorized into end-to-end learning methods and modular methods. End-to-end methods [ 34 , 35 ] employ deep reinforcement learning (RL) or supervised learning to directly predict navigation actions from raw sensory inputs. Meanwhile, modular methods [ 6 , 13 ] construct multi-modal maps that facilitate high-level decision-making and low-level motion planning, improving interpretability and structured reasoning. However, both paradigms struggle with generalization, especially when encountering novel objects and unseen environments. To address these limitations, recent works have explored foundation models [ 36 , 37 ,

Read the complete text