LLM-Evolved Pattern Generators for Optimal Classical Planning

1 Introduction

• Existing learned domain-dependent heuristics sacrifice admissibility, while A* with an admissible heuristic preserves optimal-plan guarantees.Tasks within a domain share regularities that domain-dependent heuristics could exploit.Source: §1 · p. 1
• Pattern databases project tasks onto subsets of variables, yielding admissible goal-distance estimates whose informativeness and computation cost trade off with pattern size.Collections of patterns can be combined admissibly.Source: §1 · p. 1
• The method evolves a Python generator per domain from example tasks, then applies it to new tasks with negligible test-time overhead.Saturated cost partitioning combines the generated patterns admissibly; planning performance on small training tasks guides synthesis.Source: §1 · p. 1
• Across seven optimal Autoscale domains, learned generators match or exceed the best baseline in four, lead in coverage in two, and evaluate each state substantially faster than the strongest baselines.The paper presents domain-specific pattern generation as a promising direction for optimal planning.Source: §1 · p. 1

2 Background

• Optimal classical planning seeks a minimum-cost path from the initial state to a goal in a task represented by states, actions, costs, and goal conditions.Tasks in a collection share a domain, while their initial states and goals vary.Source: §2 · p. 2
• A heuristic is admissible when it never overestimates the minimum remaining goal-path cost, preserving the optimality of A* search.The paper aims to construct accurate admissible heuristics for optimal classical planning.Source: §2 · p. 2
• A pattern projects a task onto a subset of variables, and goal distances in the abstract transition system provide admissible estimates.Pattern collections balance informativeness against the exponential growth in abstract states and combine estimates using cost partitioning.Source: §2 · p. 2
• Saturated cost partitioning greedily assigns remaining action costs across an ordered heuristic collection so their summed estimates remain admissible.The method uses a state-of-the-art configuration with standard enhancements.Source: §2 · p. 2
• OpenEvolve evolves programs scored by their outputs and characterized by behavior features, using MAP-Elites grids to retain strong programs across feature cells.Its islands migrate top-ranked programs to ring neighbors periodically; parent selection and LLM prompting draw on island programs and nearby inspirations.Source: §2 · pp. 2–3, Figure 1 · p. 3

3 Learning to Generate Pattern Collections

• A domain-specific Python generator maps task information to a pattern collection, allowing one learned program to serve tasks of different sizes.OpenEvolve improves candidate generators through LLM-guided mutation using planning performance on a small set of domain training tasks.Source: §3 · p. 3
• The combined generator score averages per-problem scores that multiply a validity indicator by one plus weighted expansion and time efficiency metrics.Valid outputs receive logarithmically scaled metrics relative to expected bounds; unsolved tasks contribute zero for both efficiency metrics.Source: §3 · pp. 3–4
• The initial prompt supplies the domain definition, required function signature, three representative training tasks, and a baseline that puts each goal atom in its own pattern.Task information includes static, initial-state, goal, and fluent atoms; each pattern is a list of ground atoms defining a PDB projection.Source: §3 · p. 4
• OpenEvolve evaluates candidate generators on training tasks in increasing difficulty, validating pattern collections before running Fast Downward and terminating early on failures.Invalid collections, syntax errors, or time or memory exhaustion mark a task unsolved and give remaining tasks a default score.Source: §3 · p. 4

4.1 Evolutionary Process

• Most score improvement occurs in the first five of 100 iterations, but refinement continues; the best generators appear at iteration 9 in Satellite and at or after 50 elsewhere.Childsnack and Transport reach their best generators at iterations 90 and 99, respectively.Source: §4.1 · p. 5, Figure 3 · p. 5

Coverage

• hevo matches or exceeds the best systematic baseline in five of seven domains, uniquely winning Childsnack and Transport and tying on Blocksworld, Rovers, and Satellite.Floortile and Miconic are the exceptions; the random-pattern ablation solves 41 tasks and never beats hevo overall.Source: Coverage · p. 5, Table 1 · p. 5
• 61/210 tasks were solved by hevo, versus 75 by hSYS3 and 74 by hSYS-SCP; excluding Miconic, hevo solves 57 versus 55 for both.The aggregate deficit comes from Miconic, where hevo solves 4 tasks while the two strongest baselines solve 20 and 19.Source: Coverage · p. 5

Expansions Before the Last f-Layer

• Against hSYS3 and hSYS-SCP, hevo needs fewer expansions on only 15/55 and 11/59 tasks, respectively, despite beating hSYS1 on jointly solved tasks.The synthesized collections trade weaker guidance than larger systematic collections for faster evaluation.Source: Expansions Before the Last f-Layer · p. 5, Figure 4 · p. 6

Total Search Time

• hevo is faster overall than hSYS3 on 54/76 tasks and hSYS-SCP on 60/78, although its per-state guidance is weaker than the strongest baselines.hSYS-SCP spends up to 100 seconds per task generating patterns, while hevo generates them at test time with negligible overhead.Source: Total Search Time · p. 6, Figure 5 · p. 6

Time per Evaluation

• On 56/75 tasks hevo evaluates states faster than hSYS3, and on 50/75 faster than hSYS-SCP.Across 40 tasks solved by all five approaches, hevo uses 1,230 patterns versus 5,998 for hSYS-SCP; fewer patterns reduce lookups per state despite larger individual patterns.Source: Time per Evaluation · p. 6

4.3 Example Pattern Collection Generators

• Miconic is the main failure case: hevo solves 4/30 tasks versus 20 for hSYS3, while systematic patterns require far fewer expansions on nearly every solved task.The paper attributes this to Miconic's uniform passenger–floor structure, which lets size-3 patterns capture key interactions.Source: §4.3 · p. 7

Pattern Database Heuristics

• Unlike domain-independent PDB methods that rediscover task structure for each instance, this work learns per-domain generators capturing regularities across tasks.Edelkamp (2006) evolves pattern collections directly, but uses a fixed encoding rather than synthesizing a generator program.Source: §5 · p. 7

Learning Heuristics for Planning

• Learned planning heuristics are typically inadmissible; N´u˜nez-Molina et al. (2024) retain inadmissibility, and Futuhi and Sturtevant (2026) enforce it only on training data.Source: §5 · pp. 7–8

Evolutionary and LLM-Guided Heuristic Search

• Edelkamp (2006) evolves collections in a fixed pattern encoding; this paper is the first application of LLM-driven synthesis to admissible heuristics for optimal planning.The approach follows LLM-guided evolution that mutates raw code rather than using restricted languages.Source: §5 · pp. 7–8

LLM-Generated Domain-Specific Solvers

• LLM-generated domain-specific heuristics can help weak planners compete, while learned policies may not scale beyond tasks admitting simple strategies.The paper's heuristic generators produce admissible heuristics that plug into a state-of-the-art planner; policy-style approaches and heuristics are described as complementary.Source: §5 · p. 8

• Across seven domains, the evolved heuristic matches or exceeds the best systematic baseline in five and is uniquely best in two.Source: §6 · p. 8
• On a majority of tasks, per-state evaluation is substantially faster than with the strongest systematic baselines, often by orders of magnitude.Source: §6 · p. 8
• The method evolves interpretable Python programs that generate admissible pattern collections for tasks in a domain.Source: §6 · p. 8
• Floortile and Miconic are the two domains where small systematic patterns provide strong guidance, leaving little room for the larger domain-specific patterns.Source: §6 · p. 8
• Future work may explore richer domain information, more training tasks, a scoring function better aligned with coverage, and obfuscated domain names.Source: §6 · p. 8

A Synthesized Pattern Generators

• In Blocksworld, the generator groups goal atoms connected through shared objects and gathers fluent atoms involving objects from those goals.It retains multi-atom connected components as candidate patterns.Source: A Synthesized Pattern Generators · p. 11
• Blocksworld candidates also capture blocks needing unstacking, pickup, or putdown, and stacking goals using relevant holding, clear, and arm-empty atoms.The code compares initial and goal supports to identify blocks to unstack and forms a stacking pattern from the goal relation and related fluents.Source: A Synthesized Pattern Generators · p. 12
• The code considers patterns of at most 20 atoms, estimates each cost as 2^size, and adds a pattern only when total_states + 2 <= 500,000,000.It tracks covered goal atoms while selecting patterns.Source: A Synthesized Pattern Generators · pp. 13–14
• In Childsnack, the generator groups tray-location and sandwich-related fluent atoms into patterns, admitting groups only when their variable count is at most 20.It connects sandwich, tray, location, and related fluents when those atoms occur in the task.Source: A Synthesized Pattern Generators · pp. 14–15
• For Childsnack served goals, the code builds candidate patterns using waiting children, available trays, valid sandwiches, and gluten constraints, subject to the same 20-variable limit.For children with allergies, it retains sandwiches marked no-gluten.Source: A Synthesized Pattern Generators · p. 15
• The Floortile generator builds paint and movement adjacency from static relations and forms patterns using goal tiles, robot atoms, and relevant clear atoms.The excerpts show pattern-size checks of at most 20 atoms.Source: A Synthesized Pattern Generators · pp. 16–18
• Patterns are ordered with goal-covering patterns first, then by size; selection skips patterns over 20 atoms and admits patterns only while cumulative 2^n states stay within 400,000,000.A singleton pattern is appended with a 2-state increment.Source: A Synthesized Pattern Generators · pp. 19–20
• The Miconic generator indexes fluent atoms, passenger destinations and origins, passenger-related atoms, and lift-at atoms.Source: A Synthesized Pattern Generators · p. 20
• Passenger patterns can include origin, destination, boarded, served, and lift-at atoms, with singleton patterns for boarded and served atoms.Source: A Synthesized Pattern Generators · pp. 20–21
• Passenger patterns group up to six passengers sharing a floor with lift atoms, provided the resulting pattern has at most 20 variables.The generator also groups each passenger’s atoms by floor before constructing these patterns.Source: A Synthesized Pattern Generators · pp. 21–22
• When multiple lift atoms are present, the generator adds patterns pairing lifts on consecutive sorted floors.Source: A Synthesized Pattern Generators · p. 22
• The Rovers generator limits patterns to 20 variables and estimated total abstract states to 500,000,000, and deduplicates them by signature.Source: A Synthesized Pattern Generators · pp. 22–23
• For image goals, Rovers patterns combine goal modes and existing images with relevant calibration and rover locations at visible waypoints.Source: A Synthesized Pattern Generators · pp. 24–25
• For soil-analysis goals, the generator combines the goal with soil-capable rover analysis, rover locations, and empty/full atoms.Source: A Synthesized Pattern Generators · p. 25
• Rover patterns link soil or rock analysis goals to matching rover-location and analysis atoms, while rock patterns also account for rover capability and visible waypoints.The code limits some goal-linked patterns to fewer than 20 atoms and adds empty/full store atoms to rock patterns.Source: A Synthesized Pattern Generators · p. 26
• The rover generator also forms patterns around multiple locations, stores, or calibrations associated with a rover, linking stores with analysis atoms and calibrations with location atoms.The snippets show patterns for rovers with multiple locations or stores, and for multiple calibrations; calibration patterns use visibility relations to select a waypoint.Source: A Synthesized Pattern Generators · pp. 26–27
• The rover code tracks which fluent goals are covered by generated patterns and adds a singleton initial-state pattern if none were produced.The snippets show goal-coverage checks and a fallback that uses the first fluent initial-state atom when the pattern collection is empty.Source: A Synthesized Pattern Generators · p. 27
• The satellite generator indexes static support, instrument-on-satellite, and calibration-target relations, then uses them to construct patterns for image goals and instrument calibration.The code also groups instruments sharing a satellite into power patterns and adds calibration, pointing, and power-availability atoms when the resulting pattern has at most 20 variables.Source: A Synthesized Pattern Generators · pp. 28–30
• The snippets show a satellite-key absence check, iteration over goals_by_sat entries, and a conditional that proceeds only when the combined collection has more than one element.Source: A Synthesized Pattern Generators · p. 30
• Both generator code paths track goal atoms covered by patterns and include a fallback that uses initial-state atoms when no patterns are produced.The transport generator also checks for each fluent goal atom not already covered.Source: A Synthesized Pattern Generators · pp. 31–32
• The generator retains package-atom and location-atom patterns only when each is nonempty and contains at most 20 atoms, as shown by separate package and location checks.Source: A Synthesized Pattern Generators · pp. 31–32