LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning
作者: Elliot Gestrin, Jendrik Seipp
分类: cs.AI
发布日期: 2026-05-28
💡 一句话要点
利用LLM进化领域无关启发式算法，超越符号AI规划人工设计水平
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 符号AI规划 启发式搜索 大型语言模型 进化搜索 领域无关 自动程序生成 MAP-Elites C++
📋 核心要点
- 现有的符号AI规划启发式搜索依赖于人工设计的启发式算法，这些算法虽然强大，但开发周期长且难以泛化到新领域。
- 该论文提出了一种基于LLM和进化搜索的自动启发式算法生成方法，通过LLM变异C++启发式代码，并使用MAP-Elites存档和适应度函数进行筛选。
- 实验结果表明，该方法生成的启发式算法在未见过的测试领域中，超越了手工设计的启发式算法，并在信息性-速度权衡方面取得了显著提升。
📝 摘要（中文）
启发式搜索是符号AI规划中的主导范式，而最强大的启发式算法是规划研究人员数十年工作的成果。最近的研究表明，大型语言模型（LLM）可以为单个规划领域设计启发式算法，但到目前为止，还没有LLM生成的启发式算法可以处理任意规划任务。在本文中，我们使用进化搜索来生成第一个LLM生成的领域无关启发式算法，其性能超过了手工设计的水平。我们让LLM变异用C++编写的父启发式算法，将候选算法存储在基于信息性和速度的MAP-Elites档案中，并通过将覆盖率与求解时间相结合来计算适应度分数。为了将进化后的程序置于上下文中，我们还对大量手工设计的启发式算法的信息性-速度权衡进行了基准测试，据我们所知，以前没有人这样做过。在未见过的测试领域中，我们最好的进化启发式算法比最强的基线算法解决了更多的任务，而我们的完整启发式算法套件跨越了所述权衡的帕累托前沿。我们还发现，从简单的盲启发式算法中进行进化播种优于从强大的FF启发式算法中播种，即使最终的程序本身是FF变体，并且LLM的推理工作对候选程序编译的频率的影响远大于对编译后的程序质量的影响。由于进化后的程序是纯C++，因此它们可以作为即插即用替代品插入到现有的规划器中，并继承底层搜索的可靠性和完整性保证。
🔬 方法详解
问题定义：论文旨在解决符号AI规划中领域无关启发式算法设计的问题。现有方法依赖于人工设计，耗时且难以泛化。即使是强大的启发式算法，也需要领域专家花费大量时间进行调整和优化。因此，如何自动生成高性能的领域无关启发式算法是一个重要的挑战。
核心思路：论文的核心思路是利用大型语言模型（LLM）的代码生成能力，结合进化搜索算法，自动生成和优化启发式算法。通过让LLM对现有的启发式算法进行变异，并根据其在规划任务上的表现进行评估和筛选，最终得到性能优越的启发式算法。这种方法避免了人工设计的繁琐过程，并有望发现新的、更有效的启发式策略。
技术框架：整体框架包括以下几个主要步骤：1) 初始化：从一个或多个初始启发式算法（例如，盲启发式或FF启发式）开始。2) 变异：使用LLM对父启发式算法的代码（C++）进行变异，生成新的候选启发式算法。3) 评估：在多个规划任务上测试候选启发式算法的性能，包括覆盖率和求解时间。4) 选择：使用MAP-Elites算法，根据信息性和速度这两个指标，将候选启发式算法存储在档案中。5) 进化：根据适应度函数（覆盖率和求解时间的加权组合）选择优秀的候选算法作为新的父启发式算法，重复步骤2-4，直到达到停止条件。
关键创新：该论文的关键创新在于：1) LLM驱动的启发式算法生成：首次利用LLM的代码生成能力，自动生成领域无关的启发式算法。2) 进化搜索与MAP-Elites存档：结合进化搜索和MAP-Elites算法，有效地探索启发式算法的空间，并保持多样性。3) 信息性-速度权衡的显式建模：通过MAP-Elites存档和适应度函数，显式地考虑了启发式算法的信息性和速度之间的权衡。
关键设计：关键设计包括：1) LLM变异策略：使用LLM对C++代码进行变异，包括插入、删除、修改代码片段等。2) MAP-Elites存档的指标：使用信息性和速度作为MAP-Elites存档的两个关键指标，以保持启发式算法的多样性。3) 适应度函数：使用覆盖率和求解时间的加权组合作为适应度函数，以平衡启发式算法的覆盖率和求解速度。4) 进化参数：包括LLM变异的次数、MAP-Elites存档的大小、进化迭代的次数等。
🖼️ 关键图片
📊 实验亮点
实验结果表明，该方法生成的启发式算法在未见过的测试领域中，比最强的基线算法解决了更多的任务。具体来说，最好的进化启发式算法在覆盖率方面取得了显著提升，同时在求解时间方面也保持了竞争力。此外，研究还发现，从简单的盲启发式算法开始进化，比从强大的FF启发式算法开始进化，效果更好。
🎯 应用场景
该研究成果可应用于各种符号AI规划问题，例如机器人路径规划、任务调度、游戏AI等。通过自动生成高性能的启发式算法，可以显著提高规划器的效率和求解能力，从而解决更复杂的实际问题。此外，该方法还可以推广到其他领域，例如自动程序修复、代码优化等。
📄 摘要（原文）
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.