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

In plain words

Language models are good at reading and writing text but often fail when a task needs a long chain of correct steps, such as stacking blocks in the right order. The paper's answer is to let the model do only what it is good at: turn the problem, written in English, into a formal problem file. A classical planner, which is a search program that is guaranteed to find correct action sequences, then does the hard part of finding the plan.

To show the model what such a file looks like, the method gives it one small example: a short description of a problem together with its formal version. The model writes the formal file for the new problem in the same style, the planner solves it, and the paper's design then has the model turn the plan back into English. The authors test this on seven planning domains and report that the planner-based approach solves far more problems than the language model does on its own.

The approach needs a formal description of the allowed actions for each domain, written once by a person. It only works where a planner can handle the domain, and the model still has to write a correct problem file. A wrong problem file is the main cause of failure the authors report.

TL;DR

LLM+P makes GPT-4 write a PDDL problem file from a natural-language task, using one in-context example, and gives that file to the Fast Downward planner §3.3 §5.2. The authors report optimal-alias success of 90% on Blocksworld, 95% on Grippers, 85% on Storage and 0% on Floortile tab. 1. Without the example, the same pipeline scores 0 in every domain tab. 1. The paper's own cases show that a wrong or missing initial condition in the generated file is the main failure §5.3.

Problem

Language models produce plausible text but cannot reliably produce correct plans for long-horizon tasks. The introduction shows GPT-4 producing an incorrect plan for a five-block Blocksworld task §1, and the related-work section cites other studies reporting the same weakness §4. Rather than fine-tune the model, which they want to avoid §1, the authors ask whether a sound and complete solver can handle the planning itself, leaving the model to translate §1 §3.1.

Assumptions §3.3:

1. The system knows when to invoke the pipeline (the paper does not implement this; it names it as future work §1 §6).
2. A domain PDDL file (action preconditions and effects) is supplied by a person per domain and is fixed across tasks §3.3.
3. One short (description, problem PDDL) example from the same domain is available as context §3.2 §3.3.

Method

Overview. The pipeline has three stages §3.3 fig. 1:

1. The LLM writes a problem PDDL file from the new task description, conditioned on the example §3.2.
2. A classical planner, given the fixed domain file and the generated problem file, returns a plan. The authors use Fast Downward with the optimal alias seq-opt-fdss-1 §5.2 main.py.
3. The LLM rewrites the plan as natural-language steps §3.3. The released code omits this step (see Paper vs code).

LLM as PDDL writer §3.1. The authors argue that writing PDDL is a translation task, which language models handle well. Without any prompt engineering, GPT-4's problem file had valid syntax but used an invented predicate and omitted an initial fact (b1 on the table) §3.1.

In-context learning §3.2. Adding one (description, PDDL) pair to the prompt makes the generated file directly solvable in the authors' example §3.2. The paper's wording of the context is: the example description, and its problem PDDL §3.2. The paper defines in-context learning as conditioning on a few input-label pairs without changing model parameters §3.2.

Pipeline. The released planner function builds the problem prompt from the example and the new task, queries the model, writes the reply to a file, runs the planner, and keeps the cheapest plan among the plan files written main.py. The paper presents the same flow in prose §3.3.

# LLM+P pipeline  [§3.3]
# Input:  task_nl (str): new problem in natural language
#         example_nl, example_pddl (str): one (description, PDDL) pair [§3.2]
#         domain_pddl (str): fixed per domain, given to the planner [§3.3]
# Output: plan (list of actions), or None if the planner finds none

def llm_plus_p(task_nl, example_nl, example_pddl, domain_pddl):
    # Ask the LLM for the problem PDDL, conditioned on the example [§3.2]
    # [code: main.py#L324-L333]
    prompt = build_pddl_prompt(example_nl, example_pddl, task_nl)
    # Temperature 0 and top_p 1 [§5.2] [code: main.py#L349-L351]
    problem_pddl = query_llm(prompt)

    # Run the optimal planner on domain and problem [§3.3] [§5.2]
    # [code: main.py#L464-L467]
    plan_files = run_planner(domain_pddl, problem_pddl, time_limit=200)

    # Keep the cheapest plan the planner wrote [code: main.py#L469-L478]
    if not plan_files:
        return None
    plan = min(plan_files, key=plan_cost)

    # The paper then has the LLM rewrite the plan in English [§3.3];
    # the released planner leaves this out [code: main.py#L481-L488]
    return plan

Equations: the paper has no numbered equations. The planning tuple and the definition of a plan are given inline in prose §2.1.

Figures: the pipeline overview is fig. 1 (intro). The tidy-up demonstration is fig. 2 (§5.4). Figure numbers are inferred from source order.

Hyperparameters

Results

Author-reported. Setup: GPT-4 as above; 7 IPC-derived domains with 20 tasks each; Fast Downward with a 200 s limit; ToT as the LLM-based search baseline §5.1 §5.2. Hardware: not stated.

Table 1 tab. 1, success rate in %. Column meanings from the caption: LLM⁻ is the LLM writing plans directly without context; LLM is the same with context; LLM-ToT is Tree of Thoughts; LMP⁻ is LLM+P without context; LMP is LLM+P tab. 1. The table values are shown without the % sign.

Meaning of parentheses §5.2: for LLM+P, the value outside parentheses is the success rate of the optimal alias; the value in parentheses is the sub-optimal lama alias, used where the optimal alias timed out. For the baselines, the outside value counts optimal plans and the parenthesised value counts correct plans, counted by hand.

Findings reported by the authors:

• Direct LLM plans are mostly infeasible; the main reason given is that the model does not reason about preconditions §5.3.
• Without context, LLM+P produces no correct problem files and scores 0 everywhere tab. 1 §5.3.
• Where LLM+P fails, the usual cause is a mis-specified problem file, such as a missing initial condition that makes the problem unsolvable §5.3.
• Tree of Thoughts usually times out because of the number of LLM calls §5.3.
• Robot demo: LLM+P's plan costs 22, the optimal total; the direct-LLM plan costs 31 §5.4 fig. 2.

Paper vs code

Repository: https://github.com/Cranial-XIX/llm-pddl, checked at commit f5f897ccabfb19d5158e5a7ac4cb36517cd4c2e0 (2023-09-27). The paper's abstract footnote links it. The repository has no LICENSE file and GitHub reports no license, so code_license is unstated. We cite it by path and line only and do not quote it.

Differences between the paper and the code:

• Planner alias. The paper says both seq-opt-fdss-1 and lama are used, with lama results in parentheses §5.2. The released planner calls use only seq-opt-fdss-1; the lama line is commented out main.py main.py. The parenthesised LLM+P figures are therefore not produced by the released planner path.
• Back-translation. The paper says the LLM translates the plan into natural language §3.3. The released LLM+P planner writes only the raw planner output to a file, and the translation call is commented out with the note "exceeding token limit of gpt-4" main.py. The reported success rates are therefore about planner-found plans, not about English output.
• Context. The paper's context is the example description plus its problem PDDL §3.2. The code's context function also loads an example solution, but the PDDL prompt does not include it main.py main.py.
• Plan selection. The live paper text does not state a selection rule. A commented-out sentence in contents/experiments.tex (line 34) says that, with several planner solutions, the one with the fewest steps is picked. The code instead picks the lowest reported cost across all plan files written by the planner main.py main.py.
• Domain count. The paper reports seven domains §5.1. The code lists eight, including manipulation, which the paper does not describe or report main.py.
• Tree of Thoughts. The paper gives no depth or breadth §5.2. The code sets depth 10 main.py and uses fixed example scores in its value prompt main.py.
• Validation. The validator counts a task as solved if any saved plan file is marked valid, with a separate domain_validation.pddl for Tyreworld validate_plans.py validate_plans.py. It does not test optimality. The paper's optimal-success numbers rely on the optimal alias §5.2.
• Robot demo. The tidy-up domain and its PDDL are not in the repository; domains/ contains no such domain. The demo's PDDL in the paper uses a total-cost metric §5.4 fig. 2.
• Appendix. The LaTeX source has the appendix input commented out (root.tex line 190), so the appendix's example files and prompts are not in the compiled paper. This card does not cite them.

No discrepancies were found for the core loop: temperature 0, top_p 1, GPT-4, the optimal alias and the 200 s planner limit all match §5.2 main.py main.py main.py.

Pitfalls

• Silent failures. query returns an empty string after 10 failed attempts main.py, and the planner then receives an empty problem file main.py. The planner run is not checked for this, so a failed API call looks like an unsolvable task. Check reply length before writing the problem file.
• No validation before planning. The paper's own failure analysis points to malformed or incomplete problem files as the main cause §5.3. Neither the paper nor the code validates the generated PDDL against the domain before planning. Add a parse and predicate-name check, or a dry run of the planner's parser.
• Predicate names come from the example. The released PDDL prompt does not include the domain file main.py. The planner checks the plan against the domain file, so the LLM's predicate and object names must match it, and the LLM only sees them through the example. The baseline prompt in the code says "Keep the domain name consistent" main.py; the PDDL prompt does not. The paper's example failure is an invented predicate §3.1.
• One example. Results rest on one example per domain §3.2 §5.1. The paper does not vary it, so sensitivity is unknown.
• Timing. The 200 s limit covers the planner only main.py. LLM latency is outside it. Totals are not reported.
• Optimality. An optimal alias returns an optimal plan only if it finishes within the limit §5.2. Timeouts fall back to sub-optimal plans, which the table reports in parentheses.
• Cost parsing. get_cost reads the number after cost = on the last plan line and returns 1e5 when it finds none main.py. A changed planner output format silently makes every plan cost 1e5.
• Determinism. The paper calls responses deterministic at temperature 0 §5.2. The code calls a hosted model name with no snapshot id main.py, so results may change when the service updates.
• ToT cost. Each expanded node costs one candidate query plus one value query per candidate line main.py. The paper reports that this usually times out §5.3.
• Licensing. The repository has no license. Implement from the paper and the citations here, and do not copy code.

Lineage

• Builds on: classical planning with PDDL §2.2; the Fast Downward planner §3.3; in-context learning §3.2.
• Compared against: direct LLM planning, with and without context §5.2; Tree of Thoughts, adapted to breadth-first search for planning §5.2.
• Related: a concurrent use of PDDL with the SayCan dataset, which the authors say has only three actions §4.
• Superseded by: not stated in this wiki.