LLM-Evolved Pattern Generators for Optimal Classical Planning

• URL: http://arxiv.org/abs/2606.02438v1
• Date: Mon, 01 Jun 2026 16:10:20 GMT
• Title: LLM-Evolved Pattern Generators for Optimal Classical Planning
• Abstract summary: We present the first method for learning domain-dependentmisss that are admissible by design and thus the optimality guarantees of A* search.<n>We use an 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.
• Score: 2.432409923443071
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning [2.9864637081333085]
  Heuristic search is the dominant paradigm in symbolic AI planning.<n>Heuristic search is the dominant paradigm in symbolic AI planning.<n>Heuristic search is the dominant paradigm in symbolic AI planning.
  arXiv  Detail & Related papers  (2026-05-28T09:14:39Z)
• Generating Robust Portfolios of Optimization Models using Large Language Models [27.600634702684733]
  We develop a novel way to generate and evaluate optimization models.<n>We provide theoretical guarantees showing that the portfolio is well-aligned with human preferences.<n>We demonstrate strong performance across range optimization modeling tasks.
  arXiv  Detail & Related papers  (2026-05-26T13:30:43Z)
• Hierarchical Task Network Planning with LLM-Generated Heuristics [45.222898125439286]
  We investigate whether large language models (LLMs) can generate effective search algorithms for HTN planning.<n>LLMs nearly match the coverage of the best available HTN planner, while substantially reducing search effort on 83% of shared problems.
  arXiv  Detail & Related papers  (2026-05-08T13:14:31Z)
• Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback [59.287761696290865]
  We propose a computationally efficient algorithm that achieves a sublinear regret guarantee for contextual episodic Markov Decision Processes (MDPs) with personalized feedback.<n>We demonstrate the effectiveness of our method in learning personalized objectives from multi-turn interactions through experiments on both a synthetic episodic MDP and a real-world user booking dataset.
  arXiv  Detail & Related papers  (2026-02-09T06:29:54Z)
• Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code [6.88204255655161]
  Large language models (LLMs) fail to plan reliably, even when prompted with a detailed definition of a planning task.<n>We show how to use LLMs to generate correct plans, even for out-of-distribution tasks of increasing size.
  arXiv  Detail & Related papers  (2025-03-24T15:50:20Z)
• LLM-Generated Heuristics for AI Planning: Do We Even Need Domain-Independence Anymore? [87.71321254733384]
  Large language models (LLMs) can generate planning approaches tailored to specific planning problems.<n>LLMs can achieve state-of-the-art performance on some standard IPC domains.<n>We discuss whether these results signify a paradigm shift and how they can complement existing planning approaches.
  arXiv  Detail & Related papers  (2025-01-30T22:21:12Z)
• Realistic Unsupervised CLIP Fine-tuning with Universal Entropy Optimization [101.08992036691673]
  This paper explores a realistic unsupervised fine-tuning scenario, considering the presence of out-of-distribution samples from unknown classes. In particular, we focus on simultaneously enhancing out-of-distribution detection and the recognition of instances associated with known classes. We present a simple, efficient, and effective approach called Universal Entropy Optimization (UEO)
  arXiv  Detail & Related papers  (2023-08-24T16:47:17Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Randomized Adversarial Style Perturbations for Domain Generalization [49.888364462991234]
  We propose a novel domain generalization technique, referred to as Randomized Adversarial Style Perturbation (RASP) The proposed algorithm perturbs the style of a feature in an adversarial direction towards a randomly selected class, and makes the model learn against being misled by the unexpected styles observed in unseen target domains. We evaluate the proposed algorithm via extensive experiments on various benchmarks and show that our approach improves domain generalization performance, especially in large-scale benchmarks.
  arXiv  Detail & Related papers  (2023-04-04T17:07:06Z)
• Cluster, Split, Fuse, and Update: Meta-Learning for Open Compound Domain Adaptive Semantic Segmentation [102.42638795864178]
  We propose a principled meta-learning based approach to OCDA for semantic segmentation. We cluster target domain into multiple sub-target domains by image styles, extracted in an unsupervised manner. A meta-learner is thereafter deployed to learn to fuse sub-target domain-specific predictions, conditioned upon the style code. We learn to online update the model by model-agnostic meta-learning (MAML) algorithm, thus to further improve generalization.
  arXiv  Detail & Related papers  (2020-12-15T13:21:54Z)
• Meta-Learning for Domain Generalization in Semantic Parsing [124.32975734073949]
  We use a meta-learning framework which targets zero-shot domain for semantic parsing. We apply a model-agnostic training algorithm that simulates zero-shot parsing virtual train and test sets from disjoint domains.
  arXiv  Detail & Related papers  (2020-10-22T19:00:36Z)
• Universal Source-Free Domain Adaptation [57.37520645827318]
  We propose a novel two-stage learning process for domain adaptation. In the Procurement stage, we aim to equip the model for future source-free deployment, assuming no prior knowledge of the upcoming category-gap and domain-shift. In the Deployment stage, the goal is to design a unified adaptation algorithm capable of operating across a wide range of category-gaps.
  arXiv  Detail & Related papers  (2020-04-09T07:26:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.