Title: LLM-Evolved Pattern Generators for Optimal Classical Planning

Abstract: While learned heuristics have emerged as a strong competitor to conventional domain-independent methods for satisficing planning, current techniques primarily aim to enhance search guidance. This focus often sacrifices admissibility, rendering them ineffective for optimal classical planning. In this work, we introduce the first approach capable of learning domain-dependent heuristics that are admissible by design, thereby maintaining the optimality guarantees inherent to A* search. Rather than training a model to map states directly to heuristic values, our method learns to generate abstractions that yield admissible heuristics. We employ an LLM-driven evolutionary program-synthesis framework to derive, for each specific domain, a program capable of producing a pattern collection for any task within that domain. These patterns are then combined admissibly using saturated cost partitioning. Our empirical results demonstrate that the learned programs capture interpretable, domain-specific insights. They operate with negligible computational overhead during testing and produce heuristics that achieve coverage comparable to state-of-the-art domain-independent baselines across various domains, while evaluating each state significantly faster.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC