# 用 HTN 和演化搜索做规划

> 符号规划处理那些计划可被证明正确的情形。演化式代码搜索处理那些适应度函数机器可校验的情形。ChatHTN（2025）和 AlphaEvolve（2025）展示了各自与 LLM 配对时能解锁什么。

**类型：** Build
**语言：** Python（标准库）
**前置要求：** 阶段 14 · 02（ReWOO 与 Plan-and-Execute）
**预计时间：** ~75 分钟

## 学习目标

- 解释分层任务网络（HTN）：任务、方法、算子、前置条件、效果。
- 描述 ChatHTN 的混合循环 —— 带 LLM 兜底分解的符号搜索。
- 解释 AlphaEvolve 的演化循环，以及为什么它只有在有程序化评估器时才管用。
- 用标准库实现一个玩具 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 年来首次在 4x4 复数矩阵乘法上超越 Strassen（48 次标量乘法）。
- 通过一个 Borg 调度启发式，给 Google 找回了 0.7% 的算力。
- 在一个前沿工作负载上 FlashAttention 提速 32%。

硬约束：适应度函数必须机器可校验。在散文式答案上做演化搜索不会收敛。

### 什么时候用哪个

| 问题类别 | 用 | 为什么 |
|---------------|-----|-----|
| 带硬约束的排程 | HTN + ChatHTN | 可证明可靠 |
| 编译器优化 | AlphaEvolve | 机器可校验的适应度 |
| 多步任务执行 | ReAct / ReWOO | LLM 在循环里，无形式化保证 |
| 带测试的代码改进 | AlphaEvolve | 测试就是评估器 |
| 受策略约束的自动化 | HTN | 前置条件编码策略 |

### 这个模式在哪里会出错

- **没有算子的 HTN。** 没有前置条件/效果 schema，可靠性主张就崩了。ChatHTN 的「LLM 建议分解」需要 schema 来拒绝无效动作。
- **没有真评估器的 AlphaEvolve。** 「问 LLM 代码是不是更好了」不是适应度函数。评估器必须确定且快。
- **过度工程。** 大多数 agent 任务两个都不需要。先上 ReAct 或 ReWOO。

```figure
htn-tree-expand
```

## 动手构建

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

- 一个标准库 HTN 规划器，带算子、方法、前置条件、效果，外加一个 `LLMFallback`，在没有方法匹配某个复合任务时介入。这个「LLM」是个脚本化的分解器，好让规划器离线运行。
- 一个标准库的、在算术程序上的演化搜索：生长那些输出能在测试集上最小化 `|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 把一个复合任务分解成子任务，然后对每个子任务的原语算子用演化搜索。它在哪里出彩，在哪里过度工程？

## 关键术语

| 术语 | 大家怎么说 | 它实际是什么 |
|------|----------------|------------------------|
| HTN | 「分层规划器」 | 带算子、前置条件、效果的任务分解 |
| Method | 「分解规则」 | 把一个复合任务拆成子任务的方式 |
| Operator | 「原语动作」 | 带前置条件和效果的具体步骤 |
| ChatHTN | 「LLM + HTN」 | 符号规划器在没有方法匹配时问 LLM |
| AlphaEvolve | 「演化式代码搜索」 | LLM 集成变异代码；确定的评估器做选择 |
| Fitness function | 「评估器」 | 在输出上的确定、机器可校验的分数 |
| Online method learning | 「缓存的 LLM 分解」 | 存下并泛化 LLM 计划以削减查询成本 |

## 延伸阅读

- [Gopalakrishnan et al., ChatHTN (arXiv:2505.11814)](https://arxiv.org/abs/2505.11814) —— 符号 + LLM 混合规划器
- [Novikov et al., AlphaEvolve (arXiv:2506.13131)](https://arxiv.org/abs/2506.13131) —— 带 LLM 变异的演化式代码搜索
- [Anthropic, Building Effective Agents](https://www.anthropic.com/research/building-effective-agents) —— 何时该上规划器、何时用一个简单循环