Automated Heuristic Design

Overview

Automated heuristic design studies how to create efficient rules that guide search and decision-making in problems such as vehicle routing, job scheduling, classical planning, and hardware design. Common approaches use genetic programming, evolutionary search, learned policies, or large language models to generate and refine executable heuristics using solver or simulator feedback. Current work increasingly combines these methods with memory, diverse heuristic portfolios, instance specialization, and transfer across tasks, while evaluating solution quality, runtime, and performance on held-out cases. A central challenge is balancing flexible search with reliable generalization, affordable evaluation, and guarantees such as execution safety or admissibility.

Latest papers

92 papers9 papers in the last four weeks, down 36% on the four weeks before. 0.1% of all new papers.

Jan 30, 2025

Successor-Generator Planning with LLM-generated Heuristics

Heuristics are a central component of deterministic planning, particularly in domain-independent settings where general applicability is prioritized over task-specific tuning. This work revisits that paradigm in light of recent advances in large language models (LLMs), which enable the automatic synthesis of heuristics directly from problem definitions -- bypassing the need for handcrafted domain knowledge. We present a method that employs LLMs to generate problem-specific heuristic functions from planning tasks specified through successor generators, goal tests, and initial states written in a general-purpose programming language. These heuristics are compiled and integrated into standard heuristic search algorithms, such as greedy best-first search. Our approach achieves competitive, and in many cases state-of-the-art, performance across a broad range of established planning benchmarks. Moreover, it enables the solution of problems that are difficult to express in traditional formalisms, including those with complex numeric constraints or custom transition dynamics. We provide an extensive empirical evaluation that characterizes the strengths and limitations of the approach across diverse planning settings, demonstrating its effectiveness.
Aug 4, 2023

Solving Witness Triangle Puzzles Faster with an Automatically Learned Predicate

The Witness is a game with combinatorial puzzles that are challenging for both human players and AI solvers. Search-based AI solvers can require large amounts of time to solve such puzzles. We accelerate search by automatically learning a predicate that predicts whether a partial path to a Witness puzzle is completable to a solution path. We demonstrate that our learned predicate is human-explainable, which makes it amenable to proofs, and we prove a key property that allows us to use it for pruning successor states in search. Doing so accelerates search by about six times while maintaining search completeness. Conversely, given a fixed time budget per puzzle, our predicate-accelerated search can solve more puzzles of larger sizes than a baseline search using a hand-coded predicate. Finally, we empirically demonstrate how accelerating search using an automatically learned predicate can outperform two competitors, weighted A* and Levin tree search with neural networks, in terms of time and number of nodes expanded.