# Exploring and Benchmarking the
Planning Capabilities of Large Language Models

Bernd Bohnet Azade Nova11footnotemark: 1 Aaron T Parisi Kevin Swersky Katayoon
Goshvadi Hanjun DaiDale SchuurmansNoah Fiedel Hanie Sedghi Google DeepMind
Equal contribution

###### Abstract

We seek to elevate the planning capabilities of Large Language Models
(LLMs)investigating four main directions. First, we construct a comprehensive
benchmark suite encompassing both classical planning domains and natural
language scenarios. This suite includes algorithms to generate instances with
varying levels of difficulty, allowing for rigorous and systematic evaluation
of LLM performance. Second, we investigate the use of in-context learning
(ICL) to enhance LLM planning, exploring the direct relationship between
increased context length and improved planning performance. Third, we
demonstrate the positive impact of fine-tuning LLMs on optimal planning paths,
as well as the effectiveness of incorporating model-driven search procedures.
Finally, we investigate the performance of the proposed methods in out-of-
distribution scenarios, assessing the ability to generalize to novel and
unseen planning challenges.

Exploring and Benchmarking the
Planning Capabilities of Large Language Models

Bernd Bohnet††thanks: Equal contribution Azade Nova11footnotemark: 1 Aaron T
Parisi Kevin Swersky Katayoon Goshvadi

Hanjun Dai Dale Schuurmans Noah Fiedel Hanie Sedghi

Google DeepMind

##  1 Introduction

Intelligent agents require the ability to plan— to proactively chart a course
of action to achieve their objectives. This capacity for strategic foresight
is fundamental to intelligent behavior (Russell and Norvig, 2016).

While classical search algorithms have long been the cornerstone of planning
studies, machine learning techniques, particularly Monte-Carlo Tree Search
(MCTS) and reinforcement learning, have emerged as useful additions,
significantly expanding the capabilities of modern planning systems.

    #  Planning Domain Definition Language
    (define (problem BW-rand-3)
    (:domain blocksworld-4ops)
    (:objects A B C)
      (:init
      (handempty)
      (ontable C) (clear C)
      (on A B) (clear A))
    (:goal (and (on C B) (on A C))))

    # Planning: LLM generates a PDDL plan.
    (unstack A B) (put-down A)
    (pick-up C) (stack C B)
    (pick-up A) (stack A C)

    # Problem in Natural Language
    The initial state:
    The hand is empty.
    C is on the table. C is clear.
    A is on B. A is clear.
    The goal is: C is on B. A is on C.

    # Planning: LLM generates natural language plan
    Unstack A from B. Putdown A on the table.
    Pickup C from the table. Stack C on B.
    Pickup A from the table. Stack A on C.

Figure 1: Blocksworld planning in PDDL and natural language.

With the advent of powerful large language models (LLMs), there are new
opportunities to both revisit classical planning problems, and to further
explore new problems through natural language specification that reflects the
ambiguity and uncertainty of real-world domains. Planning capability is
important for many tasks such as meeting scheduling and trip planning.
Moreover, it is a crucial skill for assisting users with task planning, text
planning, or performing tasks in the real world. Research is already underway
to leverage the commonsense knowledge of LLMs in real-world tasks (Huang et
al., 2022; Singh et al., 2023; Ding et al., 2023) and to generate plans
(Valmeekam et al., 2023; Hao et al., 2023; Guan et al., 2024). This research
has shed some light on LLMs’ struggle with planning tasks. They may produce
ineffective or even incorrect plans, even in straightforward scenarios.

This paper focuses on improving the planning capability of LLM systems through
focusing on both instructing the model and enhancing the search strategy
required for planning. We provide a novel exploration of in-context
learning(ICL), utilizing the emerging paradigm of many-shot learning with long
context. We compare this approach with traditional fine-tuning methods and
investigate both in-domain and out-of-domain generalization.

Specifically, we explore two distinct planning representations: the formal
Planning Domain Definition Language (PDDL) McDermott et al. (1998), which
provides a standardized representation for classical planning problems and
allows for rigorous plan validation; and natural language, which offers a more
flexible and intuitive representation better reflecting real-world scenarios.
For both scenarios, we provide a code for generating as many instances with a
degree of difficulty of choice. We also provide a mapping method for
translating PDDL benchmarks to natural language and measure the performance of
the generated benchmarks. The generated planning tasks are scalable and can
grow to examine and assist stronger models.

We observe that (1) carefully instructing the model using ICL leads to a
significant boost in planning performance, which can be further improved by
using a many-shot approach in long context. (2) finetuning with the optimal
plan can lead to near-perfect accuracy for models that are much smaller than
SOTA LLMs. (3) The proposed plans show generalization to unseen instances of
the environment: instances with similar complexity have the same accuracy, (4)
For ICL, teaching easier instances leads to better performance on hard
instances compared to teaching hard instances. (4) Finetuning leads to better
performance for both in-domain and out-of-domain scenarios, even with a much
smaller model, compared to ICL with long-context on the SOTA LLM models. (5)
Integrating the model with a search procedure such as MCTS can help earlier
versions and smaller models perform closer to SoTA foundational models.

Reasoning and planning are critical cognitive skills in humans. These
abilities can be articulated through natural language; reasoning has been
explored in natural language processing (NLP) Bauer and Bansal (2018); Ning et
al. (2020); Yu et al. (2020), whereas planning has not yet been very much
represented within the NLP research community except in the context of text
planning Reiter and Dale (2000); Gatt and Krahmer (2018).

In summary, our primary contributions are:

[1] We provide a scalable benchmark suite in both PDDL and natural language to
measure planning capability of LLMs.

[2] We teach planning capability to LLMs using both in-context learning (and
recent many-shot paradigm) and fine-tuning strategies as well as investigate
the effect of better search mechanisms.

[3] We investigate plan generalization capability of our methods.

The rest of the paper is organized as follows. We describe the benchmark suite
and approaches to enhance LLMs planning capability in Section 2; Describe
experiments setting and discuss the results in Section 3 and conclude in
Section 4. The limitations and ethics statements are in Section 5, 6
respectively.

###  1.1 Related Work

There has been some investigations of planning capabilities of LLMs stating
that these models struggle with solving planning tasks (Hao et al., 2023;
Valmeekam et al., 2023, 2024), In contrast, we show that LLMs, once instructed
well, are capable of solving such tasks and one can reach close to accuracy of
one for some scenarios. We run experiments on the same BlocksWorld benchmark,
and on more difficult cases (more number of blocks) and similar to these works
we use verifiers to compute accuracy. See Section 3.4 for details.

Xie et al. (2024) proposed a TravelPlanner benchmark and showed GPT4-Turbo can
solve some of the benchmark tasks with a success rate of $0.6\%$. The
TripPlanner benchmark used in our work has two main differences, one is that
it is not an agent environment and rather a natural language benchmark, the
other is that it has unique answers due to carefully designed constraints.
Therefore, we chose the latter for our experiments.

Stechly et al. (2024) suggested that LLMs are not capable of generalizing
their plans on BlocksWorld if one uses chain-of-thought (CoT) (Wei et al.,
2022). In this work we show positive results in terms of generalization
performance.

There is another line of work that uses a hybrid approach, meaning that they
either use an external tool to solve the planning tasks (Kambhampati et al.,
2024; Hirsch et al., 2024), or reformulate the problem as another task such as
SMT (Hao et al., 2024) and use an external tool to solve it. Lehnert et al.
(2024) use $A^{*}$ as search mechanism and a specific transformer architecture
to achieve planning capability for that specific architecture. We differ from
this line of work in that we focus on teaching LLM itself to perform the
planning task.

In addition to standard few-shot prompting, we also make use of search
procedures tree-of-thought (ToT) (Yao et al., 2023) and Monte-Carlo Tree
Search (MCTS) (Hao et al., 2023). Each of these expand on conventional chain-
of-thought reasoning. We demonstrate that these methods can considerably
improve an LLMs planning capabilities, beyond ICL and intrinsic chain-of-
thought.

##  2 Planning Datasets and Methods

To evaluate the planning capabilities of large language models (LLMs), we
constructed a benchmark suite for planning. On these benchmarks, we assessed
LLM performance using In-Context Learning (ICL), Supervised Fine-Tuning (SFT),
and Search-based Planning.

PDDL (Planning Domain Definition Language):  PDDL McDermott et al. (1998) is a
standardized language used in artificial intelligence for representing
planning problems. PDDL provides a way to describe the initial state of the
world, the desired goals, the actions that can be taken, and the effects of
those actions. PDDL has two main components (1) Domain: Describes the general
characteristics of the planning problem, including the types of objects,
actions, and predicates (conditions that can be true or false). (2) Problem:
Defines a specific instance of the planning problem within the domain,
including the initial state of the world and the goals to be achieved.

We selected three datasets that use PDDL, constructed subsets of them, and
additionally mapped these datasets to natural language for an additional
evaluation task. Additionally, we selected two native natural language
datasets, containing Trips-Planning and Calendar-Scheduling tasks Zheng et al.
(2024). For the PDDL-based datasets, we selected BlocksWorld, Logistics, and
Mini-Grid. We translated the PDDL problem descriptions of all these datasets
into natural language to compare the performance of problems provided as
formal and informal problem description.

In Section 2.1, we describe the creation of the PDDL datasets and the
generation of additional natural language tasks from these PDDL problem
definitions. Note that our generation code can be used to generate any number
of instances from these benchmarks with arbitrary complexity (through the
addition of additional constraints or elements). For all these PDDL-based
tasks, we calculate accuracy of the plan generated by LLM using a verifier
tool (Fox and Long, ). In Section 2.2, we describe the native Natural Language
Benchmarks.

###  2.1 Parallel PDDL and Natural Language Benchmarks

The creation of all PDDL datasets follows a three-step procedure. (1)
Initially, the process involves the creation of an initial state and a goal
(target state). (2) Subsequently, the initial state and goal are utilized to
formulate a problem in PDDL. (3) Finally, the problem is solved using a
classic planner Fast-Downward111https://github.com/aibasel/downward.

This procedure is iterated with increasingly difficult configurations for a
selected number of problems. The result of this procedure are datasets that
comprise a set of problems in PDDL and their solutions, i.e., the plans to
solve the problems.

Importantly, this procedure enables us to create datasets with increasingly
difficult problems, which are appropriate for assessing the ability to plan
using different methods, such as in-context learning versus Supervised Fine-
Tuning. Moreover, we can scale the dataset generation and create as many
instances as needed for different investigations. We provide the details of
our benchmark suite below.

We perform planning for Blocksworld, Logistics and Minigrid both for PDDL and
Natural Language. For the mapping to natural language, we use a slot filling
technique which maps each predicate of the initialization and goal as well the
action to sentences (Appendix B.2). For the verification of the plans, we use
regular expressions to map the plan in Natural Language back to PDDL.

#### BlocksWorld

BlocksWorld is a standard planning problem from International Planning
Conference (IPC)-2000 222https://github.com/potassco/pddl-
instances/tree/master/ipc-2000. This domain consists of a set of blocks, a
table and a robot hand, where the goal is to move from one block configuration
to another.

Algorithm 1 Create BlocksWorld Dataset

function CreateDatasetBW($num\\_blocks$, $n$)

$dataset\leftarrow[]$ $\triangleright$ Initialize an empty list

for $problem\\_id\leftarrow 1$ to $n$ do

$b\leftarrow$ RandomUniform($3$, $num\\_blocks$)

$initStacks\leftarrow$ CreateStacks($b$)

$goalStacks\leftarrow$ CreateStacks($b$)

if $initStacks==goalStacks$ then

continue $\triangleright$ Skip equal stacks.

end if

$problem\leftarrow$CreatePro($initStacks,goalStacks$)

$plan\leftarrow$FastDownward($problem,domain$)

$dataset\leftarrow dataset+[(problem,plan)]$

end for

return $dataset$

end function

In the creation of the BlocksWorld dataset as outlined in Algorithm 1, the key
parameters include the maximum number of blocks $num\\_blocks$ and the
quantity of examples $n$ to be generated for each block count. Here, the
maximum number of blocks is a number greater than 3. As we use uniform
sampling, this results in a linear increase in the number of more complex
examples. However, it’s important to note that as the number of blocks
increases, the simpler combinations are exhausted since all possible
combinations might be included. The methods CreateStacks generates random
stacks of blocks, iteratively sampling from the available blocks to determine
stack heights until all blocks are utilized. The method CreatePro denotes a
simple method to translate the block configuration into PDDL which is python
reimplementation of functionality in 4ops-Blockworld
code}333https://github.com/AI-Planning/pddl-
generators/tree/main/blocksworld/4ops.

We generate a datase for 3 to 7 blocks. We produced 28k unique BlocksWorld
samples. From these, 25.5k were randomly selected for the training set and
2,500 for the validation set. We describe the mapping via templates from PDDL
to natural language in the appendix B.2.

#### Logistics

Logistics is an AI planning problem from IPC-1998
444https://github.com/potassco/pddl-instances/tree/master/ipc-1998 expressed
in PDDL that involves arranging the delivery of packages to their destinations
using trucks within cities and airplanes between cities. The aim is to
optimize transportation modes under constraints such as vehicle capacities and
locations, showcasing model’s ability to manage multi-step logistics
efficiently.

#### Mini-Grid

Mini-Grid is a task from Artificial Intelligence Planning Systems (AIPS)-1998
555https://github.com/AI-Planning/pddl-generators/tree/main/minigrid, also
expressed in PDDL. We create various floorplans with rooms containing random
configurations of key shapes. The goal then is for a robot to navigate from an
initial position to a designated goal cell.

###  2.2 Native Natural Language Planning Benchmarks

In addition to the PDDL-derived planning tasks, we also rely on several
natural-language benchmarks.

#### Trip Planning

Trip Planning is a task from NaturalPlan (Zheng et al., 2024) benchmark
focusing on planning a trip itinerary under given constraints. The goal of the
task is to find an itinerary satisfying constraints such as the order of
visiting N cities. It includes enough constraints for each instance such that
there is only one solution to the task, which makes the evaluation of the
predictions straightforward.

#### Calendar Scheduling

Calendar Scheduling from the NaturalPlan (Zheng et al., 2024) benchmark
represents the task of scheduling a meeting of either 30 minutes or an hour
among up to 7 attendees. The attendees may have a busy schedule or a light
schedule with less than half of the working hours spent in meetings.

###  2.3 Methods

#### In-Context Learning

For in-context learning (ICL) (Brown et al., 2020), we adhere to the standard
procedure, employing a prompt containing several examples for the task. Each
example comprises a planning problem statement and its corresponding solution,
referred to as a shot. Following the examples, the test problem is added
without the solution which completes the prompt. Subsequently, a LLM receives
this prompt and is expected to generate a plan following the format and logic
of the examples in the prompt. See Appendix A for examples of prompts.

In this work, we explore potential gains by moving beyond few-shot learning
and utilizing a large number of shots (Agarwal et al., 2024).

#### Planning with Search Procedures

In addition to standard few-shot in-context methods, we explore two natural-
language search strategies: Monte Carlo Tree Search (MCTS)(Hao et al., 2023),
and Tree-of-Thought (ToT). (Yao et al., 2023) proposed Tree-of-Thought,
expanding the notion of chain-of-thought (CoT) (Wei et al., 2022) reasoning by
considering a chain-of-thought a single path through a tree constructed by
branching at each step of the search procedure. For reasoning tasks each node
represents the current state of the reasoning chain, which can be expanded by
branching children off of the node in question.

Building on tree-of-thought, (Hao et al., 2023) modified the Monte Carlo Tree
Search (MCTS) procedure described in previous works (Silver et al. (2017)) to
work with LLMs in place of the policy and world models. Similar to ToT, the
MCTS procedure at each node represents a specific state of the reasoning
chain. However, it has two key differences from the ToT procedure: 1) it uses
a function of the Q-value to drive exploration and exploitation based on node
selection, and 2) beyond the ’state’ of the reasoning chain, an additional
’world state’ is maintained, allowing tasks which interact with an environment
to approximate and reason about the environment explicitly in the reasoning
tree.

#### Supervised Fine-Tuning

Supervised fine tuning (SFT) (Ouyang et al., 2022) has proved to be an
effective method for teaching LLMs various capabilities. We investigate impact
of SFT on teaching planning to LLMs. We use the Fast-Downward classical
planner to generate the optimal plan and investigate the effect of fine tuning
on that on the planning performance for two different benchmarks with
different levels of difficulty.

#### Plan generalization

As for all machine learning capabilities, it is desired for models to
generalize to unseen inputs. Therefore, we investigate plan generalization
capabilities of LLMs. Plan generalization has three main categories: (1)
Generalize to unseen instances of the same environment (2) Generalize to
renaming of actions and objects (3) Generalize to unseen plan environments.
Here, we focus on the first category which sits at the core of the desired
capability. This is equivalent to Out of distribution (OOD) scenarios in
machine learning. For this investigation we look into effect of both SFT as
well as ICL on the generalization performance for two benchmarks.

##  3 Experiments

As mentioned earlier, without intervention LLMs often struggle with even
simple planning tasks. They often lack the information on how to structure
their plan constructively, and with respect to constraints in the task. In
this section we present our experimental results for improving LLMs planning
capability; and investigate plan generalization (i.e., the ability to
generalize to unseen instances) in several scenarios.

For PDDL experiments, we measure accuracy of the generated plan with a
verifier. For natural language experiments we rely on either recasting the
task to PDDL and verifying with a verifier (Fox and Long, ), or extracting the
answer and comparing it to expected results (Zheng et al., 2024).

In all experiments, GPT-4 refers to GPT-4 Turbo and we omit "Turbo" for space
constraints.

###  3.1 In-context learning

(a) BlocksWorld - Natural Language

(b) Logistics - Natural Language.

(c) Mini-Grid - Natural Language.

(d) BlocksWorld - PDDL.

(e) Logistics - PDDL.

(f) Mini-Grid - PDDL.

Figure 2: PDDL Planning and Natural Language Planning with few-shots. Natural
language text are generated from formal PDDL problem definitions.

In this section, we report performance of models on both classical planning
benchmarks expressed in the standard Planning Domain Definition Language
(PDDL) as well as in natural language. See Appendix A for examples of prompts
for all planning tasks considered in this section.

We evaluate the planning capability of the model as we add more examples
(“shots") into the context, inspired by the success of many-shot learning
across a large number of tasks (Agarwal et al., 2024). The challenge of “in-
context planning" involves understanding a specific task and problem through a
limited number of examples. Additionally, it requires the models to produce a
solution without checking each planning step to confirm if a proposed move is
correct. The model has to create a plan in a single inference step, keeping
’in mind’ all the constraints the task imposes.

Figure 2 shows the in-context learning performance on classical planning and
natural language benchmarks as we vary the number of shots. Overall, we notice
that for natural language and PDDL scenarios, models have similar trends in
terms of planning accuracy as we increase the number of shots. Moreover,
different models are impacted differently as we provide additional number of
shots, e.g., Gemini 1.5 Pro outperforms other models indicating that the model
not only can plan better with a fewer number of examples/shots, it can also
make effective use of additional and longer context. Gemini 1.5 Flash -a
smaller, faster and more efficient model than Gemini 1.5 Pro is still
outperformed by Gemini 1.5 Pro but occasionally matching GPT-4 Turbo
performance. The details of results for each tasks are provided below.

#### BlocksWorld

We generated BlocksWorld problem instances of 3 to 7 blocks for in-context
learning with the method described in Appendix B.1.

Figure 2(a), 2(d) show the performance of Gemini 1.5 models on this benchmark
as we increase the number of few-shot examples. We note that as we increase
the number of shots GPT-4 Turbo’s performance increases while Gemini 1.5 Pro’s
performance saturates or degrades as we go beyond 40 shots. The 1-shot
planning capability of Gemini 1.5 Pro and Gemini 1.5 Flash reaches reaches 35%
and 26%, while GPT-4 Turbo performance is close to zero. Moreover the 40-shots
planning capability of Gemini 1.5 Pro reaches 48% range which performs better
than the best (200-shots) performance of GPT-4 Turbo, which peaks at 43%.

(a) Trip Planning.

(b) Calendar Scheduling.

Figure 3: Natural Language Planning with few-shots using native natural
language datasets.

#### Logistics

The planning capabilities of GPT-4 and Gemini 1.5 models on the Logistics
benchmark are shown in Figure 2(e) for PDDL and in Figure 2(b) for Natural
Language. The 1-shot planning capability of Gemini 1.5 Pro reaches 43% for
PDDL and for Natural Language 48%. Moreover for Gemini 1.5 Pro increasing the
context consistently lead to better results, indicating that the model can
make effective use of additional contexts. For Gemini 1.5 Flash and GPT-4
Turbo, the performance drops slight for PDDL and Natural Language.

#### Mini-Grid

Figure 2(f) and Figure 2(c) show the performance of GPT-4 Turbo and Gemini
models as we increase the number of few-shot examples for PDDL and Natural
Language, respectively. The Gemini models perform comparably for both PDDL and
Natural Language, although GPT-4 Turbo appears to perform slightly better with
Natural Language. Increasing the number of few-shot examples leads to better
performance for all models. With 400 shots, specify model, Gemini 1.5 Pro
reached 77% accuracy.

#### Trip Planning and Calendar Scheduling

Figure 3(a) shows the performance on Trip planning, Calendar Scheduling as we
increase the number of few-shot examples, respectively. The 1-shot performance
of the GPT-4 Turbo model seems to be better than the Gemini 1.5 Pro. We
observe that, in both benchmarks, for both GPT-4 and Gemini 1.5 Flash the
performance first increases with the number of shots and after a certain
point, having more shots leads to worse model performance. However, for Gemini
1.5 Pro performance improves as the number of shot increases. Therefore,
Gemini 1.5 Pro seems to be making more efficient use of additional shots
compared to the other two. On the other hand GPT-4 performs better in one shot
scenario compared to the other two models for Trip Planning, while Gemini 1.5
Pro has a higher accuracy in the 1-shot setting..

Overall, we observe that the trend of accuracy vs number of shots depends both
on the model and on the benchmark.

#### Effect of better search strategies

Additionally, in Figure 4 we provide experimental evidence that methods such
as MCTS and ToT can augment even Gemini 1.0 M GeminiTeam et al. (2024a) (which
preceded Gemini 1.5 GeminiTeam et al. (2024b)), to be competitive with GPT-4
at smaller few-shot context lengths. Without these search procedures, Gemini
1.0 M fails to perform these planning tasks at any number of few-shot
examples. Additional details and parameters for these search methods are
included in Appendix B.3.

Figure 4: Calendar Scheduling task with search procedures (ToT and MCTS). We
use Gemini 1.0 M to perform these procedures, and compare with GPT-4.

###  3.2 Supervised Fine Tuning (SFT)

In this section, we investigate the effect of Supervised Fine Tuning (SFT)
with optimal plan on planning capability of LLMs. We specifically ran
experiments on Gemini 1.0 S (GeminiTeam et al., 2024a) and investigate the
effect of fine tuning on that on the planning performance for two different
benchmarks with different levels of difficulty, namely, we look into 5
scenarios: BlocksWorld with 3-7 blocks, BlocksWorld with 8-9 blocks and
BlocksWorld with 8-20 blocks, Logistics with 1-2 packets, Logistics with 3-5
packets. The data size and splits are documented in Appendix B.4.

The results are shown in Table 1. We observe that SFT leads to very high
accuracy for some instances of both datasets and outperforms long context in-
context learning. Moreover, the performance drops as the planning problem
becomes more difficult.

Model | Gemini 1.0 S
---|---
BlocksWorld(3-7) | 96.26
BlocksWorld(8-9) | 92.6
BlocksWorld(8-20) | 67.00
Logistics(1-2) | 99.8
Logistics(3-5) | 63.4
Table 1: Impact of fine-tuning with optimal plan on accuracy measured by verifier (in $\%$), for BlocksWorld: instance of 3-7, 8-9 and 8-20 blocks, and for Logistics: instances of 1-2 and 3-5 packets. Finetune data | Eval data | Accuracy
---|---|---
BW(3-7) | BW(3-7) | 96.26
BW(3-7) | BW(8-20) | 34.20
BW(8-20) | BW(3-7) | 98.27
BW(8-20) | BW(8-20) | 67.00
Table 2: Plan generalization analysis for instances of BlocksWorld of
different number of blocks in SFT scenarios, for Gemini 1.0 S. Accuracy is in
$\%$.

###  3.3 Plan generalization

Here we investigate ability of LLMs to generalize their plans to unseen cases
of different difficulty. For these experiments, we consider BlocksWorld and
Logistics benchmarks with various difficulty levels used in Section 3.2. We
look into performance of both SFT and ICL approaches. Tables 2 shows
generalization performance for BlocksWorld in SFT setting for BlocksWorld 3-7,
8-20 split and Table 3 considers generalization between BlocksWorld 3-7 and
8-9 blocks split for both SFT and ICL with different models and number of
shots. Table 4 depicts plan generalization for Logistics benchmark for splits
of 1-2 and 3-5 packets.

Our analysis reveals several key findings: (1) Superiority of SFT: SFT
consistently outperforms ICL across both benchmarks, even when utilizing a
smaller model for SFT. This suggests that SFT’s explicit training process,
focused on the specific task, leads to more effective learning and
generalization. (2) In most ICL scenarios, training the model on easier
instances first results in improved performance on harder examples, e.g., see
Table 3, rows 1-4 and 6. (3) Limitations of hard example training: Contrary to
some expectations, training the model exclusively on hard examples does not
always translate to better performance on easier ones (for example, see Table
3 rows 2, 4-6). This suggests that a balanced approach, incorporating both
easy and hard examples, might be optimal for achieving well-rounded
performance.

Model Name | Train data
---|---
3-7 | 8-9
Eval data
3-7 / 8-9 |  3-7 / 8-9
G 1.5 Flash (1 Shot) | 26.4 / 13.7 | 32.9 / 12.3
G 1.5 Flash (70 Shot) | 35.7 / 23.3 | 27.6 / 11.0
G 1.5 Pro (1 Shot) | 40.0 / 25.6 | 39.0 / 20.3
G 1.5 Pro (70 Shot) | 46.3 / 36.3 | 38.3 / 18.4
G 1.0 S (1 Shot) | 3.68 / 0.331 | 2.99 / 1.35
G 1.0 S (70 Shot) | 12.4 / 2.33 | 3.99 / 1.68
G 1.0 S (SFT) | 96.3 / 81.6 | 96.0 / 92.6
Table 3: Testing BlocksWorld (PDDL representation) accuracy results by model on OOD tasks. For training we use in-context learning or fine-tuning. We consider a split with problems of size 3-7 blocks and 8-9 blocks. We use the shorthand G for Gemini. Model Name | Train data
---|---
1-2 | 3-5
Eval data
1-2 / 3-5 | 1-2 / 3-5
G 1.5 Flash (1 Shot) | 18.3 / 1.35 | 26.7 / 1.00
G 1.5 Flash (30 Shot) | 12.7 / 1.67 | 19.7 / 1.33
G 1.5 Pro (1 Shot) | 35.3 / 9.03 | 57.6 / 7.01
G 1.5 Pro (30 Shot) | 56.4 / 11.3 | 62.7 / 8.04
G 1.0 S (1 Shot) | 7.0 / 0.0 | 5.33 / 0.0
G 1.0 S (30 Shot) | 9.99 / 0.336 | 8.00 / 0.662
G 1.0 S (SFT) | 99.8 / 10.8 | 98.0 / 63.4
Table 4: Testing Logistics (PDDL representation) accuracy results by model on
OOD tasks. For training we use in-context learning or fine-tuning. We consider
a split with problems of 1-2 packets and 3-5 packets, rest of parameters are
the same in the splits. Due to space constraints we use the shorthand G for
Gemini.

###  3.4 Comparison with Plan Bench

Valmeekam et al. (2023) proposed a benchmark for planning that maps domain
definitions to instructions and problem statements into natural language using
zero-shot and one-shot techniques. We utilize their dataset on BlocksWorld, as
the problems are comparable. Unlike their approach, which limits problems to
configurations of 3, 4, and 5 blocks using only zero-shot and one-shot
prompting, our work extends this using for ICL up to 7 blocks and by employing
many-shot prompting.

Table 5 compares results using the natural language prompts from Valmeekam et
al. (2023)(their dataset is referred to as Val-BW) and, novel to this work,
presents results on PDDL for their datasets using both 1-shot and 2-shot
techniques.

Dataset | LLM | Shots | Type | No. of Blocks
---|---|---|---|---
3 | 4 | 5
Val-BW | GPT-4 | 1 | NL | 49.0 | 32.4 | 23.2
Val-BW | G1.5P | 1 | NL | 30.0 | 18.4 | 14.2
Val-BW | G1.5P | 1 | PDDL | 60.0 | 36.4 | 23.6
Val-BW | G1.5P | 2 | PDDL | 68.0 | 46.2 | 30.9
Our-BW | G1.5P | 1 | NL | 66.0 | 38.5 | 32.4
Our-BW | G1.5P | 2 | NL | 66.0 | 58.5 | 53.9
Our-BW | G1.5P | 1 | PDDL | 100 | 44.6 | 32.0
Our-BW | G1.5P | 2 | PDDL | 100 | 44.6 | 50.9
Table 5: Reporting accuracy (in %) to compare state of the art for different
datasets and systems. Val-BW denotes BlocksWorld dataset as open-source by
Valmeekam et al. (2023). We use GPT-4 to refer to GPT-4 Turbo, the shorthand G
for Gemini, and P for Pro.

We utilize the natural language prompts from Valmeekam et al. (2023) test them
on Gemini 1.5 Pro. We observe that GPT-4 performs better with these prompts.
For our dataset, no such difference is observed. Manual inspection reveals
that especially 1-shot prompts need to be crafted carefully while few-shot or
many-shot prompts are more robust. For instance, results improve when the
prompts are more specific about the output format, changing from ’My plan is
as follows’ to ’Your plan as plain text without formatting’, which enhances
results for Gemini 1.5 Pro. Further, our prompts do not include explanations
of the actions and we do not use color coding for the blocks but rather keep
the names (e.g., blue block vs block b3).

##  4 Conclusion and Future Work

In this study, we comprehensively investigated the planning capabilities of
Large Language Models (LLMs) through three key approaches: (1) Benchmark
development (2) Learning and search techniques, (3) Generalization assessment.
Our results demonstrate that SFT, ICL and search procedures all contribute
significantly to enhancing the planning capabilities of LLMs.

In many-shot learning setting, comparing the performance of different LLMs
reveals an intriguing phenomenon: while accuracy generally improves with
increasing context, for some benchmarks, certain LLMs struggle to utilize
additional context effectively, leading to a decline in performance. This
observation holds implications for the future development and training of
LLMs, potentially informing strategies to enhance their capacity to process
and leverage extended contextual information.

Our investigation of plan generalization reveals three key findings:
superiority of SFT, curriculum learning effectiveness and limitations of hard
example training; suggesting that a balanced approach, incorporating both easy
and hard examples, might be optimal for achieving well-rounded performance.

For future studies we are interested in two main aspects: Enabling plan
generalization across diverse environments and Augmenting LLMs with replanning
capabilities. These enhancements can unlock new levels of versatility and
robustness in LLM-based planning systems, paving the way for their broader
adoption in real-world applications.

##  5 Limitations

In this work we investigated a small number of large language models and did
not cover every existing LLM such as Claude and Llama, in part due to compute
and time constraints and in part due to some preliminary experiments where
some of these models led to worse results compared to Gemini and GPT-4 for
some of the approaches in the paper. For these reasons, and for the sake of
environmental impact, we decided not to run extensive experiments on those
models. Additionally, it is known that LLMs are sensitive to prompt
engineering and it can be possible that our designed prompts were not
necessarily optimal for any of the models we did include in this paper. In
addition to prompt engineering there may also exist additional hyperparameters
which can improve the performance of the methods described in this paper.

##  6 Ethics Statement

As is, our approach only teaches the LLM specific planning tasks mentioned in
the paper which pose no significant ethical concerns. But we acknowledge that
malicious actors might get inspiration from any work that teaches LLM a new
capability and LLMs are prone to potential misuse and the improved planning
ability can potentially be used for malicious intent. However, recommend
careful consideration of all aspects of safety before relevant techniques are
applied to the real world and suggest that the owners and engineers behind
these models ensure that they filter out such requests.

The data used in our work is sourced from public datasets and our work
complies with ACL Ethics Policy.

## References

  * Agarwal et al. (2024) Rishabh Agarwal, Avi Singh, Lei M Zhang, Bernd Bohnet, Stephanie Chan, Ankesh Anand, Zaheer Abbas, Azade Nova, John D Co-Reyes, Eric Chu, et al. 2024.  Many-shot in-context learning.  _arXiv preprint arXiv:2404.11018_.
  * Bauer and Bansal (2018) Yicheng Bauer, Lisa andvWang and Mohit Bansal. 2018.  Commonsense for generative multi-hop question answering tasks.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 4220–4230, Brussels, Belgium. Association for Computational Linguistics.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Ding et al. (2023) Yan Ding, Xiaohan Zhang, Chris Paxton, and Shiqi Zhang. 2023.  Task and motion planning with large language models for object rearrangement.  In _2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 2086–2092. IEEE.
  * (5) Maria Fox and Derek Long.  Kcl-planning/val: The plan validation system.
  * Gatt and Krahmer (2018) Albert Gatt and Emiel Krahmer. 2018.  Survey of the state of the art in natural language generation: Core tasks, applications and evaluation.  _Preprint_ , arXiv:1703.09902.
  * GeminiTeam et al. (2024a) GeminiTeam, Rohan Anil, Sebastian Borgeaud, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M. Dai, Anja Hauth, Katie Millican, David Silver, Melvin Johnson, Ioannis Antonoglou, Julian Schrittwieser, Amelia Glaese, Jilin Chen, Emily Pitler, Timothy Lillicrap, Angeliki Lazaridou, Orhan Firat, et. al, Jeffrey Dean, and Oriol Vinyals. 2024a.  Gemini: A family of highly capable multimodal models.  _Preprint_ , arXiv:2312.11805.
  * GeminiTeam et al. (2024b) GeminiTeam, Machel Reid, Nikolay Savinov, Denis Teplyashin, Dmitry Lepikhin, Timothy Lillicrap, Jean baptiste Alayrac, Radu Soricut, Angeliki Lazaridou, Orhan Firat, Julian Schrittwieser, Ioannis Antonoglou, Rohan Anil, Sebastian Borgeaud, Andrew Dai, Katie Millican, Ethan Dyer, Mia Glaese, Thibault Sottiaux, Benjamin Lee, Fabio Viola, et al, Jeffrey Dean, and Oriol Vinyals. 2024b.  Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context.  _Preprint_ , arXiv:2403.05530.
  * Guan et al. (2024) Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. 2024.  Leveraging pre-trained large language models to construct and utilize world models for model-based task planning.  _Advances in Neural Information Processing Systems_ , 36.
  * Hao et al. (2023) Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. 2023.  Reasoning with language model is planning with world model.  _arXiv preprint arXiv:2305.14992_.
  * Hao et al. (2024) Yilun Hao, Yongchao Chen, Yang Zhang, and Chuchu Fan. 2024.  Large language models can plan your travels rigorously with formal verification tools.  _arXiv preprint arXiv:2404.11891_.
  * Hirsch et al. (2024) Eran Hirsch, Guy Uziel, and Ateret Anaby-Tavor. 2024.  What’s the plan? evaluating and developing planning-aware techniques for llms.  _arXiv preprint arXiv:2402.11489_.
  * Huang et al. (2022) Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, et al. 2022.  Inner monologue: Embodied reasoning through planning with language models.  _arXiv preprint arXiv:2207.05608_.
  * Kambhampati et al. (2024) Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Kaya Stechly, Mudit Verma, Siddhant Bhambri, Lucas Saldyt, and Anil Murthy. 2024.  Llms can’t plan, but can help planning in llm-modulo frameworks.  _arXiv preprint arXiv:2402.01817_.
  * Lehnert et al. (2024) Lucas Lehnert, Sainbayar Sukhbaatar, Paul Mcvay, Michael Rabbat, and Yuandong Tian. 2024.  Beyond a*: Better planning with transformers via search dynamics bootstrapping.  _arXiv preprint arXiv:2402.14083_.
  * McDermott et al. (1998) Drew McDermott, Malik Ghallab, Adele E. Howe, Craig A. Knoblock, Ashwin Ram, Manuela M. Veloso, Daniel S. Weld, and David E. Wilkins. 1998.  Pddl-the planning domain definition language.
  * Ning et al. (2020) Qiang Ning, Hao Wu, Rujun Han, Nanyun Peng, Matt Gardner, and Dan Roth. 2020.  TORQUE: A reading comprehension dataset of temporal ordering questions.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1158–1172, Online. Association for Computational Linguistics.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022\.  Training language models to follow instructions with human feedback.  _Advances in neural information processing systems_ , 35:27730–27744.
  * Reiter and Dale (2000) Ehud Reiter and Robert Dale. 2000.  _Building Natural Language Generation Systems_.  Cambridge University Press, Cambridge.
  * Russell and Norvig (2016) Stuart J Russell and Peter Norvig. 2016.  _Artificial intelligence: a modern approach_.  Pearson.
  * Silver et al. (2017) David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. 2017.  Mastering chess and shogi by self-play with a general reinforcement learning algorithm.  _Preprint_ , arXiv:1712.01815.
  * Singh et al. (2023) Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. 2023.  Progprompt: Generating situated robot task plans using large language models.  In _2023 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 11523–11530. IEEE.
  * Stechly et al. (2024) Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. 2024.  Chain of thoughtlessness: An analysis of cot in planning.  _arXiv preprint arXiv:2405.04776_.
  * Valmeekam et al. (2024) Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. 2024.  Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change.  _Advances in Neural Information Processing Systems_ , 36.
  * Valmeekam et al. (2023) Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. 2023.  On the planning abilities of large language models-a critical investigation.  _Advances in Neural Information Processing Systems_ , 36:75993–76005.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in neural information processing systems_ , 35:24824–24837.
  * Xie et al. (2024) Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. 2024.  Travelplanner: A benchmark for real-world planning with language agents.  _arXiv preprint arXiv:2402.01622_.
  * Yao et al. (2023) Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. 2023.  Tree of thoughts: Deliberate problem solving with large language models.  _Preprint_ , arXiv:2305.10601.
  * Yu et al. (2020) Weihao Yu, Zihang Jiang, Yanfei Dong, and Jiashi Feng. 2020.  Reclor: A reading comprehension dataset requiring logical reasoning.  In _International Conference on Learning Representations_.
  * Zheng et al. (2024) Huaixiu Steven Zheng, Swaroop Mishra, Hugh Zhang, Xinyun Chen, Minmin Chen, Azade Nova, Le Hou, Heng-Tze Cheng, Quoc V. Le, Ed H. Chi, and Denny Zhou. 2024\.  Natural plan: Benchmarking llms on natural language planning.  _arXiv preprint arXiv:2406.04520_.

Appendix

##  Appendix A Prompts

Bellow is the 1-shot prompt for the BlocksWorld task.

⬇

Please solve the problem:

(define (problem BW-rand-4)

(:domain blocksworld-4ops)

(:objects b4 b1 b3 b2)

(:init

(on b3 b1)

(on b1 b4)

(clear b3)

(handempty)

(ontable b2)

(ontable b4)

(clear b2)

)

(:goal (and

(on b2 b4)

(on b3 b1)

))

)

Your plan as plain text without formatting:

(unstack b3 b1)

(put-down b3)

(unstack b1 b4)

(put-down b1)

(pick-up b2)

(stack b2 b4)

(pick-up b3)

(stack b3 b1)

done.

Please solve the problem:

(define (problem BW-rand-6)

(:domain blocksworld-4ops)

(:objects b5 b1 b4 b2 b3 b6)

(:init

(on b4 b1)

(handempty)

(ontable b6)

(on b2 b4)

(clear b3)

(ontable b5)

(on b3 b2)

(clear b6)

(on b1 b5)

)

(:goal (and

(on b4 b2)

(on b1 b4)

(on b5 b1)

(on b3 b5)

))

)

Your plan as plain text without formatting:

Bellow is the 1-shot prompt for the Logistics task.

⬇

Please solve the problem:

(define (problem logistics-c4-s2-p3-a4)

(:domain logistics-strips)

(:objects

a0 a1 a2 a3

c0 c1 c2 c3

t0 t1 t2 t3

l0-0 l0-1 l1-0 l1-1 l2-0 l2-1 l3-0 l3-1

p0 p1 p2

)

(:init

(AIRPLANE a0) (AIRPLANE a1)(AIRPLANE a2)(AIRPLANE a3)

(CITY c0)(CITY c1)(CITY c2)(CITY c3)

(TRUCK t0)(TRUCK t1)(TRUCK t2)(TRUCK t3)

(LOCATION l0-0)(in-city l0-0 c0)

(LOCATION l0-1)(in-city l0-1 c0)

(LOCATION l1-0)(in-city l1-0 c1)

(LOCATION l1-1)(in-city l1-1 c1)

(LOCATION l2-0)(in-city l2-0 c2)

(LOCATION l2-1)(in-city l2-1 c2)

(LOCATION l3-0)(in-city l3-0 c3)

(LOCATION l3-1)(in-city l3-1 c3)

(AIRPORT l0-0)(AIRPORT l1-0)(AIRPORT l2-0)(AIRPORT l3-0)

(OBJ p0)(OBJ p1)(OBJ p2)

(at t0 l0-0)(at t1 l1-1)(at t2 l2-0)(at t3 l3-0)

(at p0 l1-1)(at p1 l0-1)(at p2 l0-0)

(at a0 l1-0)

(at a1 l1-0)

(at a2 l2-0)

(at a3 l3-0)

)

(:goal

(and

(at p0 l2-0)

(at p1 l2-0)

(at p2 l1-1)

)

)

)

Your plan as plain text without formatting:

(load-truck p0 t1 l1-1)

(drive-truck t1 l1-1 l1-0 c1)

(unload-truck p0 t1 l1-0)

(load-airplane p0 a1 l1-0)

(fly-airplane a1 l1-0 l2-0)

(unload-airplane p0 a1 l2-0)

(drive-truck t0 l0-0 l0-1 c0)

(load-truck p1 t0 l0-1)

(drive-truck t0 l0-1 l0-0 c0)

(unload-truck p1 t0 l0-0)

(fly-airplane a3 l3-0 l0-0)

(load-airplane p2 a3 l0-0)

(fly-airplane a3 l0-0 l1-0)

(unload-airplane p2 a3 l1-0)

(load-truck p2 t1 l1-0)

(drive-truck t1 l1-0 l1-1 c1)

(unload-truck p2 t1 l1-1)

(fly-airplane a1 l2-0 l0-0)

(load-airplane p1 a1 l0-0)

(fly-airplane a1 l0-0 l2-0)

(unload-airplane p1 a1 l2-0)

done.

Please solve the problem:

(define (problem logistics-c2-s2-p3-a2)

(:domain logistics-strips)

(:objects

a0 a1

c0 c1

t0 t1

l0-0 l0-1 l1-0 l1-1

p0 p1 p2

)

(:init

(AIRPLANE a0)(AIRPLANE a1)

(CITY c0)(CITY c1)

(TRUCK t0) (TRUCK t1)

(LOCATION l0-0)(in-city l0-0 c0)

(LOCATION l0-1)(in-city l0-1 c0)

(LOCATION l1-0)(in-city l1-0 c1)

(LOCATION l1-1)(in-city l1-1 c1)

(AIRPORT l0-0) (AIRPORT l1-0)

(OBJ p0)(OBJ p1)(OBJ p2)

(at t0 l0-1)(at t1 l1-0)

(at p0 l0-1)(at p1 l1-0)(at p2 l1-1)

(at a0 l0-0)(at a1 l0-0)

)

(:goal

(and

(at p0 l0-1)

(at p1 l1-0)

(at p2 l0-0)

)

)

)

Your plan as plain text without formatting:

Bellow is the 1-shot prompt for the Mini-Grid task.

⬇

Please solve the problem:

(define (problem grid_2Vroom2)

(:domain grid)

(:objects

p0 p1 p2 p3 p4 p5 p6 p7 p8

shape0

key0

)

(:init

; Object types

(place p0) (place p1) (place p2) (place p3) (place p4) (place p5) (place p6)
(place p7) (place p8)

(shape shape0)

(key key0)

; Open/locked cells

(open p0) (open p1) (open p2) (open p3) (open p5) (open p6) (open p7) (open
p8)

(locked p4)

; Connected cells

(conn p0 p1)

(conn p0 p2)

(conn p1 p0)

(conn p1 p3)

(conn p2 p0)

(conn p2 p3)

(conn p2 p4)

(conn p3 p2)

(conn p3 p1)

(conn p4 p2)

(conn p4 p5)

(conn p5 p4)

(conn p5 p6)

(conn p5 p7)

(conn p6 p5)

(conn p6 p8)

(conn p7 p5)

(conn p7 p8)

(conn p8 p7)

(conn p8 p6)

; Lock and key shapes

(lock-shape p4 shape0)

(key-shape key0 shape0)

; Key placement

(at key0 p0)

; Robot placement

(at-robot p3)

(arm-empty)

)

(:goal (at-robot p7))

)

Your plan as plain text without formatting:

(move p3 p2)

(move p2 p0)

(pickup p0 key0)

(move p0 p2)

(unlock p2 p4 key0 shape0)

(move p2 p4)

(move p4 p5)

(move p5 p7)

done.

Please solve the problem:

(define (problem grid_3Vroom3)

(:domain grid)

(:objects

p0 p1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 p13 p14 p15 p16 p17 p18 p19 p20 p21
p22 p23 p24 p25 p26 p27 p28

shape0

key0

)

(:init

; Object types

(place p0) (place p1) (place p2) (place p3) (place p4) (place p5) (place p6)
(place p7) (place p8) (place p9) (place p10) (place p11) (place p12) (place
p13) (place p14) (place p15) (place p16) (place p17) (place p18) (place p19)
(place p20) (place p21) (place p22) (place p23) (place p24) (place p25) (place
p26) (place p27) (place p28)

(shape shape0)

(key key0)

; Open/locked cells

(open p0) (open p1) (open p2) (open p3) (open p4) (open p5) (open p6) (open
p7) (open p8) (open p10) (open p11) (open p12) (open p13) (open p14) (open
p15) (open p16) (open p17) (open p18) (open p20) (open p21) (open p22) (open
p23) (open p24) (open p25) (open p26) (open p27) (open p28)

(locked p9) (locked p19)

; Connected cells

(conn p0 p1)

(conn p0 p3)

(conn p1 p0)

(conn p1 p2)

(conn p1 p4)

(conn p2 p1)

(conn p2 p5)

(conn p3 p0)

(conn p3 p4)

(conn p3 p6)

(conn p4 p3)

(conn p4 p1)

(conn p4 p5)

(conn p4 p7)

(conn p5 p4)

(conn p5 p2)

(conn p5 p8)

(conn p6 p3)

(conn p6 p7)

(conn p6 p9)

(conn p7 p6)

(conn p7 p4)

(conn p7 p8)

(conn p8 p7)

(conn p8 p5)

(conn p9 p6)

(conn p9 p10)

(conn p10 p9)

(conn p10 p11)

(conn p10 p13)

(conn p11 p10)

(conn p11 p12)

(conn p11 p14)

(conn p12 p11)

(conn p12 p15)

(conn p13 p10)

(conn p13 p14)

(conn p13 p16)

(conn p14 p13)

(conn p14 p11)

(conn p14 p15)

(conn p14 p17)

(conn p15 p14)

(conn p15 p12)

(conn p15 p18)

(conn p16 p13)

(conn p16 p17)

(conn p17 p16)

(conn p17 p14)

(conn p17 p18)

(conn p18 p17)

(conn p18 p15)

(conn p18 p19)

(conn p19 p18)

(conn p19 p22)

(conn p20 p21)

(conn p20 p23)

(conn p21 p20)

(conn p21 p22)

(conn p21 p24)

(conn p22 p21)

(conn p22 p19)

(conn p22 p25)

(conn p23 p20)

(conn p23 p24)

(conn p23 p26)

(conn p24 p23)

(conn p24 p21)

(conn p24 p25)

(conn p24 p27)

(conn p25 p24)

(conn p25 p22)

(conn p25 p28)

(conn p26 p23)

(conn p26 p27)

(conn p27 p26)

(conn p27 p24)

(conn p27 p28)

(conn p28 p27)

(conn p28 p25)

; Lock and key shapes

(lock-shape p9 shape0)

(lock-shape p19 shape0)

(key-shape key0 shape0)

; Key placement

(at key0 p12)

; Robot placement

(at-robot p16)

(arm-empty)

)

(:goal (at-robot p4))

)

Your plan as plain text without formatting:

Bellow is the 1-shot prompt for the Trip Planning task.

⬇

Please solve the problem:

You plan to visit 6 European cities for 13 days in total. You only take direct
flights to commute between cities. You want to spend 3 days in Dublin. You
would like to meet your friends at Dublin between day 7 and day 9 to tour
together. You would like to visit Madrid for 2 days. You plan to visit
relatives in Madrid between day 2 and day 3. You plan to stay in Oslo for 3
days. You would like to visit London for 2 days. You want to spend 3 days in
Vilnius. You plan to stay in Berlin for 5 days. You are going to attend a
wedding in Berlin between day 3 and day 7\.

Here are the cities that have direct flights:

London and Madrid, Oslo and Vilnius, Berlin and Vilnius, Madrid and Oslo,
Madrid and Dublin, London and Oslo, Madrid and Berlin, Berlin and Oslo, Dublin
and Oslo, London and Dublin, London and Berlin, Berlin and Dublin.

Find a trip plan of visiting the cities for 13 days by taking direct flights
to commute between them.

Here is the trip plan for visiting the 6 European cities for 13 days:

**Day 1-2:** Arriving in London and visit London for 2 days.

**Day 2:** Fly from London to Madrid.

**Day 2-3:** Visit Madrid for 2 days.

**Day 3:** Fly from Madrid to Berlin.

**Day 3-7:** Visit Berlin for 5 days.

**Day 7:** Fly from Berlin to Dublin.

**Day 7-9:** Visit Dublin for 3 days.

**Day 9:** Fly from Dublin to Oslo.

**Day 9-11:** Visit Oslo for 3 days.

**Day 11:** Fly from Oslo to Vilnius.

**Day 11-13:** Visit Vilnius for 3 days.

done.

Please solve the problem:

You plan to visit 6 European cities for 17 days in total. You only take direct
flights to commute between cities. You want to spend 4 days in Manchester. You
plan to stay in Florence for 5 days. You want to spend 3 days in Geneva. You
are going to attend a wedding in Geneva between day 1 and day 3. You want to
spend 3 days in Seville. During day 7 and day 9, you have to attend a
conference in Seville. You would like to visit Prague for 2 days. You plan to
stay in Valencia for 5 days. From day 3 to day 7, there is a annual show you
want to attend in Valencia.

Here are the cities that have direct flights:

Manchester and Prague, Seville and Manchester, Geneva and Manchester, Valencia
and Seville, Geneva and Valencia, Valencia and Prague, Prague and Florence,
Geneva and Prague.

Find a trip plan of visiting the cities for 17 days by taking direct flights
to commute between them.

Bellow is the 1-shot prompt for the Calendar Scheduling task.

⬇

Please solve the problem:

You need to schedule a meeting for Samuel, Evelyn, Ruth and Amanda for half an
hour between the work hours of 9:00 to 17:00 on Monday.

Here are the existing schedules for everyone during the day:

Samuel is free the entire day.

Evelyn has meetings on Monday during 9:00 to 10:00, 11:00 to 12:00, 12:30 to
13:00, 15:30 to 16:00;

Ruth has meetings on Monday during 9:30 to 11:00, 11:30 to 12:30, 13:00 to
13:30, 14:00 to 14:30, 15:00 to 16:00, 16:30 to 17:00;

Amanda has meetings on Monday during 10:00 to 10:30, 11:00 to 12:30, 13:00 to
13:30, 14:00 to 15:00, 15:30 to 16:00;

Amanda can not meet on Monday before 16:00. Find a time that works for
everyone’s schedule and constraints.

Here is the proposed time: Monday, 16:00 - 16:30

done.

Please solve the problem:

You need to schedule a meeting for Walter, Jacob, Jennifer and Joan for one
hour between the work hours of 9:00 to 17:00 on Monday.

Here are the existing schedules for everyone during the day:

Walter is busy on Monday during 9:30 to 10:00, 13:00 to 13:30;

Jacob has meetings on Monday during 11:00 to 11:30, 13:00 to 13:30;

Jennifer is busy on Monday during 9:30 to 10:30, 11:30 to 12:00, 12:30 to
15:00;

Joan has blocked their calendar on Monday during 9:30 to 10:00, 10:30 to
11:30, 12:00 to 12:30, 13:00 to 14:00, 14:30 to 15:30;

Find a time that works for everyone’s schedule and constraints.

##  Appendix B Experimental Details

###  B.1 Dataset Creation

Algorithm 1, we generate 28k unique samples. From these, we randomly select
25500 of the for training set and 2500 for validation set. This procedure
yields a problem distribution as shown in Figure 5.

Figure 5: Distribution with number of blocks and average plan length.

###  B.2 Mappings PDDL to Natural Language

Here we present the templates to map PDDL problems to Natural Language.
Details are shown in Table 6.

Term (with arguments) | Mapping to Natural Language
---|---
AIRPLANE object2 | object2 is an AIRPLANE.
CITY object2 | object2 is a CITY.
TRUCK object2 | object2 is a TRUCK.
at object2 object3 | object2 is at object3.
in-city object2 object3 | object2 is in the city object3.
drive-truck param2 param3 param4 param5 | Drive truck param2 from param3 to param4 in param5.
load-truck param2 param3 param4 | Load param2 into truck param3 at param4.
unload-truck param2 param3 param4 | Unload param2 from truck param3 in param4.
fly-airplane param2 param3 param4 | Fly airplane param2 from param3 to param4.
load-airplane param2 param3 param4 | Load param2 into airplane param3 at param4.
unload-airplane param2 param3 param4 | Unload param2 from airplane param3 at param4.
on object2 object3 | object2 is on object3.
handempty | The hand is empty.
ontable object2 | object2 is on the table.
clear object2 | object2 is clear.
unstack param2 param3 | Unstack param2 from param3.
put-down param2 | Put down param2.
pick-up param2 | Pick up param2.
stack param2 param3 | Stack param2 on param3.
conn object2 object3 | object2 and object3 are connected.
lock-shape object2 object3 | The lock object2 is object3 shaped.
key-shape object2 object3 | The key object2 is object3 shaped.
arm-empty | The arm is empty.
open object2 | object2 is OPEN.
move param2 param3 | Move from param2 to param3.
pickup param2 param3 | Pickup param2 at param3.
unlock param2 param3 param4 param5 | Unlock param2 at param3 using param4, which has param5.
pickup-and-loose param2 param3 | At param2, pick up param3 and lose param2.
at-robot object2 | Robot is at object2.
Table 6: Semantic mappings used in the system, showing terms and their
arguments.

###  B.3 Search Procedure Parameters

.

The two search procedures deployed and compared alongside ICL and SFT methods,
(ToT) (Yao et al., 2023) and monte-carlo tree search (MCTS) (Hao et al.,
2023), were implemented as specified in their original papers. The only
deviations are listed below.

The biggest deviation from the reference papers are the LLM’s prompts, which
had to be edited to make the search procedures more aligned with the planning
task.

Additionally, for the MCTS procedure, the action log-probs were weighted by a
factor of 1.5. All other weights specified in the Reasoning as Planning MCTS
procedure are the same (state log-probs, UCT, and exploration lambda factor
are all 1.0).

The same weights are used to compute the value of the nodes in the tree-of-
thought search procedure.

Hyperparameter | Value | Description
---|---|---
LLM Model | Gemini 1.0M | The language model
|  | used for text
|  | generation.
LLM Temperature | 1.0 | Controls the
|  | randomness of LLM
|  | outputs (higher
|  | values = more
|  | variance).
LLM Num Samples | 1 | The number of
|  | different outputs
|  | generated by the
|  | LLM for each input.
Max Depth | 5 | The maximum number
|  | of steps in the
|  | search tree.
Max Branching Factor | 3 | The maximum number
|  | of actions to
|  | consider at each
|  | node.
Num Simulations | 3 | The number of times
|  | to simulate the
|  | game from each
|  | node.
Table 7: Monte Carlo Tree Search (MCTS) Hyperparameters Hyperparameter | Value | Description
---|---|---
LLM Model | Gemini 1.0M | The language model
|  | used for text
|  | generation.
LLM Temperature | 1.0 | Controls the
|  | randomness of LLM
|  | outputs (higher
|  | values = more
|  | variance).
LLM Num Samples | 1 | The number of
|  | different outputs
|  | generated by the
|  | LLM for each input.
Max Depth | 5 | The maximum number
|  | of steps in the
|  | thought process.
Max Branching Factor | 3 | The maximum number
|  | of alternative
|  | thoughts to
|  | explore at each
|  | step.
Num Simulations | 3 | The number of
|  | rollouts for each
|  | thought to
|  | simulate.
Table 8: Tree of Thought (ToT) Hyperparameters Prompt Name |  Prompt Content
---|---
MCTS_STATE_PROMPT |  `Given the provided state and` `action, estimate the next` `state. Your state should` `look similar to preceding` `state, enclosed in [STATE]` `blocks. Do not repeat or` `reiterate information from` `the preceding states /` `actions. [STATE CONTEXT]` `{state} [END STATE CONTEXT]` `[STATE]`
MCTS_ACTION_PROMPT |  `[CONTEXT] {state} [END` `CONTEXT] Given the` `preceding task, and action,` `what action should be taken` `next? Only take a SINGLE STEP` `at a time. Any composite` `actions will be penalized.` `[ACTION]`
Table 9: MCTS Agent Prompts Prompt Name |  Prompt Content
---|---
MCTS_STATE_PROMPT |  `Given the provided state and` `action, estimate the next` `state. Your state should` `look similar to preceding` `state, enclosed in [STATE]` `blocks. Do not repeat or` `reiterate information from` `the preceding states /` `actions. [STATE CONTEXT]` `{state} [END STATE CONTEXT]` `[STATE]`
MCTS_ACTION_PROMPT |  `[CONTEXT] {state} [END` `CONTEXT] Given the` `preceding task, and action,` `what action should be taken` `next? Only take a SINGLE STEP` `at a time. Any composite` `actions will be penalized.` `[ACTION]`
Table 10: Tree-of-Thought Prompts Table 11: CalendarPlan Performance with search procedures (ToT, MCTS) per number of few-shot examples provided to the procedure. We observe that for contexts fitting within Gemini 1.0M, it competes with significantly more powerful models. Without these methods, the model fails outright. N |  G1.0M ToT |  G1.0M MCTS |  G1.5 Flash |  GPT4 Turbo
---|---|---|---|---
1 | 29 | 28 | 39 | 19
4 | 33 | 39 | 50 | 64
10 | 31 | 36 | 58 | 71

###  B.4 Finetune experiments

Dataset | Train Size | Test Size
---|---|---
BW(3-7) | 28,386 | 500
BW(8-9) | 3,995 | 500
BW(8-20) | 4,160 | 500
Logistics(1-2) | 13,483 | 500
Logistics(3-5) | 13,483 | 500
Table 12: Details of the dataset size

For the fine tuning of the Gemini 1.0 S, we use learning rate of 0.0001 with
drop out rate of 0.1. We train the model for 5k step and choose the checkpoint
with highest accuracy on the validation set. We then run the verifier on the
inference results of that checkpoint and report the results.