LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning

AI planners rely on heuristic functions that estimate the cost from a state to the goal. The strongest heuristics have been hand-engineered over decades, and while large language models can now synthesize heuristics for a single domain, one heuristic that works on *any* symbolic planning task has remained out of reach. We address this with an evolutionary search over C++ heuristics: LLMs propose code mutations, a MAP-Elites archive keyed by informedness and evaluation speed maintains diversity, and fitness blends coverage with solving time. Benchmarked against nineteen hand-engineered heuristics, our evolved heuristics are both the most informative and among the fastest. On held-out domains they are competitive with the strongest baselines, and our best one outperforms all of them. Further, seeding evolution from the trivial `blind` heuristic yields a similar mean but a higher spread and ceiling compared to seeding from the state-of-the-art `FF` heuristic, and even the `FF` variants it creates beat those evolved from `FF` itself. The evolved programs are ordinary C++ that inherit the soundness and completeness of the underlying search and can be integrated into existing planners. Combining two evolved heuristics inside LAMA solves 50 more held-out tasks, yields a 1.11× speedup to the first plan and improves its aggregate plan-quality score.