PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, Peter Stone

arXiv:2304.11477v3cs.AIcs.RO

TL;DR

LLMs struggle with reliable long-horizon planning, motivating a method that combines their language abilities with classical planners. LLM+P converts natural-language problems into PDDL, obtains a plan from a classical planner, and translates it back into natural language; experiments report optimal solutions for most problems while standalone LLMs often fail to produce feasible plans.

  • Problem

    LLMs can be easily fooled by novel planning problems and often produce incorrect plans for complex long-horizon tasks.

  • Method

    LLM+P uses an LLM to convert a natural-language planning problem into PDDL, applies a classical planner, and translates the resulting plan back into natural language.

  • Results

    LLM+P provides optimal solutions for most benchmark problems, whereas LLMs fail to provide even feasible plans for most problems.

  • Takeaways & Limitations

    Classical planners can supply long-horizon planning capabilities to existing LLMs without fine-tuning or retraining them.

Abstract

from arXiv · show

Large language models (LLMs) have demonstrated remarkable zero-shot generalization abilities: state-of-the-art chatbots can provide plausible answers to many common questions that arise in daily life. However, so far, LLMs cannot reliably solve long-horizon planning problems. By contrast, classical planners, once a problem is given in a formatted way, can use efficient search algorithms to quickly identify correct, or even optimal, plans. In an effort to get the best of both worlds, this paper introduces LLM+P, the first framework that incorporates the strengths of classical planners into LLMs. LLM+P takes in a natural language description of a planning problem, then returns a correct (or optimal) plan for solving that problem in natural language. LLM+P does so by first converting the language description into a file written in the planning domain definition language (PDDL), then leveraging classical planners to quickly find a solution, and then translating the found solution back into natural language. Along with LLM+P, we define a diverse set of different benchmark problems taken from common planning scenarios. Via a comprehensive set of experiments on these benchmark problems, we find that LLM+P is able to provide optimal solutions for most problems, while LLMs fail to provide even feasible plans for most problems.\footnote{The code and results are publicly available at https://github.com/Cranial-XIX/llm-pddl.git.

I. INTRODUCTION

LLMs can produce plausible language but struggle with understanding and long-horizon planning. LLM+P addresses this by connecting LLMs to classical planners through an intermediate structured representation.

  • I. INTRODUCTION: LLMs exhibit linguistic competence but are less reliable at functional competence, including novel planning problems.They can be fooled by arithmetic or planning tasks requiring knowledge of how the world works.
  • I. INTRODUCTION: GPT-4 can generate an infeasible block-world plan despite producing a fluent sequence of actions.The example lists six moves for rearranging five blocks.
  • I. INTRODUCTION: Connecting LLMs to symbolic tools offers an alternative to training them on every arithmetic and planning problem.The paper motivates using calculators and general-purpose symbolic planners for guaranteed correct answers.
  • I. INTRODUCTION: LLM+P converts a natural-language problem into a planner-ready description, solves it with a general-purpose planner, and translates the result back into natural language.The framework is intended to enable correct planning without altering the LLM itself.

II. BACKGROUND

This section introduces the notation for planning problems and reviews the standard representation used by classical planners.

  • II. BACKGROUND: The section establishes planning-problem notation and recaps classical-planner representations.

A. The Classical Planning Problem

A classical planning problem specifies a discrete state space, an initial state, goal states, symbolic actions, and state transitions. A solution is an action sequence whose preconditions hold throughout and whose final state satisfies the goals.

  • A. The Classical Planning Problem: A planning problem is represented as ⟨S,sinit,SG,A,f⟩, combining states, an initial state, goals, actions, and transitions.
  • A. The Classical Planning Problem: S is a finite discrete state space, with each state described by values of a fixed set of variables.
  • A. The Classical Planning Problem: A solution plan is an action sequence whose preconditions hold at each step and whose resulting state satisfies all goal conditions.

B. Planning Domain Definition Language (PDDL)

PDDL standardizes classical planning problems by separating domain rules from instance-specific information. LLM+P uses an LLM to formulate natural-language problems in PDDL before symbolic planning.

  • B. Planning Domain Definition Language (PDDL): PDDL is a standardized encoding of classical planning problems divided into domain and problem files.The domain file represents the world’s rules, while the natural-language prompt supplies the initial state and goals to formulate in PDDL.
  • B. Planning Domain Definition Language (PDDL): LLM+P assumes that domain rules are available as a fixed PDDL domain description for each problem domain.Automatically generating that domain description is left as a separate research question.
  • B. Planning Domain Definition Language (PDDL): LLMs are used to rewrite planning prompts into PDDL because the paper treats this as a translation task.The method relies on LLMs for encoding textual inputs rather than for directly performing long-horizon search.

B. In-Context Learning

LLMs can perform unseen downstream tasks by conditioning on a few demonstrations without parameter finetuning. In this planning example, providing paired natural-language and PDDL descriptions as context enables GPT-4 to generate a planner-solvable PDDL problem file.

  • B. In-Context Learning: In-context learning means performing unseen downstream tasks by conditioning on a few input-label pairs without finetuning model parameters.The demonstrations serve as context for the task.
  • B. In-Context Learning: A paired natural-language description and PDDL problem can be supplied to GPT-4 as context for generating a planning problem file.The example includes both forms of the same planning task.
  • B. In-Context Learning: The resulting PDDL problem file is directly solvable by the planner, which returns a sequence of unstack, putdown, pickup, and stack actions.The demonstrated plan contains twelve actions that achieve the stated goals.
  • B. In-Context Learning: The prompt asks GPT-4 to provide the problem PDDL directly, without further explanations, after receiving the problem description and context.The example prompt explicitly combines the problem description, context, and requested output format.
  • B. In-Context Learning: The generated PDDL specifies objects, initial conditions, and goal conditions for a blocks-world planning problem.The example output lists five blocks, their relations, the arm state, and three goal relations.

C. Large Language Model + Classical Planner (LLM+P)

LLM+P combines an LLM’s natural-language-to-PDDL translation with a classical planner, assuming a fixed domain description and contextual example for each planning domain.

  • C. Large Language Model + Classical Planner (LLM+P): LLM+P assumes a human expert provides a fixed PDDL domain description specifying action preconditions and effects for each problem domain.Automatically generating this domain description is left as a separate research question.
  • C. Large Language Model + Classical Planner (LLM+P): The LLM infers a new problem’s PDDL file from its natural-language description using in-context learning.The domain PDDL remains fixed while task-specific entities and facts are represented in the generated problem PDDL.
  • C. Large Language Model + Classical Planner (LLM+P): A classical planner receives the generated problem PDDL and the provided domain PDDL, then produces a PDDL plan.The LLM subsequently translates that plan into natural language or connects it to robot action executors.
  • C. Large Language Model + Classical Planner (LLM+P): LLM+P requires a robot to recognize when to trigger the method, a task-agnostic domain PDDL, and one natural-language/PDDL example pair.The domain file defines the robot’s available actions, while the generated problem file specifies task-relevant entities.

IV. RELATED WORK

Related work spans classical planning, LLM-based robot planning, and external-module augmentation, with LLM+P targeting LLMs’ limited long-horizon reasoning ability.

  • A. Classical Planning: Classical planning computes action sequences that achieve goals and commonly uses PDDL or ASP to represent planning problems.These methods have been applied to delivery robots, autonomous driving, and teams of mobile robots.
  • A. Classical Planning: Many classical planning methods require domain-specific programming languages to represent problems and solutions.LLM+P instead provides a natural-language interface while relying on classical planners’ soundness and completeness.
  • B. Large Language Models: LLMs’ zero-shot generalization has been leveraged for robot planning, including methods that extract task knowledge to decompose natural-language instructions.The related models include BERT, CodeX, GPT-3, ChatGPT, GPT-4, Llama, Llama2, and PaLM.
  • B. Large Language Models: Existing LLMs often lack long-horizon reasoning for complex tasks, producing plans that do not actually solve the task.The paper addresses this issue by leveraging classical planners.

C. Augmenting LLMs with External Modules

External modules can improve LLM downstream performance, and this work proposes classical planners as a tool for adding planning capability without retraining.

  • C. Augmenting LLMs with External Modules: External modules have been combined with LLMs to improve downstream tasks through web knowledge, search, memory, retrieval, calculators, and tool APIs.Examples include WebGPT, MemPrompt, REPLUG, and ToolFormer.
  • C. Augmenting LLMs with External Modules: LLM+P uses classical planners as an external module without fine-tuning or retraining the LLM.The proposed augmentation is intended to incorporate long-horizon reasoning and planning capabilities into existing LLMs.
  • C. Augmenting LLMs with External Modules: Unlike the concurrent SayCan-PDDL work, the paper characterizes LLM+P as a broader investigation because SayCan contains only three predefined actions and may permit infeasible plans.The paper reports approximately 90% success for all evaluated SayCan model variants on that homogeneous dataset.
  • C. Augmenting LLMs with External Modules: The experiments examine direct LLM planning, LLM+P relative performance, the role of context, and efficiency on realistic service-robot tasks.The authors summarize the expected answers as poor direct LLM planning, much better LLM+P performance, crucial context, and improved efficiency.
  • C. Augmenting LLMs with External Modules: The paper presents seven robot planning domains from past International Planning Competitions and 20 automatically generated tasks per domain.The domains include scenarios such as block rearrangement, cocktail preparation, floor tiling, and tire replacement.
  • C. Augmenting LLMs with External Modules: Each benchmark problem has a natural-language description and ground-truth problem PDDL, while each domain supplies an example problem, PDDL file, and plan description as context.A domain PDDL file is assumed to be provided by a user or domain expert before solving problems in that domain.

B. Experiment Setup

The experiments compare direct LLM planning and Tree of Thoughts against LLM+P across seven domains, using GPT-4, FAST-DOWNWARD, and a 200-second limit. LLM+P produces optimal plans for most problems, whereas direct approaches commonly produce infeasible plans; correct PDDL generation depends on context.

  • Experiment Setup: Experiments compare LLM-AS-P, Tree of Thoughts, and LLM+P across seven planning domains.GPT-4 generates PDDL deterministically, and FAST-DOWNWARD searches with optimal and sub-optimal aliases under a 200-second limit.
  • Results and Analysis: LLM-AS-P produces natural-language plans for every problem, but most plans are not feasible because it fails to reason about preconditions.Its failures include mishandling object properties, cleaning requirements, and spatial constraints.
  • Results and Analysis: Tree of Thoughts often ranks partial plans reasonably but fails to recognize goal achievement and times out on most long-horizon problems.The method requires repeated LLM calls at each tree node and for each path evaluation.
  • Results and Analysis: LLM+P produces an optimal plan for the majority of problems, with most failures caused by mis-specified problem files.Examples include missing initial conditions that leave FLOORTILE instances unsolvable.
  • Results and Analysis: Without an example problem and corresponding PDDL, LLMs fail to produce correct problem PDDL files, making context crucial for LLM+P.The experiments therefore evaluate both contextualized and non-contextualized variants.

D. Robot Demonstration

LLM+P was deployed on a real robot to solve a home tidying task involving a mustard bottle and an empty soup can. It found an optimal route that combines both errands efficiently, outperforming the direct LLM baseline.

  • Robot Demonstration: The real robot must move a mustard bottle from the coffee table to the pantry and discard an empty soup can from the side table.The task is specified in natural language and converted into a PDDL problem with locations, objects, initial state, goals, and a cost metric.
  • Robot Demonstration: 22 is the optimal total cost for taking the bottle to the side table, discarding the soup can, re-grasping the bottle, and continuing to the pantry.The side table and recycle bin lie along the route from the coffee table to the pantry.
  • Robot Demonstration: 31 is the sub-optimal total cost of the direct LLM plan, which reaches the pantry before returning for the soup can.Figure 2 depicts the optimal sequence of pickups, navigation, disposal, re-grasping, and placement.

VI. CONCLUSION AND FUTURE WORK

The paper proposes LLM+P as a way to combine LLM translation abilities with classical planners’ optimal planning capabilities. It emphasizes demonstration context and identifies automation and reduced human information requirements as future directions.

  • Conclusion and Future Work: LLM+P focuses the LLM on translating natural-language planning problems into structured PDDL, then uses classical planners to solve them.A simple problem–PDDL demonstration is also provided for in-context learning.
  • Conclusion and Future Work: The framework is proposed to empower LLMs with optimal planning capabilities while retaining the use of classical planners.The paper highlights context as an important design choice for making the translation work.
  • Conclusion and Future Work: Future work includes enabling automatic detection of when to apply LLM+P and reducing its dependency on information supplied by humans.The paper suggests finetuning as one possible route for reducing this dependency.
Loading 2304.11477v3…