GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models

GenePlan 是一个利用大语言模型辅助进化算法的框架，通过迭代优化可解释的 Python 规划器，在多个基准领域中以低成本实现了接近最先进水平且显著优于传统提示方法的 PDDL 泛化规划性能。

要点

这篇论文介绍了一个名为 GenePlan 的新系统，它就像是一个"AI 教练 + 进化论"的组合，专门用来教大语言模型（LLM）如何写出更聪明、更高效的“行动指南”（规划程序）。

为了让你轻松理解，我们可以把整个故事想象成训练一支“万能探险队”。

1. 背景：大模型很聪明，但有点“笨拙”

想象一下，你有一个超级聪明的大语言模型（LLM），它读过世界上所有的书，知道很多知识。如果你让它直接写一个“如何把箱子堆好”或者“如何送报纸”的计划，它往往能写出来，但计划通常很啰嗦、步骤很多，甚至有时候会走弯路。这就像让一个博学的教授去指挥一个从未下过地的探险队，他懂理论，但缺乏实战经验，写出的路线不够优化。

2. 核心创意：GenePlan 是什么？

GenePlan 的名字来自 Generalized（通用）和 Plan（规划）。它的核心思想是：不要只让 AI 写一次计划，而是让它“进化”出一套通用的行动代码（Python 程序）。

这就好比：

• 传统方法：每次遇到新任务，都让 AI 现场写一份新的说明书。
• GenePlan 方法：让 AI 写一个通用的“行动算法”。这个算法一旦写好，就可以用来解决该领域内成千上万个不同的具体问题（比如不同的地图、不同的货物量），而且越用越精。

3. 工作原理：像“自然选择”一样进化

GenePlan 使用了一种叫**“进化算法”**的方法，过程非常像生物进化：

1. 孵化（生成）：
   首先，让大语言模型（LLM）根据任务描述，写出 10 个不同的“行动代码”（就像生出了 10 个不同基因的孩子）。

   • 比喻：就像让 10 个不同的探险家分别画出他们心中的“寻宝路线图”。

2. 实战演练（评估）：
   把这 10 个代码放到各种模拟场景里去跑。

   • 如果代码跑通了，而且步骤很少（比如只用了 5 步就完成任务），它的**“分数”就很高**。
   • 如果代码跑不通，或者走了 100 步才完成任务，它的**“分数”就很低**。
   • 比喻：让这 10 个探险家真的去走一遍路。走得快、不绕弯的，就是“优等生”。

3. 优胜劣汰（选择与淘汰）：
   系统会保留那些“优等生”的代码，把那些“差生”（跑不通或步骤太多的）直接淘汰掉。

4. 杂交与变异（进化）：
   这是最精彩的一步。系统把“优等生”的代码片段拿出来，让大语言模型把它们**“杂交”（结合优点）或者“变异”**（尝试新的改进点）。

   • 比喻：系统告诉 AI：“你看，A 探险家的‘找路’方法很好，B 探险家的‘搬运’方法很省力。请你结合这两点，再加点新创意，写一个更完美的‘超级探险家’代码。”

5. 循环迭代：
   这个过程会重复很多次（比如 10 代）。每一代，留下的代码都比上一代更聪明、更精简。最后，系统会选出那个**“最强王者”**的代码。

4. 成果：它有多厉害？

论文在 8 个不同的领域（比如送报纸、运汽车、堆箱子、做研究等）进行了测试：

• 质量极高：GenePlan 生成的代码，其规划质量（步骤是否最少）几乎和世界上最顶尖的传统规划软件（Fast Downward）一样好，甚至更好。
• 速度极快：一旦这个“进化好”的代码生成完毕，用它来解决新问题，平均只需要 0.49 秒！这比让 AI 现场思考要快得多。
• 成本很低：生成这样一个“超级代码”的成本，平均每个领域只要 1.82 美元（大概一杯咖啡的钱）。
• 可解释性：生成的代码是人类可读的 Python 语言，我们可以清楚地看到它是怎么思考的，而不是一个黑盒子。

5. 一个有趣的发现

研究人员还发现，如果给 AI 的提示词里把具体的名词（比如“箱子”、“人”）都换成乱码（比如“物体 A"、“物体 B"），AI 就完全写不出好代码了。

• 比喻：这就像你告诉一个厨师“把那个红色的东西和那个圆形的东西炒在一起”，他可能知道怎么做；但如果你说“把物体 A 和物体 B 炒在一起”，他就懵了。上下文和具体的名字对 AI 理解世界至关重要。

总结

GenePlan 就像是一个**“进化实验室”。它不满足于让 AI 偶尔写出一个不错的计划，而是通过不断的“试错、淘汰、结合、改进”，逼迫 AI 进化出一套通用的、高效的、人类能看懂的“行动法则”**。

这套法则一旦生成，就可以像瑞士军刀一样，迅速、廉价地解决该领域内成千上万个具体问题。这对于需要重复性规划任务的场景（比如物流调度、机器人控制）来说，是一个巨大的突破。

技术摘要

1. 研究背景与问题定义

核心问题：
在经典规划（Classical Planning）领域，大语言模型（LLM）虽然擅长代码生成和推理，但在直接处理序列决策任务（如 PDDL 规划）时表现不佳，通常生成的计划质量低、不可靠或无法求解。现有的基于 LLM 的通用规划（Generalized Planning）方法（如 Silver et al., 2024）虽然能生成可解释的 Python 策略，但往往仅关注“可解性”（Satisficing），缺乏对计划质量（如计划长度最小化）的优化。

研究目标：
提出一种名为 GenePlan（GENeralized Evolutionary Planner）的新框架。该框架旨在将通用规划视为一个优化问题，利用大语言模型辅助的进化算法，自动演化出能够针对特定 PDDL 领域生成高质量、可解释且高效的 Python 规划器（Planner）。

关键定义：

• 通用规划实例 ($\Pi_G$)：一组共享相同 PDDL 领域结构（动作、谓词定义相同），但对象实例、初始状态和目标状态不同的经典规划任务集合。
• 通用规划器 ($\Phi$)：一个 Python 函数，能够接收任意规划任务实例，并输出一个有效的动作序列（计划）。
• 优化目标：最小化所有训练任务上的平均计划长度（即动作数量）。

---

2. 方法论：GenePlan 框架

GenePlan 将进化算法（Evolutionary Algorithms, EA）与大语言模型（LLM）相结合，通过迭代进化来搜索最优的 Python 规划代码。

2.1 核心架构

GenePlan 的架构包含两个主要循环（如图 1 所示）：

1. 右循环（生成与变异）：LLM 根据当前种群中的优秀规划器作为示例，生成新的候选规划器（子代）。
2. 左循环（选择与替换）：评估新候选者的适应度，保留表现最好的个体，淘汰表现差的，形成下一代种群。

2.2 具体流程

1. 种群初始化：

   • 初始种群可以是随机生成的，也可以由 LLM 通过思维链（Chain-of-Thought, CoT）提示生成的初始策略，或者由用户提供。
   • 每个个体是一个 Python 方法 get_plan(objects, init, goal)。

2. 适应度评估 (Fitness Evaluation)：

   • 对每个候选规划器，在训练集任务上运行。
   • 使用 PDDL 验证器（Plan Validator）确保生成的计划合法。
   • 适应度函数：计算所有训练任务上的平均计划长度。
     • 如果规划器无法解决某个实例，则给予一个极大的惩罚分数（Failure Score）。
     • 目标是最小化该分数。

3. 选择策略 (Selection)：

   • 采用基于玻尔兹曼分布的采样机制。
   • 引入温度参数 ($T$)，该参数随种群数量增加而双曲衰减（从 $T_{max}$ 降至 $T_{min}$）。
   • 机制：早期温度高，鼓励探索（Exploration），允许较差的解被选中以维持多样性；后期温度低，鼓励利用（Exploitation），优先选择适应度高的解。

4. 提示构建与生成 (Prompt Construction & Generation)：

   • 构建包含 PDDL 领域定义、当前选中的父代规划器代码及其执行反馈（成功/失败原因、得分）的提示词（Prompt）。
   • LLM 接收提示词，执行交叉（Crossover）（合并不同父代的优秀代码片段）和变异（Mutation）（修改逻辑、优化启发式规则），生成新的子代代码。

5. 代码验证与执行：

   • 使用 AST（抽象语法树）解析器 检查生成的代码是否符合预定义的安全规范（如禁止导入危险库、限制函数类型）。
   • 验证通过后编译并执行，若执行出错则捕获异常并反馈给 LLM。

6. 替换策略 (Replacement)：

   • 采用 $(\mu + \lambda)$ 选择策略（精英策略）。
   • 从当前种群（$\mu$）和新生成的子代（$\lambda$）中，选取适应度最好的 $\mu$ 个个体进入下一代。

---

3. 关键贡献

1. 将通用规划转化为优化问题：
   不同于以往仅关注“能否解出”的方法，GenePlan 明确将“最小化计划长度”作为优化目标，利用进化算法在巨大的代码空间中搜索最优解。

2. LLM 辅助的进化规划框架：
   创新性地结合了 Romera-Paredes et al. (2024) 的进化 LLM 框架与 PDDL 规划领域。LLM 不再仅仅是生成器，而是作为进化算子（交叉、变异）的执行者，能够理解代码逻辑并进行结构化改进。

3. 可解释性与高效性：
   生成的解决方案是人类可读的 Python 代码，而非黑盒模型。一旦生成，该规划器在推理阶段（解决新实例）极快（平均 0.49 秒/任务），且成本极低。

4. 广泛的实证评估：
   在 8 个 PDDL 领域（包括 6 个基准和 2 个新领域）上进行了验证，涵盖了从简单策略到复杂依赖关系的多种场景。

---

4. 实验结果

4.1 性能对比

• SAT 分数 (Satisficing Score)：GenePlan 在所有 8 个领域的平均 SAT 分数为 0.91。
  • 与最先进的传统规划器 Fast Downward（运行 30 分钟限制）的 0.93 非常接近。
  • 显著优于其他 LLM 基线：
    • 优于 CoT (GPT-4o)：0.91 vs 0.64 (提升 0.27)。
    • 优于 CoT (GPT-4)：0.91 vs 0.64。
• 统计显著性：通过 Friedman 检验和 Nemenyi 事后检验，GenePlan 的表现与 Fast Downward (1800s) 统计上无显著差异，但显著优于所有纯 LLM 提示方法。

4.2 效率与成本

• 推理速度：生成的 Python 规划器解决单个任务平均仅需 0.49 秒，远快于 Fast Downward（平均数十秒至数百秒）。
• 生成成本：使用 GPT-4o 生成一个领域的规划器平均成本仅为 $1.82。
• 生成时间：平均约 10-15 分钟（取决于领域复杂度），这是一次性成本。

4.3 消融实验与发现

• 领域摘要 vs. 完整 PDDL：使用自然语言摘要（evo_ds）在简单领域表现尚可，但在复杂领域（如 manymiconic）表现大幅下降，证明完整的 PDDL 上下文信息对 LLM 生成高质量规划至关重要。
• 名称消融：将 PDDL 中的谓词/动作名称替换为通用名称（如 action1）会导致 LLM 完全无法生成有效解，突显了语义上下文的重要性。
• 无评估器：若不给 LLM 反馈（evo_nev），性能大幅下降，证明进化反馈循环是成功的关键。
• 无简单策略的领域：在 Sokoban 等存在不可逆状态（死锁）的复杂领域，GenePlan 倾向于尝试构建搜索算法但失败，而传统搜索规划器（Fast Downward）表现更好。这表明 GenePlan 适合具有通用策略的领域，对于极度复杂的搜索空间仍需传统启发式搜索。

---

5. 意义与未来展望

5.1 意义

• 填补了 LLM 在规划质量优化上的空白：证明了 LLM 不仅能生成代码，还能通过进化机制优化代码性能，达到甚至接近传统专用规划器的水平。
• 低成本、高可解释性：为工业界提供了一种低成本（< $2/领域）、可快速部署且逻辑透明的规划解决方案。
• 范式转变：从“LLM 直接求解”转向"LLM 辅助优化求解器”，结合了神经网络的生成能力与传统算法的优化能力。

5.2 局限性

• 复杂搜索空间：对于像 Sokoban 这样需要深度搜索且容易陷入局部最优或死锁的领域，纯策略生成的方法可能不如基于搜索的规划器（如 A*）。
• 生成时间：虽然推理极快，但生成规划器本身需要数分钟到数十分钟，不适合实时动态变化的领域（除非结合早停机制）。

5.3 未来工作

• 早停机制 (Early Stopping)：开发自动判断何时收敛的机制，减少不必要的计算成本。
• 多目标优化：除了计划长度，探索优化其他指标（如执行时间、资源消耗）。
• 混合架构：利用 LLM 作为路由接口，动态选择是使用 GenePlan 生成的策略，还是调用传统的搜索规划器（如 Fast Downward），以应对不同难度的问题。
• 启发式生成：利用 GenePlan 生成传统搜索算法中的启发式函数（Heuristics），进一步提升搜索效率。

总结

GenePlan 是一个强有力的框架，它成功地将大语言模型从“尝试者”转变为“优化者”。通过进化算法的迭代反馈，它能够生成在质量和效率上媲美传统顶尖规划器的 Python 代码，同时保持了极高的可解释性和极低的部署成本，为自动化规划领域带来了新的突破。