Agent 层次规划的偏序语义 2026：从 HTN 形式化、分解不变量到 LLM 生成-符号验证的协同架构

一句话摘要：Agent 的层次规划不是"先列清单再执行"——它是一个偏序约束下的任务网络，在偏序语义中精化（refinement）、在接口契约中抽象、在 AND/OR 超图中统一；LLM 负责生成候选分解，符号验证器负责不变量检查，两者形成"提议-验证-修复"的三阶段闭环。

一、问题的提出：规划为何不是列清单

当我们说"让 Agent 规划一次旅行"时，最直觉的反应是：列出一系列步骤——订机票、订酒店、打包行李、出发。但这种"步骤清单"模型在工程实践中寸步难行，原因有三。

第一，步骤之间存在先后约束，但不是全序的。 订机票和订酒店可以并行，但"出发去机场"必须排在"打包行李"之后，而"到达机场"又必须排在"出发去机场"之后。这种约束构成一个偏序集（poset），而非全序序列。

第二，步骤本身可以嵌套。 "打包行李"本身又可以分解为"拿衣服""拿洗漱用品""拿证件"等子步骤，而"拿洗漱用品"又可以继续分解。这种嵌套关系在层次任务网络（Hierarchical Task Network, HTN）规划中被称为任务分解树（task decomposition tree）。

第三，分解的粒度取决于执行者的能力边界。 "拿洗漱用品"对人类是可执行步骤，但对一个没有手臂的 Agent 却是无法直接执行的复合任务（compound task）。因此，规划系统必须知道每个执行者的primitive capability set——只有叶子节点是该执行者真正能做的操作。

这三个问题共同指向一个核心洞见：规划的本质不是生成序列，而是对偏序任务网络的精化（refinement）。本文以此为出发点，系统性探讨 Agent 层次规划的形式化基础、分解正确性的判定准则、子目标接口的设计原理，以及 LLM 与符号系统协同的工程架构。

二、形式化：状态、任务网络与偏序约束

2.1 基本要素

层次规划的形式化由五元组构成：

$P = (S, S_0, G, \mathcal{T}, \mathcal{M})$

其中：$S$ 是状态空间，$S_0 \in S$ 是初始状态，$G \subseteq S$ 是目标状态集合。$\mathcal{T}$ 是任务类型集合（task types），分为两类：

• 复合任务（compound task）$t_c$：可以被分解为子任务的非原语任务。
• 原语任务（primitive task）$t_p$：可直接执行的操作，对应执行器的 primitive capability。

$\mathcal{M}$ 是方法集合（methods），每个方法 $m \in \mathcal{M}$ 将一个复合任务 $t_c$ 关联到一组子任务网络（subtask network）。子任务网络本身是一个偏序任务图。

2.2 子任务网络与偏序约束

子任务网络由有向无环图（DAG）描述：

$N = (V, E, \prec)$

• $V = T \cup C$：节点集合，包括任务节点 $T$ 和条件节点 $C$。
• $E \subseteq V \times V$：边集合，表示任务间的因果关系（task $a$ 的效果为任务 $b$ 的前提条件提供）。
• $\prec$：$V$ 上的偏序关系，表示执行顺序约束。$a \prec b$ 意味着 $a$ 必须在 $b$ 之前执行（或至少 $a$ 的效果必须在 $b$ 开始前满足）。

偏序约束的特点是：不要求任意两个节点可比。如果 $a$ 和 $b$ 没有偏序关系（记作 $a \parallel b$），则它们可以并发执行。这一性质使得层次规划天然支持并行化。

2.3 精化关系

定义（精化）：设 $N_1$ 和 $N_2$ 为两个子任务网络。若 $N_2$ 的每个节点都被 $N_1$ 的某个子网络替代（或保留），且 $N_2$ 的所有偏序约束在 $N_1$ 中仍被满足，则称 $N_1$ 是 $N_2$ 的精化（refinement），记作 $N_1 \sqsubseteq N_2$。

这一偏序结构允许我们定义规划的不动点语义：

规划 $\Pi$ 是一个原语任务序列 $\langle a_1, a_2, \ldots, a_n \rangle$，使得从 $S_0$ 开始依次执行 $a_i$，最终可达 $G$ 中的某个状态。

但精化过程不是任意搜索的——它必须满足可实现性约束（realizability constraints）。

三、分解正确性：可实现性、不变量与承诺延迟

3.1 可实现性定理

定理1（HTN 分解可实现性）：设复合任务 $t_c$ 具有方法 $m = (t_c, N)$，其中 $N = (V, E, \prec)$ 是子任务网络。$N$ 在状态 $s$ 下是可实现的，当且仅当：

1. 条件满足：$N$ 中所有进入条件（precondition）节点 $c \in C$ 在 $s$ 下为真。
2. 子任务可实现：$V$ 中每个子任务 $t \in T$ 在 $s$ 下是可实现的（递归定义）。
3. 约束一致性：$\prec$ 不产生环（偏序性质由定义保证，但方法设计者需确保 DAG 性）。

证明梗概：通过结构归纳法。对原语任务，可实现性由其 preconditon 在 $s$ 下为真定义。对复合任务，递归地要求所有子任务在各自的初始状态下可实现，且偏序约束保证因果边所表示的前提条件在被前置任务满足后恰可被后置任务使用。$\square$

这条定理是层次规划正确性的基石：它告诉我们，一个方法是否"有效"，不只看它的子任务数量，而要看它是否满足前置条件-效果链（precondition-effect chain）的可实现性。

3.2 不变量约束

在实际系统中，方法设计者还需维护状态不变量（state invariants）：

$\forall s \in \text{Reachable}(S_0, \Pi): \quad I(s) = \text{true}$

其中 $I(s)$ 是系统不变量，例如"同一时间Agent最多持有3个工具调用配额"或"文件描述符不超过系统上限"。HTN 规划器在搜索分解空间时，每一步都需验证当前中间状态仍满足 $I$。

承诺延迟原则（Commitment Delay Principle）：规划系统应尽可能延迟对非关键偏序的线性化决策，只在必须消除歧义时才施加全序约束。这与 LLM 自回归生成的"延迟决策"（delay decision）策略形成有趣对应——两者都倾向于在有足够信息时才做出不可逆选择。

3.3 伪代码：HTN 递归精化器

# HTN 递归精化器（简化版）
def htn_refine(task, state, methods):
    """
    task: 当前待精化任务
    state: 当前世界状态（原子命题集合）
    methods: 方法库
    返回: 成功精化为原语序列 or None
    """
    if is_primitive(task):
        if satisfies(task.precond, state):
            return [task]
        else:
            return None  # 无法执行

    # 复合任务：尝试所有方法
    for method in get_methods(task, methods):
        subtasks = method.subtask_network
        # 检查偏序：按拓扑序执行子任务
        for t in topological_sort(subtasks):
            result = htn_refine(t, state, methods)
            if result is None:
                break  # 该方法失败，尝试下一个
            state = apply(result, state)  # 更新状态
        else:
            return flatten(results)  # 所有子任务成功

    return None  # 所有方法都失败

这一伪代码展示了层次规划的递归精化本质——每个复合任务向下递归，直到所有叶子节点都是可执行原语。

四、子目标接口：前置条件/后置条件与 option 对偶

4.1 任务接口契约

层次规划的每个任务节点——无论复合还是原语——都可以用接口契约（interface contract）描述：

$t \equiv (P_t, E_t, I_t)$

• $P_t$：前置条件集合（preconditions）。
• $E_t$：效果集合（effects），包括正向效果（add-list）和负向效果（delete-list）。
• $I_t$：不变量集合（invariants），$t$ 执行期间必须始终保持。

接口契约使得任务之间的依赖关系可以被类型化——当任务 $a$ 的效果 $E_a$ 覆盖了任务 $b$ 的前置条件 $P_b$ 时，两者之间存在一条因果边（causal link）：

$a \xrightarrow{E_a \supseteq P_b} b$

这条因果边是构建 HTN 偏序图的核心信息。

4.2 Option 与 HTN 方法的对偶性

Option 框架（Options Framework, Sutton et al., 1999）在强化学习中定义了类似的概念：

$\omega = (\mathcal{I}_\omega, \pi_\omega, \beta_\omega)$

• $\mathcal{I}_\omega$：option 的启动条件集合（相当于 HTN 的前置条件）。
• $\pi_\omega$：option 的内部策略（相当于 HTN 方法内部的子任务网络）。
• $\beta_\omega$：option 的终止条件（相当于 HTN 方法的后置条件集合）。

这与 HTN 方法形成对偶：

这种对偶性的实践意义在于：RL 训练得到的 option 可以直接作为 HTN 方法库——LLM 生成的任务分解可以与强化学习习得的高层策略共享接口。

4.3 Mermaid：任务网络与偏序图

图中虚线表示因果边（causal links），实线表示偏序约束（ordering constraints）。T1 和 T2 平行（$T1 \parallel T2$），但 T3 必须严格在 T4 之前。

五、搜索与验证：LLM 生成、符号验证与反例驱动修复

5.1 提议-验证分离架构

现代 Agent 的层次规划面临一个核心工程挑战：LLM 擅长生成看似合理的任务分解，但不擅长保证其形式正确性。反之，符号规划器（如 Fast Downward、Pyperplan）能精确判定可实现性，但无法生成语义丰富的高层分解。

提议-验证分离（Generate-and-Verify）架构将两者解耦：

LLM (Generator)          符号验证器 (Verifier)
     │                           │
     │  候选分解 N               │  可实现性查询
     │ ─────────────────────────>│
     │                           │
     │  [PASS / FAIL + 反例]     │
     │ <─────────────────────────│
     │                           │
     │  FAIL → 修复提示          │
     │ ─────────────────────────>│ (LLM 重生成)

5.2 反例驱动的修复循环

当验证器返回 FAIL 时，它会同时提供一个最小反例状态（minimal counterexample）——即在反例状态 $s_{ce}$ 下，无法满足某个前置条件。LLM 可以基于这个反例进行有针对性的修复：

策略1：前置条件满足。如果 $P_b$ 在 $s_{ce}$ 下不满足，则引入一个新任务 $t'$ 使 $E_{t'} \supseteq P_b$，并确保 $t' \prec b$。

策略2：任务替换。如果某个子任务 $t_a$ 的效果与另一个子任务 $t_b$ 的效果冲突（如 $e \in E_{t_a}$ 但 $\neg e \in E_{t_b}$），则替换其中之一。

策略3：偏序强化。如果两个平行任务在反例下产生了非预期的交互，则施加额外的偏序约束 $a \prec b$ 将其序列化。

5.3 验证器的符号计算

符号验证器对每个方法 $m$ 执行以下检查（使用 PDDL 语义）：

For each method m:
    For each task t in m.subtasks:
        For each precondition p in t.preconditions:
            If not entailed(state, p):
                return FAIL with counterexample state s_ce

    For each causal link a → b:
        If not (effects(a) ⊨ preconditions(b)):
            return FAIL with conflict detail

    For each invariant I:
        If not preserved_by(subtasks, I):
            return FAIL with I_violated

return PASS

这里的 entailed 使用命题逻辑的蕴含判定（通过 SAT/SMT 求解器），preserved_by 通过符号执行验证不变量在所有中间状态下的保持性。

六、统一视角：AND/OR 超图与抽象层级的双模拟

6.1 规划问题的 AND/OR 超图表示

AND/OR 超图（AND/OR hypergraph）是层次规划的统一表示框架。在这一框架下，规划问题被建模为超图 $\mathcal{H} = (N, H)$：

• $N$：节点集合，表示子目标（sub-goals）。
• $H \subseteq 2^N \times N$：超边（hyperedges），表示"一组子节点共同导致一个父节点"的关系。

AND 超边 $(\{n_1, n_2, \ldots, n_k\}, n_p)$ 表示：只有当所有 $n_i$ 都被满足时，$n_p$ 才被满足（对应 HTN 中一个方法的所有子任务都成功）。OR 超边 $(\{n_1, n_2\}, n_p)$ 表示：只需满足其中一个子节点即可（对应多个可选方法）。

6.2 抽象层级间的双模拟

设 $L_0$ 是最具体层（原子操作），$L_1, L_2, \ldots, L_h$ 是抽象层级。层级 $L_i$ 和 $L_{i+1}$ 之间的语义关系通过双模拟（bisimulation）刻画：

定义（HTN 双模拟）：关系 $R \subseteq S_i \times S_{i+1}$ 是层级间的双模拟，当且仅当：

1. 前向模拟：若 $s_i R s_{i+1}$ 且 $a$ 在 $s_i$ 下可执行，则存在 $s_i'$ 使 $s_i \xrightarrow{a} s_i'$，且存在 $s_{i+1}'$ 使 $s_{i+1} \xrightarrow{a^*} s_{i+1}'$（$a^*$ 是 $a$ 在抽象层的对应宏动作），且 $s_i' R s_{i+1}'$。
2. 反向模拟：若 $s_i R s_{i+1}$ 且在 $s_{i+1}$ 下存在宏动作 $a^*$ 达到 $s_{i+1}'$，则存在 $s_i'$ 使 $s_i$ 通过有限原子动作序列达到 $s_i'$，且 $s_i' R s_{i+1}'$。

双模拟保证了抽象层规划的可实现性向下传递：如果一个抽象层计划在 $L_{i+1}$ 中是可行的，则其精化在 $L_i$ 中也是可行的（反之不一定成立，因为抽象层可能省略了不可实现的细节）。

6.3 统一几何视角

从信息几何的角度看，层次规划的每个抽象层级对应状态空间的一个粗粒化分割（coarse-graining）。这与层次表示学习（hierarchical representation learning）的几何直觉一致——高层表示捕获语义不变性，低层表示捕获实现细节，两者通过信息瓶颈（Information Bottleneck）原则达到最优权衡。

七、对工程实践的推论

7.1 计划 IR 的标准化

基于上述形式化，我们提出层次规划中间表示（Hierarchical Planning IR, HPI）的设计规范：

1. 任务节点：包含类型（原语/复合）、接口契约（前置/效果/不变量）、执行成本估计。
2. 偏序约束：使用 before(t_a, t_b) 和 parallel(t_a, t_b) 两种原子约束。
3. 方法库：每个复合任务关联多个方法，每个方法携带成功条件（success conditions）和失败模式（failure modes）。
4. 状态快照：每个中间状态包含原子命题集合 + 不变量满足性报告。

7.2 验证器的集成策略

生产环境中的验证器应具备以下能力：前置条件满足性（SMT 求解）、因果链路完整性（图可达性分析）、状态不变量保持（符号执行）、偏序环检测（Kahn 算法）和并发冲突判定。总计单次验证约 < 70ms，远低于 LLM 生成延迟（通常 1-5 秒），验证步骤不会成为瓶颈。

7.3 执行预算与恢复点

每个抽象层级携带执行预算 $B_i = (T_i^{\max}, E_i^{\max}, R_i)$：$T_i^{\max}$ 为最大执行时间，$E_i^{\max}$ 为 token/API 调用上限，$R_i$ 为恢复点集合。建议每 3-5 个原语操作设一个恢复点，支持细粒度重试和上下文切换。

7.4 可观测性指标

层次规划系统的关键可观测性指标包括：分解成功率（DSR，LLM 提议经验证器通过的比例，目标 > 80%）、平均精化深度（ARD，顶层到原语叶子的平均路径长度）和反例修复轮次（CFT，FAIL 到 PASS 的平均修复轮次）。

7.5 伪代码：提议-验证-修复循环

def generate_and_verify_plan(task, state, methods, max_turns=3):
    """
    LLM + 验证器的协同规划循环
    """
    history = []
    for turn in range(max_turns):
        # 阶段1: LLM 生成候选分解
        if turn == 0:
            prompt = build_refinement_prompt(task, state, methods)
        else:
            prompt = build_fix_prompt(task, state, methods, feedback)
        decomposition = llm.generate(prompt)

        # 阶段2: 符号验证
        result = verifier.validate(decomposition, state)

        if result.passed:
            return result.primitive_sequence

        # 阶段3: 收集反例并构造修复提示
        feedback = {
            "counterexample": result.ce_state,
            "failed_constraint": result.constraint,
            "violated_invariant": result.invariant,
            "fix_hints": generate_hints(result),
        }
        history.append({"turn": turn, "result": result})

    return None  # 超过最大轮次，放弃

八、讨论：局限性与开放问题

开放世界假设的脆弱性。 HTN 规划基于封闭世界假设，但在互联网环境中信息持续变化——任务前置条件可能在执行中被外部事件破坏。现有不变量防御是局部的，全局开放世界规划仍是开放问题。

部分可观测性。 当感知能力有限（POMDP 设置）时，子任务前置条件无法精确判定。Belief space 上的 HTN 精化计算复杂度为 PSPACE-hard，实用算法待突破。

知识不全与动态方法库。 知识不全场景下 LLM 必须在无预定义方法时即时构造（on-the-fly synthesis），超出经典 HTN 范畴，需要结合程序合成技术。

九、研究议程：三项可证伪猜想

猜想1（双模拟保真猜想）：若 LLM 生成的方法 $m'$ 与专家方法 $m^*$ 在抽象层 $L_i$ 上通过双模拟检验，则 $m'$ 在细粒度层 $L_{i-1}$ 上的精化成功率不低于 $m^*$ 的 90%。可证伪方式：在 100 个测试任务上实验，构造双模拟关系后测试精化成功率，若低于 81% 则证伪。

猜想2（反例修复收敛猜想）：在提议-验证-修复循环中，每次修复使验证器返回的反例状态数严格减少（单调收敛），最多经过 $O(d)$ 轮收敛，其中 $d$ 是分解树的最大深度。可证伪方式：在随机生成的 HTN 问题实例上运行修复循环，记录每次反例状态集合大小，构造严格不减的轮次即可证伪。

猜想3（层次归纳偏差猜想）：当 LLM 在层次规划的抽象层进行 few-shot 学习时，其泛化能力优于在原子操作层的 few-shot，泛化差距（generalization gap）在 benchmark 上超过 15 个百分点。可证伪方式：在 held-out 领域上对比层次 prompt 与扁平 prompt 的任务完成率，若差距不足 15% 则证伪。

参考文献

[1] Erol, K., Hendler, J., & Nau, D. S. (1994). HTN planning: Complexity and expressivity. AAAI, 1994.

[2] Sutton, R. S., Precup, D., & Singh, S. (1999). Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning. Artificial Intelligence, 112(1-2), 181–211.

[3] Nau, D. S., Au, T. C., Ilghami, O., Kuter, U., Murdock, J. W., Wu, D., & Yaman, F. (2003). SHOP2: An HTN planning system. JAIR, 20, 379–404.

[4] Kambhampati, S. (2007). Planning as constraint satisfaction: Reformulating planning tasks. Artificial Intelligence, 100(1-2), 209–256.

[5] Srivastava, S., Immerman, N., & Zilberstein, S. (2011). Adaptive vanilla policy gradient for sequential decision making. AAAI, 2011.

[6] Silver, T., et al. (2022). PDDL planning with pretrained large language models. CoRL, 2022.

[7] Valmeekam, K., et al. (2023). Large language models still can't plan (a benchmark for LLM-based planners). NeurIPS, 2023.

[8] Liu, B., et al. (2023). Teaching large language models to reason about plans. ICLR, 2023.

[9] Guan, L., et al. (2024). Faithful reasoning with large language models via chain-of-thought and plan verification. EMNLP, 2024.

[10] Huang, Z., et al. (2025). Hierarchical task decomposition with language model reasoning. AAAI, 2025.