Source-linked AI summary
Navigation with Large Language Models: Semantic Guesswork as a Heuristic for Planning
Dhruv Shah, Michael Equi, Blazej Osinski, Fei Xia, Brian Ichter, Sergey Levine
TL;DR
Robots exploring unfamiliar environments need semantic guidance, but ungrounded LLM plans can be arbitrarily wrong. LFG converts LLM semantic suggestions into search heuristics for metric or topological-map planning, and outperforms uninformed exploration and other LLM-based approaches in simulated and real-world evaluations.
Problem
Unfamiliar-environment navigation requires costly exploration, while LLM-generated plans are not grounded in the target environment and may be wrong.
Method
LFG uses LLM-derived semantic scores for candidate subgoals as heuristics within planning over metric or topological maps.
Results
LFG outperforms uninformed exploration and other LLM-based approaches in challenging real-world environments and simulated benchmarks.
Takeaways & Limitations
LLM semantic inferences are useful for navigation when treated as suggestions that guide a dedicated planner rather than as direct plans.
Takeaways & Limitations
The experiments cover only indoor environments, and repeated cloud-LLM calls with chain-of-thought are slow and require an internet connection.
Abstract
from arXiv · showhide
Navigation in unfamiliar environments presents a major challenge for robots: while mapping and planning techniques can be used to build up a representation of the world, quickly discovering a path to a desired goal in unfamiliar settings with such methods often requires lengthy mapping and exploration. Humans can rapidly navigate new environments, particularly indoor environments that are laid out logically, by leveraging semantics -- e.g., a kitchen often adjoins a living room, an exit sign indicates the way out, and so forth. Language models can provide robots with such knowledge, but directly using language models to instruct a robot how to reach some destination can also be impractical: while language models might produce a narrative about how to reach some goal, because they are not grounded in real-world observations, this narrative might be arbitrarily wrong. Therefore, in this paper we study how the ``semantic guesswork'' produced by language models can be utilized as a guiding heuristic for planning algorithms. Our method, Language Frontier Guide (LFG), uses the language model to bias exploration of novel real-world environments by incorporating the semantic knowledge stored in language models as a search heuristic for planning with either topological or metric maps. We evaluate LFG in challenging real-world environments and simulated benchmarks, outperforming uninformed exploration and other ways of using language models.
1 Introduction
Navigation in unfamiliar environments can benefit from semantic knowledge, but ungrounded language-model narratives should guide rather than directly control exploration. LFG uses LLM-derived guidance within heuristic planning to improve goal-directed navigation in novel environments.
- Motivation: Robotic navigation is typically framed geometrically, but semantic regularities in real environments can guide exploration toward goals.Examples include using building layout knowledge or object relationships when the specific environment is unfamiliar.
- Motivation: Because LLM-generated navigation narratives may be ungrounded, they are better used as proposals or navigational heuristics than followed blindly.The paper studies how to use these suggestions to inform an underlying navigation stack.
- Contribution: LFG produces a search heuristic from LLM reasoning to guide exploration of previously unseen real-world environments.The method combines search-based planning with language-model reasoning.
- Contribution: LFG supports both metric-map geometric navigation and topological-map learning-based navigation for open-vocabulary natural-language goals.Its memory representation and planning framework are not fixed to one navigation pipeline.
- Contribution: LFG outperforms other LLM-based approaches for semantic goal-finding in challenging real-world environments and on the Habitat ObjectNav benchmark.The paper reports this as an experimental finding across real-world and simulated settings.
2 Related Work
Prior navigation methods use geometric planning, learned policies, semantic representations, or direct language-model decisions. LFG instead uses language-model semantics as heuristic suggestions that a dedicated planner can accept or override.
- Vision-based navigation: Vision-based navigation commonly maps an environment and plans geometric paths, while learning-based methods exploit patterns from training environments.The related work contrasts these approaches with language-guided frontier ranking.
- Vision-based navigation: LFG differs from learned frontier prioritization by using a language model to rank frontier points rather than a learned potential function.The comparison is made with PONI.
- Semantic knowledge-guided navigation: Semantic navigation research uses vision-language representations or language models, often to improve instruction interpretation and decision making.The paper instead targets reaching language-specified goals in particular environments.
- Semantic knowledge-guided navigation: Because LLMs lack awareness of a particular environment's observations and layout, their plans depend strongly on the supplied context.The paper notes contradictory evidence about their ability to plan and therefore avoids relying on a complete LLM-generated plan.
- LLM-guided navigation: LFG incorporates language-model suggestions as heuristics, allowing a heuristic planner to override incorrect predictions while retaining useful semantic guidance.This distinguishes it from approaches that mainly filter infeasible decisions or process instructions.
3 Problem Formulation and Overview
LFG formulates language-guided exploration as heuristic search over unvisited subgoals in an episodic memory. LLM-derived semantic scores guide this search while remaining compatible with conventional planning and recovery from incorrect suggestions.
- Problem formulation: The planner receives a natural-language query, explores a novel environment, and commands a low-level policy to control the robot.Episodic memory can be represented as either a semantic 2D metric map or a topological map of image observations and object labels.
- Problem formulation: LFG reduces exploration to proposing unvisited waypoints, scoring them, and using a search algorithm such as A* to plan toward the goal.The core computational problem is scoring candidate subgoals.
- Problem formulation: The target score p(s_i, q, M) estimates how likely a candidate subgoal is to lead to query q given the partially explored memory M.Candidates are textual descriptions of possible semantic regions or waypoints.
- Heuristic guidance: LLMs provide semantic narratives about which regions are likely to lead to the goal, but LFG uses those outputs as goal-directed heuristics rather than direct plans.This exploits broad semantic regularities without requiring the narrative to be fully grounded.
- Heuristic guidance: Using LLM scores as heuristics lets search benefit from correct suggestions, fall back to frontier-based exploration when they are wrong, and combine semantic and grounded signals.The paper specifically mentions distance-to-subgoal scores as another compatible signal.
4 LFG: Scoring Subgoals by Polling LLMs
LFG estimates task-relevant subgoal likelihoods by polling an LLM with structured positive and negative prompts, using chain-of-thought to improve score reliability. The resulting scores guide exploration without requiring direct grounding of generated plans.
- Likelihood estimation: LFG estimates task-relevant subgoal likelihoods by sampling an LLM multiple times rather than relying directly on next-token logprobs.The method is designed to score semantically distinct candidate descriptions according to their relevance to the navigation task.
- Likelihood estimation: Given candidate subgoal images, a vision-language model produces textual descriptors that the LLM scores through repeated sampling.The samples are used to form empirical likelihood estimates for the candidates.
- Structured query: LFG uses structured query responses so each LLM sample selects a valid candidate subgoal from the available set.The prompt asks the model to end with an answer identifying a subgoal index.
- Positive and negative prompts: Negative prompts complement positive prompts by downweighting subgoals that are clearly irrelevant when the LLM is uncertain about the best candidate.The scoring procedure uses the difference between positive and negative evidence.
- Chain-of-thought prompting: Chain-of-thought prompting improves the quality, consistency, and interpretability of the likelihood estimates used by LFG.The generated reasoning is not directly used by the navigation policy, but prompting for it improves the scores.
5 LLM Heuristics for Goal-Directed Exploration
LFG extends frontier-based exploration by adding semantic scores from language models as a search heuristic. It grounds frontier observations in textual subgoals, selects the highest-scoring frontier, and replans iteratively.
- Frontier-based exploration: The robot maintains a geometric or topological map and explores the nearest frontier under the uninformed FBE baseline.FBE navigates to frontier points separating observed and unexplored regions until the goal is found or exploration ends.
- LLM-guided frontier exploration: LFG extends frontier-based exploration with an additional semantic search heuristic derived by polling language models.The framework uses VLM-derived semantic labels and LLM scores to guide exploration.
- Semantic scoring: LFG converts frontier images into textual subgoal candidates, associates each frontier with its nearest object cluster, and scores the resulting points.The scoring pipeline uses semantic labels from a VLM before applying the LLM-based heuristic.
- Planning loop: The planner chooses the highest-scoring frontier, navigates there with a local controller, and repeats the planning process.This integrates language-model scores into the existing frontier-based planning loop.
6 System Evaluation
LFG is evaluated in simulated ObjectNav and real-world exploration using geometric and topological systems. It outperforms search and LLM-based baselines on HM3D and improves performance over both LLM baselines in real environments.
- Evaluation setup: LFG is evaluated with a geometric map and deterministic control in simulation, and with a topological map and learned control in the real world.The experiments cover simulated ObjectNav and real exploration in a cafeteria and apartment building.
- Simulated evaluation: Figure 4 shows LFG discouraging exploration of the bedroom and living room, enabling fast convergence toward the goal while FBE fails.The example attributes the frontier choices to negative scores and associated chain-of-thought reasoning.
- Real-world evaluation: Figure 5 illustrates LFG using floor-plan semantics to guide the robot toward a bedroom rather than a kitchen, successfully reaching a bathroom goal.The example demonstrates semantic reasoning over likely room adjacencies in a novel apartment.
- Simulated evaluation: LFG significantly outperforms search and LLM-based baselines on the HM3D ObjectNav benchmark.It also outperforms most learning-based baselines and closely matches the state of the art without pre-training.
- Real-world evaluation: 16% better performance is achieved by LFG than the two LLM baselines in challenging real-world environments.The language-agnostic FBE baseline times out, whereas LFG successfully reaches goals such as a toilet in an apartment.
7 Discussion
The paper presents semantic language-model inferences as heuristics that complement conventional planning in unfamiliar environments. Its evaluation supports the approach, while indoor-only testing and slow, internet-dependent LLM calls limit current deployment.
- Discussion: CoT prompting with positive and negative prompts, combined with polling, is essential to achieve LFG’s best performance.The discussion points to the scoring pipeline as central to the method’s effectiveness.
- Discussion: LFG uses language-model inferences as suggestions and heuristics rather than directly executing ungrounded navigation plans.When semantic inferences are incorrect, the planner can revert to conventional unguided search.
- Limitations and future work: The experiments are limited to indoor environments, so applicability to domains such as forests remains untested.The authors state that the role of semantics may differ substantially across domains.
- Limitations and future work: Multiple cloud-hosted LLM requests with chain-of-thought are slow and require an internet connection, constraining real-world deployment.The authors identify quantized edge deployment and faster inference as possible future remedies.
A.1 Hyperparameters
The appendix reports the hyperparameters used by LFG and the parameters and resources required for one benchmark evaluation round.
- Table 3 lists the hyperparameters used in the experiments.
- Table 4 records the parameters and resources required to run one evaluation round on the benchmark.
A.3 Real World Results
The real-world LFG system combines semantic perception, frontier-based high-level planning, and a learned low-level policy. Its implementation clusters detected objects and uses LLM-derived scores to select exploratory frontiers.
- Generating Prompts: Detected objects are parsed into class-specific cluster centers and grouped with agglomerative clustering using a 6-meter threshold.Objects detected in each camera-facing frame are treated as one cluster.
- Perception: The robot uses four cameras positioned 90 degrees apart to semantically annotate observations and choose forward, left, right, or 180-degree turns.A whitelist of object classes reduces language-model API-call size and focuses reasoning on useful information.
- Low-level Policy: The NoMaD goal-conditioned diffusion policy avoids obstacles during exploration and determines which frontiers can be explored further.
- High-level Planning: LFG uses frontier-based exploration and incorporates LLM scores as goal-directed heuristics for selecting the best subgoal frontier.The real-world system uses topological mapping, while the simulation system uses a geometric map and deterministic control.
- High-level Planning: The topological implementation receives observations and a natural-language goal, repeatedly explores until completion, and checks whether the goal appears among frontier points.
- High-level Planning: Each frontier score combines positive and negative LLM evidence with distance, using the form scores[point] ← wp · LLM pos[i] - wn · LLM neg[i] - distance.
A.4 More Experiment Rollouts
Additional rollouts show LFG succeeding in unseen apartments and offices, including cases with LLM failures or imperfect detections. The prompt examples illustrate how object clusters guide both search and avoidance decisions.
- Failure tolerance: LFG’s negative scoring can compensate for an LLM failure, allowing FBE to succeed where the Greedy agent fails.
- Positive guidance: The positive-search prompt asks the LLM to identify numbered object clusters that are likely to contain the queried object.It uses common objects rather than room labels and requests reasoning plus one or more cluster numbers.
- Apartment rollout: In an unseen apartment, LFG guides exploration toward kitchen appliances instead of a bedroom door and finds the oven.
- Office rollout: In an unseen open-plan office, LFG continues exploring despite erroneous detections and finds a sink by favoring frontiers containing appliance-related objects.
- Positive guidance: For a knife query, the example selects the cluster containing a sink, microwave, and refrigerator because those objects suggest a kitchen.
- Negative guidance: The negative-search prompt asks the LLM to identify clusters where exploration should be avoided for the current query.For the knife example, it rejects clusters suggesting a living room or office and answers 1,2.
- Negative guidance: The negative knife example avoids the sofa-tv-speaker and desk-chair-computer clusters because they suggest living-room or office spaces.