LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning
This work, "LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning" by Elliot Gestrin and Jendrik Seipp, published on arXiv, introduces a novel method for automatically generating effective heuristics for symbolic AI planning systems. The core contribution is the creation of domain-independent heuristics that outperform, in certain aspects, decades of hand-engineered heuristics. This addresses the long-standing challenge of developing generalizable heuristics that can boost the performance of AI planners across a wide range of problem domains, rather than being specialized to a single one. The intended audience is researchers and engineers working in AI planning, automated reasoning, and related fields who can leverage these improved heuristics to build more efficient and capable planning systems.
Two critical technical innovations underpin this research. Firstly, the authors employ an evolutionary search process guided by a large language model (LLM). The LLM's role is to propose mutations to existing C++ heuristic code, fostering exploration of novel heuristic structures. This LLM-driven mutation mechanism is coupled with the MAP-Elites algorithm, a technique for maintaining a diverse archive of candidate solutions. The archive is indexed by key performance metrics, specifically "informedness" (how well the heuristic guides the search) and "speed" (the computational overhead of calculating the heuristic value). Secondly, fitness is evaluated by a blend of heuristic coverage (the proportion of tasks solved) and average solving time, allowing for a robust assessment of heuristic utility across various planning problems. A key finding is that starting the evolutionary process from a simple "blind" heuristic, rather than a more complex hand-engineered one, paradoxically leads to superior results, even when the evolved heuristic is an FF variant. The authors also observe that the LLM's reasoning effort impacts the compilation rate of generated code more significantly than the inherent quality of the successful compilations.
This research enables the creation of planners that can tackle a broader spectrum of tasks more efficiently, without requiring manual heuristic engineering for each new domain. By producing heuristics as plain C++ code, they integrate seamlessly into existing planners, inheriting their theoretical guarantees of soundness and completeness. This work signals a promising direction for the automated discovery of AI components, potentially accelerating progress in domains requiring sophisticated planning capabilities, such as robotics, logistics, and game playing. It suggests that LLMs, when combined with robust evolutionary search and appropriate performance metrics, can transcend their typical text-generation roles to contribute to algorithmic innovation.