LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning

• URL: http://arxiv.org/abs/2605.29649v1
• Date: Thu, 28 May 2026 09:14:39 GMT
• Title: LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning
• Abstract summary: 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.
• Score: 2.9864637081333085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Heuristic search is the dominant paradigm in symbolic AI planning, and the strongest heuristics are the result of decades of work by planning researchers. Recent work has shown that large language models (LLMs) can design heuristics for individual planning domains, but no LLM-generated heuristic has so far worked on arbitrary planning tasks. In this paper, we use evolutionary search to produce the first LLM-generated domain-independent heuristics that exceed the hand-engineered state of the art. We let an LLM mutate parent heuristics written in C++, store candidates in a MAP-Elites archive keyed on informedness and speed and calculate fitness scores by blending coverage with solving time. To place the evolved programs in context, we additionally benchmark a broad set of hand-engineered heuristics on their informedness-speed tradeoff, which to our knowledge has not been done before. On unseen testing domains, our best evolved heuristic solves more tasks than even the strongest baseline, with our full heuristic suite spanning the Pareto frontier of said tradeoff. We also find that seeding evolution from the trivial blind heuristic outperforms seeding from the strong FF heuristic, even when the resulting program is itself an FF variant, and that LLM reasoning effort affects how often candidates compile much more than the quality of those that do. Because the evolved programs are plain C++, they slot into existing planners as drop-in replacements and inherit the soundness and completeness guarantees of the underlying search.

Related papers

• MLEvolve: A Self-Evolving Framework for Automated Machine Learning Algorithm Discovery [36.12600393708582]
  Large language model (LLM) agents are increasingly applied to long-horizon tasks such as scientific discovery and machine learning engineering.<n>We present MLEvolve, an LLM-based self-evolving multi-agent framework for end-to-end machine learning algorithm discovery.
  arXiv  Detail & Related papers  (2026-06-04T17:55:59Z)
• LLM-Evolved Pattern Generators for Optimal Classical Planning [2.432409923443071]
  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.
  arXiv  Detail & Related papers  (2026-06-01T16:10:20Z)
• LLM Agents Beyond Utility: An Open-Ended Perspective [50.809163251551894]
  We augment a pretrained LLM agent with the ability to generate its own tasks, accumulate knowledge, and interact extensively with its environment.<n>It can reliably follow complex multi-step instructions, store and reuse information across runs, and propose and solve its own tasks.<n>It remains sensitive to prompt design, prone to repetitive task generation, and unable to form self-representations.
  arXiv  Detail & Related papers  (2025-10-16T10:46:54Z)
• Evolving Prompts In-Context: An Open-ended, Self-replicating Perspective [65.12150411762273]
  We show that pruning random demonstrations into seemingly incoherent "gibberish" can remarkably improve performance across diverse tasks.<n>We propose a self-discover prompt optimization framework, PromptQuine, that automatically searches for the pruning strategy by itself using only low-data regimes.
  arXiv  Detail & Related papers  (2025-06-22T07:53:07Z)
• 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)
• Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design [33.58608225370497]
  Large Language Model (LLM)-based automatic design (AHD) methods have shown promise in generating high-quality designs without manual intervention.<n>This paper proposes to use Monte Carlo Tree Search (MCTS) for evolutionary evolution.
  arXiv  Detail & Related papers  (2025-01-15T06:00:50Z)
• WorkArena++: Towards Compositional Planning and Reasoning-based Common Knowledge Work Tasks [85.95607119635102]
  Large language models (LLMs) can mimic human-like intelligence.<n>WorkArena++ is designed to evaluate the planning, problem-solving, logical/arithmetic reasoning, retrieval, and contextual understanding abilities of web agents.
  arXiv  Detail & Related papers  (2024-07-07T07:15:49Z)
• Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning [53.6472920229013]
  Large Language Models (LLMs) have demonstrated impressive capability in many natural language tasks. LLMs are prone to produce errors, hallucinations and inconsistent statements when performing multi-step reasoning. We introduce Q*, a framework for guiding LLMs decoding process with deliberative planning.
  arXiv  Detail & Related papers  (2024-06-20T13:08:09Z)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  We learn high-quality traces from POMDP executions generated by any solver. We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications. We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
  arXiv  Detail & Related papers  (2024-02-29T15:36:01Z)

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.