ViTL: Temporal Logic-Guided Zero-Shot Natural Language Navigation via Vision-Language Models
Kaier Liang, Hengde Dai, Cristian-Ioan Vasile · 2026
Read ViTL: Temporal Logic-Guided Zero-Shot Natural Language Navigation via Vision-Language Models by Kaier Liang, Hengde Dai, Cristian-Ioan Vasile (2026) 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-2606-30696.txt.
Introduction
Kaier Liang, Hengde Dai and Cristian-Ioan Vasile teach a robot to follow spoken errands with deadlines and choices built in. Commands like tidy either the chair or the couch, then switch on the TV, hide temporal and logical rules: multiple targets in a set order. Existing zero-shot navigation systems, which explore unknown rooms using vision-language models, handle only one target.
Their framework, ViTL, works at two levels. A language model compiles each command into a Linear Temporal Logic formula, a notation for timing rules. That formula becomes a finite-state machine. It coordinates value maps and triggers replanning when new objects appear. At the navigation level, a directional score labels frontier directions on the camera image. The vision model then rates each direction separately. Tests in the Habitat-Matterport benchmark showed full long-horizon task completion, and the score improved single-target accuracy and efficiency.
Catalog record
| CREATOR | Kaier Liang, Hengde Dai, Cristian-Ioan Vasile |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30696
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
ViTL: Temporal Logic-Guided Zero-Shot Natural Language Navigation via Vision-Language Models Kaier Liang, Hengde Dai, Cristian-Ioan Vasile Abstract Enabling robots to follow natural language commands to complete zero-shot long-horizon tasks remains challenging. It requires extracting implicit temporal and logical constraints from natural language commands and executing multiple sub-tasks accordingly. Recent zero-shot object navigation methods use vision-language models (VLMs) to guide frontier-based exploration in unknown environments, but they are limited to single-target tasks. Real-world commands such as “Clean either the chair or the couch, then turn on the tv.” require navigating to multiple targets in a temporally constrained order, which no existing zero-shot system can handle. We present ViTL, a framework that addresses this gap at two levels. At the task level, we use a large language model (LLM) to compile natural language commands into Linear Temporal Logic (LTL) formulas, which are then converted into Deterministic Finite Automata (DFA) that coordinate multi-channel value maps and trigger dynamic replanning when new objects are detected. At the navigation level, we introduce directional score: rather than producing a direction-agnostic value across the entire field of view, we label frontier directions on the observation image and extract per-direction scores from the VLM. Experiments on Habitat-Matterport 3D (HM3D) show that the full framework enables zero-shot long-horizon completion of natural language navigation tasks with temporal constraints, and that directional score improves single-target navigation accuracy and efficiency over the baseline. I INTRODUCTION Object-goal navigation (ObjectNav), the task of navigating to an object specified by its semantic category in an unknown environment, is a fundamental capability for autonomous mobile robots [ 1 , 14 ] . Recent zero-shot approaches have made remarkable progress by leveraging pre-trained vision-language models (VLMs) to guide exploration without task-specific training [ 6 , 25 , 24 , 23 ] . However, current zero-shot ObjectNav methods are limited to single-target navigation. Real-world robot deployments demand capabilities beyond them. For instance, consider a household service robot that receives a natural language command: “Clean either the chair or the couch, then turn on the tv.” . Such tasks require navigating to multiple targets in a temporally constrained order. To the best of the authors’ knowledge, no existing zero-shot navigation system can handle this problem. Solving this problem requires addressing two interleaved challenges. At the task level , the system needs a high-level planner that continuously incorporates environment observations, identifies the efficient completion path, and dynamically selects the current sub-task. At the navigation level , each sub-task demands accurate and efficient zero-shot single-target navigation executor. We present ViTL ( Vi sion-Language T emporal L ogic Navigation), a zero-shot navigation framework that addresses both levels. At the task level , we leverage prior work on natural language to temporal logic translation [ 9 , 13 , 11 ] to compile natural language commands into Linear Temporal Logic (LTL) formulas using a large language model (LLM). For instance, the household task above can be expressed as \varphi=\Diamond((\textit{chair}\lor\textit{couch})\land\Diamond\,\textit{tv}) , where \Diamond denotes the eventually operator. The LTL formula is then converted into a Deterministic Finite Automaton (DFA) [ 3 ] , whose graph structure enables principled sub-task decomposition. The DFA selects the current navigation target through dynamic edge weights that decrease when a target object is detected, enabling the system to opportunistically reorder sub-tasks in real time to reduce the overall travel distance. To support this, the system maintains multi-channel value maps, one per target category, that accumulate spatial knowledge in parallel so that no exploration effort is lost when the planner switches targets. At the navigation level , we introduce directional score. Rather than computing a single direction-agnostic score from the full RGB observation, we visually label frontier directions on the observation image and query the VLM to score each direction independently. These per-direction scores are temporally fused using scene-weighted averaging and spatially smoothed through angle-based interpolation to produce dense value maps. Our contributions are as follows. 1. We propose ViTL, a zero-shot framework that enables robots to execute long-horizon natural language navigation tasks with complex temporal constraints. 2. We introduce a novel directional score method that leverages vision-language models to generate spatially-varying navigation value maps, improving single-target zero-shot navigation accuracy. 3. We conduct comprehensive experiments to evaluate ViTL’s capability for complex natural language navigation tasks. II RELATED WORK ObjectNav requires a robot to find an instance of a target object category in an unseen environment. Learned approaches train task-specific policies via reinforcement learning [ 1 ] or semantic map prediction [ 14 ] , but are restricted to closed-set categories and simulated data. Zero-shot methods avoid task-specific training by leveraging foundation models. CoW [ 6 ] explores the nearest frontier until an open-vocabulary detector finds the target. ESC [ 27 ] and L3MVN [ 25 ] use large language models to evaluate frontiers based on nearby object detections converted to text. VLFM [ 24 ] instead queries a vision-language model directly on the RGB observation to produce a cosine-similarity score, which is assigned uniformly across the field of view to build a value map. More recent methods enrich spatial reasoning through learned environment predictions [ 12 ] , geometric cues [ 7 ] , and scene-graph representations [ 23 ] . All of these methods are designed for single-target navigation and cannot handle complex temporal dependencies. Executing multi-step tasks from natural language requires both high-level planning and low-level navigation. InstructNav [ 10 ] re-queries an LLM at every decision step for complex navigation tasks. However, it does not model temporal constraints between sub-tasks and provides no formal guarantees on task completion. NavGPT-2 [ 26 ] aligns vision-language model features with a graph-based navigation policy for navigation tasks, but requires task-specific fine-tuning and does not operate in a zero-shot setting. SayPlan [ 16 ] grounds LLM plans in robot affordances or scene graphs for long-horizon manipulation, but assumes known environments and does not address the navigation problem in unexplored spaces. Our approach instead uses a single offline LLM call to compile the task into an LTL formula, which is then executed by a DFA that provides provable temporal constraint satisfaction and supports dynamic replanning upon new object detections. Translating natural language commands into formal temporal logic specifications is an active research area [ 2 , 5 , 22 ] . Lang2LTL [ 9 ] fine-tunes language models to convert grounded natural language into LTL formulas for robot task planning. LTLCodeGen [ 13 ] leverages code-generation LLMs to produce syntactically correct LTL from natural language. Once an LTL formula is obtained, recent works use temporal logic to guide robot execution. SELP [ 21 ] constructs a Büchi automaton to constrain LLM plan generation through token masking in known environments where all landmark locations are given; the automaton acts as an offline verifier and the robot executes the resulting plan without replanning. NL2HLTL2PLAN [ 5 ] extends NL-to-LTL translation to hierarchical specifications for multi-robot allocation, but similarly assumes known workspaces. In [ 18 ] , the authors address LTL planning under semantic uncertainty using a product automaton with value iteration over discrete grids, updating beliefs as labels are revealed. While related in handling unknown environments, their method operates on small discrete state spaces with probabilistic label priors rather than continuous visual observations. In