HTN规划与进化搜索

符号规划处理计划可证明正确的情况。进化代码搜索处理适应度函数可机器检查的情况。ChatHTN（2025）和AlphaEvolve（2025）展示了与LLM配对时各自解锁了什么。

类型： 构建 语言： Python (stdlib) 前置条件： Phase 14 · 02 (ReWOO与计划执行) 时间： ~75分钟

学习目标

• 解释层次任务网络：任务、方法、操作符、前置条件、效果。
• 描述ChatHTN的混合循环——带LLM回退分解的符号搜索。
• 解释AlphaEvolve的进化循环以及为什么它只在有程序化评估器时才有效。
• 在stdlib中实现玩具HTN规划器和玩具进化搜索。

问题所在

ReWOO（第02课）、Plan-and-Execute和ReAct覆盖了大多数Agent规划。两种情况它们覆盖不好：

1. 可证明正确性的计划。 调度、航线规划、合规工作流——计划必须在构造上可靠。流畅的LLM计划有时幻觉一个步骤是不可接受的。
2. 有机器可检查适应度函数的优化。 矩阵乘法、调度启发式、编译器pass——目标不是”一个正确的计划”而是”最好的计划”。

HTN规划和AlphaEvolve解决两个不同的问题。两者都将LLM用作放大器而非替代品。

核心概念

层次任务网络

HTN是：

• 任务 — 复合（待分解）和原始（可直接执行）。
• 方法 — 将复合任务分解为子任务的方式，带前置条件。
• 操作符 — 带前置条件和效果的原始动作。
• 状态 — 一组事实。

规划：给定目标任务和初始状态，找到一个分解为原始操作符的方案，其前置条件按序列满足。

HTN比LLM更古老，仍然是可证明正确计划的参考。

ChatHTN（Gopalakrishnan等人，2025）

ChatHTN（arXiv:2505.11814）交替符号HTN与LLM查询：

1. 尝试用现有方法分解当前复合任务。
2. 如果没有方法适用，问LLM：“在状态s中你会如何分解task？”
3. 将LLM响应翻译为候选子任务。
4. 针对操作符Schema验证；拒绝无效分解。
5. 递归。

论文的核心声明：每个产生的计划都是可证明可靠的，因为LLM建议只作为候选分解进入，从不作为直接计划编辑。符号层拥有正确性；LLM扩展方法库。

在线方法学习（OpenReview gwYEDY9j2x，2025年后续）添加了一个学习器，通过回归泛化LLM产生的分解——将LLM查询频率削减高达75%。

AlphaEvolve（Novikov等人，2025）

AlphaEvolve（arXiv:2506.13131，DeepMind，2025年6月）是不同的野兽：由Gemini 2.0 Flash/Pro集编排的进化代码搜索。

循环：

1. 从种子程序 + 程序化评估器（返回适应度分数）开始。
2. LLM集成提出变异。
3. 通过评估器运行变异。
4. 保留最好的；再次变异。

已发布的成果：

• 56年来首次改进Strassen的4x4复矩阵乘法（48次标量乘法）。
• 通过Borg调度启发式恢复0.7%的Google计算。
• 在前沿工作负载上32%的FlashAttention加速。

硬约束：适应度函数必须是机器可检查的。散文答案上的进化搜索不会收敛。

何时使用哪个

这个模式哪里会出错

• 没有操作符的HTN。 没有前置条件/效果Schema，可靠性声明崩溃。ChatHTN的”LLM建议分解”需要Schema来拒绝无效移动。
• 没有真实评估器的AlphaEvolve。 “问LLM代码是否更好”不是适应度函数。评估器必须是确定性和快速的。
• 过度工程。 大多数Agent任务不需要任何一个。先尝试ReAct或ReWOO。

构建它

code/main.py实现两个玩具：

• 一个stdlib HTN规划器，带操作符、方法、前置条件、效果，以及当没有方法匹配复合任务时启动的LLMFallback。“LLM”是脚本化的分解器，使规划器可离线运行。
• 一个stdlib算术程序进化搜索：生长表达式，使其输出在测试集上最小化|f(x) - target|。评估器是确定性的。

运行：

python3 code/main.py

跟踪显示HTN规划器分解复合任务（带中途LLM回退）和进化循环收敛到目标表达式。

使用它

• HTN规划器 — pyhop、SHOP3，或为领域特定策略执行自建。
• ChatHTN — 研究代码；模式（符号 + LLM回退）可干净地移植到任何HTN规划器。
• AlphaEvolve — DeepMind论文；模式（集成 + 评估器）可复现。OpenEvolve和类似开源分支正在出现。
• Agent框架 — 没有框架提供一等HTN或AlphaEvolve。将其构建为子Agent或后台Worker。

发布它

outputs/skill-hybrid-planner.md生成混合规划器脚手架（HTN或进化），LLM角色显式限定范围。

练习

1. 用回溯扩展HTN规划器：当操作符的后置条件在运行时失败时，回滚并尝试下一个方法。
2. 给ChatHTN添加LLM方法缓存：当LLM在状态模式P中分解任务T时，存储结果。下次调用时先重新检查方法库。
3. 将进化搜索评估器替换为真实测试套件。进化一个通过20个测试用例的排序函数；报告收敛代数。
4. 阅读AlphaEvolve的评估器设计笔记。为你关心的领域设计一个评估器（SQL查询优化、测试套件最小化、部署YAML）。
5. 组合：用HTN将复合任务分解为子任务，然后对每个子任务的原始操作符使用进化搜索。它在哪里出色，在哪里过度工程？

关键术语

延伸阅读

• Gopalakrishnan等人, ChatHTN (arXiv:2505.11814) — 符号 + LLM混合规划器
• Novikov等人, AlphaEvolve (arXiv:2506.13131) — 带LLM变异的进化代码搜索
• Anthropic, Building Effective Agents — 何时使用规划器而非简单循环