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

We choose Multi-Object Navigation task, to validate SayNav. The goal of this task is to navigate the agent in a large-scale unknown environment in order to find an instance for each of three predefined object categories (such as ”laptop”, ”tomato”, and ”bread”). The agent is initialized at a random location in the environment and receives the goal object categories ($o_{i}$, $o_{j}$, $o_{k}$) as input. At each time step $t$ during navigation, the agent receives environment observations $e_{t}$ and takes control actions $a_{t}$. The observations include RGBD images, semantic segmentation maps, and the agent’s pose (location and orientation). The action space includes five control commands: $turn$-$left$, $turn$-$right$, $move$-$forward$, $stop$, and $look$-$around$. Both $turn$-$left$ and $turn$-$right$ actions rotate the agent by 90 degrees. The $move$-$forward$ action moves the agent by 25 centimeters. The task execution is successful if the agent locates (by detection) all three objects within a time period.

Note that MultiON task poses much larger planning challenges and task complexities than previous navigation tasks, which either look for a single object (Chaplot et al. 2020) or reach a single target point (Wijmans et al. 2019). For example, the agent needs to dynamically set up the search plan based on the prioritized order among three different objects. This plan can also be changed during exploration in a new house with unknown layouts. As shown in Figure 1, the agent first realizes that it is in the bedroom and then decides to prioritize places (such as the table) to locate the laptop inside this room. On the other hand, if the agent had started in the kitchen, it would have been more efficient to search for the fork and spoon first. Therefore, this new task requires extensive semantic reasoning and dynamic planning capabilities, as what humans possess, for an autonomous agent to explore in large-scale unknown environments.

SayNav’s framework is illustrated in Figure 2. The corresponding pseudo-code is in Algorithm 1. It includes three modules: (1) Incremental Scene Graph Generation, (2) High-Level LLM-based Dynamic Planner, and (3) Low-Level Planner. The Incremental Scene Graph Generation module accumulates observations received by the agent to build and expand a scene graph, which encodes semantic entities (such as objects and furniture) from the areas the agent has explored. The High-Level LLM-based Dynamic Planner continuously converts relevant information from the scene graph into text prompts to a pre-trained LLM, for dynamically generating short-term high-level plans. Each LLM-planned step is executed by the Low-Level Planner to generate a series of control commands for execution.

This module continuously builds and expands a 3D scene graph of the environment being explored. A 3D scene graph is a layered graph which represents spatial concepts (nodes) at multiple levels of abstraction with their relations (edges). This representation has recently emerged as a powerful high-level abstraction for 3D large-scale environments in robotics. Here we define four levels in the 3D scene graph: small objects, large objects, rooms, and house. Each object node is associated with its 3D coordinate and room node is associated with its bounds. Every door is treated as an edge between two rooms, which also has an associated 3D coordinate. All other edges reveal the topological relationships among semantic concepts across different levels. Figure 3 shows one example of our scene graph. Mathematically, our scene graph can be represented as a set of 4 kinds of triplets:

where, $s_{h}$: small object, $l_{i}$: large object, $r_{j},r_{k}$: rooms ($i\neq j$), $d_{jk}$: door between $r_{j}$ & $r_{k}$, $H$: house (root node).

Large objects act as landmarks which are visible from far away distance. LLM uses these large objects to reason if a small object can be found near them. For example, it may be logical to walk towards a dining table to find a knife. The decision of small vs. large objects is made based on its dimensions and LLM’s understanding about the object class.

The scene graph is built using environmental observations received by the agent during exploration. The depth of each segmented object can be obtained based on RGBD images and semantic segmentation images. The 3D coordinate of each perceived object can then be estimated by combining its depth information at multiple timestamps and the corresponding agent’s poses.

We also utilize LLMs to augment and refine high-level abstractions of the scene graph. For example, we use LLMs to annotate and identify the spatial entity (room type) at the room level of the graph based on its connected objects at lower levels. For instance, a room is probably a bedroom if it includes a bed. The bounds of a room are calculated based on the detection of walls and floor of the room.

SayNav also uses the 3D scene graph to support memory for future planning. For example, it automatically annotates the room nodes that have been investigated. Therefore, it will not generate repeated plans when the agent revisits the same room during exploration.

Similar to previous works in LLM-based planning, SayNav utilizes a two-level planning architecture to reduce the learning complexity of the assigned task. However, instead of generating a complete high-level plan for the entire task in the beginning, SayNav utilizes LLMs to incrementally generate a short-term plan regularly, based on current observations and the memory of previously-visited regions. This high-level planner can be set-up using only a few training examples via typical in-context learning procedures (Brown et al. 2020; Ouyang et al. 2022) (as shown in Figure 4).

Our high-level LLM-based dynamic planner extracts a subgraph from the full 3D scene graph and converts it into text prompts, which are fed to an LLM. The extracted subgraph includes spatial concepts in the local region centered around the current position of the agent. We implemented the LLM prompts similar to (Singh et al. 2023), which constructs programming language prompts based on the text labels in the extracted subgraph. Once prompts are received, the LLM planner outputs short-term step-by-step instructions, as pseudo code. The generated plan provides an efficient search strategy within the current perceived area based on human knowledge, prioritizing locations to visit inside the room based on the likelihoods of target objects being discovered. For example, LLM may provide a plan to first check the desk and then the bed to find the laptop in the bedroom. Figure 4 shows the prompt structure used to generate the plan. We provide two in-context examples inside the prompt to constrain the LLM-generated plans. For instance, we constrain each step to generate a navigate or look function call with arguments and a high-level comment. Note that we also make LLM output a descriptive comment associated with each step in the generated plan, for minimizing the prevailing issue of hallucinations in LLMs.

The LLM-based planner also extends and updates the plan when the previous plan fails or the task goal (finding three objects) is not achieved after the execution of previous short-term plan. It attempts to update the plan either by (i) generating a plan based on new information received from the environment, (ii) putting the low-level planner into an exploratory mode (ex: try to go to next room), or (iii) refining the scene graph by instructing the low-level planner to randomly move around and collect more observations.

Before generating the high-level plan for a local region (room), LLM also reasons about the feasibility of locating the target object(s) in the detected room-type. It may decide to skip searching a specific room and come back later if the feasibility is low. In this case, it would mark the corresponding room-node in the scene graph to come back later. Figure 5 shows the structure of prompts used to identify the room type and determine the feasibility of locating target object in a room.

The Low-Level Planner converts each LLM-planned step into a series of control commands for execution. To integrate two planners, SayNav formulates each LLM-planned step as a short-distance point-goal navigation (PointNav) sub-task for the low-level planner. The target point for each sub-task, such as moving from the current position to the table in the current room, is assigned by the 3D coordinate of the object (e.g. table) described in each planned step.

SayNav’s low-level planner takes the RGBD images (resolution $320\times 240$) and the agent’s pose (location and orientation) as inputs, and it outputs move_forward, turn_left and turn_right actions to control the robot following standard PointNav settings. Note that large-scale DRL approaches typically take $10^{8}$ to $10^{9}$ simulation steps during training to solve PointNav tasks in simulation environments  (Wijmans et al. 2019; Weihs et al. 2020), which poses serious training requirements and computation demands. In SayNav, however, the two-level planning architecture simplifies the job of the low-level planner. The low-level planner mostly outputs control commands for short-range movements. The LLM-based high-level planner is also robust to failures in the low-level planner, by making regular plan updates. In this way, the training load required on the low-level planner can be greatly reduced.

Encouraged by the success of imitation learning (IL) on navigation tasks under resource constraints (Ramrakhya et al. 2022, 2023; Shah et al. 2023), we investigate a sample efficient IL-based method to train the low-level planner for the agent in SayNav. This low-level planner is trained from scratch (without pretraining) on only 2800 episodes or $7\times 10^{5}$ simulation steps. Specifically, the low-level planner is trained using the DAgger algorithm (Ross et al. 2011) to follow a shortest path oracle as the expert. Despite the fact that the shortest path oracle lacks the exploration behavior required to solve the PointNav task in complex environments (e.g. multiple rooms), we find that it helps the agent to learn short-distance navigation skills very quickly, without human-in-the-loop.

We first implement a shortest path oracle using A* algorithm on the grid of reachable positions in the house, and then train a PointNav agent using the DAgger (Ross et al. 2011) algorithm with the A* oracle as the expert. We perform DAgger dataset aggregation over two rounds. In the first round, 2,000 episodes were collected using a random agent. In the second round, 800 additional episodes were collected using an agent trained using episodes from the first round. The aggregated dataset contains a total of 2,800 episodes or $7\times 10^{5}$ simulator steps for IL. For each episode, we choose a scene from the ProcThor-10k train split, randomly sample a start location and sample a random object from the scene as the goal location. The robot then performs the task by taking expert action with $p=0.2$ and agent action from $p=0.8$. The robot’s observations and expert actions are stored for behavior cloning.

For behavior cloning, the objective function is to minimize cross entropy loss of predicted action against expert action at every step. For agent architecture, following (Wijmans et al. 2019), we use a standard architecture shown in Figure 6. As mentioned, our agent receives an RGBD image and the agent’s pose with respect to the goal location as the input. A GroupNorm (Wu et al. 2018) ResNet18 (He et al. 2016) encodes the input RGBD image, and a 2-layer 512 hidden size gated recurrent unit (GRU) (Cho et al. 2014) combines history and sensor inputs to predict the next action. We use the Adamax optimizer with lr $10^{-4}$ and weight decay $10^{-4}$. We optimize the objective function with batch size of 16 episodes for 50 epochs.

We evaluate the PointNav performance of the agent on the publicly available AI2Thor ObjectNav dataset ¹¹1https://github.com/allenai/object-nav-eval ProcThor-10k-val split, using the ground truth location of the object as the goal for PointNav evaluation. The evaluation split contains 1550 episodes. When multiple instances of the target object are available, we arbitrarily select the first instance as the PointNav goal. Our low-level planner achieves $84.5\%$ SR (success radius 1.5m, max 300 steps) and $0.782$ SPL. On the subset of episodes where the starting position and the goal position are in the same room, performance increases to $98.5\%$ SR and $0.930$ SPL.

Most prior Embodied AI simulators such as AI2-THOR (Kolve et al. 2017) or Habitat (Szot et al. 2021) are either based on environments with single rooms or lack the natural placement of objects within the environment or lack the ability to interact with the objects. For our experiments, we opted for the recently introduced ProcTHOR framework (Deitke et al. 2022), which is built on top of the AI2-THOR simulator. ProcTHOR is capable of procedurally generating full floor plans of a house given a room specification (ex: a house with 2 bedrooms, 1 kitchen and 1 bathroom). It also populates each floorplan with 108 object types, with realistic, physically plausible, and natural placements. The scenes in ProcTHOR are interactive which allows to change the state, lighting and texture of objects, posing a bigger challenge for perception and a broader scope for future work. We build a benchmark dataset of 132 episodes using 132 different houses with 3-10 rooms each and select 3 objects for each house to conduct MultiON task. Each episode in the dataset is described using the following properties:
1. data_type : This corresponds to either ‘val’ or ‘test’ based on which set of data was used from ProcThor-10K to construct the episode.
2. house_idx : This corresponds to index of the specific house in the ProcThor-10K dataset.
3. num_rooms : Number of rooms in the house
4. num_targets : Number of targets in the house (Currently we have limited the dataset to 3 targets)
5. targets : List of unique targets in the house along with their ground truth locations
6. start_position : Start position randomly sampled from all reachable positions in the house
7. start_heading : Start heading randomly sampled from 0, 90, 180 and 270 degrees
8. shortest_path_targets_order : The order of targets that results in shortest path using A* planner. This is evaluated by running A* planner on all possible target orders.
9. shortest_path_length : Length of the shortest path computed via A* planner along the shortest_path_targets_order

We report two standard metrics that are used for evaluating navigation tasks: Success Rate (SR) and Success Weighted by Path Length (SPL) (Anderson et al. 2018). SR measures the percentage of cases where the agent is able to find all the three objects successfully, while SPL normalizes the success by ratio of the shortest path to actual path taken. We use the minimum of the shortest path from the starting point to permutations of all the target objects. In addition to these two metrics, we measure the similarity between the object ordering obtained by the agent and that by the ground-truth. The ground-truth object ordering gives an idea of how a perfect agent would have explored the space by first identifying objects that are highly probably in current room/scene-graph and then exploring other rooms. We use the Kendall distance metric (Lapata 2006), which computes the distance between two rankings based on the number of disagreeing pairs. We use the Kendall Tau that converts this distance into a correlation coefficient, and report it over the successful episodes (all three targets are located).

We use the default robot with head-mounted RGBD camera in the AI2-Thor simulator. The camera has $320\times 240$ resolution with 90°field-of-view (FoV). The details of the robot observations and actions can be referred to the section 3.1.

We conduct experiments with 2 different LLMs: gpt-3.5-turbo and gpt-4. For training the low-level planner, we used the IL method, described in the section 3.5. It achieves $84.5\%$ SR (success radius 1.5m, max 300 steps) and $0.782$ SPL in unseen ProcThor-10k-val scenes with random start and goal locations. For short-range movements within a single room, performance increases to $98.5\%$ SR and $0.930$ SPL.

Note that SayNav consists of three modules – incremental scene graph generator, LLM-based planner, and a low-level planner. The major goal of our experiments is to fully validate and verify the LLM-based planning capabilities in SayNav for MultiON. Therefore, for each of the other two modules, we implemented an alternative option which uses ground truth information to avoid any error within that module. This allows us to conduct ablation study for determining the impact of each module on the overall performance.

First, we allow the scene graph to be generated using ground truth (GT) instead of visual observations (VO). We have described the generation of scene graph using VO in the section 3.3. The GT option directly uses the ground truth information of surrounding objects, including 3D coordinates and geometric relationships among objects, to incrementally build the scene graph during exploration. This option avoids any association and computation ambiguity from processing on visual observations, such as computing 3D coordinates for each object based on RGBD image and its segmentation.

Second, we use an oracle planner (OrNav) as the low-level planner instead of our efficiently-trained IL agent (PNav). We have described the implementation of PNav in the section 3.5. For OrNav, we use an A* planner which has access to the map of the environment. Given a target location, it can plan the shortest path from the agent’s current location to the target.

Most existing LLM-based approaches for robot navigation operate in known and/or small-scale environments. However, there do exist RL / IL based approaches (ex: (Gireesh et al. 2023)) and traditional SLAM-based approaches that can work in our problem setting. Many previous works (ex: (Savva et al. 2019)) have shown that RL/IL based Point-goal Navigation (PointNav) outperforms SLAM-based approaches in unknown environments by a large extent (80% vs 62% in the mentioned example). Due to lack of open-source datasets/code from existing works, we chose to implement the strongest possible baseline method which employs IL-based PointNav policy that could potentially reflect the upper bound of the performance of a learning-based agent using the same amount of training data as ours. The baseline agent uses two privileged information that SayNav doesn’t have access to. First, it has access to the optimal order of target objects which achieves the shortest path. This simplifies the MultiON task to become a series of ObjectNav tasks. Second, as a PointNav policy typically performs better than an ObjectNav policy, we also provide the baseline agent access to the ground truth coordinate of each target object, which then simplifies the task to a series of PointNav tasks. In other words, we implement a PointNav agent to navigate through ground truth points of the objects in the optimal order.

Table 1 shows the results of the baseline along with different implementation choices in SayNav. Note for the baseline method, even after using ground-truth object locations in optimal order, SR is only $56.06\%$, which indicates the difficulty of MultiON task. It is because of the fact that PointNav policy observes a loss in performance in large-scale environments. Although, the baseline has access to the locations of the goal objects, finding each object still requires it to plan a long-range path across multiple rooms. In comparison, SayNav, without using any ground truth, achieves a higher SR ($60.32\%$ and $64.34\%$ with gpt-3.5-turbo and gpt-4 respectively). This improvement highlights the superiority of SayNav in navigating in large-scale unknown environments.

SR: With SayNav, we observe that the best performance is achieved when using scene graph generated by ground-truth object/room location from the simulator (GT) along with OrNav. Note that SR of 95.35% with gpt-3.5 and 93.93% with gpt-4 in this setting reflects the strength of our LLM-based high-level planner which is the only imperfect module in the experiment. When we replaced GT with VO, we do observe a loss in performance. We found that the drop in SR can be associated with various challenges encountered in any perception based algorithms. The inaccurate estimation of objects’ 3D positions due to partial observations can lead to failures in detecting targets and navigation. In addition, we remove objects less than 20 pixels on semantic segmentation observations for more practical behavior. Therefore, very small objects can also be missed-out while building the scene graph from visual observations. We also observed a specific challenge in VO associated with estimating the location of glass doors. In the depth map, the depths of visible objects behind the glass door represent the depths of the actual physical door, which fails the estimation of the location of the door. A similar trend can be found from results with GT & PNav and with VO & PNav. When replacing OrNav with PNav, we also observe a fall in performance. This is obvious as PNav doesn’t access any ground truth information, as compared to OrNav.

However, even with all these challenges, SayNav outperforms the oracle-based baseline and succeeds in MultiON tasks. We believe it is due to LLM-based dynamic planning capabilities, with the grounding mechanism based on incremental scene graph generation. It leverages common-sense knowledge, as humans do, to efficiently search multiple different objects in an unknown environment. It also refines or corrects the plan in case of any failure in a planned step.

SPL: Looking at the SPL metric, we see a drop in SayNav as compared to the baseline. Note that SPL reflects the length of the path taken by the agent as compared to the shortest possible path. For example, SPL=1 for an episode would mean that the agent, starting from initial position, goes straight to the targets along the shortest path in the optimal order with zero exploration which is practically impossible in an unknown environment. As a result of access to the ground-truth object locations in optimal order, it becomes obvious for the baseline to have higher SPL. From the results, we also observe that the low-level planner has the major impact on SPL. The system achieves higher SPL with OrNav as compared to PNav.

Kendall-Tau: The Kendall-Tau ($\tau$) metric measures the similarity between the order of objects as located by the agent and the optimal ordering based on the ground-truth. It shows the importance of the knowledge provided by the LLMs, for finding the optimal plan. We observe that the ordering of the objects is not affected much by the low-level planner. This is reasonable since the ordering should majorly depend on the plans generated by the high-level planner. As expected, the score drops when we replace GT with VO since LLM uses scene-graph to generate the plan. The considerable improvement in the score with gpt-4 (vs gtp-3.5-turbo) shows that using a better LLM enables an improvement in use of common-sense priors and yields more optimal ordering. Also, note that Kendall Tau metric doesn’t apply to the baseline since it already has access to the optimal order of targets.

We show an example of a typical episode in Figure 7 where the agent is asked to locate an alarm-clock, a laptop, and a cellphone in an unknown house. The agent happens to start in the kitchen (determined by LLM based on perceived objects). The planner reasons that it is unlikely to find either of the objects there, so it decides to go to another room through a door. Then, it comes to a living-room where it is able to locate the laptop and cellphone. The third object still remains unfound, so it again decides to go to another room via a door. Eventually, it locates the alarm-clock in the final room. The complete demo-video for this example can be found at our project link.

As mentioned in the section 3.3, SayNav uses the 3D scene graph to support memory for future planning. For instance, it automatically annotates the room nodes that have already been explored and won’t plan for the room if the agent happens to visit the same room again. This type of implementation to support memory works perfectly for our chosen task. However, we also wanted to explore the possibility of making the LLM track its own plans. Hence, we also implemented SayNav’s memory via LLM by using Conversational Chains module of the LangChain framework²²2https://python.langchain.com/docs/modules/chains. Here we use two separate instances of identical LLM models, one to generate the high level plans and another to track the generated plans. The LLM tracking the generated plan, uses the Room Tracking Prompt in Figure 8 and is also equipped with a conversational memory. The LLM responsible for generating the plans receives detailed description of the surrounding environment while the other LLM instance only receives the minimal information necessary to do the tracking. A key advantage of this framework is that it avoids hitting the maximum token limit on the LLM by not relying on the entire conversational history (as is usually done). We believe that LLM-based tracking might be able to generalize better to other tasks since it eliminates the need of a module for tracking plan history, which would require different implementations for different task (we will test this in our future work).

Table 2 shows the performance of SayNav using LLM Memory via gpt-3.5-turbo and gpt-4. Note that we use the same model for both the instances of LLM in our experiments. We do observe substantial drop in SR and SPL metrics by using LLM Memory in the case of gpt-3.5-turbo as compared to the results reported in Table 1. However, with gpt-4, the LLM Memory is able to achieve similar results as compared to Table 1. This shows that it is feasible to hand-over the task of tracking to the better LLM models.

We also ported SayNav to a real robot and tested under various settings, for showcasing the efficient generalization of SayNav to real environments. The demonstration video for a cafeteria environment is available at our project link.