GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models

Andrew Murray; Danial Dervovic; Alberto Pozanco; Michael Cashmore

cs.AIMar 10, 2026

GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models

Authors: Andrew Murray, Danial Dervovic, Alberto Pozanco, Michael Cashmore

Organizations: J.P. Morgan AI Research

Abstract

We present GenePlan (GENeralized Evolutionary Planner), a novel framework that leverages large language model (LLM) assisted evolutionary algorithms to generate domain-dependent generalized planners for classical planning tasks described in PDDL. By casting generalized planning as an optimization problem, GenePlan iteratively evolves interpretable Python planners that minimize plan length across diverse problem instances. In empirical evaluation across six existing benchmark domains and two new domains, GenePlan achieved an average SAT score of 0.91, closely matching the performance of the state-of-the-art planners (SAT score 0.93), and significantly outperforming other LLM-based baselines such as chain-of-thought (CoT) prompting (average SAT score 0.64). The generated planners solve new instances rapidly (average 0.49 seconds per task) and at low cost (average $1.82 per domain using GPT-4o).

Figures & tables

Figure 1: Figure showing architecture of GenePlan. Python planners are stored in the planner_db . The right loop (1-9) generates new candidate planners, while the left loop (10-11) prunes low scoring candidates at the end of each generation. After running, the best planner can be extracted by querying the planner_db (12)

Figure 2: Evolutionary prompt template.

	domain	heavypack	hiking	manyferry	manygripper	manymiconic	research	trading	trapnewspapers
method	metric
fd_300	% Solved	100.0	100.0	100.0	100.0	100.0	90.0	43.33	83.33
	Runtime	21.19 $\pm$ 2.05	5.45 $\pm$ 0.27	18.69 $\pm$ 4.20	63.57 $\pm$ 13.28	22.86 $\pm$ 5.55	83.48 $\pm$ 12.57	219.94 $\pm$ 15.79	71.69 $\pm$ 16.64
	Score	1.00 $\pm$ 0.00	0.89 $\pm$ 0.05	0.93 $\pm$ 0.01	0.94 $\pm$ 0.01	0.98 $\pm$ 0.00	0.90 $\pm$ 0.06	0.43 $\pm$ 0.09	0.64 $\pm$ 0.05
fd_1800	% Solved	100.0	100.0	100.0	100.0	100.0	100.0	93.33	86.67
	Runtime	10.04 $\pm$ 0.89	2.73 $\pm$ 0.09	110.76 $\pm$ 49.71	88.17 $\pm$ 27.73	49.12 $\pm$ 18.65	31.87 $\pm$ 4.28	394.48 $\pm$ 50.64	216.66 $\pm$ 30.44

Table 1: Performance comparison across different methods and domains

Figure 3: Critical difference diagram showing average rank per method across all problem instances. Lower ranks (left) are better and the horizontal lines connecting approaches indicate statistical indistinguishability.

Domain	$k$
trading	1.66
trapnewspapers	1.83
manyferry	5.52
manygripper	8.5
manymiconic	14.39
research	30.01

Table 2: Minimum number of instances

k

required for LLM-based planner to be more efficient than fd_1800 per domain.

Figure 4: Normalized score

\hat{f}(\Phi^{*}_{t})/\hat{f}(\Phi^{*})

versus generation

t

\hat{f}(\Phi^{*})

is the optimal average plan length found by Fast Downward on the training tasks (or best found within 1 hour for domains labelled +), and

\hat{f}(\Phi^{*}_{t})

is GenePlan’s current incumbent solution.

Symbolic Planning

Symbolic planning represents goals, states, and actions explicitly, then searches for action sequences that satisfy constraints.

See all 89 papers

Provably Complete Generalized Planning with LLMs
Sep 22, 2026Katharina Stein, Chaahat Jain, Jörg Hoffmann +1LLM Planning Symbolic Planning
Saarland Informatics Campus, Saarland University, Saarbrücken, Germany · German Research Center for Artificial Intelligence (DFKI), Saarbrücken, Germany
LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs
Oct 6, 2026André G. Pereira, Augusto B. Corrêa, Felipe Meneguzzi +1Automated Heuristic Design LLM Planning
Federal University of Rio Grande do Sul Brazil · University of Oxford United Kingdom · University of Aberdeen United Kingdom +1
GRASP: Generating, Revising, and Assessing for Strategic Planning with Agentic AI
Sep 24, 2026Arunabh Srivastava, Mohammad A., Khojastepour +2LLM Planning
Amir · NEC Laboratories America, Inc. · University of Maryland, College Park, MD

Sep 22, 2026J/K move · Enter open · S save

Provably Complete Generalized Planning with LLMs

Katharina Stein, Chaahat Jain, Jörg Hoffmann, Alexander Koller

Saarland Informatics Campus, Saarland University, Saarbrücken, Germany · German Research Center for Artificial Intelligence (DFKI), Saarbrücken, Germany

LLM Planning Symbolic Planning

Open paper AskPDF arXiv

Generalized planning aims to compute a plan that solves all instances of a planning domain. Recent work has used LLMs to automatically generate and debug such generalized plans in the form of Python programs and achieved perfect test data coverage for several domains. However, whether these generalized plans are actually complete, i.e. solve all instances of the domain, could only be determined by manual evaluation. Here, we present an approach for automatically generating generalized plans in Lean together with proofs of their completeness relative to a specification of the domain constraints provided as input. We introduce a semantic-preserving PDDL-to-Lean conversion, and use an LLM to generate both the generalized plan and the formal proof that it solves every instance satisfying the domain constraints. The correctness of the completeness proof is determined by Lean's kernel. We evaluate our approach on 13 commonly used benchmark domains, using GPT-5.6-Sol as the LLM. For 12 of the domains we obtain generalized plans together with valid completeness proofs. This is a major advancement of the state of the art in automatic generalized-plan completeness proofs.

Abstract

Symbolic Planning

Explore similar work

Provably Complete Generalized Planning with LLMs

LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs

GRASP: Generating, Revising, and Assessing for Strategic Planning with Agentic AI