PaperlayerView exact revision on arXiv

Source-linked AI summary

SayNav: Grounding Large Language Models for Dynamic Planning to Navigation in New Environments

Abhinav Rajvanshi, Karan Sikka, Xiao Lin, Bhoram Lee, Han-Pang Chiu, Alvaro Velasquez

arXiv:2309.04077v4cs.ROcs.AI

TL;DR

Finding multiple objects in unknown environments requires common-sense reasoning and dynamic planning, capabilities that are challenging for autonomous agents. SayNav grounds LLM-generated navigation plans in an incrementally updated 3D scene graph. On MultiON, it outperforms an oracle-based Point-nav baseline, achieving 64.34% success rate versus 56.06%.

  • Problem

    Autonomous agents struggle with complex navigation in unknown environments, which requires common-sense knowledge and dynamic planning.

    Source: §1 · p. 1

  • Method

    SayNav incrementally builds a 3D scene graph from exploration and uses it to ground LLM-generated high-level plans that are updated as new information is perceived.

    Source: §1 · p. 2

  • Results

    64.34% success rate for SayNav versus 56.06% for an oracle-based Point-nav baseline on MultiON.

    Source: §6 · p. 10

  • Takeaways & Limitations

    SayNav's dynamic planning supports locating multiple objects in large-scale new environments.

    Source: §6 · p. 10

    The agent cannot open or close doors and can traverse only open doors; missed open-door perception can prevent access to a target room.

    Source: §5 · p. 10

Abstract

from arXiv · show

Semantic reasoning and dynamic planning capabilities are crucial for an autonomous agent to perform complex navigation tasks in unknown environments. It requires a large amount of common-sense knowledge, that humans possess, to succeed in these tasks. We present SayNav, a new approach that leverages human knowledge from Large Language Models (LLMs) for efficient generalization to complex navigation tasks in unknown large-scale environments. SayNav uses a novel grounding mechanism, that incrementally builds a 3D scene graph of the explored environment as inputs to LLMs, for generating feasible and contextually appropriate high-level plans for navigation. The LLM-generated plan is then executed by a pre-trained low-level planner, that treats each planned step as a short-distance point-goal navigation sub-task. SayNav dynamically generates step-by-step instructions during navigation and continuously refines future steps based on newly perceived information. We evaluate SayNav on multi-object navigation (MultiON) task, that requires the agent to utilize a massive amount of human knowledge to efficiently search multiple different objects in an unknown environment. We also introduce a benchmark dataset for MultiON task employing ProcTHOR framework that provides large photo-realistic indoor environments with variety of objects. SayNav achieves state-of-the-art results and even outperforms an oracle based baseline with strong ground-truth assumptions by more than 8% in terms of success rate, highlighting its ability to generate dynamic plans for successfully locating objects in large-scale new environments. The code, benchmark dataset and demonstration videos are accessible at https://www.sri.com/ics/computer-vision/saynav.

1 Introduction

Finding multiple objects in novel settings is difficult for autonomous agents because it requires common-sense priors and dynamic search, while learning-based approaches require extensive training even for simpler navigation tasks. SayNav grounds LLM planning in an incrementally built scene graph to generate and refine navigation steps as the environment is explored.

1 Introduction

  • Finding multiple objects in novel environments is difficult for agents because it calls for common-sense object-location priors and dynamic search, while learning-based methods require extensive training even for simpler navigation tasks.Source: §1 · p. 1
  • MultiON asks agents to locate multiple named objects in a new 3D environment, and SayNav's experiments use three targets per episode while the method can search for any number.Source: §1 · pp. 1–2
  • SayNav incrementally builds a 3D scene graph from observations and uses it to ground LLM knowledge in the environment's spatial layouts and geometric relationships.Source: §1 · p. 2
  • At each step, SayNav prompts LLMs with a local scene-graph subgraph to prioritize likely object locations and generate conditional steps with fallback options.Source: §1 · p. 2
  • LLMs can augment the scene graph during navigation by annotating room type from currently perceived objects.Source: §1 · p. 2
  • Room-type feasibility helps optimize the search, such as skipping a restroom for a spoon while leaving it available for later.Source: §1 · p. 2
  • A pre-trained low-level planner executes each LLM-planned step as a short-distance point-goal navigation subtask.The paper says this decomposition reduces planning complexity because the subtasks are simple enough for low-level planners to execute successfully.Source: §1 · p. 2
  • The paper introduces a benchmark dataset for evaluating MultiON across different houses.Source: §1 · p. 3

2 Related Work

Prior approaches either incur heavy training costs or rely on grounding and plans that do not fit unknown, large-scale environments. SayNav instead grounds an LLM planner in an incrementally built scene graph and updates its search instructions during exploration.

Visual navigation and LLM planning

  • Learning-based navigation can require hundreds of millions of training iterations, raising data and computation costs for more complex tasks.These costs hinder development of agents for tasks such as multi-object navigation that require common-sense reasoning and dynamic planning.Source: §2 · p. 3

Multi-object navigation

  • SayNav evaluates multi-object navigation, which requires searching for multiple objects in unknown environments using common-sense knowledge.The paper defines its task without a required object sequence, unlike the ordered-sequence definition used by many earlier MultiON works.Source: §2 · pp. 3–4

Visual navigation and LLM planning

  • LLM planners for large-scale visual navigation can lack room-layout grounding and generate long-horizon plans that cannot be updated during exploration.Prior grounding often relies on detected objects without room layout or topological relations, while effective search plans must adapt to newly perceived scenes and visited-region memory.Source: §2 · p. 3

LLMs for navigation in unknown environments

  • SayPlan grounds high-level plans in a pre-built ground-truth scene graph, so it does not address task planning in unknown environments.The availability of the complete graph before execution simplifies its planning problem.Source: §2 · p. 3
  • L3MVN uses LLMs to suggest nearby semantic frontiers, whereas SayNav uses a scene graph for full, dynamically updated step-by-step planning.L3MVN points exploration toward likely regions; SayNav considers prior planned steps when revising future instructions.Source: §2 · p. 3

3 SayNav

SayNav combines an incrementally built scene graph with an LLM that generates short-term search plans and a low-level point-goal planner that executes each step. Its planning and memory are updated as the agent explores.

3.1 Task Definition

  • The task requires finding three predefined object categories from a random starting location within a time limit, making object ordering and search plans consequential.The agent receives RGBD images, semantic segmentation, and pose observations, and can turn, move forward, stop, or look around.Source: §3.1 · p. 4

3.2 Overview

  • SayNav accumulates observations into a scene graph, prompts an LLM for short-term high-level plans, and executes each planned step with a low-level planner.The framework has three modules: incremental scene-graph generation, a high-level LLM-based dynamic planner, and a low-level planner.Source: §3.2 · p. 4

3.3 Incremental Scene Graph Generation

  • The scene graph represents small objects, large objects, rooms, and a house, with object coordinates, room bounds, and doors linking rooms.It is built from exploration observations; large objects can serve as landmarks for reasoning about nearby small objects, and explored room nodes support memory to avoid repeated plans.Source: §3.3 · pp. 4–5

3.4 High-Level LLM-based Dynamic Planner

  • The LLM converts a local scene-graph subgraph into short-term step-by-step search instructions and updates plans when goals remain unmet or a plan fails.It can use new observations, exploratory movement, or additional scene-graph observations to revise its search; it can also defer a low-feasibility room for later.Source: §3.4 · pp. 5–6

3.5 Low-Level Planner

  • Each LLM-planned step becomes a short-distance POINTNAV subtask, with the target point set by the 3D coordinate of the named object.The low-level planner is trained from scratch using DAGGER and a shortest-path oracle, on 2,800 episodes or 7 × 10^5 simulation steps.Source: §3.5 · p. 6
  • 98.5% SR and 0.930 SPL on same-room episodes; overall, the low-level planner achieves 84.5% SR and 0.782 SPL on POINTNAV evaluation.The evaluation uses 1,550 episodes and ground-truth object locations as goals.Source: §3.5 · p. 7

4 Experimental Results

The paper introduces a ProcTHOR-based MultiON benchmark and describes the metrics used to evaluate navigation success, path efficiency, and object-order similarity.

4.1 Multi-Object Navigation Dataset

  • The MultiON benchmark comprises 132 episodes across 132 different houses, each with 3–10 rooms and three selected target objects per house; each episode records targets and their ground-truth locations.Source: §4.1 · p. 7
  • Each episode also records the shortest-path target order and path length, computed by evaluating all target orders with A*.The dataset uses start positions sampled from reachable house positions and headings sampled from 0, 90, 180, or 270 degrees.Source: §4.1 · p. 7

4.2 Metrics

  • Evaluation reports Success Rate, Success Weighted by Path Length, and Kendall Tau object-order similarity over episodes where all three targets are found.SR measures finding all three objects; SPL normalizes success by the ratio of shortest to actual path, while Kendall Tau compares object rankings.Source: §4.2 · p. 7

4.3 Implementation Details

SayNav combines an RGB-D robot setup with LLM-based high-level planning and a learned low-level planner. The experiments also compare visual scene graphs and learned navigation against ground-truth and oracle alternatives.

4.3 Implementation Details

  • The robot uses a head-mounted 320 × 240 RGB-D camera with a 90° field of view in AI2-Thor.The experiments use gpt-3.5-turbo and gpt-4; the learned low-level planner achieves 84.5% SR and 0.782 SPL in unseen ProcThor-10k-val scenes, rising to 98.5% SR and 0.930 SPL for short-range, within-room movements.Source: §4.3 · p. 7
  • A ground-truth scene graph uses simulator-provided object coordinates and geometric relationships, avoiding visual-estimation ambiguity.The visual-observation scene graph is compared with this alternative; the table also distinguishes oracle and learned low-level planners.Source: §4.3 · pp. 7–8, Table 1 · p. 8
  • OrNav uses A* with access to the environment map to plan shortest paths, while PNav is the learned low-level planner.The study substitutes ground-truth scene graphs and oracle navigation for their standard counterparts to assess the modules’ impact.Source: §4.3 · pp. 7–8, Table 1 · p. 8

4.4 Baseline

The baseline is designed as a strong learning-based comparator for MultiON in unknown environments. It receives privileged information that simplifies the task to point-goal navigation along an optimal target order.

4.4 Baseline

  • The baseline uses an IL-based PointNav policy, selected as a strong learning-based comparator because prior work reports PointNav outperforming SLAM in unknown environments.The cited example reports 80% versus 62%, respectively; the authors note limited open-source datasets and code for existing approaches.Source: §4.4 · p. 8
  • It is given the optimal target order, simplifying MultiON to a sequence of ObjectNav tasks.The optimal order is the one that achieves the shortest path.Source: §4.4 · p. 8
  • It also receives ground-truth coordinates for each target, turning the sequence into point-goal navigation tasks.The baseline navigates through ground-truth object points in the optimal order.Source: §4.4 · p. 8

4.5 Quantitative Results

SayNav outperforms the oracle-based baseline in success rate despite lacking its ground-truth object locations and optimal target order. The results also show performance trade-offs across scene-graph sources, low-level planners, path efficiency, and target-order quality.

4.5 Quantitative Results

  • 60.32% SR with gpt-3.5-turbo and 64.34% SR with gpt-4 exceed the oracle-based baseline’s 56.06% SR, despite SayNav using no ground truth.The baseline has ground-truth object locations in optimal order; the authors attribute its difficulty to long-range paths across multiple rooms.Source: §4.5 · p. 8
  • The best SayNav setting uses a ground-truth scene graph with OrNav, while visual observations and PNav each reduce success rate.Visual estimates can misplace objects from partial observations or miss small objects; depth behind glass doors can also distort door-location estimates. PNav lacks OrNav’s ground-truth information.Source: §4.5 · pp. 8–9
  • SayNav can refine or correct a plan after a planned step fails.The authors connect its success in unknown environments with LLM-based dynamic planning grounded in an incrementally built scene graph.Source: §4.5 · p. 9
  • SayNav has lower SPL than the baseline, and OrNav yields higher SPL than PNav.The baseline’s privileged object locations and order support shorter paths; SPL compares path length with the shortest possible route.Source: §4.5 · p. 9
  • Kendall-Tau scores indicate that object ordering depends more on the high-level plan than on the low-level planner, and scores drop when visual observations replace ground truth.The authors also report better ordering with gpt-4 than gpt-3.5-turbo; the baseline is excluded because it is given the optimal order.Source: §4.5 · p. 9

4.6 Qualitative Results

A sample episode illustrates SayNav searching for three objects by moving between rooms as it updates its plan. The section also points to results for a version using LLM memory.

4.6 Qualitative Results

  • The agent starts in a kitchen and infers from perceived objects that the targets are unlikely to be there, so it heads through a door.The targets are an alarm clock, a laptop, and a cellphone.Source: §4.6 · p. 9
  • In the living room, it finds the laptop and cellphone, then continues to another room to search for the alarm clock.It eventually locates the alarm clock in the final room.Source: §4.6 · p. 9
  • Table 2 reports results for SayNav on the MultiON task using LLM Memory.Source: Table 2 · p. 9

4.7 Memory via LLM

SayNav’s LLM-based memory uses a separate model instance to track plans, with GPT-4 achieving results similar to the earlier setup while GPT-3.5-turbo shows lower SR and SPL.

4.7 Memory via LLM

  • LLM Memory uses two identical-model instances: one generates high-level plans, and the other tracks them using a room-tracking prompt and conversational memory.The tracking instance receives only the minimum information needed for tracking, while the planning instance receives a detailed description of the surroundings.Source: §4.7 · p. 9, Figure 8 · p. 10
  • The separate tracker avoids the LLM token limit by not relying on the entire conversational history.The authors suggest LLM-based tracking might generalize better to other tasks, but leave that for future work.Source: §4.7 · p. 9
  • With LLM Memory, GPT-4 achieves results similar to Table 1, while GPT-3.5-turbo shows substantial drops in SR and SPL.Table 2 reports the comparison; both LLM instances use the same model in each experiment.Source: §4.7 · p. 9

4.8 Real-World Demonstration

SayNav was ported to a real robot and tested in various settings to showcase its generalization to real environments; a cafeteria demonstration video is available.

4.8 Real-World Demonstration

  • SayNav was ported to a real robot and tested under various settings to showcase generalization to real environments.Source: §4.8 · p. 10, Figure 9 · p. 10
  • The real-robot tests are described as taking place under various settings, but the passage does not specify those settings.Source: §4.8 · p. 10
  • A demonstration video for a cafeteria environment is available through the project link.Source: §4.8 · p. 10

5 Limitations and Discussion

Visual observations can leave the agent unable to identify an open door, preventing passage to a target room; the authors propose attribute verification and plan-feedback mechanisms as possible improvements.

5 Limitations and Discussion

  • In the reported failure, room geometry prevents the agent from observing that a door is open, so it cannot navigate through to the target room.The agent has no arms and can only pass through open doors.Source: §5 · p. 10, Figure 10 · p. 10
  • The agent repeatedly moves toward the room center and refines its scene graph, yet still fails to identify the door’s open status.Source: §5 · p. 10
  • The authors propose checking door attributes from multiple angles and comparing door and wall depth, alongside future plan-verification and feedback mechanisms.Source: §5 · p. 10

6 Conclusion

SayNav uses an incrementally built 3D scene graph to ground dynamic LLM plans for MultiON. It outperforms an oracle-based Point-nav baseline on success rate in large-scale new environments.

6 Conclusion

  • 64.34% vs 56.06% success rate: SayNav outperforms the oracle-based Point-nav baseline in locating objects in large-scale new environments.Source: §6 · p. 10
  • SayNav incrementally builds and converts a 3D scene graph of the explored environment into inputs for dynamic, contextually appropriate high-level navigation plans.Source: §6 · p. 10
  • The evaluation uses MultiON, which requires searching for multiple different objects in an unknown environment.Source: §6 · p. 10

Related papers

Loading 2309.04077v4…