Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel method for learning admissible heuristics in optimal classical planning by leveraging an LLM-driven evolutionary program-synthesis framework. By focusing on constructing abstractions that yield admissible heuristics rather than directly mapping states to heuristic values, the approach ensures that the optimality guarantees of A* search are preserved. Empirical results demonstrate that the learned heuristics not only match the performance of state-of-the-art domain-independent baselines but also evaluate states significantly faster while providing interpretable insights into the domain.
Learning admissible heuristics through LLM-driven program synthesis can yield faster evaluations and deeper domain insights without sacrificing optimality.
Learned heuristics have recently become a competitive alternative to traditional domain-independent heuristics for satisficing planning. Existing approaches, however, focus on improving search guidance rather than guaranteeing admissibility, which makes them unsuitable for optimal classical planning. We present the first method for learning domain-dependent heuristics that are admissible by design and thus preserve the optimality guarantees of A* search. Instead of learning a direct mapping from states to heuristic values, we learn to construct abstractions that induce admissible heuristics. We use an LLM-driven evolutionary program-synthesis framework to obtain, for each domain, a program that produces a pattern collection for any task in that domain, and we combine the resulting patterns admissibly via saturated cost partitioning. Empirically, the learned programs encode interpretable domain-specific insights, run with negligible overhead at test time and yield heuristics that match the coverage of state-of-the-art domain-independent baselines on several domains while evaluating each state substantially faster.