LLM+P: Empowering Large Language Models with Optimal Planning Proficiency

I Introduction

Ever since the birth of the field, AI researchers have sought to create programs that can converse in natural language with the same grace and flexibility as people. While even relatively simple models, such as Eliza from 1966 , can generate responses to some prompts that seem reasonable, it has always been relatively easy to generate prompts that expose their weaknesses compared to people — their lack of true “understanding.”

While large language models (LLMs) such as GPT-4 and ChatGPT have far surpassed expectations of just a few years ago, they are no different in this respect. Indeed the internet is now awash with examples of people reveling in getting ChatGPT to generate output that even a 5-year-old human child would know to be ill-advised.

Given how LLMs are designed and trained, this phenomenon should come as no surprise. They are not specifically built to demonstrate understanding. They are trained to generate sequences of words that might be plausible to a human given a prior context. In the terms of Mahowald et al. LLMs have become amazingly proficient at linguistic competence — knowing how to say things; but they are not nearly as good at functional competence — knowing what to say. Specifically, they can be (relatively) easily fooled by, for example, asking for the result of a straightforward arithmetic problem that does not appear in their training corpus or by asking for the solution to a novel planning problem that requires knowledge about how the world works.

A Failure Example of GPT-4 in Planning Problem (P1): You have 5 blocks. One cannot place more than one block on another block. b5 is on top of b3. b4 is on top of b2. b2 is on top of b1. b3 is on top of b4. b1 is on the table. b5 is clear. Your arm is empty. Your goal is to move the blocks. b1 should be on top of b2. b3 should be on top of b5. b4 should be on top of b1. GPT-4: 1. Move b5 from b3 to the table. 2. Move b3 from b4 to b5. 3. Move b4 from b2 to the table. 4. Move b2 from b1 to b5. 5. Move b1 from the table to b2. 6. Move b4 from the table to b1. Does that mean that we should increase efforts to include all arithmetic and planning problems in their training corpus? Clearly, that is a fool’s errand. On the other hand, why should it be necessary? We already have calculators and general-purpose symbolic planners that are guaranteed to produce correct answers. Thus a natural alternative approach, and one that we are admittedly not the first to explore, is to connect LLMs to such tools.

With this motivation in mind, the objective of the research reported in this paper is, for the first time, to enable LLMs to solve planning problems correctly. We aim to do so without altering the LLMs themselves, even with finetuning . Rather, we introduce a methodology, called LLM+P by which, when posed a natural language description of a planning problem, the LLM:

outputs a problem description suitable as input to a general-purpose planner;

solves the problem using the general-purpose planner; and

converts the output of the planner back to natural language (or connects to action executors of a robot).

Our extensive empirical evaluations indicate that LLM+P is able to generate correct solutions to many more planning problems than are LLMs on their own. While demonstrated in this paper on planning problems, this general methodology can be applied to any class of problems for which we have a sound and complete solver, such as arithmetic problems (by leveraging calculators).

Limitation: In this paper, we do not ask the LLM to recognize that it has been posed a prompt that is suitable for processing using the proposed LLM+P pipeline. A valuable future research direction will be to consider recognizing when a prompt should be processed by LLM+P.

II Background

This section introduces the notation we use for representing a planning problem to be solved by LLMs, and recaps the standard representation of classical planners.

Formally, the input of a planning problem $P$ is defined by a tuple $\langle\mathcal{S},s^{init},\mathcal{S}^{G},\mathcal{A},f\rangle$:

$\mathcal{S}$ is a finite and discrete set of states used to describe the world’s state (i.e., state space). We assume a factored state space such that each state $s\in\mathcal{S}$ is defined by the values of a fixed set of variables.

$s^{init}\in\mathcal{S}$ is an initial world state.

$\mathcal{S}^{G}\subset\mathcal{S}$ is a set of goal states. $\mathcal{S}^{G}$ are usually specified as a list of goal conditions, all of which must hold in a goal state.

$\mathcal{A}$ is a set of symbolic actions.

$f$ is the underlying state transition function. $f$ takes the current state and an action as input and outputs the corresponding next state.

A solution to a planning problem $P$ is a symbolic plan $\pi$ in the form of $\langle a_{1},a_{2},\dots,a_{N}\rangle$, such that the preconditions of $a_{1}$ hold in $s^{init}$, the preconditions of $a_{2}$ hold in the state that results from applying $a_{1}$, and so on, with the goal conditions all holding in the state that results after applying $a_{N}$.

II-B Planning Domain Definition Language (PDDL)

The planning domain definition language (PDDL) serves as a standardized encoding of classical planning problems . The PDDL representation of a planning problem $P$ is separated into two files: a domain file and a problem file. The domain PDDL file provides a lifted representation of the underlying rules of the world. It includes a set of predicates that define the state space $\mathcal{S}$ and the actions (i.e., $\mathcal{A}$) with their preconditions and effects (i.e., the transition function $f$). The problem PDDL file provides a list of objects to ground the domain, the problem’s initial state $s^{init}$ and goal conditions $\mathcal{S}^{G}$. There exists a rich set of symbolic planners that implement efficient search algorithms to solve planning problems formalized in PDDL. In this work, we aim to take a natural language prompt which describes the initial state $s^{init}$ and goal conditions $\mathcal{S}^{G}$, formulate it in PDDL, and leverage symbolic planners to output correct plans. We assume the domain rules are available (See the assumptions in Section III).

III Method

This section first uses a running example to investigate ways for formulating planning prompts in PDDL and then introduces the LLM+P method.

LLMs are bad at planning (or long-horizon reasoning) but they are good at describing and translating textual inputs, including re-writing planning prompts in the PDDL format. The intuition is that we can view PDDL as a different language than English, so re-writing planning prompts in PDDL is essentially a “machine translation” task that LLMs are known to excel at. Here we provide an example of a PDDL problem file written by GPT-4 without any prompt-engineering. As we see, the generated file appears to have the correct PDDL syntax but uses a made-up predicate (empty) and misses the initial condition that b1 is on the table.

III-B In-Context Learning

LLMs are known to be capable of in-context learning without finetuning their parameters. By in-context learning, we mean LLMs’ ability to perform unseen downstream tasks by simply conditioning on a few input-label pairs (demonstrations) . Here is a pair of problem descriptions in natural language and in PDDL provided to GPT-4 as context. When the context is included with the prompt from the example above, the resulting PDDL problem file is directly solvable by the planner.

III-C Large Language Model + Classical Planner (LLM+P)

Having introduced the LLM’s ability to encode problems in PDDL and in-context learning, we are ready to introduce the proposed LLM+P solution (the bottom of Fig. 1). In particular, we assume that for each problem domain, a human expert can provide a domain description (i.e. action preconditions and effects) that will be fixed for all problem instances that happen in that domain. While the problem of automatically generating the description is another valuable research question, in this proposed work, we assume that the description is available as a PDDL domain file. The LLM+P method is directly applicable as a natural language interface for giving tasks to robot systems. For instance, assume we want a robot to act as a bartender to make cocktails. It is reasonable to tell it what actions it can take, but leave itself to infer how to make new cocktails most efficiently given a set of ingredients to combine. Moreover, we assume the agent is provided with a minimal example that demonstrates what an example problem PDDL looks like for a simple problem inside that domain. Next, the agent is provided with a new (potentially quite complicated) problem ($P$). The LLM then uses the in-context learning to infer the problem PDDL file corresponding to $P$. Once the problem PDDL file is generated, we feed it into any classical planner, together with the provided domain PDDL file, to generate a PDDL plan . In the end, the LLM translates the PDDL plan back into the natural language to finish up the LLM+P pipeline. To summarize, the assumptions we need for LLM+P are:

A robot knows when to trigger LLM+P based on its conversation with a human user.

A domain PDDL is provided to define the actions that the robot is capable of. This specification is task-agnostic — the entities relevant to the task are specified in the LLM-generated problem PDDL.

A simple problem description in natural language and its corresponding problem PDDL file are also provided.

IV Related Work

This section first provides a brief overview of classical planning algorithms. Then it summarizes recent advances in using large language models for planning tasks. It concludes with a discussion of recent research on augmenting LLMs with external modules.

Automated planning (or classical planning) techniques can be used for computing a sequence of actions that achieves a given goal . Automated planning algorithms have been widely used in robot systems. Shakey is the first robot that was equipped with a planning component, which was constructed using STRIPS . Some previous general-purpose planning architectures were also demonstrated to be useful for robot planning, such as PRODIGY and HTN . Recent classical planning systems designed for robotics frequently use planning domain description language (PDDL) or answer set programming (ASP) as the underlying action language for the planners . For example, researchers have used classical planning algorithms for sequencing actions for a mobile robot working on delivery tasks , reasoning about safe and efficient urban driving behaviors for autonomous vehicles , and planning actions for a team of mobile robots . Task and motion planning (TAMP) is a hierarchical planning framework that combines classical planning in discrete spaces and robot motion planning in continuous space .

Most of the above-mentioned planning methods require domain-specific programming languages as the underlying representation of the problems and their solutions. LLM+P, on the other hand, takes advantage of LLMs and serves as a natural language interface for robots to solve complex planning tasks. The main feature that motivates us to use such classical planning systems is that most of these planners are sound and complete, meaning that they are guaranteed to be logically correct and will output a plan if one exists. Many are also able to find optimal (shortest) plans, at least if given sufficient time.

IV-B Planning with Large Language Models

Various large language models (LLMs) have been developed in recent years, such as Bert , CodeX , Opt , GPT-3 , ChatGPT , GPT-4 , Llama , Llama2 , and PaLM . As LLMs are pretrained with a tremendous amount of offline text data, they can emerge with surprising zero-shot generalization ability, which can be leveraged for robot planning tasks . Several recent methods had successes in extracting task knowledge from LLMs to decompose commands or instructions for robots in natural language. For instance, the work of Huang et al. showed that LLMs can be used for task planning in household domains by iteratively augmenting prompts . SayCan is another approach that enabled robot planning with affordance functions to account for action feasibility, where the service requests are specified in natural language . Vemprala et al. recently studied how ChatGPT can be applied to generalized robotics domains .

However, a major drawback of existing LLMs is their lack of long-horizon reasoning ability for complex tasks (See and Section 8.2 from ). Specifically, the output they produce when presented with such a task is often incorrect in the sense that following the output plan will not actually solve the task. Therefore, in this work, we focus on resolving this issue by leveraging the properties of classical planners. Similarly, some recent work also investigates approaches for combining classical planning with LLMs . They either use prompting or fine-tuning to make LLMs capable of solving PDDL planning problems. Improvements to long-horizon planning capabilities have also been made by iteratively querying LLMs, as demonstrated in Minecraft . In contrast, we do not solely rely on LLM as the problem solver, but are more into taking the advantage of both the planner (i.e., generating accurate and optimal plans) and the LLM itself (i.e., 1-shot generalization for translating natural-language problem descriptions into PDDL).

IV-C Augmenting LLMs with External Modules

Recently developed methods have shown that the performance of downstream tasks of LLMs can be improved by combining them with external modules. For instance, WebGPT is a fine-tuned version of GPT-3 by combining web knowledge to answer open-ended questions. Lazaridou et al. studied how search engines like Google can be utilized as external tools for LLMs . MemPrompt presented a human-in-the-loop system where a growing memory of errors and user feedback is served as past experience adding to the prompts for more accurately answering new questions. REPLUG is another retrieval-augmented language modeling paradigm that treats the language model as a black box and augments it with a tuneable retrieval model. Specifically, people have investigated using calculators for computation . In very recent work related to ours, Schick et al. trained a model called ToolFormer that can decide when and how to call certain tool APIs by in-line augmentation on prompts for LLMs . In this work, we propose that classical planners can be another particularly useful external module. In comparison, LLM+P, does not rely on any fine-tuning or re-training of LLMs. By simply incorporating knowledge from classical planners, LLM+P incorporates long-horizon reasoning and planning capabilities into existing LLMs.

The authors are informed that a concurrent work presents preliminary results of integrating LLMs with PDDL using the SayCan dataset . However, the SayCan dataset has a limited scope, as it contains only three predefined actions. Consequently, all model variants evaluated in the original paper achieved a success rate of approximately 90%. Due to the homogeneity of the SayCan dataset, Lyu et al. did not necessitate a rigorous definition of the domain PDDL, which can lead to infeasible plans. As a result, we consider our LLM+P method as a more comprehensive investigation into enhancing LLMs with optimal planning proficiency.

V Experiments

We conduct experiments to answer these questions:

How well does LLM-as-P work? To what extent can state-of-the-art LLMs and LLM-based reasoning methods be directly used for planning? (Not at all)

How well does LLM+P work compare to LLM-as-P? (Much better)

What role does the context play in the success of LLM+P? (It’s crucial)

Can LLM+P help make service robots more efficient on realistic tasks? (Yes)

We present seven robot planning domains borrowed from past International Planning Competitions and 20 automatically generated tasks for each domain . Below is a list of the planning domains, along with a brief summary of each.

Blocksworld: Given a set of piles of blocks on a table, a robot is tasked with rearranging them into a specified target configuration.

Barman: A robot bartender is tasked with creating cocktails for a customer’s order, utilizing the available ingredients and containers.

Floortile: A set of robots are tasked to use paint color patterns on floor tiles. Robots can move around and change colors but cannot step on painted tiles.

Grippers: A set of robots with two grippers is given a task to move objects among different rooms.

Storage: Given a set of hoists, the goal is to lift and drop crates using the hoists into a depot. Crates are initially stored in different areas and hoists can be moved among storage areas.

Termes: A robot is tasked to build complex structures by carrying and placing blocks, and also climbing on them so that it can build towers.

Tyreworld: The robot is given a task to replace flat tires by, for example, inflating tires, tightening nuts, and moving tools back to the boot when done, all in the proper order.

For each problem $P$, $P$ comes with a natural language description and a ground-truth problem PDDL file. Each domain also includes an example problem description, a corresponding PDDL file, and a plan description, used as context in various approaches. We assume each problem domain has its own domain PDDL file given by the user or a domain expert prior to addressing any planning problems in that domain. This dataset is made publicly available in our codebase for reproducibility.

V-B Experiment Setup

We leverage the gpt-4 model provided by OpenAIWe use the most recent model as of September 2023. https://platform.openai.com/docs/models/gpt-4 for all experiments. We set the temperature to , and use the top probability response. As a result, the response returned from the LLM is deterministic. Once a text PDDL response is generated, we feed it into the fast-downward plannerhttps://github.com/aibasel/downward/tree/release-22.12.0 and try both aliases seq-opt-fdss-1 (guaranteed optimal) and lama (not guaranteed optimal) with a maximum search time of $200$ seconds. We report the success rate of the optimal alias, and for the domains that time out, we show the success rate of the sub-optimal alias in parentheses. For the baseline methods, we manually count the number of optimal plans, and report the number of correct plans in parentheses (if there are any sub-optimal plans).

We also evaluate a recent LLM-based approach for deliberate reasoning called Tree of Thoughts , referred to as LLM-as-P (ToT). We adapt the breadth-first-search algorithm from the original ToT implementationhttps://github.com/princeton-nlp/tree-of-thought-llm/ for planning. The LLM is prompted to expand the search tree from allowed actions and evaluate the paths on their likelihood of reaching the goal. The same time limit of $200$ seconds is applied.

V-C Results and Analysis

The results of applying LLM-as-P and LLM+P across 7 domains are provided in Table I.

We observe that though LLM-as-P provides a plan in natural language for every problem, most of these plans are not feasible. The main reason is that LLM-as-P lacks the ability to reason about preconditions.

In most cases, LLM-as-P fails in the same way with or without the example plan as context. In particular, in the Blocksworld domain, LLM-as-P cannot keep track of properties like on and clear. In the Barman domain, LLM-as-P’s plans fail to clean shot glasses before using them again.

The hardest domains are the ones with complex spatial relationship. The LLM-as-P methods (with or without context) completely fail at this type of problems. In the Floortile domain, LLM-as-P generates “move right to tile_0-4 and paint tile_1-2 black” but the robot can only paint neighboring tiles. In Termes and Storage, LLM-as-P ignores the requirement that the robot cannot unload the block/crate at the same position it occupies.

LLM-as-P (ToT) calls the LLM at each tree node to provide a list of available actions, and then calls the LLM to evaluate each new path on the tree as a partial plan. We find that the LLM is able to give reasonable rankings on the partial plans, but it often fails to recognize whether the plan reaches the goal. LLM-as-P (ToT) times out in most cases due to the large number of LLM calls, so it is not suitable for solving long-horizon problems.

The proposed LLM+P produces an optimal plan for the majority of problems. Most failed cases are due to mis-specified problem files, such as missing one of the initial conditions (e.g. leaving the tiles disconnected in Floortile), causing the planning problem to be unsolvable.

Without the context (i.e., an example problem and its corresponding problem PDDL), we observe that LLMs fail to produce correct problem PDDL files. Therefore, the context is important for LLM+P to work.

V-D Robot Demonstration

We verify that LLM+P can efficiently solve realistic service robot problems by deploying it on a real robot tasked with tidying up a home. The user asks the robot to move a mustard bottle from the coffee table to the pantry, and throw away the empty soup can from the side table. Since the side table and the recycle bin are on the way from the coffee table to the pantry, the optimal plan is to take the mustard bottle to the side table, and re-grasp it after throwing away the soup can, with a total cost of 22. Fig. 2 shows the optimal plan found by LLM+P. Parts of the prompt and the generated PDDL are shown below. LLM-as-P outputs a sub-optimal plan which takes the bottle to the pantry first and travels back for the soup can, with a total cost of 31.

VI Conclusion and Future Work

In this work, we propose to leverage classical planners to empower large language models with optimal planning capabilities. The key design choice of the proposed LLM+P framework is to focus LLMs on translating the planning problem from natural language to structured PDDL format. Moreover, we show that it is important to also make LLMs aware of a simple (problem, PDDL) pair as a demonstration (or the context) for in-context learning. Some interesting directions to further extend the LLM+P framework include: 1) enabling the LLM to auto-detect when and how to apply LLM+P; and 2) reducing LLM+P’s dependency on information by humans, potentially involving finetuning.

References