HTN 与进化规划:可证正确与可机器检验

HTN 与进化规划:可证正确与可机器检验

本节摘要:ReWOO(第 02 节)、计划-执行、ReAct 已经覆盖了大多数 Agent 规划。但有两类场景它们处理不好:一类是计划必须构造上就可证正确——调度、航路、合规流程,流畅但偶尔幻觉一步的 LLM 计划不可接受;另一类是优化有可机器检验的适应度函数——矩阵乘法、调度启发式、编译 pass,目标不是「一个对的计划」而是「最好的计划」。本节对照两个解法:**HTN(层次任务网络)**用符号规划保证正确性,ChatHTN(2025)在符号层卡壳时让 LLM 提议候选分解、再由算子模式校验,保证「每个产出的计划都可证可靠」,LLM 只扩展方法库、不直接改计划;**AlphaEvolve(2025)**用 LLM 集体变异代码、用确定性适应度函数选择,56 年来首次改进 Strassen 的 4×4 复数矩阵乘法。两者都把 LLM 当放大器而非替代品。本节吃透 HTN 的任务/方法/算子/前置后效、ChatHTN 的混合循环、AlphaEvolve 的进化循环与「必须有可检验适应度」硬约束,并用标准库从零实现一个玩具 HTN 规划器与一个玩具进化搜索。

对应原课程:Phase 14 · Lesson 11 · planning-htn-and-evolutionary(原英文 phases/14-agent-engineering/11-planning-htn-and-evolutionary/docs/en.md)。

学习目标

阅读完本节,你应当能够:

1. 解释层次任务网络(HTN):任务、方法、算子、前置条件、后效。
2. 描述 ChatHTN 的混合循环——符号搜索 + LLM 兜底分解,以及为什么产出的计划仍然可证可靠。
3. 解释 AlphaEvolve 的进化循环,以及为什么它只在适应度函数可机器检验时才管用。
4. 用标准库实现一个玩具 HTN 规划器和一个玩具进化搜索。
5. 识别何时该用 HTN、何时该用进化、何时两者都不需要(回退到 ReAct/ReWOO)。

一、问题与直觉

ReWOO、计划-执行、ReAct 覆盖了大多数 Agent 规划。但有两类它们处理不好:

1. 计划必须可证正确(Provable Correctness) —— 调度、航路、合规流程,计划必须构造上就是可靠的。一个流畅但偶尔幻觉一步的 LLM 计划不可接受。
2. 优化有可机器检验的适应度函数(Machine-Checkable Fitness) —— 矩阵乘法、调度启发式、编译 pass,目标不是「一个对的计划」,而是「最好的计划」。

HTN 规划与 AlphaEvolve 分别解决这两个不同的问题。两者都把 LLM 当放大器,不是替代品。

层次任务网络(HTN)

一个 HTN 由四样东西组成:

• 任务(Tasks) —— 复合任务(待分解)与原语任务(可直接执行)。
• 方法(Methods) —— 把一个复合任务分解成子任务的方式,带前置条件。
• 算子(Operators) —— 原语动作,带前置条件与后效。
• 状态(State) —— 一组事实。

规划就是:给定一个目标任务和一个初始状态,找到一个分解,分解成的前后条件在序列中依次满足的原语算子。

HTN 比 LLM 老得多,至今仍是「可证正确计划」的参考。

ChatHTN:符号 + LLM 兜底

ChatHTN(Gopalakrishnan 等人, 2025, arXiv:2505.11814)在符号 HTN 与 LLM 查询之间交替:

1. 尝试用已有方法分解当前复合任务。
2. 若无方法适用,问 LLM:「在状态 s 下你会怎么分解 task?」
3. 把 LLM 回应翻译成候选子任务。
4. 对照算子模式校验,拒掉非法分解。
5. 递归。

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

在线方法学习(OpenReview gwYEDY9j2x, 2025 续作)加了一个学习器,用回归把 LLM 产出的分解泛化成新方法——可砍掉多达 75% 的 LLM 查询。

💡 设计要点:ChatHTN 的精髓是责任分离:符号层管正确性,LLM 管覆盖面。LLM 可以胡乱提议,但算子模式是铁闸——不合法的分解一律拒掉。这样即使 LLM 幻觉,产出的计划仍然可靠。这与第 06 节「工具调用要校验、失败回灌错误观察」是同一个心法:把 LLM 当不可信的提议者,把确定性逻辑当守门员。

AlphaEvolve:进化代码搜索

AlphaEvolve(Novikov 等人, 2025, arXiv:2506.13131,DeepMind 6 月)是另一种野兽:由 Gemini 2.0 Flash/Pro 集体编排的进化代码搜索。

循环:

1. 从一个种子程序 + 一个程序化评估器(返回适应度分数)开始。
2. LLM 集体提议变异。
3. 把变异跑过评估器。
4. 留下最好的,再变异。

公开的战绩:

• 56 年来首次改进 Strassen 的 4×4 复数矩阵乘法(48 次标量乘法)。
• 通过 Borg 调度启发式回收 0.7% 的 Google 算力。
• 在一个前沿负载上 FlashAttention 提速 32%。

硬约束:适应度函数必须可机器检验。对散文式答案做进化搜索不会收敛。

何时用哪个

这个模式在哪里出错

• 没有算子的 HTN —— 没有前置/后效模式,可靠性论断就垮了。ChatHTN 的「LLM 提议分解」必须有模式来拒掉非法动作。
• 没有真评估器的 AlphaEvolve —— 「问 LLM 代码是不是更好」不是适应度函数。评估器必须确定且快。
• 过度工程 —— 大多数 Agent 任务两者都不需要。先伸手够 ReAct 或 ReWOO。

二、从零实现

原课程 code/main.py 实现两个玩具:

• 一个标准库 HTN 规划器:算子、方法、前置、后效,加一个 LLMFallback——当没有方法匹配某个复合任务时触发。「LLM」是一个脚本化分解器,让规划器离线可跑。
• 一个标准库进化搜索:在算术程序上进化,让输出在测试集上最小化 |f(x) - target|。评估器是确定性的。

核心骨架如下,用伪代码展示。

Step 1:HTN 算子与方法

class Operator:
    def __init__(self, name, precond, effects):
        self.name = name
        self.precond = precond      # dict: 要求 state 里的事实
        self.effects = effects      # dict: 执行后更新 state

    def applicable(self, state):
        return all(state.get(k) == v for k, v in self.precond.items())

    def apply(self, state):
        s = dict(state)
        s.update(self.effects)
        return s

class Method:
    def __init__(self, task, precond, subtasks):
        self.task = task            # 要分解的复合任务名
        self.precond = precond
        self.subtasks = subtasks    # 子任务列表(可复合可原语)
​

Step 2:HTN 规划器(带 LLM 兜底)

def htn_plan(task, state, methods, operators, llm_fallback):
    # 原语任务:直接找算子执行
    if task in operators:
        op = operators[task]
        if not op.applicable(state):
            return None, "前置条件不满足"
        return [op.name], op.apply(state)
    # 复合任务:先试已有方法
    for m in methods:
        if m.task == task and all(state.get(k)==v for k,v in m.precond.items()):
            plan, new_state = decompose(m.subtasks, state, methods, operators, llm_fallback)
            if plan is not None:
                return plan, new_state
    # 兜底:问 LLM 提议分解,再由算子模式校验
    candidate = llm_fallback(task, state)
    if validate_decomposition(candidate, operators):
        methods.append(Method(task, {}, candidate))   # 学到新方法
        return htn_plan(task, state, methods, operators, llm_fallback)
    return None, "无法分解"
​

Step 3:进化搜索

def alpha_evolve(seed, evaluator, llm_mutate, gens=50, pop=20):
    population = [seed]
    best = (evaluator(seed), seed)
    for _ in range(gens):
        # LLM 集体变异当前最优
        mutants = [llm_mutate(best[1]) for _ in range(pop)]
        scored = [(evaluator(m), m) for m in mutants]
        scored.sort(key=lambda x: x[0])
        if scored[0][0] < best[0]:
            best = scored[0]          # 评估器选择,确定且快
    return best
​

运行 python3 code/main.py 会展示 HTN 规划器分解一个复合任务(计划中途触发 LLM 兜底),以及进化循环收敛到一个目标表达式。

💡 设计要点:HTN 的可靠性来自算子模式校验——validate_decomposition 这一步是铁闸。AlphaEvolve 的收敛性来自评估器确定且快——不确定或慢的评估器会让进化发散或跑不完。这两个「守门员」分别承起了两个方法的招牌性质,缺一不可。

三、框架对比

• HTN 规划器 —— pyhop、SHOP3,或为领域特定的策略执行自建。
• ChatHTN —— 研究代码;其模式(符号 + LLM 兜底)可干净地移植到任何 HTN 规划器。
• AlphaEvolve —— DeepMind 论文;其模式(集体 + 评估器)可复现。OpenEvolve 等开源分支正在出现。
• Agent 框架 —— 目前没有一个把 HTN 或 AlphaEvolve 当一等公民。要把它建成子 Agent 或后台 worker。

四、可复用产物

本节产出一份可复用技能(原课程 outputs/skill-hybrid-planner.md):

• skill-hybrid-planner.md:生成一个混合规划器脚手架(HTN 或进化),显式界定 LLM 的角色。包含一份选型决策树(任务是调度类还是优化类?有形式约束还是可检验适应度?有没有现成算子/评估器?),以及一份可靠性检查清单(HTN 的算子模式是否齐全?ChatHTN 的兜底是否被校验?AlphaEvolve 的评估器是否确定且快?)。

Python 代码(code/main.py)是独立可运行的双玩具,HTN 的算子/方法/兜底与进化的变异/选择都是逻辑无关的;把脚本分解器换成真实 LLM、把玩具评估器换成真实测试套件即可投入生产。

五、练习

1. (Easy) 给 HTN 规划器加回溯:当某个算子的后效在运行时失败,回滚并试下一个方法。
2. (Medium) 给 ChatHTN 加LLM 方法缓存:当 LLM 在状态模式 P 下分解了任务 T,存下结果。下次先查方法库。
3. (Medium) 把进化搜索的评估器换成真实测试套件。进化一个能过 20 个测试用例的排序函数,报告收敛代数。
4. (Hard) 读 AlphaEvolve 的评估器设计笔记。为你关心的领域(SQL 查询优化、测试套件最小化、部署 YAML)设计一个评估器。
5. (Hard) 组合:用 HTN 把复合任务分解成子任务,再在每个子任务的原语算子上跑进化搜索。哪里闪光,哪里过度工程?

本节要点回顾

1. 两类 ReAct/ReWOO 处理不好的场景:计划必须可证正确、优化有可机器检验的适应度。
2. HTN 四要素:任务(复合/原语)、方法(分解规则)、算子(原语动作带前后效)、状态。
3. ChatHTN 混合循环:先试方法,卡壳问 LLM 提议,算子模式校验后采纳,递归。
4. 责任分离:符号层管正确性,LLM 管覆盖面;LLM 是不可信提议者,模式是守门员。
5. 在线方法学习:把 LLM 分解泛化成新方法,可砍 75% LLM 查询。
6. AlphaEvolve 循环:种子 + 评估器 → LLM 集体变异 → 评估器选择 → 留最优再变异。
7. 硬约束:适应度函数必须可机器检验、确定且快,否则进化不收敛。
8. AlphaEvolve 战绩:56 年首改 Strassen、回收 0.7% Google 算力、FlashAttention 提速 32%。
9. 何时用哪个:调度/合规用 HTN,优化/带测试的代码用 AlphaEvolve,多步任务回退 ReAct/ReWOO。
10. 过度工程警示:大多数 Agent 任务两者都不需要,先够 ReAct/ReWOO。

下一节,我们回到工程模式——Anthropic 总结的 Agent 工作流模式(提示链、路由、并行化、编排者-工作者、评估者-优化者),把前几节的循环、规划、反思整理成可复用的生产编排骨架。