Source-linked AI summary
Generalized Planning in PDDL Domains with Pretrained Large Language Models
Tom Silver, Soham Dan, Kavitha Srinivas, Joshua B. Tenenbaum, Leslie Pack Kaelbling, Michael Katz
TL;DR
The paper asks whether pretrained LLMs can synthesize efficient generalized planners from PDDL domains and a few training tasks. It uses GPT-4 to generate Python planning programs, with CoT summarization and automated debugging, and finds strong generalized-planning performance across seven domains, alongside important effects from debugging, PDDL names, and model choice.
Problem
The paper asks whether pretrained LLMs can synthesize a domain-specific program that efficiently produces plans for unseen tasks from a small number of training tasks.
Method
GPT-4 receives a PDDL domain and training tasks, proposes a strategy through CoT summarization, synthesizes a Python planner, and receives automated debugging feedback when validation fails.
Results
GPT-4 with CoT summarization and automated debugging is a strong generalized planner in seven PDDL domains, with strong performance in Delivery, Forest, Gripper, Ferry, and Heavy but poor performance in Miconic and Spanner.
Takeaways & Limitations
Automated debugging, PDDL names, and GPT-4 are very important, CoT has non-uniform impact, and two training tasks are often sufficient for strong generalization.
Takeaways & Limitations
A major limitation is that generalized plans can be hand-designed easily for all domains considered, limiting the challenge posed by the evaluation setting.
Abstract
from arXiv · showhide
Recent work has considered whether large language models (LLMs) can function as planners: given a task, generate a plan. We investigate whether LLMs can serve as generalized planners: given a domain and training tasks, generate a program that efficiently produces plans for other tasks in the domain. In particular, we consider PDDL domains and use GPT-4 to synthesize Python programs. We also consider (1) Chain-of-Thought (CoT) summarization, where the LLM is prompted to summarize the domain and propose a strategy in words before synthesizing the program; and (2) automated debugging, where the program is validated with respect to the training tasks, and in case of errors, the LLM is re-prompted with four types of feedback. We evaluate this approach in seven PDDL domains and compare it to four ablations and four baselines. Overall, we find that GPT-4 is a surprisingly powerful generalized planner. We also conclude that automated debugging is very important, that CoT summarization has non-uniform impact, that GPT-4 is far superior to GPT-3.5, and that just two training tasks are often sufficient for strong generalization.
Introduction
The paper asks whether pretrained LLMs can synthesize domain-specific programs for generalized planning. GPT-4 is evaluated with strategy decomposition and automated feedback, and is found to be a strong generalized planner across seven PDDL domains.
- Generalized planning seeks a single domain-specific program that efficiently solves other tasks after learning from a small number of training tasks.
- GPT-4 is prompted with a PDDL domain and training tasks to write a Python program that consumes task descriptions and outputs plans.
- The protocol extends basic synthesis with CoT domain summarization and strategy proposal before implementation.
- Automated debugging re-prompts GPT-4 with feedback when synthesized programs fail on training tasks.
- Seven PDDL domains were evaluated, with automated debugging, PDDL names, and GPT-4 especially important while CoT had non-uniform impact.
Related Work
Related work frames this study within generalized planning, LLM-based planning and code generation, while distinguishing program synthesis from generating individual plans.
- LLMs for (PDDL) Planning: LLM-based generalized planning differs from per-task planning because synthesized programs can be inspected, validated, and executed more cheaply than repeated LLM queries.
- Generalized Planning: Prior generalized-planning methods search policy spaces, construct finite-state machines from example plans, or discover programs in domain-specific representations.
- LLMs for Code Generation: The approach builds on LLM code generation and CoT techniques that ask models to outline reasoning before producing implementations.
- LLMs for Code Generation: Automated debugging relates to program repair methods that re-prompt language models using feedback from failed validation checks.
Background and Problem Setting
The paper studies deterministic, fully observed STRIPS-style PDDL tasks and defines generalized planning as synthesizing a program that produces valid plans for held-out tasks within a time budget.
- PDDL Domains and Tasks: PDDL domains contain names, types, predicates, and operators defining the available planning structure.The Delivery example includes loc and paper types, an at predicate, and pick-up, move, and deliver operators.
- PDDL Domains and Tasks: A PDDL task consists of a domain, objects, an initial state, and a goal expressed through ground atoms.States list true ground atoms while unspecified atoms are false; goals specify atoms that must hold.
- PDDL Domains and Tasks: Actions are grounded operators whose preconditions determine applicability and whose effects add or delete ground atoms.
- PDDL Domains and Tasks: Human-readable PDDL names are expected to help LLMs interpret domains even though standard planners do not require them.
- Generalized Planning in PDDL Domains: Generalized planning uses at most 10 training tasks to synthesize a program for held-out tasks, counting success when a valid plan is returned within 30 seconds.The objective is satisficing rather than optimal planning, with primary concern on planning efficiency.
Generalized Planning with LLMs
The prompting protocol decomposes generalized planning into domain understanding, strategy proposal, and Python implementation, then validates and iteratively debugs the resulting program on training tasks.
- Domain Summarization: The LLM first receives a PDDL domain and example training problems and writes a short natural-language domain summary.
- Domain Summarization: Only two training tasks are always shown, with large object sets and initial states truncated to fit the context window.The protocol aims to communicate the gist of the task distribution rather than complete tasks.
- Strategy Proposal: The LLM is then asked for a generalized strategy that solves the domain without search.Omitting the phrase “without using search” often led to search-based proposals in preliminary experiments.
- Strategy Implementation: The proposed strategy is implemented as a Python get_plan function mapping objects, initial atoms, and goal atoms to a list of grounded action strings.
- Automated Interactive Debugging: Training-task validation checks outputs for exceptions, timeouts, syntax errors, and semantic plan validity, then feeds failures back to the LLM.
- Automated Interactive Debugging: Debugging responses are appended to a growing Python file and the validation-feedback cycle repeats up to four times.Full tracebacks can improve performance, while nearly all observed timeouts were attributed to logic errors rather than correct but slow implementations.
Experiments and Results
The experiments evaluate nine generalized planning approaches across seven PDDL domains, testing GPT-4's efficiency, debugging, prompting, model, and data-efficiency properties. GPT-4 performs strongly in several domains, scales favorably against Fast Downward, and benefits substantially from automated debugging, while CoT and domain names have mixed and important effects.
- Experimental setup: Nine generalized planning approaches are evaluated on seven PDDL domains over 10 random seeds, with randomly generated tasks for each seed.The evaluation includes the main GPT-4 approach, four ablations, and four baselines.
- Main results: GPT-4 performs strongly in Delivery, Forest, Gripper, Ferry, and Heavy, but poorly in Miconic and Spanner.Its strong Heavy performance is notable because generalized-planning baselines cannot represent the required “heaviest overall” concept with lifted decision lists.
- Program efficiency: Synthesized programs scale favorably and consistently beat Fast Downward in absolute runtime by large margins.The programs can go directly from task to plan without operator grounding, which is often Fast Downward's bottleneck.
- CoT summarization: CoT summarization has mixed effects: it helps in most cases but hurts in Miconic and Heavy by influencing the strategy GPT-4 implements.In Miconic, CoT often induces a sweep strategy requiring a floor ordering, whereas No CoT often uses a simpler passenger-by-passenger strategy.
- Automated debugging: Automated debugging generally improves performance dramatically, with substantial gains after one step and diminishing marginal improvements thereafter.Python exceptions are most common, followed by plan-semantic errors, plan-syntax errors, and timeouts; each feedback type appears beneficial.
- Ablations and data efficiency: Performance without PDDL names is overall very poor, GPT-3.5 performs much worse than GPT-4, and two training tasks are sufficient in the vast majority of successful cases.Evaluation performance is typically all-or-nothing, with overfitting to training tasks being very rare.
Discussion and Future Work
The paper frames GPT-4-based generalized planning as promising but bounded by domain complexity and limited task examples. It identifies planner integration and automatic detection of simple-program domains as future directions.
- Hand-designing generalized plans remains easy for every evaluated domain, limiting the challenge addressed by this work.
- A few training tasks may not fully express the task distribution of interest to the LLM.The paper suggests natural language or procedural-generation representations as alternatives, but they require more human input.
- Planning remains essential for domains where no simple generalized program exists.
- Providing a PDDL planner could help an LLM generate targeted example plans for generalized planning.Naively generated examples may confuse the LLM, whereas diverse or targeted plans could be useful.
Additional Results
Additional results show strong data efficiency and typically all-or-nothing generalization across evaluation tasks. In most successful trials, GPT-4 needs only two training tasks.
- GPT-4 typically either solves all evaluation tasks or solves none, indicating rare overfitting to training tasks.Table 3 reports the maximum fraction of evaluation tasks solved over seeds.
- In the vast majority of cases, GPT-4 needs only two training tasks for successful generalized planning.Figure 4 reports fractions over all trials and domains.
Example Programs
The paper presents GPT-4-synthesized programs for several PDDL domains, including successful programs for Delivery, Forest, Gripper, Ferry, and Heavy, alongside failures for Miconic and Spanner.
- Delivery and Forest: GPT-4 synthesized successful programs for Delivery and Forest that parse initial or goal locations and generate movement actions toward target locations.The Delivery program identifies locations and appends a move to a requested safe location; the Forest program repeatedly follows adjacent trails and climbs hills when necessary.
- Gripper: The Gripper program groups balls, rooms, and grippers, then moves, picks, and drops each ball at its goal location.It extracts typed objects and tracks ball locations before appending move, pick, and drop actions.
- Miconic: The Miconic program organizes floors and passengers by building, transports the lift through floors, and boards or departs passengers, but the synthesized example is marked as a failure.Its code uses origin, destination, and lift-at facts while traversing floors in forward and reverse order.
- Ferry: The Ferry program iterates over cars, sails to each car’s initial and goal locations, boards the car, and debarks it at the destination.The program tracks the ferry location and conditionally appends sail actions before boarding and debarking.
- Spanner: The Spanner program selects the nearest spanner, walks Bob to it and the gate, tightens one nut, and removes the used spanner from availability; the example is marked as a failure.It computes distances and paths from the initial state before generating walk, pickup, and tightening actions.
- Heavy: The Heavy program extracts heavier-than relations, sorts objects by weight, packs the first object, and stacks the remaining objects sequentially.Sorting repeatedly selects an object with no heavier object remaining among the unsorted objects.