PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Planning Abilities of Large Language Models : A Critical Investigation

Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, Subbarao Kambhampati

arXiv:2305.15771v2cs.AI

TL;DR

The paper asks whether web-trained LLMs can plan effectively on their own and whether they can help external planners and verifiers. It systematically evaluates autonomous and LLM-Modulo modes on generated planning instances. Autonomous executable-plan generation is poor, while LLM-generated plans and verifier feedback are useful in assisted settings.

  • Problem

    The paper investigates whether LLMs can generate executable commonsense plans autonomously and provide useful heuristic guidance to external planners and verifiers.

  • Method

    The authors generate planning instances based on International Planning Competition domains and evaluate LLMs in autonomous and LLM-Modulo modes with automated planning tools.

  • Results

    Autonomous performance is poor, while LLM-generated plans reduce LPG search steps and verifier feedback improves plan correctness through repeated back-prompting.

  • Takeaways & Limitations

    LLMs perform poorly as standalone planners but can provide useful guidance to sound planners and can improve through external verifier feedback.

  • Takeaways & Limitations

    The verifier-assisted logistics evaluation includes only instances solvable in fewer than 550 search steps.

Abstract

from arXiv · show

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

1 Introduction

This paper systematically investigates whether LLMs can generate executable plans autonomously and whether they can provide useful heuristic guidance to external planners and verifiers. It contrasts limited standalone planning performance with more promising assisted settings.

  • Research questions: The study asks how effectively LLMs generate simple commonsense plans autonomously and how useful they are as heuristic guidance in LLM-Modulo settings.The questions target both standalone plan correctness and assistance to other planning agents.
  • Motivation: The authors hypothesize that LLMs may produce plausible suggestions across domains without guaranteeing correctness, unlike sound planners operating in narrower domains.This distinction is linked to LLM pattern-finding abilities rather than first-principles simulation over world models.
  • Evaluation design: The evaluation uses a systematically generated suite of planning instances based on domains employed in the International Planning Competition, with automated planning tools for evaluation.This design replaces subjective assessment with automated evaluation of generated plans.
  • Main findings: 12%: GPT-4’s average share of generated plans that are executable without errors and reach their goals in autonomous evaluation.The study tests multiple GPT-family models and examines effects of model choice, fine-tuning, obfuscation, and relaxed executability conditions.
  • Main findings: LLM-generated plans reduce the average search steps required by LPG relative to empty-plan and random-plan seeds.The result indicates that generated plans can provide useful guidance even when they are not independently guaranteed correct.
  • Main findings: External verifier feedback followed by repeated back-prompting improves the correctness of LLM-generated plans in commonsense domains.VAL identifies plan errors and supplies feedback for subsequent generation.

2 Related Work

The related work situates LLM planning within broader studies of reasoning and distinguishes executable, domain-specified evaluation from human-mediated prompting and unconstrained commonsense tasks.

  • Prior LLM planning evaluations: Earlier commonsense evaluations often omit domain information and rely on human judgment, making plausible but non-executable plans difficult to assess.SayCan instead filters or interprets LLM plans against actions available to an executor.
  • Evaluation setting: This paper supplies the domain in the prompt, following standard automated-planning practice, and evaluates zero-shot and few-shot plan generation.The approach is intended to make generated plans directly evaluable against a specified planning domain.
  • Evaluation setting: The authors separate autonomous evaluation from assistance to external planners or reasoners to avoid Clever Hans effects in which humans may perform the actual planning.Incremental human interaction and reprompting are identified as vulnerable to this problem.
  • Planning and reasoning research: Prior planning research treats planning as inference over world and reward models, while broader LLM studies investigate commonsense, logical, and ethical reasoning.The paper focuses on whether web-trained LLMs already possess planning abilities.

3 Prompt Generation for Classical Planning Problems

The paper frames experiments in classical planning and constructs prompts from PDDL domains using natural-language or PDDL presentations, zero- or one-shot examples, and state-tracking variants.

  • 3.1 Background: Classical planning defines a domain, initial state, and goal state, with actions specified by preconditions and add and delete effects.A valid plan is an action sequence that transforms the initial state into one satisfying the goal conditions.
  • 3.2 Prompt Generation: Four configurations combine natural-language or PDDL presentation with zero-shot or one-shot prompting.The configurations vary both how the domain is presented and whether an example problem and plan are supplied.
  • 3.2 Prompt Generation: Each prompt begins with a lifted domain description and ends with a planning problem; one-shot prompts additionally include an example instance and plan-end tag.Generated text up to the tag is extracted as the candidate plan, and unextractable instances are marked incorrect.
  • 3.2 Prompt Generation: Table 1 reports natural-language plan-generation results for GPT-4, GPT-3.5, Instruct-GPT3.5, Instruct-GPT3, and GPT3.The table compares the listed GPT-family models on the plan-generation task.
  • 3.2 Prompt Generation: Natural-language prompts describe actions and initial conditions in complete sentences, whereas PDDL prompts encode domains, states, goals, and plans in PDDL.Natural-language plans use commands such as stacking one block on another.
  • 3.2 Prompt Generation: A fifth experiment uses state-tracking chain-of-thought prompting in a natural-language one-shot setting, annotating actions with prior states, applicability reasons, and resulting states.
  • 3.2 Prompt Generation: The prompt-generation pipeline accepts PDDL domain files and outputs experiment-specific prompts, generating planning problems and adding valid examples when needed.A planner is used during example generation, although other techniques could generate valid plans.

4 Evaluating Planning Capabilities of LLMs in Autonomous Mode

The autonomous evaluation tests LLM-generated plans against external validation across classical-planning domains and prompt configurations. GPT-4 outperforms earlier GPT models, but performance remains weak and is highly sensitive to names, examples, and domain presentation.

  • Evaluation setup: The evaluation translates LLM outputs into plans and uses external validators to assess whether they execute correctly and reach the goals.The autonomous mode treats the LLM as an automated planner and evaluates translated plans with VAL.
  • Overall performance: GPT-4 improved over earlier GPT models across all four prompt configurations, but overall Blocksworld performance remained approximately 34%.Chain-of-thought prompting had little effect, while natural-language prompts outperformed PDDL prompts for GPT-4.
  • Other models: BLOOM solved 4 of 250 Blocksworld instances, a 1.6% success rate, and solved none of 50 deceptive Mystery Blocksworld instances.This was measured with one-shot natural-language prompts.
  • Human baseline: Human participants produced valid plans for 39 of 50 Blocksworld instances, with 35 of those 39 plans also optimal.The study used instances drawn from the same 600-instance evaluation set.
  • Overall performance: GPT-4 solved 14% of natural-language instances with one-shot prompting and 7.5% with zero-shot prompting.These correspond to 28/200 and 15/200 instances, respectively.
  • Robustness to obfuscation: Obfuscating domain names reduced GPT-4 performance from 210 solved Blocksworld instances to 1 in deceptive Mystery Blocksworld and 0 in the randomized mystery domain.The corresponding PDDL results were 106 solved Blocksworld instances versus 3 in deceptive Mystery Blocksworld.

5 Evaluating LLMs as Idea Generators

The LLM-Modulo evaluation uses LLM plans as candidate guidance for sound planners and verifiers rather than requiring standalone correctness. LLM seeds reduce search effort in some domains, while verifier feedback substantially improves repeated plan generation in domains with recognizable commonsense patterns.

  • 5.1 LLM Plans as Heuristics to Sound Planners: LLM-generated plans can serve as seed plans for LPG, a local-search planner that repairs flaws until it finds a correct plan.The approach tests whether an LLM suggestion can guide the search of an underlying sound planner.
  • 5.1 LLM Plans as Heuristics to Sound Planners: Approximately 50% of each final plan retained elements of the initial LLM seed plan across domains.The reported edit distances were approximately half the seed-plan length.
  • 5.1 LLM Plans as Heuristics to Sound Planners: GPT-4 seeds significantly reduced LPG search steps versus empty and random seeds in Blocksworld and Logistics, but assistance weakened in deceptive Mystery Blocksworld.In Mystery Blocksworld, GPT-4 used more steps than the empty plan and achieved only a meager reduction over the random plan.
  • 5.2 Verifier-assisted repeated backprompting of LLMs: Verifier-assisted backprompting uses VAL to identify plan faults and feeds that feedback back to GPT-4 for repeated plan generation.The experiment allowed up to 15 backprompting rounds on failed instances from three domains.
  • 5.2 Verifier-assisted repeated backprompting of LLMs: GPT-4 produced correct plans for 82% of Blocksworld instances and 70% of Logistics instances under verifier-assisted backprompting.Successful cases required an average of 3.68 feedback rounds for Blocksworld and 3.31 for Logistics.
  • 5.2 Verifier-assisted repeated backprompting of LLMs: Backprompting remained poor on deceptive Mystery Blocksworld, where GPT-4 could not perform well without inferring commonsense patterns from domain names.The paper contrasts this automated verifier loop with human prompting, which can raise Clever Hans concerns.

6 Conclusion and Future Work

The paper finds that LLMs perform poorly as autonomous planners but can support sound planners and improve through verifier feedback.

  • LLMs such as GPT-3 perform poorly even in simple commonsense planning domains where humans can readily devise plans.
  • GPT-4 improves in Blocksworld but still fails substantially in Mystery Blocksworld, suggesting difficulty with abstract reasoning.
  • LLM-generated plans can improve the search process of sound planners such as LPG.
  • External verifiers can identify plan errors and back-prompt LLMs to generate better plans in commonsense domains.

A.1 Classical Planning Problem Formulation

Classical planning represents a problem through its domain, initial state, and goal, with actions governed by preconditions and effects over a predicate-defined state space.

  • A classical planning problem is represented as P = ⟨D, I, G⟩, comprising a domain, initial state, and goal specification.
  • The domain contains fluents defining the state space and actions that can be performed.
  • Each action has parameters, preconditions describing when it is executable, and effects describing the resulting state changes.
  • In Blocksworld, picking up a block requires it to be clear, on the table, and held with an empty arm.
  • The pickup action makes the agent hold the block while removing its clear, on-table, and arm-empty predicates.
  • The planning formalism can be extended with object typing, complex preconditions, conditional effects, and richer formalisms.

A.2 Comparisons between the instances and plans generated by GPT-4

The study compares instance difficulty with GPT-4 success and reports that conventional planning complexity does not predict LLM performance.

  • The study examines Blocksworld and Logistics instances by optimal plan length and GPT-4’s number of correct plans.
  • For LLMs, easier and harder instances under traditional planning complexity appear equivalent because generation depends on token weights and context.
  • Figure 4 compares Blocksworld instances with those where GPT-4 generated correct plans using PDDL or natural-language prompts with one example.

A.3.1 LLM failures

Relaxing plan assessment increases the number of goal-reaching GPT-4 plans, but non-goal-reaching or inexecutable plans remain in the relaxed settings.

  • In Mystery Blocksworld, relaxed assessments increase goal-reaching plans, yet many plans remain non-goal-reaching even under Delete+Precondition Relaxation.
  • In Logistics, progressively relaxed assessments also increase goal-reaching plans, while the most relaxed configuration still contains non-goal-reaching plans.
  • Figure 5 compares Blocksworld instances with GPT-4 successes under PDDL or natural-language prompts without examples.
  • Figure 6 compares Logistics instances with those where GPT-4 generated correct plans using prompts with one example.

A.3.2 Human failures

In the human baseline user study, 11 of 50 participants failed to produce a valid plan. Every failed plan was inexecutable.

  • 11 of 50 participants failed to come up with a valid plan.
  • All 11 failed participants produced inexecutable plans.
  • The reported human baseline therefore distinguishes invalidity through plan inexecutability.

A.4 Blocksworld Prompts in Natural Language

The Blocksworld experiments describe action constraints and compare GPT-4 prompting styles, including one-shot, zero-shot, and state-tracking plans. The examples show both successful plans and a state-tracking plan judged valid despite extra actions.

  • A.4.1 Domain description: Blocksworld requires arranging blocks into stacks using pickup, unstack, put-down, and stack actions.
  • A.4.1 Domain description: Actions are constrained by hand occupancy, block location, and whether blocks are clear or supporting other blocks.
  • A.4.2 One-shot prompt with GPT-4 plan: GPT-4’s one-shot example contains six extracted actions, whereas the ground-truth plan contains four actions and is marked successful.
  • A.4.2 One-shot prompt with GPT-4 plan: The one-shot examples specify initial conditions and goals before asking GPT-4 to produce a plan.
  • A.4.3 Zero-shot prompt with GPT-4 plan: The zero-shot example asks only for actions and produces a four-action plan matching the ground truth, which is marked successful.
  • A.4.3 Zero-shot prompt with GPT-4 plan: The zero-shot example’s ground-truth sequence is unstack, put-down, pick-up, and stack, ending in success.
  • A.4.4 State-tracking prompt with GPT-4 plan: State-tracking prompting records the current state, selected action, precondition-based reason, and resulting state after execution.
  • A.4.4 State-tracking prompt with GPT-4 plan: The state-tracking example declares its plan valid after checking sequential executability and final goal satisfaction, although its extracted plan includes extra actions.

A.5 Mystery Blocksworld Prompts in Natural Language

Mystery Blocksworld uses obfuscated action semantics and tests GPT-4 with one-shot, zero-shot, and state-tracking prompts. The examples include failed one-shot and zero-shot plans alongside a state-tracking plan marked valid.

  • A.5.1 Domain description (Deceptive Disguising): Mystery Blocksworld defines actions including Attack, Feast, Succumb, and Overcome over objects and relational predicates.
  • A.5.1 Domain description (Deceptive Disguising): The action rules specify preconditions and add-delete effects involving Province, Planet, Pain, Harmony, and Craves relations.
  • A.5.2 One-shot prompt with GPT-4 plan (Deceptive Disguising): The one-shot GPT-4 example produces a five-action extracted plan, while the listed ground-truth plan is marked failure.
  • A.5.2 One-shot prompt with GPT-4 plan (Deceptive Disguising): The one-shot task states initial facts and a goal requiring object c to crave object b.
  • A.5.3 Zero-shot prompt with GPT-4 plan (Deceptive Disguising): The zero-shot GPT-4 example also produces a five-action extracted plan followed by a ground-truth plan marked failure.
  • A.5.4 State-tracking prompt with GPT-4 plan: The state-tracking example evaluates actions by checking their preconditions against successive states and records resulting states after execution.
  • A.5.4 State-tracking prompt with GPT-4 plan: The reported state-tracking trace reaches a final state satisfying object c craves object b, and the plan is declared valid.
  • A.5.4 State-tracking prompt with GPT-4 plan: In one state-tracking trace, Succumb changes pain object b into harmony and restores province and planet facts.

A.6 Logistics Prompts in Natural Language

The Logistics experiments model package transport through trucks within cities and airplanes between cities, then compare GPT-4 one-shot and zero-shot plans. The examples include a successful one-shot plan and a failed zero-shot plan.

  • A.6.1 Domain description: Logistics planning transports packages within cities by truck and between cities by airplane.
  • A.6.1 Domain description: The domain provides loading, unloading, driving, and flying actions for packages, trucks, and airplanes.
  • A.6.1 Domain description: Truck movement requires the truck and both locations to be in the same city, while airplane movement connects cities through airports.
  • A.6.2 One-shot prompt with GPT-4 plan: The one-shot GPT-4 example produces a three-action airplane plan that exactly matches the ground-truth plan and is marked successful.
  • A.6.2 One-shot prompt with GPT-4 plan: The one-shot task supplies airport, vehicle, package, and city-location facts together with a package-delivery goal.
  • A.6.3 Zero-shot prompt with GPT-4 plan: The zero-shot logistics prompt explicitly repeats action examples and movement restrictions before requesting a plan.
  • A.6.3 Zero-shot prompt with GPT-4 plan: GPT-4’s zero-shot response contains a ten-action extracted plan involving trucks and airplanes, whereas the ground-truth plan is marked failure.
  • A.6.3 Zero-shot prompt with GPT-4 plan: The zero-shot example’s listed plan and ground truth differ in both action sequence and outcome, with the ground truth marked failure.

A.7 Blocksworld Prompts in PDDL

The appendix specifies PDDL prompts and illustrates GPT-4 planning behavior across Blocksworld, disguised Mystery Blocksworld, and Logistics examples. The examples include both successful and failed plans, alongside broader safety and bias considerations for using LLMs in planning.

  • A.7.1 Domain description: The Blocksworld domain uses STRIPS predicates and four actions whose preconditions and effects govern unstacking, putting down, picking up, and stacking objects.The domain description defines predicates including clear, ontable, handempty, holding, and on.
  • A.7.2 One-shot prompt with GPT-4 plan: One-shot prompts provide a Blocksworld example problem and plan before asking GPT-4 to solve a query problem.The prompt includes the BW-rand-4 problem, a four-action example plan, and a separate query problem.
  • A.7.2 One-shot prompt with GPT-4 plan: GPT-4’s one-shot Blocksworld response fails because it un-stacks a and b, whereas the ground-truth plan must first un-stack d and c.The extracted response and ground-truth plan differ in the initial action sequence, and the example is marked FAILURE.
  • A.7.3 Zero-shot prompt with GPT-4 plan: Zero-shot Blocksworld prompting omits the example plan and asks GPT-4 to output only PDDL action syntax for the query problem.In the shown instance, GPT-4 generates the same four-action plan as the ground truth, marked SUCCESS.
  • A.8.1 Domain description (Deceptive Disguising): The Mystery Blocksworld domain disguises ordinary planning predicates and actions with names such as province, planet, harmony, pain, and craves.Its one-shot and zero-shot examples show GPT-4 producing plans marked FAILURE, including a failure to achieve the requested craves relation.
  • A.8.2 One-shot prompt with GPT-4 plan (Deceptive Disguising): In the disguised domain, both one-shot and zero-shot GPT-4 examples fail to match the ground-truth plans for their query problems.The one-shot response begins with (feast a b), while the ground truth begins with (feast d c); the zero-shot response also differs from its ground truth.
  • A.9.1 Domain description: The Logistics examples test transporting packages by airplane, but GPT-4 produces plans that use the wrong airplane or omit required actions compared with ground truth.The one-shot and zero-shot examples are both marked FAILURE, while a separate logistics example is marked SUCCESS.
  • A.13 Broader Impact on using LLMs for planning: LLM-generated plans can raise safety concerns and should be verified by an automated verifier or a human verifier in the loop.The appendix also notes that a carefully scrutinized domain model can reduce default culturally biased plans.
Loading 2305.15771v2…