面向符号AI规划的LLM进化式领域无关启发式

启发式搜索是符号AI规划的主流范式，最强的启发式是规划研究者数十年工作的结晶。近期研究表明大语言模型（LLM）能为单个规划领域设计启发式，但迄今为止尚无LLM生成的启发式能适用于任意规划任务。本文利用进化搜索产出了首批超越人工设计最优水平的LLM生成领域无关启发式。我们让LLM对以C++编写的父代启发式进行变异，将候选存入以信息量和速度为键的MAP-Elites存档，并通过融合覆盖率与求解时间计算适应度分数。为给进化程序提供参照，我们额外在信息量-速度权衡上对广泛的人工启发式进行基准测试，据我们所知这尚未有人做过。在未见过的测试领域上，我们最好的进化启发式比最强基线解决更多任务，且完整的启发式套件覆盖了该权衡的帕累托前沿。我们还发现，用平凡的盲启发式作为进化种子优于用强大的FF启发式作为种子，即使最终程序本身就是FF的变体；此外，LLM推理力度对候选能否编译通过的影响远大于对编译通过者质量的影响。由于进化程序是纯C++，它们可作为即插即用的替代嵌入现有规划器，并继承底层搜索的可靠性与完备性保证。