Can Large Language Models be Good Path Planners? A Benchmark and Investigation on Spatial-Temporal Reasoning

We thank the reviewer for spending time reviewing our work and acknowledging our contributions to the discussion of IID vs. OOD!

Regarding “why the path planning task in this benchmark can be used to measure temporal reasoning” and the challenge of our benchmark, please refer to “General Responses to All Reviewers”.

Missing references We thank the reviewer for suggesting the missing references! We apologize for the oversight and missing these references; we will make sure to add them to our updated draft.

Looking into the suggested papers, they all revolve around planning in a minecraft environment. Below, we briefly discuss their connect to our work. [1] proposed an interactive approach for open-world planning based on LLMs allowing error correction through self-explanation. This, indeed is relevant to our work as we find substantial improvements on our benchmark by incorporating “interactive” environment feedback (i.e., the ReAct experiments).

[2] relied on an approach where LLMs are used for skill planning. The proposed approach combines reinforcement learning with LLMs in order to decompose the planning task in a minecraft world to achieve long-term planning tasks. LLMs are used to build a skill graph by learning relationships between skills, while RL is used to plan over the learnt graph. This paper highlights another example of how LLMs can be useful tools to assist with long-term planning approaches.

[3] Used LLM to break down the goals and map them to structured actions for final control signals. The proposed LLM-based agent consists of an LLM Decomposer, an LLM Planner, and an LLM Interface. Similarly to [1], this work is very relevant to our work as it supports the conclusions reached through our ReAct agent.

Q1: Clarification on the OOD evaluation For the training data for the fine-tuned models, we use the “#Train” subsets from Table 1, which contains 16k instances in single-goal setting and 53k instances in multi-goal setting, all under 6x6 grids and with 1-5 obstacles. We point the reviewer to the first as well as the last two paragraphs of Section 3 for implementation details and experimental design. for more details about the different settings. Similarly, for in-context learning, we draw few-shot examples from the training sets used for finetuning and evaluate on instances drawn from the OOD test sets.

Q2: Clarification on the “exact prompts used in the task” The full prompts used for all in-context experiments are presented in Appendix B for reproducibility. The few shot exemplars are drawn from the training set. The prompt for predicting whether the goal is reachable is not a separate one, however, we provide few-shot exemplars that include this case, and we expect the LLMs to identify these cases based on these examples.

We thank the reviewer for sharing the thoughtful comments on our work! We appreciate the reviewer’s acknowledgement on the importance of our research topic (i.e., temporal and spatial reasoning).

We refer the reviewer to “General Responses to All Reviewers” regarding the concern about “the experiment setting is a bit too simple” and “multimodal” modeling. We welcome further comments from the reviewer and will be happy to have deeper discussions!

We are grateful to the reviewer for their insightful comment on the state of research on LLM spatial reasoning!

We noticed a misunderstanding on our experimental results. Therefore, we would first like to clarify our major observation. That is, based on our results, we believe that LLMs do exhibit some ability for reasoning over spatial information. However, they are still not perfectly solving spatial reasoning, and they have failed in long-horizon temporal reasoning.

Below, we clarify how we reached the conclusion that “LLMs do exhibit some ability for spatial reasoning”. We believe that the observed success of LLMs is not solely “pattern/instruction imitation”. Whether LLMs can reason or not is still a debatable question and our work does not aim to resolve the argument (instead, we provided a benchmark to facilitate it). In our humble opinion, pattern imitation happens when the same or similar patterns have been provided to the LLM, either during its pre-training or in-context learning, so that the LLM may succeed by memorizing the patterns from the data and then adapting the language to the specific test input, rather than reasoning about the test problem from scratch. However, it is important to note that the path planning task we have focused on in this work is very different from the commonly seen math reasoning tasks (e.g., GSM8k, MATH) in the following ways:

First of all, path planning itself is an optimization problem. As elaborated in Appendix A.2, a path planning task essentially projects to the A* search (single-goal setting) or combining A* search with the Traveling Salesman (multi-goal setting) problems. This is very different from math problem solving where an LLM could cheat by imitating the pattern of how numbers given in the condition can be combined into an equation and eventually led to a numerical answer. Due to its optimization nature, path planning cannot be achieved with trivial pattern imitation.

While math problems are often framed in daily scenarios (such that an LLM may leverage the commonsense pattern it has learned to play “shortcuts”), the path planning problems in PNNL is highly symbolic (e.g., using p0 and p1 rather than the specific city names as locations, and indicating all obstacles using x-y coordinates). So playing “shortcuts” is not very likely. We want to clarify that our prompts to LLMs do not include the exact test environments, and can even include completely OOD ones, so there does not exist any potential “pattern” for imitation. Notably, GPT-4 with CoT obtains stable generalization to smaller or larger grid environments (success rate of 0.787 -> 0.763 and 0.836). While it suffers from degradation in the obstacle OOD evaluation, the success rate is still decent (0.544). To further uncover its underlying mechanism, we added one experiment for 168 20x20 grid environments, each consisting of 40 obstacles. We still observed a success and optimal rates of 0.279 from GPT-4 AE and 0.351 from GPT-4 CoT. This implied that LLMs do reason about their optimization strategy in path planning, although the strategy is not very generalizable. We would like to denote a distinction between (a) whether LLMs can reason and (b) where their reasoning outcome (e.g., their path planning strategy) is generalizable to the more complicated scenarios. Intuitively, even for humans (e.g., human soldiers), when they have learned skills exclusively only in a small-size practice room, they would have difficulty when entering a real-size battlefield, but this does not imply their lack of reasoning or learning during the practice. Lastly, while similar math problems may have potentially been included the pre-training data of LLMs, this is much less likely to be true for path planning, because intuitively people do not commonly verbalize a symbolic task on the Internet data.

As discussed in our experimental results section, LLMs still cannot “perfectly” reason about the spatial information. This again can be evidenced by the degradation of LLMs in OOD evaluation. They also fail to perform long-horizon, temporal reasoning; for example, we observed that the success of ReAct compared with CoT is attributed to the way how it receives environment feedback and decomposes a long-horizon task into multiple short-horizon ones. Another result highlighting LLMs inability for temporal planning is the low ability to find the optimal path, particularly for the multi-goal setting; We particularly probe the LLM ability to perform optimization in Appendix D, and present the results in Table 10, which clearly shows that GPT-4 falls short on this task.

Thank you very much for the thorough rebuttal. I have thought carefully about the rebuttal points and am currently keep my score.

Some remarks:

• "playing shortcuts is not very likely" seems like a conjecture, and I do not know that there is evidence to back up this claim. Again, I will say that it seems to me that evidence of the solution being beyond imitation is the ability to execute the same logic on out of distribution or long horizon tasks (where the models tend to fail) since these cases cannot be imitated. In terms of "number of examples" being limited, the authors fine-tune the LLMs so the models do receive examples of this type of input/output combination or execute an explicit reasoning policy on top of the LLM .

• Similar and the same are quite different. I would argue that providing fine-tuned information to an LLM of 6x6 grid path planning problems and then testing on different 6x6 grid path planning problems are "similar". I would expect a method which actually performs reasoning to fairly easily generalize to 7x7 grids. I think it is a substantially overstated analogy by the authors to make the comparison to this small degree of grid size generalization with human soldiers "learn[ing] skills exclusively only in a small-size practice room, [...] hav[ing] difficulty when entering a real-size battlefield."

• Regarding the simplicity of the environment which several other reviewers brought up, I understand the point that the environment is intentionally simple to probe the capability very directly for the intended planning task. I think this is a good design choice. However, a red flag regarding this proposed benchmark is the comment of the following comment from the authors combined with the fairly high performance results of the LLMs:

"A key takeaway from our conclusion is that LLMs are not able to perform any mature level if spatial-temporal reasoning. A future research question to be explored is: “Are LLMs incapable of spatial-temporal reasoning, or do they just need to be prompted in a specific way to elicit such capability?”."

If LLMs are not able to perform any mature level of spatial-temporal reasoning, why should we use a benchmark to measure spatial-temporal reasoning where 90+% success metrics reported in results tables for models that cannot do this reasoning? See Table 3 in the paper.

We thank the reviewer for acknowledging the quality of our experimental design and the thoughtful comments they provided.

Clarification on the contribution of this work to the community We refer the reviewer to the general response for a detailed discussion on the contributions of our benchmark compared with prior work.

Here, we further clarify that our work has provided many novel insights beyond “what we would expect from other recent papers”, particularly on the less studied topic of “spatial-temporal reasoning”. For example, Patel et. al (2022) studied whether text-only LLMs can ground spatial concepts (e.g. direction, color, etc.) to a grid world. They find that these concepts are, indeed, encoded in the LLMs. However, the conclusions have been limited to only concept understanding but not “reasoning”. Bubeck et. al (2023) evaluated LLMs ability to navigate a map of a house. They found that, while GPT-4 is not successful at exploring the whole house, it is able to accurately describe what it is exploring, despite being prompted solely through a text-based interface, highlighting LLMs' "spatial awareness" but also underscoring a shortcoming at planning; however the latter point was not explored in depth. Besides, as shown in the general response, most existing benchmarks do not support the assessment combining spatial and long-horizon temporal reasoning; as a result, not many insights can be obtained on this topic.

Our work fills the gap by systematically evaluating a set of advanced LLMs in path planning, where both spatial and long-horizon temporal reasoning are needed. Our experiments were based on both fine-tuned LLMs and the state-of-the-art GPT-4, when it is augmented with the most advanced prompting methods (e.g., CoT, ReAct), which were not explored in prior work. Our experimental results showed that LLMs, with careful prompting, exhibit a certain level of spatial reasoning, but they still fall short in temporal reasoning.

Q1: How do the authors justify the use of the 7x7 path planning environment as a valid proxy & Q2: findings are scalable and applicable to real-world tasks

We refer the reviewer to the general response for the discussion about PNNL’s simplicity but that its findings can be generalized to more complex, real-world scenarios.

Q3: Could the authors comment on any additional metrics or methods that might be used to evaluate planning performance in more complex scenarios?

The metrics used in this work (e.g., success rate) can still be generalizable to more complex scenarios. Another useful metric for motion and path planning in complex environments is Clearance from obstacles (Plaku, 2017), which measures the distance of the agent to nearby obstacles. This metric allows for better evaluation of the plans as, in some cases, paths having lower clearances might be harder to execute when taking dynamics into account.

Q4: How might advancements in LLMs impact the spatiotemporal reasoning capability?

A key takeaway from our conclusion is that LLMs are not able to perform any mature level if spatial-temporal reasoning. A future research question to be explored is: “Are LLMs incapable of spatial-temporal reasoning, or do they just need to be prompted in a specific way to elicit such capability?”. Our work shows that interactions with environment feedback idea is very promising in this regard, however, it remains impractical due to a high cost and slow inference. Therefore, an idea that can be explored is whether LLMs are able to self-correct intrinsically without need for external signals; recent work has shown that this skill is not present in current LLMs (https://arxiv.org/pdf/2310.01798.pdf); indicating that they lack the ability for true reasoning; but they seem to encode enormous knowledge which allows them to exhibit what seems to be concept commonsense understanding (which can be reduced to a memorization task). Hence, developing low-cost and efficient approaches (e.g. smaller fine-tuned models trained with carefully designed objective functions) can yield significant improvements.

Regarding Reviewer yt2L’s suggestion on multimodal modeling

The main aim for our task is to look at whether text-only LLMs can plan over spatial information, not to have an end-to-end navigation agent for a realistic environment. That is, we focus on “probing” LLMs and forming better understanding on their capability scope. Prior benchmarks investigated spatial reasoning for vision-language models as a whole (Lake, 2018; Shridhar, 2020; Qiu, 2021); however, with our benchmark, we decouple the evaluation of spatial reasoning in language and vision. This is important because it offers insight into the LLMs ability to ground spatial knowledge drawn from the pre-training data, without having to account for errors that may be due to failures of the vision component. In fact, recent work has shown subpar performance of state-of-the-art vision-language models on basic tasks such as object identification and mapping language utterances to visual signals (e.g.https://arxiv.org/pdf/2309.17421.pdf ; https://cdn.openai.com/papers/GPTV_System_Card.pdf; https://arxiv.org/pdf/2311.09247.pdf). Evaluating each component separately can help shed more light on what each component can and cannot do, and how they fit together. Because of the same reason, it is shown that the more recent benchmarks on similar topics have all decoupled the reasoning tasks from vision components (see the summary in our table in the general response). In addition, in our response Regarding Reviewer w1hA and yt2L’s concerns about the simplicity of our benchmark, we showcased that the findings obtained from our text-only grid environments are generalizable to the more complicated cases with visual inputs.

Regarding Reviewer wB3J’s question on “why the path planning task in this benchmark can be used to measure temporal reasoning”

The path planning task in the proposed benchmark is an effective measure for temporal reasoning because it requires the model to engage in sequential thinking. The task demands that the model plans several steps ahead. This involves not only understanding the current spatial configuration but also anticipating how each move will impact future options and outcomes, in order to be able to optimize over long trajectories. In fact, a common way to represent the task formulation for our multi-goal setting is using temporal logic, a type of logic particularly designed for problems involving temporal planning (Plaku, 2016; Fainekos, 2009; Ayala, 2013 to name a few).

We refer the reviewer to the following sources which similarly studied spatial-temporal reasoning under the same definition as ours; for example, [4] emphasize how AI agents interacting with a physical world need to utilize spatial knowledge to understand the positions and relations between physical objects, and temporal reasoning to assess which actions to perform over time.

[1]https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6420843, [2]https://arxiv.org/abs/2103.14230, [3]https://books.google.com/books?hl=en&lr=&id=BIHLm7W44MoC&oi=fnd&pg=PR8&dq=spatial+temporal+reasoning&ots=-WvD0Xm1Wm&sig=Ewg2juC2BwtMy6xQ4E_EJJnnEQs#v=onepage&q=spatial%20temporal%20reasoning&f=false
[4] https://paperswithcode.com/paper/neuro-symbolic-spatio-temporal-reasoning

Regarding Reviewer w1hA and yt2L’s concerns about the simplicity of our benchmark and whether “the findings can be generalized to more complex, real-world scenarios”

First, we would like to note that, albeit being simple, our benchmark based on the 2D grid environments is already sufficiently challenging for LLMs at their current stage. For example, while ReAct reveals impressive performance in in-distribution settings, it still suffers from OOD generalization, and as we discussed in Section 4.1, ReAct’s success does not imply any salient temporal reasoning capability; instead, it is attributed to breaking the long-horizon task into multiple short-horizon ones with the costly iterative prompting. The fine-tuned LLMs also struggled significantly in OOD generalization. Therefore, we don’t consider the path planning task being “solved”.

Second, our benchmark can be easily extended to be much more complex in the future, owing to its synthetic nature. For example, by placing the obstacles strategically, we can simulate rather complicated geometric shapes (e.g., circular mazes or battlefields with scattered blocks). Additional constraints (e.g. specifying the need for the fuel level) can also be seamlessly integrated. In addition to its scalability, the synthetic nature of our benchmark also makes it resilient to “data contamination”. That is, while ChatGPT/LLMs may continually re-train themselves from the up-to-date internet data, we can refresh the benchmark (via synthesis) and ensure that newer generations of ChatGPT/LLMs have not encountered the exact problems being tested. Furthermore, developing a complicated simulation environment can be time-consuming, while our relatively simpler (yet challenging) benchmark can greatly accelerate this development process and be easier for implementing the evaluation metrics.

Finally, we emphasize that the findings that we obtained from the current relatively smaller-scale grid environments can generalize to the more complex ones. To showcase this, we have performed two additional sets of experiments. In the first set of experiment, we performed an OOD evaluation of GPT-4 Action-Effect and CoT on 168 synthesized environments with a much larger grid size (20x20, compared to 6x6 in IID) and more obstacles (40, compared to 5 in IID). The two LLM variants obtained a success and optimal rate of 0.279 and 0.351, respectively, indicating a consistent finding as what we observed in the relatively smaller-scale grid environments. In the second set of experiments, we aimed to evaluate LLMs in a 3D environment (see Appendix D in our updated draft). Because of bringing in the vision component, we replaced GPT-4 with GPT-4V(ison). However, the current GPT-4V does not seem to be able to learn from few-shot image-and-text demonstrations, even when we tried to feed the information through multiple turns of conversations. Therefore, all experiments were performed in only a zero-shot setting. However, our findings from the small-scale 2D grid environments still generalized here — we showed that (a) the naive zero-shot GPT-4V only generates random action sequences, (b) augmenting GPT-4V with Action-Effect can dramatically improve the chance to succeed, and (c) GPT-4V with zero-shot CoT gives a similar output as GPT-4V Action-Effect due to the limitation of zero shot, but it also outlines a strategy of requesting environment feedback, which implies the promise of ReAct.