On the Planning Abilities of Large Language Models - A Critical Investigation
Authors: Karthik Valmeekam
Matthew Marquez
Sarath Sreedharan
Subbarao Kambhampati
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Large Language Models
Planning
LLMs for autonomous and heuristic planning guidance

Abstract: Intrigued by the claims of emergent reasoning capabilities in LLMs trained on general web corpora, in this paper, we set out to investigate their planning capabilities. We aim to evaluate (1) the effectiveness of LLMs in generating plans autonomously in commonsense planning tasks and (2) the potential of LLMs as a source of heuristic guidance for other agents (AI planners) in their planning tasks. We conduct a systematic study by generating a suite of instances on domains similar to the ones employed in the International Planning Competition and evaluate LLMs in two distinct modes: autonomous and heuristic. Our findings reveal that LLMs’ ability to generate executable plans autonomously is rather limited, with the best model (GPT-4) having an average success rate of ~12% across the domains. However, the results in the heuristic mode show more promise. In the heuristic mode, we demonstrate that LLM-generated plans can improve the search process for underlying sound planners and additionally show that external verifiers can help provide feedback on the generated plans and back-prompt the LLM for better plan generation.

On the Planning Abilities of Large Language Models : A Critical Investigation
Karthik Valmeekam
Matthew Marquez
School of Computing & AI
School of Computing & AI Arizona State University, Tempe. mmarqu22@asu. edu
Arizona State University Tempe. kvalmeek@asu. edu
Sarath Sreedharan'
Subbarao Kambhampati School of Computing & AI Arizona State University, Tempe. raoßasu. edu
Department of Computer Science, Colorado State University, Fort Collins. sarath. sarath. wweeedharan@cooosttaeeee edu
Abstract
Intrigued by the claims of emergent reasoning capabilities in LLMs trained on general web corpora, in this paper, set out to investigate their planning capa- bilities. We aim to evaluate (I) the effectiveness of LLMs in generating plans autonomously in commonsense planning tasks and (2) the potential of LLMs as a source of heuristic guidance for other agents (AI planners) in their planning tasks. We conduct systematic study by generating a suite of instances on domains simi- lar to the ones employed in the International Planning Competition and evaluate LLMS in two distinct modes: autonomous and heuristic. Our findings reveal that LLMSs ability to generate executable plans autonomously is rather limited, with the best model (GPT-4) having an average success rate of ~22 across the domains. However, the results in the heuristic mode show more promise. In the heuristic mode, we demonstrate that LLM-generated plans can improve the search process for underlying sound planners and additionally show that external verifiers can help provide feedback on the generated plans and back pack-prompt the LLM for better plan generation.
Introduction
It would be exaggeration say that transformer-based large language models (LLMs) have revolutionized the field of natural language processing (NLP). Kicked off by the advances presented by the GPT-x models developed by OpenAl (27), these types of language models currently provide state-of-the-art performance many of the standard NLP tasks. Although LLMs were originally developed mostly do word sequence completion tasks, with no guarantees about the completion beyond its coherence, there have been increasing claims and anecdotal evidence that they have other emergent capabilities that are normally associated with sequence completion. Indeed, the hints of such emergent capabilities has started veritable land rush, with researchers probing (prompting) and studying LLM behavior almost as if they were artificial organisms (c.f. (16).. Of particular interest to us in this paper is the thread of efforts that aim to investigate (and showcase) reasoning abilities
of L.L.M-includdng commonsense reasoning [35] 29 77 logical reasoning [33], and even ethical
reasoning [5). The macro-tenor of the drumbeat of these works has been suggesting that L.M''s are
indeed capable of doing such kinds of reasoning 19 37
Author was at Arizona State University during part of this work
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

One type of reasoning task that has been well studied in the Al community is planning and sequential decision making. At its simplest. planning involves developing a course of actions (policy) which when executed takes the agent to a desired state of the world. Planning has generally been studied primarily as an inference on world and reward models- specified by humans or learned by the agent by interacting with its world. In this paper, we are interested in seeing what planning abilities, if any, LLMs may already have, given their high capacity functions (with billions of tunable parameters) trained on web-scale corpora. Specifically, we are interested in answering two broad questions:
1. How effective are LLMs by themselves in generating simple plans in commonsense planning tasks (of the type that humans are generally quite good at)?
2. How good are LLMs in being source of heuristic guidance for other agents in their planning tasks?
Notice that in theory, it is possible for LLMs to be very effective as idea generators for external sound planners or humans in the loop in cemputee--upportee cooperative work scenarios, while themselves being very bad at generating plans that are guaranteed to be correct. This is especially likely because the chief power of L.LMs comes from their pattern- finding abilities than from first- principles simulations over world models. Compared to planner that is guaranteed to be correct in narrow set of domains, LLMs may likely be good at generating plausible (but not guaranteed to be correct) plan heuristies/suggestion in many more domains.
To investigate these questions in a systematic rather than anecdotal manner, we generate a suite of planning problem instances Fl based on the kinds of domains employed in the International Planning Competition [14). To eliminate the subjective aspect of analysis that forms the core part of many earlier efforts on evaluating the reasoning capabilities of LLMs. we automate the evaluation by leveraging models and tools from the automated planning community. The evaluation itself is done
Back-prompling
Seed
LPG
plun
Prompt Geseratoz
Model
Candidate pisa
Planning System
Language Model
LLM heuristics
sound planners like verifiers
Planning System
LLM
planner
Figure 1: The diagrammatic overview of the two modes of LLMs for planning.
in two modes (shown in Figure D] In the first "autonomous" mode, LLMs are used standalone, and we directly assess the quality and correctness of plans they generate. As we shall see, the results in the autonomous mode are pretty bleak. On an average, only about 12% of the plans that the best LLM (GPT-4) generates are actually executable without errors and reach their goals. We will show that the choice of the specific LLM (we have tested the family of GPT L.LMs including GPT-4 (25. GPT-3.5 24), InstructGPT-3.5. InstructGPT-3 (26) and GPT-3 3. as well as fine tuning does not seem to have major effeect on this dismal performance. We also show that the performance deteriorates further if the names the actions and objects in the domain are obfuscated-a change that doesn't in anyway affect the performance of the standard AI planners. To shed further light on the performance of GPT4 we present an evaluation of the plans generates under a series of more relaxed (more forgiving) executability conditions. Further, provide human baseline for the simplest domain in our set of domains, by presenting the planning instances to human subjects (through IRB-an approved studies) and evaluating the quality and correctness of their plans. These results are substantially better than those of Loossconi that L.LMs can't plan even in simple common sense domain in the autonomous mode. In the second "heuristic" mode, the plans produced by L.LMs are given as input to an automated planner working off of a correct domain model to check whether the LLM's plans help with the search process of the underlying planner to come up with correct plans. Specifically we show that a well known automated planner called LPG [6], that uses Link to the github repo: http::///tttttuocm//mmrrrttrtttt PPanning

---

local search to locate and remove flaws in a candidate plan to make it correct, is able to repair the LLM plans with relative ease. We compare the LLM+LPG combination with two baselines, one where an empty plan is used as the seed plan for the LPG and two, where a random plan is provided as the seed plan to the LPG. We show that the average search steps by the LLMMLPP combination is much lesser than both the baselines, thereby revealing that LLMs' plans are indeed helping with the search process of the underlying planner. Further, instead of having LPG correct the plans, we use an external verifier, VAL [I]] to point out the errors in the LLM-generated plans and back-prompt the LLM for a new plan with this feedback. We show that this repeated interaction indeed improves the plan correctness in common-senss domains. Overall, our findings demonstrate that, with respect to planning, LLMs' perform poorly in the autonomous mode but the generated plans can help AI planners in the search process or can be given to externa verifiers and back pockmprompt the LLM for better plans. In this paper, we first present an overview of the related work. Following that, we describe the necessary background and the prompt generation pipeline. Finally, we provide the results and analysis of various experiments undertaken in both autonomous and heuristic evaluation modes.
2 Related Work
In this work, we look at LLMs' planning capabilities when the domain is given as part of the prompt (as is the standard practice in automated planning (8). Our evaluation focuses on zero-shot (just domain and problem specification), and few-shot (example problems with plans) modes. There have been a few works that looked at the planning capabilities of LLMs. Most of them, such [12 2 focus on commonsense domains/tasks (c.g. moving things in kitchens, wedding/menu planning etc.) and thus evaluate LLMs in a mode wherein the prompt doesn't 't include any information about the specific domain. Plans generated in that way are hard to evaluate as they are not directed at any plan executor and the humans often wind up giving the benefit of doubt for a plausible-but but not actually executable- plann. This is why in SayCan (2]. where executability is critical, they try to filter out/interpret the LLM plans in terms of the skills/actions that are actually available to the executor. While SayCan does this in a rather convoluted way that requires access to the internal log probabilities of the LLM, our approach simplifies this by specifying the domain as part of the prompt. In all our experiments, we found that LLMs only use the actions listed as part of the domain specification.
One other mode of evaluation of planning capabilities in the literature involves the user incrementally interacting with the LLM, and re- re-prompting it to point out flaws in its plans, with the hope that
the LLM eventually reaches executable plan B 39 28 Such evaluations are notorious for their Clever Hans effect [1 with the actual planning being done by the humans in the loop rather than the LLMs themselves. We thus separate our evaluation into two autde--utonomouus and as assistants to external planners/reasoners. There have also been efforts which mostly depended on LLMs as "translators" of natural language problem/goal specification into formal specifications, which are then thrown over to sound external planners
[38 21). Such efforts don't shed any light on the internal planning capabilities of the LLMs themselves. as our evaluations in autonomous and assistive modes do. Finally, after our initial study and benchmark were made public, other groups did parallel studies that largely corroborate our results on the ineffectiveness of LLMs in finding executable plans 332 21).
Taking broader perspective, making plans in the world involves (1) discovering actions (and their precondition/effect causal dependencies), and (2) sequencing an appropriate subset of available/dis- covered actions to achieve the agent's goals. The former requires broad knowledge about actions available in the world and their individual effects, while the latter requires deep drilling-dwwn over a given set of actions ensure that all goals are supported (causal chaining) without any undesirable interactions. L.LMs have an edge on the former-they do indeed have web-scale broad knowledge! As we shall see however, they are very bad at the second phase of developing valid interaction free plans (in part, because LLMs don't 't have the ability to do combinatorial search). Most cases in literature (as outlined in [8] where LLMs are claimed to have "planned" turn out, upon close examination, to be instances of phase 1 1-your wedding plans, recipe plans etc.-where you are either using very forgiving plan correctness criterion, or the phase 2 vacuous. Standard AI planners on the other hand-asso assume that the discovery part is done and handed down as compact domain model, and focus mostly on the second part: selecting among known actions to establish causal chains and sequencing them to make them interaction free. In this sense, LLMs and Al planners can be complementary, as we have shown this paper-with the former helping with phase 1-either with a candidate/approximaae plan or domain model-and the latter with phase 2.
3

---

Prompt Generation for Classical Planning Problems
3.1 Background
Given that we interested in investigating the basic reasoning about actions and change problem, want to look at the most fundamental planning formalism first, namely the goal-directed deterministic planning problem. Colloquially referred to classical planning problem, these problem classes consist of problem domain, an initial state and a goal state. The problem domain consists of a set of fluents which correspond to predicates with some arity and set of actions. The state-space for the planning problem defined by the possible truth assignment over the predicates. Each action consists of preconditions and effects where preconditions is set of predicates that describe when action can be executed and effects are set of predicates that describe what happens when an action is executed. The effects further consist of add effects, which the set of predicates that will be set true by the action, and delete effects, which the set of predicates that will be set false. The solution for a planning problem is sequence of actions, result in a state where the goal conditions are satisfied. A standard representation to specify such kind of planning problems is the Planning Definition and Domain Language (PDDL) 22]. Below is snippet of an action from popular benchmark problem called Blocksworld, in PDDL. The action corresponds to picking up block in that domain.
plan, that when applied in the initial state will
(raction pickup
:paraneters (?ob)
:precondition (and (clear ?ob) (on-table ?ab) (arn-enpty)) :effect: (and (holding ?ob) (not (clear ?ob)) (not. (on-table ?ob))
(not (arn-enpty))))
more detailed description on classical planning problems is provided in Appendix A.I. We now will describe how we generate the prompts that are given to the LLMs.
3.2 Prompt Generation
One Shot NL (with State Tracking)
Example Generation
Example Generetor
Arnotator
One Shot NL
PDDL Problem
Natural
PDOL Files
Language
Translator
One Shot PDOL
Figure 2: The diagrammatic overview of the prompt generation pipeline. The prompt configurations for the different experiments generated from PDDI. domain files and modified with example generator and natural language translator as needed depending on the experiment requirements.
Prompt Configurations: We have developed suite unique planning problems to test LLMs abilities to generate plans. We have multiple prompt configurations based on this suite of problems, varying both the method of presentation as well as number of examples given to the LLM. In particular, we two methods of presentation, natural language and PDDL, as well as two different methods of providing examples, zero shot (with no examples provided) and one shot (with an example provided), giving us four different configuration combinations for our experiments.
Within a prompt, LLMs are first provided with lifted domain description. For one shot configura- tions, the prompt additionally contains an example instance of planning problem (consisting of a description of the initial state and the goal) and the corresponding plan (which ends with a tag, referred to the plan-end tag, that denotes the end of the plan). All prompts end with planning problem description. The text generated by the I.L. until the plan-end tag is used as the candidate for extracting the plan. If the extractor cannot reasonably extract an instance, it is marked as incorrect.

---

Table I: Results of GPT-4, GPT-3.5 (popularly known ChatGPT), Instruct-GPT3.5, instuct-GPT3 (text-davinci-002) and GPT3 (davinci) for the Plan Generation task with prompts in natural language.
Domain
Method
Instances correct
GPT-4
GPT-3.5
I-GPT3.5
I-GPT3
GPTT-
54/600
41/600
6/600
One-shot
206/600 (34.3%)
37/600 (6.1%)
Blocksworld
(9%)
(6.8%)
(1%)
(BW)
Zero-shot
210/600 (34.6%)
8/600 (1.3%)
COT
214/600 (35.6%)
3/200
Logisties Domain
One-shot
28/200 (14%)
1/200 (0.5%)
6/200 (3%)
(1.5%)
Zero-shot
15/200 (7.5%)
1/200 (0.5%)
4/600
14/600 (2.3%)
0/600
Mystery BW (Deceptive)
One-shot
26/600 (4.3%)
0/600 (0%)
(0.6%)
(0%)
Zero-shot
1/600 (0.16%)
0/600 (0%)
COT
54/600 (9%)
5/600
5/600
1/600
Mystery BW (Randomized)
One-shot
12/600 (2%)
0/600 (0%)
(0.8%)
(0.8%)
(0.1%)
Zero-shot
0/600 (0%)
0/600 (0%)
The prompt is either formatted in natural langauge PDDL. Natural language prompts utilize complete natural language sentences to describe feasible actions in the domain. Initial conditions are also reported as complete sentences. Plans in the natural language setting take the form of series of commands such as "stack the orange block on top the blue block". As implied by the name, PDDL prompts format all elements (domain description, initial state, goal state, and plans) using PDDL. We point the reader to the supplementary material for examples on each of these prompt configurations.
Chain of Thought Prompting: In addition to the four experiments above, we look at a fifth experiment using state tracking chain of thought prompting technique in natural language one shot setting. Within this configuration, we provide an annotated example where each action is annotated with the state prior to the action, the reason for why the action is applicable in the prior state, and the resulting state after applying the action. After the example, a meta-explanation about plan correctness is provided. The LLM is then asked to return response making the same state tracking and justification annotations that were included in the example.
Prompt Generation Pipeline: We've developed a prompt generation pipeline (visualized in Figure 2) that accepts PDDL domain files input and outputs prompts that follow the experiments described above. The prompt generation component takes care of creating the set of PDDL problems to be solved for all experiments. Following that, examples
added the prompt in one shot experiments. While our setup utilizes planner during example generation, any example generation technique could be used here so long as the examples generated are valid plans. In the state tracking experiment, we also have developed a component to add justification annotations for examples so that the examples reflect what we expect of the LLM. The last step before finishing translation: since problems at this point are currently in PDDL, prompts for all natural language experiments (whether an example was added or not) need to be translated into natural language. We utilize a domain-speciffe translator to do so.
4 Evaluating Planning Capabilities of LLMs in Autonomous Mode
In the autonomous mode, we treat the LLM as an automated planner and perform a single run of the dataset on the LLMs for each domain and prompt configuration. In this mode, the plan generated by the LLM is back-translated from natural language forms that can used by external plan validators. For each domain, we perform template-based translation to translate between PDDL. and natural language for the natural language prompt configurations. We use VAL. [I]] to evaluate the translated plan with the corresponding domain and problem file. Our evaluation here primarily
5

---

Table 2: Results of GPT-4 and GPT-3.5 (popularly known ChatGPT) for the Plan Generation task with one or zero examples in the prompt by directly providing the domain and problem in PDDL.
Domain
Method
Instances correct
GPT-
GPT-3355
One-shot
75/600 (12.5%)
12/600 (2%)
Blocksworld (BW)
Zero-shot
106/600 (17.6%)
12/600 (2%)
One-shot
28/200 (14%)
1/200 (0.5%)
Logisties Domain
Zero-shot
11/200 (5.5%)
0/200 (0%)
One-shot
17/600 (2.8%)
1/600 (0.1%%
Mystery BW (Deceptive)
Zero-shot
3/600 (0.5%)
0/600 (0%)
focuses on the GPT family of LLMs. We tested GPT-4 25 and GPT-3.5 (commonly known as Chat-GPT) [24] on all the prompt configurations while we tested the older versions of GPT (namely, Instruct-GPT3 and GPT3) on one-shot natural language prompts across the domains. We set the temperature for all models to be 0, thereby making them deterministic. In this section, we detail the evaluation of LLMs on these domains and prompt configurations. We would like to point the reader to the Appendix for example prompts.
Evaluation of LLMs on the Blocksworld domain: Blocksworld problems capture common sense block manipulations and consist of a set of blocks. Blocks are identified with unique colors and are placed either on a table or on top of other blocks. The goal is to arrange some of these blocks in stack in a particular order. The general expectation here would be that one can pick up block if is clear, i.e., there are no other blocks on top of that block and you can only stack block on top of another block if it is clear. The choice of this particular domain motivated by both the fact that this is a simple common sense domain and is very popular domain in planning literature, that has long history of being used in various planning challenges. The instances were generated using PDDL generator employed in the IPC competitions. We permitted the generation of problems that varied in terms of the number of blocks (3-5), optimal plan length, and goal properties (positive, negative, or no interactions between subgoals).
As shown in Table I and Table 2 GPT-4 improves upon previous versions of GPT models in the Blocksworld domain across all four prompt configurations. However, the overall performance is still approximately 34% in the Blocksworld dataset. Even the chain of thought style prompting (indicated by COT in the tables) had little effect on improving the performance. GPT-4 performs better with natural language prompts (206 and 210 instances for one-shot and zero-shot prompts, respectively) as opposed to PDDL prompts (75 and 106 instances). The performance drops significantly with other GPT models. We also discovered that for instances where Instruct-GPT3 generated the correct plans, replacing the example plan in the prompt with another example plan led to an even greater drop in accuracy. This suggests that the LLM seems to rely primarily on pattern matching, rather than inducing some internal model from the prompts. Overall, even in seemingly simple common-senss domain like Blocksworld, which humans typically find easy to navigate, LLMs prove to be quite ineffective in planning autonomously.
Finetuning GPT-3 on Blocksworld: Along with directly testing the LLMSs from the GPT family, we have also looked at the utility of fine-tuning the LLMs. Specifically, we fine-tuned GPT-3 (Davinci) in the Blocksworld domain. For this, we prepared dataset comprising the initial state, goal state, and the respective plan for 1,000 distinct Blocksworld instances. It's important to note that these instances were separate from our test set of 600 instances. By using the default hyperparameters provided by OpenAl and an 80-20 train- prain-validation data split, we carried out the fine-tuning process. Our results revealed that the fine-tuned GPT-3 solved only 122 instances out of the 600 in our set, representing approximately 20% of the total. This suggests that fine-tuning has a limited impact on improving the performance of L.MSs in Blocksworld planning. This outcome aligns with the observations of [40]. who argue that language models trained for reasoning tend to concentrate on the inherent statistical features instead of the causal structure, which in turn affects their performance on such tasks.

---

Open-source models: In addition to the GPT family of LLMs, we have also conducted preliminary experiments with an open-source LLM, BLOOM [1I, and found that BLOOM too ineffective in plan generation. We assessed BLOOM's performance in the blocksworld and mystery blocksworld (deceptive) domains using a one-shot natural language prompt configuration. In the blocksworld domain, BLOOM correctly handled only 4 out of 250 instances, representing a 1.6% success rate. In the mystery domain, it failed to produce a single correct response in all 50 instances.
Human Baseline for the Blocksworld: We have previously mentioned that planning tasks on the blocksworld domain are anecdotally simple enough for humans to perform. To establish this and come up with a preliminary baseline to compare LLMs performance, we conducted an IRB-approved user study where we asked 50 participants come up with plan for blocksworld instance picked at random, from the set of 600 instances that we used for the evaluation of LLMs. We presented the same domain description We point the reader to the supplementary material for further details on the study.
did for the LLMs and then primed them with an example instance.
Out of the 50 participants, 39 of them (78%) came up with valid plan, Along with validity, we also tested the optimality of their plans even though they were not required to come up with an optimal plan. Out of the 39 participants, 35 (89.7%) participants came up with optimal plan. These initial results show that the blocksworld domain is a simple enough domain where most humans are able to come up with plans (which are also optimal) while LLMs, on the other hand, showcase subpar performance.
Evaluation of LLMs on the Logistics domain: Logistics is also a widely recognized domain in the planning literature. In this domain, the objective is to transport packages within cities via trucks, and between cities via airplanes. Within a city, the locations are directly linked, allowing trucks to travel between any two of these locations. Similarly, cities are directly connected each other allowing airplanes to travel between any two cities. Each city is equipped with one truck and has a designated location that functions as an airport. We generated 200 instances on this domain.
From Tables D and 2 we see that in the one-shot setting with natural language input, GPT-4 only solved 14% of the instances (28/200), and this rate dropped to 7.5% (15/200) when using zero-shot prompting. When provided with the domain and problem in PDDL format, GPT-4's performance remained the same in the one-shot setting (14% 28/200) but decreased to 5.5% (11/200) in the zero-shot setting. GPT-3355 did even worse.
Obfuscating names to test the brittleness of LLM Planning: Although the domain specification part of our prompts, the names of the objects (e.g. blocks, trucks), predicates (e.g. on-table, in-city) and actions (e.g. pickup, drive) still do provide connections to the commonsense knowledge that the pretrained LLMs possess. One intriguing question is whether the planning performance is based really only on the domain model or these other background connections. To test this, we experimented with a variation of the Blocksworld domain, where we obfuscate the action names (for example pickup becomes attack, and unstack becomes feast) and predicate names (for example ontable becomes planet, and handempty becomes harmony). Note that from the perspective of standard planners, these [ In addition to such deceptive obfuscation, we also considered a
domains are essentially identical variation where random alphanumeric names were substituted for the action and object names.
Tables I and 2 we see that this simple obfuscation leads to a catastrophic drop in performance. Specifically, with zero-shot prompting and natural language input, GPT-4 able solve 210 instances out of 600 in the Blocksworld domain, but it could only solve 1 instance in the deceptive Mystery Blocksworld domain and 0 instances in the randomized mystery domain. A similar result is observed with the PDDL-style prompts: GPT-4 could solve 106 instances in Blocksworld, but only 3 instances in the deceptive Mystery Blocksworid. Notably, chain of thought prompting does not significantly improve performance over one-shot natural language prompts. GPT-3.5 does not solve even single instance in the entire set of natural language instances. For most of the instances, GPT-3.5 outputs that the instance can't 't be solved. These results strongly suggest that whatever accidental planning performance LLMs show is likely connected to pattern matching rather than reasoning (which should be robust to name change).
'Such obfuscated domains were originally introduced into the Intl. Planning Competition by Drew McDer- mott in 1998 specifically to check if the competion planners were truly domain independent.
7

---

Planning RODL Promatt
Blocspword
Natura Langaage mompes
500
500
One shet 5066 Zero shot
400
400
Deire Dny
Mer Rocaodd
Duki Proveellow
Proceitl m0e
Peler Day
Foar Rolard
Figure Assessment of GPT-4 plans with relaxations in Blocksworld domain Table 3: Evaluation of GPT-4 and Instruct-Gri GPT3 (I-GPT-3) plans heuristics for a local search planner LPG, on blocksworld (BW), logistics and mystery blocksworld domains.
Avg. Search Steps
Avg. Plan Length
Avg. Lev. Distance
Domain
LLM
Empty
Random
LLM
Empty
Random
LLM Seed
Seed
Seed
Seed
Seed
Seed
Plan
Plan
Plan
Plan
Plan
Plan
I-GPT-3
15.8
20.07
14.5
8.45
9.62
11.7
7.22
BW
GPT-4
15.8
20.07
8.9
8.45
9.62
10.76
4.15
Logisties
GPT-4
77.5
144.39
51.3
23.7
32.72
32.24
15.04
Mystery BW
GPT-4
15.8
20.45
16.09
8.45
9.78
11.53
7.77
Analyzing GPT-4 failures: To get better sense of the type of failures LLM generated plans encounter, we wondered whether they will fare much better with a more forgiving test of the validity of the generated plans. In automated planning community, the notion of relaxations of the domain model are used to simplify the cobblem-cheeh to derive heuristics for planning problems [8]. Taking leaf from them, considered two types of relaxations: (i) delete relaxation involves ignoring all the delete conditions of the domain actions (thus making sure that there can be no negative interactions between subgoals) and (ii) precondition relaxation involves ignoring all the preconditions of the domain actions-thus assuming that the the actions are executable from any state giving their effects. Our idea is to evaluate the plans produced by GPT4 with respect to domain models that delete relaxed, precondition relaxed or both. It should be clear that a plan that is correct with respect to the normal (unrelaxed) model will also be correct with respect to all the relaxed models. Figure 3 shows the results for blocksworid. We see that while the correctness of LLM generated plans increased under more forgiving (relaxed) assessments (area in green), even in the most lenient assessment mode Relaxed), there still are plans (~39%) that are incorrect (because they still don't reach the goals) across all the prompt configurations. The plots further classify the failure cases in terms of whether they were inexecutable, shown in maroon, or could be executed but didn't 't reach the goals (shown in red). Note that when preconditions are relaxed, plans are executable. We provide additional details on the relaxed assessments in Appendix A.2.
(Delete+Precondiit)
5 Evaluating LLMs as Idea Generators
While the preceding discussion establishes that LLMs are not capable of generating correct plans in autonomous mode, there is still the possibility that they can be useful idea generators for other sound external planners, verifiers or even humans-in intthe-ooo..... In this section, we investigate this possibility and demonstrate that LLMs show promise this front (especially with external planners and verfiers).
5.1 LLM Plans as Heuristics to Sound Planners
To see if the LLM generated plans can provide heuristic guidance to sound external planners, use a local-search planner I.G ( which generates plans by starting with seed plan and iteratively repairing flaws until correct plan is found. We feed the LLM-generated plan the initial seed plan

---

for LPG's iterative search. Our hypothesis is that this might put LPG on the right path and reduce the time for it to generate correct plan. is interesting to note the similarities between this LLM+LPG approach, and the approaches used in base-based planning in the past g 17 Here the L.M can be loosely viewed as "retrieving a potentially useful plan case/sketch" out of thin air, which the LPG adapts/corrects.
We utilized the plans that were generated by LLMs in the one-shot natural language prompt configura- tion on all three of our previous domains -Blocksworld, Mystery Blocksworid. and Logistics as the "seed plans" from which LPG would begin its local search for valid plan. For the Blocksworld do- main, both GPT-4 and Instruct-GPT's were evaluated, whereas for the Logistics and Mystery domains only GPT-4 was evaluated. We confirmed that all the plans that were generated by this LLM+LPG combination for both the domains were valid (which is as expected given that the underlying planner, I.GG, is sound). To get an idea of how far the initial L.LM generated plans were from the final correct solutions generated by LPG, we measured the Levenshtein edit distance between them. While the default LPG local search doesn't 't aim to minimize the changes to the suggested plan (there do exist versions of LPG that do this; see (23) the edit distances also give an idea of how partially or approximately correct the original LLM plan is. Along with the edit distance, we also measured the number of search steps that were taken by the LPG to come up with correct plan.
As shown in Table 3 the edit distances across domains are approximately half the length of the seed plans generated by the LLMs, indicating that 50% of the final plan retains the elements of the initial LLM plan. For each problem, we performed two additional plan initializations to serve as baselines: initializing with an empty plan and initializing with random plan of the same length as the plan generated by the LLM for that problem. In the Blocksworld and Logistic Pogisticccdomiiinn domains, we see a significant improvement in search steps over the empty seed plan when GPT-4 is used and an even larger one over the random seed plan. Consistent with our findings in the autonomous mode, the usefulness of this assistance wanes in domains where the relationships between predicates can no longer be inferred from common sense understandings of their names: in the Mystery Blocksworld domain, the LLM only has meager reduction in step size over the random plan and actually uses more steps than the empty plan.
5.2 Verifier-assisted repeated backprompting of LLMs
The interaction between LLM and LPG was uni- directional-with LLM sending a seed plan that LPG aims to repair. One supposed advantage of LLMs is that they can be prompted to improve their solutions. Suppose sound automated verifier that not only checks the plan correctness but also pinpoints faults (in terms of unsatisfied preconditions or delete interactions). Such feedback can be easily con- verted into "backprompt" to the LLM, with the hope that LLM comes up with a better plan. This is what we do with the help of [AL[II an AI planning tool that uses the domain model to validate the correctness of the plans (and point out errors).
Table 4: GPT4 Performance with Backprompting
by VAL (I. Mystery BW had deceptive disguis- ing. LCC Instances correct (within 15 feedbacks);
have access to
A.F.R Avg. feedback rounds for correct instances.
LC
A.E.R
Domain
GPT-4
GPT4
Blocksworld (BW)
41/50 (82%)
3.68
Logisties
35/50 (70%)
3.31
Mystery BW
5/50 (10%)
7.0
While, as we mentioned earlier, there can be thorny "clever hans" issues about humans prompting LLMs, automated verifier mechanically backprompting the LLM doesn't suffer from these.
We tested this setup on a subset of the failed instances in the one-shot natural language prompt configuration using GPT-4, given its larger context window. We set threshold of 15 backprompting Logistics and Mystery BW-with 50 failed
rounds. We tested on three instances from each domain. Table shows the results. We provide the prompt+feedback examples in Appendix A.9. We found that GPT4 is able to come up with correct plans 82% of the Blocksworld instances and 70% of the Logistics one. The average number of backprompting rounds for these
'For the logistics domain, we considered only those instances for which plan could be generated in less than 550 search steps (179 instances).

---

successful cases was 3.68 for BW and 3.31 for Logisties. The performance on the Mystery BW however remained quite puor-suggesting that even with back prompting, GPT4 cannot do well unless it can tease out commonsense patterns for the domain.
In this backprompting configuration, L.M serves as the candidate plan generator while VAL serves as the external sound verifier. While it is tempting to have a self-critiquing architecture with LLM also serving as the verifier, our recent work shows that approach to be of questionable utility as LLMs are no better at verifying plans than they are at generating them [36 34
5.3 LLMs as idea generators for humans-in-the-lon
Along with external planners and verifiers, LLMs may also offer their insights as plan suggestions directly the all, this sort of computer supported cooperative work (CSCW) use case has been the staple of LLM applications. We explored the efficacy of LLMs in assisting human planners through between- subjects user study, structured similarly to the study outlined in Section 4, but with two primary distinctions: (1) The study involved two separate participant groups. The first group received no assistance in devising plans, paralleling the approach in Section 4, while the second group had access to LLM- suggestions. (2) both participant sets were asked offer subjective feedback via the NASA- -LX assessment tool [10), gauging their cognitive load. Additionally, participants from the second group evaluated the correctness of the LLM suggestions presented to them. We utilized the plans generated by GPT-4 to provide plan suggestions.
which might potentially guide the user to the correct plan. After
The study included 49 participants in the unassisted group and 48 in the LLM-assisted group. We evaluated the statistical significance regarding accuracy, time taken, and cognitive load between the groups Our findings revealed statistical significance between the groups across all three aspects 5 Notably, 3 out of 48 participants mistakenly accepted incorrect LLM suggestions, with two submitting these erroneous suggestions as their plans. This shows the potential for automation bias in such methodologies [5). We have provided the details of the user-study in Appendix A.12
6 Conclusion and Future Work
In this paper, we presented critical investigation of the planning abilities of large language models (LLMs). To this end, we evaluated the plan generation abilities of LLMs in two different modes. In the autonomous mode, our results show that even in simple common-sense planning domains where humans could easily come up with plans, LLMs like GPT-3 exhibit a dismal performance. Even though there is an uptick in the performance by the newer GPT-4 in the blocksworld domain, still fails miserably on the mystery blocksworld domain, indicating their inability to reason in an abstract manner. In the heuristic mode, have seen that plans generated by LLMs can help improve the scarch of sound planners like LPG. Further, we showed that using external verifiers, LLMs for better plan. We showed that this indeed
we can point out the errors and helps in common-senss domains. In the supplementary material, we show the prompt examples for all the configurations and the details of the user-studies (Appendix 1.11). From our studies, we see that LLMs as autonomous planners fail miserably, but we also see that the generated plans improve the search when used by an underlying sound planner and that better plans can be obtained by pock-prompting the LLM with feedback from an external verifier.
7
Acknowledgements
This research was supported by ONR grants N00014-18-1-2442, N00014-18-1-2840, N00014- 19-1-2119 19 and N00014-23-1 1-249, AFOSR grant FA9550- 10--118--107,7 DARPA SAIL-ON grant 1911NF-19-2-000 and a JP Morgan AI Faculty Research Grant to Kambhampati. Sreedharan was supported in part by NSF grant 2303019.
'We conducted independent-samples t-tests plan accuracy, formulation time, and task-related cognitive load between the two groups, with a significance threshold set at a=0.05. The t-tests yielded statistic values of -1 -1.21, 0.09, and -0.63, with p-values of 0.22, 0.92, and 0.52 for accuracy, time, and cognitive load, respectively. These results imply that the null hypothesis cannot be rejected for any of the tests, indicating no statistically significant differences in accuracy, time taken, or cognitive load between the two groups
10

---

References
[1] Clever Hans. https://en. https//ww..wiiippddd....g////e/e
[2] Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, et al. Do i can, not as say: Grounding language in robotic affordances. arXiv preprint arXiv:2204.01691, 2022.
[3] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-19011 2020.
[4] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022.
[5] Mary Cummings. Automation bias in intelligent time critical decision support systems. In Decision making in aviation, pages 289-294- Routledge, 2017.
[6] Alfonso Gerevini and Ivan Serina. Lpg: A planner based on local search for planning graphs with action costs. In AIPS, volume 2, pages 281 2002.
[7] Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. Did aristotle use a laptop? a question answering benchmark with implicit reasoning strategies. Transactions of the Association for Computational Linguistics, 9:346-361, 2021.
[8] Malik Ghallab, Dana S. Nau, and Paolo Traverso. Automated Planning and Acting. Cambridge University Press, 2016.
[9] Kristian J. Hammond. CHBF: A model of case-based planning. In Tom Kehler, editor, Proceedings of the 5th National Conference on Artificial Intelligence. Philadelphia, PA, USA, August I 11-15, 1986. Volume I: Science, pages 267-271. Morgan Kaufmann, 1986.
[10] Sandra G Hart and Lowell E Staveland. Development of nasa-tlx (task load index): Results of empirical and theoretical research. Advances in psychology, 52:139-183, 1988.
[11] Richard Howey, Derek Long, and Maria Fox. VAL: Automatic plan validation, continuous effects and mixed initiative planning using PDDL. In 16th IEEE International Conference on Tools with Artificial Intelligence, pages 294-301. IEBE, 2004.
[12] Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents. In International Conference Machine Learning, pages 9118-9144 PMLR, 2022.
[13] Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, et al. Inner monologue: Embodied reasoning through planning with language models. arXiv preprint arXiv:2207.05608 2022.
[14] IPC. International planning competition, 1998.
[15] Liwei Jiang, Jena D. Hwang. Chandrasekhar Bhagavatula, Ronan Le Bras, Maxwell Forbes, Jon Borchardt, Jenny Liang, Oren Etzioni, Maarten Sap, and Yejin Choi. Delphi: Towards Machine Ethics and Norms. ArXiv, abs/21 10.00574, 2021.
[16] Subbarao Kambhampati. AI as (an Ersatz) Natural Science? https///com..cm..rrbbbbgshbu -a-------------tt--aatte
Jun 2022.
[17] Subbarao Kambhampati and James A. Hendler. A validattion-stuucture--aass theory of plan modification and reuse. Artif. Intell., 55(2): 1992.
[18] Subbarao Kambhampati, Karthik Valmeekam, Matthew Marquez, and Lin Guan. On the role of large language models in planning. July 2023. Tutorial presented at the International Conference on Automated Planning and Scheduling (ICAPS), Prague,
llbb. ..b.giie github
No/tuuoorial/CCAP-2000

---

[19] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large Language Models are Zero-Shot Reasoners. arXiv preprint orXiv:2255.11916 2022.
[20] Paul Pu Liang, Chiyu Wu, Louis-Philippe Morency, and Ruslan Salakhutdinov. Towards understanding and mitigating social biases in language models. In International Conference on Machine Learning, pages 6565 6576. PMLR, 2021.
[21] Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. Lim+ p: Empowering large language models with optimal planning proficiency. arXiv preprint arXiv:2304. 11477, 2023.
[22] Drew McDermott, Malik Ghallab, Adele E. Howe, Craig A. Knoblock, Ashwin Ram, Manuela M. Veloso, Daniel S. Weld, and David E. Wilkins. Pddl-the planning domain definition language. 1998.
[23] Tuan Anh Nguyen, Minh Do, Alfonso Emilio Gerevini, Ivan Serina, Biplav Srivastava, and Subbarao Kambhampati. Generating diverse plans to handle unknown and partially known user preferences. Artificial Intelligence, 190:1-31, 2012.
[24] OpenAL. Introducing chatgpt by openai, 2022.
[25] OpenAl. Gpt-4 technical report, 2023.
[26] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. arXiv preprint N..iv:2203.0215:: 2022.
[27] Alec Radford, Karthik Narasimhan, Tim Salimans, and llya Sutskever. Improving language understanding by generative pre-training. 2018
[28] Shreyas Sundara Raman, Vanya Cohen, Eric Rosen, Ifrah Idrees, David Paulius, and Stefanie Tellex. Planning with large language models via corrective re- re-prompting, arXiv preprint arXiv:2211.09935. 2022.
[29] Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge at scale. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 8732-8740, 2020.
[30] Patrick Schramowski, Cigdem Turan, Nico Andersen, Constantin A Rothkopf, and Kristian Kersting, Large pre-trained language models contain human-like biases of what is right and wrong do. Nature Machine Intelligence, 4(3):258-268) 2022.
[31] Big Science. BigScience Large Open-science Open-access Multilingual Language Model. co/ ww//bigccienneelloooooooooo 2022.
[32] Tom Silver, Varun Hariprasad, Reece Shuttleworth, Nishanth Kumar, Tomás Lozano-Pérez. and Leslie Pack Kaelbling. PDDL planning with pretrained large language models. In NeurIPS 2022 Foundation Models for Decision Making Workshop, 2022.
[33] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, al. Beyond the imitation game: Quantifying and extrapolating the capabilities language models. arXiv preprint arXhh:2206.04611 2022.
[34] Kaya Stechly, Matthew Marquez, and Subbarao Kambhampati. Gpt-4 doesn't 't know it's wrong: An analysis of iterative prompting for reasoning problems. arXiv preprint arXiv:2310.12397,
2023.
[35] Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsensegqu: A ques- tion answering challenge targeting commonsense knowledge. arXiv preprint arXiv:1811.00937, 2018.
[36] Karthik Valmeekam, Mathew Marquez, and Subbarao Kambhampati. Can large language models really improve by self-critiquing their own plans? arXiv preprint 10.0v:2310.081 2023.
12

---

[37] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoe Le. and Denny Zhou. Chain of thought prompting elicits reasoning large language models. arXiv preprint arXiv:2201. 1903, 2022.
[38] Yaqi Xie, Chen Yu, Tongyao Zhu, Jinbin Bai, Ze Gong, and Harold Soh. Translating natural language to planning goals with large-language models. arXiv preprint arXiv:2302.05128, 2023.
[39] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, 2023.
[40] Honghua Zhang, Liunian Harold Li, Tao Meng, Kai-Wei Chang, and Guy Van den Broeck. On the paradox of learning to reason from data, arXiv preprint arXiv:2205. 1502, 2022.
13


Reviews:
[{"review_id": "QCg9qyhKcy", "reviewer": "Reviewer_NTC1", "summary": "The paper investigates the (lack of) capabilities of pretrained LLM for solving classical well-known planning benchmarks. They study both the case of fully autonomous LLM without any external feedback and the case of using external tools, for validation feedback or as a seed for improving an external planner. As no fine-tuning is done, the work involves variations of prompts for the task considered. Fig 2 is an excellent summary of the studied tasks including zero and one-shot tasks with the problem in NL or in the original PDDL. GPT-4 is reported as the most powerful LLM, but it is still not satisfactory. Moreover, it's shown to be sensitive to the name description, performing better when using the standard names for well-known benchmarks.\n", "questions": "- Did you try COT with PDDL prompts?\n- Are there any indications of how LLM would perform in problems with shallow plans? If the number of objects or actions is big enough, that might be challenging for classical planners.\n- For the interactive scenario, does it make sense to keep the temperature at 0? Perhaps randomization might help the LLM to recover to deviate from earlier commitments.\n- Did you attempt relaxations with other planning problems? Perhaps it's not \"natural\" in blocks world, but there are other problems where the plans are equivalent to their relaxed versions.\n", "limitations": "A potential limitation of this work is that it might inform about the relevant problems that required planning from LLMs. That's not the scope of the work, so that argument should be left aside. Instead, this work is a systematic investigation of well-known planning benchmarks. Those problems might be close to the distribution of the LLMs.\n\nI miss a discussion on the complexity of the planning tasks per se. There are some simple algorithms for solving block world problems. While logistics can be a complex problem, in the PDDL benchmark solving a single problem is bounded by the complexity of moving one package, a simple problem that as cities are fully connected and it takes one airplane trip for a package to the right city. The relaxed plans discussed in the paper might be related to my question about shallow plans.\n\nOther comments:\n- Fig 2 summarizes well the approaches studied, but that's sometimes not mentioned in the table captions. For instance, Table 1 and 2 should mention that they consider the automated approach.\n- What's I-GPT-3 in Table 3?\n\n", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "\n- Some LLMs such as GPT-4 are being used to obtain plans, so it's important to investigate their capabilities. \n- Classical planning benchmarks are well-understood so offer a solid ground for evaluation.\n- Consider explicitly the case of autonomous mode vs external but automatic feedback.\n- Chain of thought is investigated, answering a question that people familiar with LLMs might have.\n", "weaknesses": "- LLMs are trained in language and human-written code. The evaluation with Randomized Disguising might be less meaningful.\n\t- However, Randomized Disguising is a small part of the work.\n\t- An alternative not explored in the paper is to add human-readable description to the domains. Even though that requires human intervention, it's reasonable to assume the ones providing the domain can also provide a description.\n- The domain-specific translator is not discussed.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank reviewer NTC1 for their valuable comments. We are glad that the reviewer found our work to be important and comprehensive. Below, we provide responses to the concerns raised by the reviewer.\n\n> 1. Are there any indications of how LLM would perform in problems with shallow plans? If the number of objects or actions is big enough, that might be challenging for classical planners.\n\nWe considered this possibility too but found that LLMs don’t necessarily perform well in problems with shallow plans. We would like to point to the graphs in the pdf attached above as part of the global response. These graphs represent the distribution of the correct plans by GPT-4 over optimal plan lengths. From these graphs, we can say that our traditional notions of planning complexity do not hold with LLMs. For an LLM, an easier instance from the perspective of planning complexity is the same as a harder one as it just predicts the next tokens based on their weights and the context. We will update the Appendix with these discussions. \n> 2. Did you attempt relaxations with other planning problems? Perhaps it's not \"natural\" in blocks world, but there are other problems where the plans are equivalent to their relaxed versions.\n\nWe have included the relaxation evaluation for other planning domains as well (Logistics and Mystery Blocksworld) in Appendix A.2.1.\n> 3. Did you try COT with PDDL prompts?\n\nWe haven’t looked into chain of thought experiments with PDDL prompts, but we don’t expect the results to be any better.\n> 4. For the interactive scenario, does it make sense to keep the temperature at 0? Perhaps randomization might help the LLM to recover to deviate from earlier commitments.\n\nWe had kept the temperature to be 0 primarily for the reproducibility of the results. We believe that it is an interesting additional investigation to play around with the temperature and check for performance improvement in the back-prompting method.\n> 5. What's I-GPT-3 in Table 3?\n\nI-GPT3 refers to the Instruct GPT3 model.\n> 6. The domain-specific translator is not discussed.\n\nFor each domain, we perform template-based translation to translate from PDDL to natural language for the natural language prompt configurations. We will include this information in the paper as well.\n> 7. LLMs are trained in language and human-written code. The evaluation with Randomized Disguising might be less meaningful.\n    - However, Randomized Disguising is a small part of the work.\n    - An alternative not explored in the paper is to add human-readable description to the domains. Even though that requires human intervention, it's reasonable to assume the ones providing the domain can also provide a description.\n\nOur point in that domain obfuscation section was to show that LLM’s don’t seem to possess plan generation abilities that can’t be explained by their approximate retrieval abilities. To the extent LLM’s significantly worsen in plan generation when predicate names are changed either to other meaning-bearing words or random words, we believe it lends credence to our hypothesis. \n"}, {"review_id": "45UX1Mrz5P", "reviewer": "Reviewer_JKYr", "summary": "This work evaluates the planning abilities of LLMs in two distinct settings:  (1) As generators of final plans, with or without feedback from a validator, and (2) as generators of seed plans which are then corrected by a standard planner. The evaluations are performed on two commonsense domains for which humans tend to produce high-quality plans:  Blocksworld and Logistics. Four LLMs are tested, including GPT-4, which generates more correct plans than the other models. Still, GPT-4 is found to fail on most of the problems, even with the benefit of one-shot prompting and CoT reasoning. But feedback from a validator (VAL) dramatically boosts the solution rate to 82% in BW and 70% in logistics, after just 3-4 feedback loops on average. In the other setting, the standard planner (LPG) produces correct plans in significantly fewer steps when starting with seed plans generated by GPT-4. ", "questions": "Line 97 says that “our approach of specifying the domain as part of the prompt ensures that the generated plans only use the actions in the domain specification.” How does domain specification provide this guarantee? Can't the LLM still hallucinate nonsense?\n\nLine 191 says:  “We set the temperature for all models to be 1, thereby making them deterministic.” Is this a typo? The appendix correctly identifies zero as the temperature that produces deterministic behavior. \n", "limitations": "No concerns.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This is excellent work, carefully detailed, and clearly presented. It avoids the Clever Hans effect that often arises when humans are involved in evaluations.\n\nThe different evaluation settings are very well chosen, and the results provide valuable guidance as industries work to understand how these LLMs can best be leveraged.\n\nGPT-4 is thoroughly evaluated on all benchmarks. Inclusion of three other LLMs on many of the evaluations provides additional insight.\n", "weaknesses": "Covering more domains beyond these two would be a useful contribution. But two are sufficient to support the conclusions drawn, and they light the way for others to run similar evaluations on additional planning domains.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer JKYr for their valuable comments. We are glad that the reviewer found our work to be detailed and well-presented. Below, we provide responses to the questions raised by the reviewer.\n> Line 97 says that “our approach of specifying the domain as part of the prompt ensures that the generated plans only use the actions in the domain specification.” How does domain specification provide this guarantee? Can't the LLM still hallucinate nonsense?\n\nWe agree with the reviewer that even after specifying the actions in the domain, there is a possibility that LLMs could hallucinate the actions in the generated plan. However, in our experiments, we found that none of the LLMs hallucinates actions for any of the instances. We will update the paper to make this clearer.\n> Line 191 says: “We set the temperature for all models to be 1, thereby making them deterministic.” Is this a typo? The appendix correctly identifies zero as the temperature that produces deterministic behavior.\n\nYes. It is a typo. We will update the paper and fix it.\n"}, {"review_id": "Aj8Z6tH7La", "reviewer": "Reviewer_GZ9T", "summary": "This paper provides a systematic evaluation of the Planning abilities of a class of LLM (GPT series until the latest GPT-4), using standardized planning problems such as those provided in symbolic planning competitions. It analyzes LLM as autonomous planners, but also as heuristic planners providing suggestions to sound planners (heuristic mode). The experiments use a sophisticated prompting mechanism allowing both NL prompting and PDDL prompting. In the heuristic mode, LLM plans can be repaired via a local search planner (LPG), or use a verifier to send feedback to the LLM ('backprompting'). While LLMs score poorly as autonomous planners, they can achieve high scores (70-80%) in heuristic mode on standard benchmarks. \n\nPost-rebuttal comments: the authors have fully answered my questions, in particular providing additional results for another LLM (BLOOM, which appears a very reasonable choice, due to how its ecosystem differs from that of the GPT family). Their commitment to release some of the evaluation resources can only enhance the contribution of this work, which is reflected in my increasing the 'contribution' score in this review. Having also considered other reviewers' comments and the author responses, I remain very positive about this paper and maintain my original score. ", "questions": "Can any of the observations be related to the autoregressive nature of the LLM explored? \nWhat variability in performance would you expect across LLMs (other than GPT versions)?", "limitations": "The conclusion section leaves little space to discuss limitations of the approach. Since CoT prompting has also been explored, it could have been interesting to discuss the proposed coupling of LLM to reasoners via PDDL exchange proposed as part of \"Faithful CoT\" [1].\n\nThe paper rightly identifies the potential role of the natural language semantics of predicates or operators' names in LLM's planning abilities, for which it designs various methods of obfuscation. However, further discussions would be interesting for this phenomenon reported in [2] (\"semantics of the English terms used in the PDDL problems\"), such semantics of PDDL contents having also been proposed as a mechanism for planning model extension and planning repair [3].\n\n[1] Lyu, Q., Havaldar, S., Stein, A., Zhang, L., Rao, D., Wong, E., Apidianaki, M. and Callison-Burch, C., 2023. Faithful chain-of-thought reasoning. arXiv preprint arXiv:2301.13379.\n[2] Silver, T., Hariprasad, V., Shuttleworth, R.S., Kumar, N., Lozano-Pérez, T. and Kaelbling, L.P., 2022, November. PDDL planning with pretrained large language models. In NeurIPS 2022 Foundation Models for Decision Making Workshop. - ref [24] of the paper\n[3] Porteous, J., Ferreira, J.F., Lindsay, A. and Cavazza, M., 2021. Automated narrative planning model extension. Autonomous Agents and Multi-Agent Systems, 35(2), p.19.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper introduces a comprehensive evaluation method for the Planning abilities of LLM, harnessing the full methodology of traditional Planning in terms of benchmarks and reasoners. The choice of the latter is particularly appropriate to the experiments at hand, since it includes both a local planner, well-suited to Plan repair, and a validator that can send feedback by identifying gaps or flaws in the proposed plan under the 'heuristic mode'. It is fairly impressive to have automated a process previously taking place in an interactive form with a human in the loop, which was vulnerable to the Clever Hans effect, also observed in other forms of LLM reasoning [1]. \nThe prompting mechanism is particularly sophisticated without being over-engineered, as their is a clear rationale for supporting each option and a rather elegant design starting with PDDL domains and branching out to generate NL or PDDL prompts. \nIn line with some claims that LLM reasoning tend to reproduce human reasoning to some extent, the choice of planning domains known to be solvable by humans is of high interest, although some of the user/human experiments have been moved back to supplementary material. \nThe paper is highly readable and quite systematic, and has all the elements to become a reference paper on the topic, not least for the results produced and the contrast between autonomous and heuristic modes, the latter avoiding pitfalls of interactivity or CoT limitations. \n\n[1] Shapira, N., Levy, M., Alavi, S.H., Zhou, X., Choi, Y., Goldberg, Y., Sap, M. and Shwartz, V., 2023. Clever hans or neural theory of mind? stress testing social reasoning in large language models. arXiv preprint arXiv:2305.14763.", "weaknesses": "The paper is technically sound with very few weaknesses. Perhaps one issue is the limited number of Planning test domains used in the experiments, especially compared to [Silver et al., 2022] (ref [24] in the paper). This might be in relation to the need to explore human solutions to Planning problems as described in the supplementary material, still it could be worth justifying explicitly. \nAnother potential issue would be concentrating on the GPT family, as LLM may vary in their real-world knowledge depending on their training base.\n\nThe paper has similarities with the following preprint: https://arxiv.org/abs/2302.06706\nThis is not a major issue, either in terms of novelty or in terms of anonymity, since the submission has substantial new material and there is no direct link to the authors of the preprint. Regardless of whether the preprint is from the same authors (or a subset), it would still be appropriate to reference it in the final version of the paper. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank reviewer GZ9T for their detailed feedback. We are glad that the reviewer found our work to be systematic, comprehensive and likely to be a standard. We will incorporate all the reviewer's suggestions such as referencing other relevant papers and additional justifications.  Below, we provide our response to the question raised by the reviewer.\n\n> Can any of the observations be related to the autoregressive nature of the LLM explored? What variability in performance would you expect across LLMs (other than GPT versions)?\n\nBeyond the general \"approximate retrieval\" capabilities of the LLMs that can be attributed at some level to their auto-regressive n-grams-on-steroids nature, we did not see any other planning-specific insights. The n-gram auto-regressive nature does seem to help in the context of prompts--especially for the back-prompting techniques--in as much as it seems to get LLMs to generate the correct plan with the back-prompt augmented context. There is however no reason to believe that this is anything more than the usual context-sensitive completion capabilities. \n\nRegarding the variability of capabilities across LLMs, we believe that the results of GPT-4 could act as an upper bound on the performance of LLMs in planning as they currently are state-of-the-art in a lot of natural language processing tasks. We have also done preliminary experiments on BLOOM (an open-source large language model) and the results indicate bad plan generation capabilities. We have included the results in the PDF attached as part of the global response. We would also like to point out that we plan to release the required resources and code for the community to evaluate other LLMs of interest.\n"}, {"review_id": "x4siB4Zyo1", "reviewer": "Reviewer_Y3FL", "summary": "This paper conducts a systematic study by generating a suite of instances on domains similar to the ones employed in the International Planning Competition and evaluate LLMs in two distinct modes: autonomous and heuristic. The experiments show that LLMs' ability to generate executable plans autonomously is rather limited, while the results in the heuristic mode show more promise.", "questions": "Answer questions in weakness section.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper is well-written and easy to understand.\n2. The paper provides a detailed investigation of GPT's planning abilities in different domains and presents some interesting findings.", "weaknesses": "1. Some of the conclusions presented in the paper, such as re-planning makes better performance, have already been widely applied in robotics task and motion planning applications, which is not considered novel. The community has developed a range of interesting algorithms to enhance the planning capabilities of LLM, including re-plan and generating feasible plans [1,2,3,4,5]. While the authors ignores these efforts.\n2. The author's investigation of GPT's planning abilities in certain domains overlooks the fact that GPT's greatest strength lies in its zero-shot or few-shot capabilities across different domains, without the need for pre-defined action spaces. Additionally, the metrics used to evaluate GPT are not fair to the model itself. At least human evaluation should be introduced for a more comprehensive assessment. More detailed experiments and metrics can be found in [zero-shot].\n3. For a survey paper, it is not sufficient to only consider OpenAI's GPT-level models. Open-source models like LLaMA and Vicuna should also be included in the analysis to better understand if there are fundamental differences in planning capabilities across different levels of language models.\n4. More demonstrations in the prompts seem to effectively improve planning performance. The author only conducted zero-shot and one-shot experiments, which is insufficient. A ablation experiment to explore the importance of the \"how much-shot\" factor would be valuable to the community.\n5. Some relevant papers are not cited, which are listed in the references.\nReferences:   \n[1] Inner Monologue: Embodied reasoning through planning with language models    \n[2] Describe, Explain, Plan and Select: Interactive Planning with Large Language Models Enables Open-World Multi-Task Agents   \n[3] ReAct: Synergizing Reasoning and Acting in Language Models    \n[4] Reflexion: Language Agents with Verbal Reinforcement Learning     \n[5] Text2Motion: From Natural Language Instructions to Feasible Plans   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank reviewer Y3FL for their thoughtful feedback. We are glad that the reviewer found our work to be well-written, detailed and interesting. We will incorporate all the reviewer's suggestions such as citing other relevant papers.  Below, we provide responses to some of the concerns raised by the reviewer.\n\n> 1. Some of the conclusions presented in the paper, such as re-planning makes better performance, have already been widely applied in robotics task and motion planning applications, which is not considered novel. \n\nWe thank the reviewer for bringing up these relevant papers. We will make sure to cite them. Firstly, we would like to differentiate our backprompting technique from the scenarios that works like [3,4] describe. Our backprompting method provides only verification feedback that can be deduced from the original problem specification. The methods in the current works do not focus on providing verification for an end-to-end plan but instead, provide step-by-step environmental feedback that can inform later steps. This distinction is important, particularly in non-ergodic domains where irreversible actions could be executed. Additionally, the current works provide search guidance information as part of their prompts and this information is created by humans which could potentially lead to phenomena like the Clever Hans effect [1].\n\nFurther, in examining the interaction resolution for the domains presented in these works, there appear to be some simplifications. In [5], the instructions seem to provide a substantial amount of the high-level plan, which could potentially reduce the LLM to a semantic parser. Similarly, in [2], the block stacking tasks often present scenarios where n-1 blocks are already stacked, only requiring the agent to stack the nth block. We believe that these efforts do not shed light on the plan generation capabilities of the LLMs themselves as both our evaluations in autonomous and heuristic modes do.\n\n[1] Clever hans or neural theory of mind? stress testing social reasoning in large language models. arXiv preprint arXiv:2305.14763.\n\n[2] Inner Monologue: Embodied reasoning through planning with language models\n\n[3] ReAct: Synergizing Reasoning and Acting in Language Models\n\n[4] Reflexion: Language Agents with Verbal Reinforcement Learning\n\n[5] Text2Motion: From Natural Language Instructions to Feasible Plans\n\n> 2. The author's investigation of GPT's planning abilities in certain domains overlooks the fact that GPT's greatest strength lies in its zero-shot or few-shot capabilities across different domains, without the need for pre-defined action spaces. Additionally, the metrics used to evaluate GPT are not fair to the model itself. At least human evaluation should be introduced for a more comprehensive assessment. \n\nAs we discuss in Section 2 (lines 110-126), we readily concede that the approximate omniscience of LLMs allow them to retrieve relevant planning knowledge in many cases. The main point of our paper is that doing correct planning requires both having planning knowledge and dealing with the situation specific interaction resolution issues to ensure the correctness of the plan. Our paper shows both that LLMs can’t do the second part, and that we can gainfully leverage LLM’s approximate retrieval capabilities  in the context of external planners/verifiers to provide better planning capabilities. In other words, we are saying that LLM’s can be useful even without us erroneously ascribing them planning capabilities they don’t have. \n\nIn terms of metrics, since we are talking about plan correctness, and the model is known, it makes sense to consider the categorical correctness of the plan. Human evaluations don’t provide that as humans may themselves be careless verifiers and/or suffer from automation bias (as we discuss in Appendix A.10)\n\n> 3. For a survey paper, it is not sufficient to only consider OpenAI's GPT-level models. \n\nWe believe our work is not a survey paper but rather a critical examination of the planning capabilities of state-of-the-art LLMs. GPT-4 currently is the state-of-the-art among the current LLMs in natural language processing tasks. We believe that the results of GPT-4 on our planning tasks could act as an upper bound on the performance of LLMs in planning. Further, the other GPT models provide us with an approximate understanding of the planning capabilities across varying sizes of the model and fine-tuning methods (instruction-based or chat-based). We have also done preliminary experiments on BLOOM (an open-source large language model) and the results indicate bad plan generation capabilities. We have included the results in the PDF attached as part of the global response. We would also like to point out that we plan to release the required resources and code for the community to evaluate other LLMs of interest.\n\n> 4. More demonstrations in the prompts seem to effectively improve planning performance. The author only conducted zero-shot and one-shot experiments, which is insufficient. An ablation experiment to explore the importance of the \"how much-shot\" factor would be valuable to the community.\n\nAs discussed above, our intent is not to dismiss LLM’s relevance for planning tasks, but to point out that they can be useful without us having to bend over backwards to ascribe them autonomous planning capabilities they don’t have. We won’t argue that we can’t “customize” LLM’s either by giving a large number of examples in-context or during fine-tuning–but that only increases the chance that the plan generation becomes approximate retrieval–and doesn’t prove much about the inherent plan generation capabilities of LLMs. On the whole, we believe that we have done a fair evaluation of the autonomous planning capabilities of the LLMs, giving them as much benefit of doubt as possible."}]

Author rebuttal:
We thank the reviewers for their thoughtful feedback. We have provided our responses separately for each reviewer. We have attached a PDF containing the images and tables which we refer to in the individual responses.

Meta-review: The paper investigates the ability of language models to plan on a set of commonsense planning tasks. It finds that though they are often unsuccessful at planning on their own, their use as a heuristic to guide search is more promising. 

Overall the reviewers found the paper interesting, useful, and timely. They do note however the limited number of domains, which for the generality of LLMs would be quite useful to add. I agree with the reviewers (on both accounts) and recommend acceptance. 

A few ablations such as CoT would improve the paper and new domains. The authors should consider including numbers for an open source model as well, though their point that GPT-4 is SoTA is well taken, but this would be useful for reproducibility (as GPT-4 is not a fixed, permanent checkpoint) and for those that build on the work.
Decision: Accept (spotlight)