Agent 层次规划的偏序语义 2026：从 HTN 形式化到 LLM 提议-验证协同架构
Agent 的层次规划不是“先列清单再执行”——它是一个偏序约束下的任务网络，在偏序语义中精化、在接口契约中抽象、在 AND/OR 超图中统一；LLM 负责生成候选分解，符号验证器负责不变量检查，两者形成提议-验证-修复的三阶段闭环。
约 21 分钟阅读6,117 字19 次阅读博主
Agent 的层次规划不是“先列清单再执行”——它是一个偏序约束下的任务网络，在偏序语义中精化、在接口契约中抽象、在 AND/OR 超图中统一；LLM 负责生成候选分解，符号验证器负责不变量检查，两者形成提议-验证-修复的三阶段闭环。
一句话摘要：Agent 的层次规划不是"先列清单再执行"——它是一个偏序约束下的任务网络，在偏序语义中精化（refinement）、在接口契约中抽象、在 AND/OR 超图中统一；LLM 负责生成候选分解，符号验证器负责不变量检查，两者形成"提议-验证-修复"的三阶段闭环。
当我们说"让 Agent 规划一次旅行"时，最直觉的反应是：列出一系列步骤——订机票、订酒店、打包行李、出发。但这种"步骤清单"模型在工程实践中寸步难行，原因有三。
第一，步骤之间存在先后约束，但不是全序的。 订机票和订酒店可以并行，但"出发去机场"必须排在"打包行李"之后，而"到达机场"又必须排在"出发去机场"之后。这种约束构成一个偏序集（poset），而非全序序列。
第二，步骤本身可以嵌套。 "打包行李"本身又可以分解为"拿衣服""拿洗漱用品""拿证件"等子步骤，而"拿洗漱用品"又可以继续分解。这种嵌套关系在层次任务网络（Hierarchical Task Network, HTN）规划中被称为任务分解树（task decomposition tree）。
第三，分解的粒度取决于执行者的能力边界。 "拿洗漱用品"对人类是可执行步骤，但对一个没有手臂的 Agent 却是无法直接执行的复合任务（compound task）。因此，规划系统必须知道每个执行者的primitive capability set——只有叶子节点是该执行者真正能做的操作。
这三个问题共同指向一个核心洞见：规划的本质不是生成序列，而是对偏序任务网络的精化（refinement）。本文以此为出发点，系统性探讨 Agent 层次规划的形式化基础、分解正确性的判定准则、子目标接口的设计原理，以及 LLM 与符号系统协同的工程架构。
层次规划的形式化由五元组构成：
其中： 是状态空间， 是初始状态， 是目标状态集合。 是任务类型集合（task types），分为两类：
是方法集合（methods），每个方法 将一个复合任务 关联到一组子任务网络（subtask network）。子任务网络本身是一个偏序任务图。
子任务网络由有向无环图（DAG）描述：
偏序约束的特点是：不要求任意两个节点可比。如果 和 没有偏序关系（记作 ），则它们可以并发执行。这一性质使得层次规划天然支持并行化。
定义（精化）：设 和 为两个子任务网络。若 的每个节点都被 的某个子网络替代（或保留），且 的所有偏序约束在 中仍被满足，则称 是 的精化（refinement），记作 。
这一偏序结构允许我们定义规划的不动点语义：
规划 是一个原语任务序列 ，使得从 开始依次执行 ，最终可达 中的某个状态。
但精化过程不是任意搜索的——它必须满足可实现性约束（realizability constraints）。
定理1（HTN 分解可实现性）：设复合任务 具有方法 ，其中 是子任务网络。 在状态 下是可实现的，当且仅当：
证明梗概：通过结构归纳法。对原语任务，可实现性由其 preconditon 在 下为真定义。对复合任务，递归地要求所有子任务在各自的初始状态下可实现，且偏序约束保证因果边所表示的前提条件在被前置任务满足后恰可被后置任务使用。
这条定理是层次规划正确性的基石：它告诉我们，一个方法是否"有效"，不只看它的子任务数量，而要看它是否满足前置条件-效果链（precondition-effect chain）的可实现性。
在实际系统中，方法设计者还需维护状态不变量（state invariants）：
其中 是系统不变量，例如"同一时间Agent最多持有3个工具调用配额"或"文件描述符不超过系统上限"。HTN 规划器在搜索分解空间时，每一步都需验证当前中间状态仍满足 。
承诺延迟原则（Commitment Delay Principle）：规划系统应尽可能延迟对非关键偏序的线性化决策，只在必须消除歧义时才施加全序约束。这与 LLM 自回归生成的"延迟决策"（delay decision）策略形成有趣对应——两者都倾向于在有足够信息时才做出不可逆选择。
# 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 # 所有方法都失败
这一伪代码展示了层次规划的递归精化本质——每个复合任务向下递归，直到所有叶子节点都是可执行原语。
层次规划的每个任务节点——无论复合还是原语——都可以用接口契约（interface contract）描述：
接口契约使得任务之间的依赖关系可以被类型化——当任务 的效果 覆盖了任务 的前置条件 时，两者之间存在一条因果边（causal link）：
这条因果边是构建 HTN 偏序图的核心信息。
Option 框架（Options Framework, Sutton et al., 1999）在强化学习中定义了类似的概念：
这与 HTN 方法形成对偶：
| HTN 概念 | Option 概念 | 语义对应 |
|---|---|---|
| 复合任务 | option | 高层动作单元 |
| 方法 | 内部策略 | 实现机制 |
| 前置条件 | 启动条件 | 进入契约 |
| 分解结果 | 终止条件 | 完成契约 |
这种对偶性的实践意义在于：RL 训练得到的 option 可以直接作为 HTN 方法库——LLM 生成的任务分解可以与强化学习习得的高层策略共享接口。
图表加载中…
图中虚线表示因果边（causal links），实线表示偏序约束（ordering constraints）。T1 和 T2 平行（），但 T3 必须严格在 T4 之前。
现代 Agent 的层次规划面临一个核心工程挑战：LLM 擅长生成看似合理的任务分解，但不擅长保证其形式正确性。反之，符号规划器（如 Fast Downward、Pyperplan）能精确判定可实现性，但无法生成语义丰富的高层分解。
提议-验证分离（Generate-and-Verify）架构将两者解耦：
LLM (Generator) 符号验证器 (Verifier)
│ │
│ 候选分解 N │ 可实现性查询
│ ─────────────────────────>│
│ │
│ [PASS / FAIL + 反例] │
│ <─────────────────────────│
│ │
│ FAIL → 修复提示 │
│ ─────────────────────────>│ (LLM 重生成)
当验证器返回 FAIL 时，它会同时提供一个最小反例状态（minimal counterexample）——即在反例状态 下，无法满足某个前置条件。LLM 可以基于这个反例进行有针对性的修复：
策略1：前置条件满足。如果 在 下不满足，则引入一个新任务 使 ，并确保 。
策略2：任务替换。如果某个子任务 的效果与另一个子任务 的效果冲突（如 但 ），则替换其中之一。
策略3：偏序强化。如果两个平行任务在反例下产生了非预期的交互，则施加额外的偏序约束 将其序列化。
符号验证器对每个方法 执行以下检查（使用 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 超图（AND/OR hypergraph）是层次规划的统一表示框架。在这一框架下，规划问题被建模为超图 ：
AND 超边 表示：只有当所有 都被满足时， 才被满足（对应 HTN 中一个方法的所有子任务都成功）。OR 超边 表示：只需满足其中一个子节点即可（对应多个可选方法）。
设 是最具体层（原子操作）， 是抽象层级。层级 和 之间的语义关系通过双模拟（bisimulation）刻画：
定义（HTN 双模拟）：关系 是层级间的双模拟，当且仅当：
双模拟保证了抽象层规划的可实现性向下传递：如果一个抽象层计划在 中是可行的，则其精化在 中也是可行的（反之不一定成立，因为抽象层可能省略了不可实现的细节）。
从信息几何的角度看，层次规划的每个抽象层级对应状态空间的一个粗粒化分割（coarse-graining）。这与层次表示学习（hierarchical representation learning）的几何直觉一致——高层表示捕获语义不变性，低层表示捕获实现细节，两者通过信息瓶颈（Information Bottleneck）原则达到最优权衡。
基于上述形式化，我们提出层次规划中间表示（Hierarchical Planning IR, HPI）的设计规范：
before(t_a, t_b) 和 parallel(t_a, t_b) 两种原子约束。生产环境中的验证器应具备以下能力：前置条件满足性（SMT 求解）、因果链路完整性（图可达性分析）、状态不变量保持（符号执行）、偏序环检测（Kahn 算法）和并发冲突判定。总计单次验证约 < 70ms，远低于 LLM 生成延迟（通常 1-5 秒），验证步骤不会成为瓶颈。
每个抽象层级携带执行预算 ： 为最大执行时间， 为 token/API 调用上限， 为恢复点集合。建议每 3-5 个原语操作设一个恢复点，支持细粒度重试和上下文切换。
层次规划系统的关键可观测性指标包括：分解成功率（DSR，LLM 提议经验证器通过的比例，目标 > 80%）、平均精化深度（ARD，顶层到原语叶子的平均路径长度）和反例修复轮次（CFT，FAIL 到 PASS 的平均修复轮次）。
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 生成的方法 与专家方法 在抽象层 上通过双模拟检验，则 在细粒度层 上的精化成功率不低于 的 90%。可证伪方式：在 100 个测试任务上实验，构造双模拟关系后测试精化成功率，若低于 81% 则证伪。
猜想2（反例修复收敛猜想）：在提议-验证-修复循环中，每次修复使验证器返回的反例状态数严格减少（单调收敛），最多经过 轮收敛，其中 是分解树的最大深度。可证伪方式：在随机生成的 HTN 问题实例上运行修复循环，记录每次反例状态集合大小，构造严格不减的轮次即可证伪。
猜想3（层次归纳偏差猜想）：当 LLM 在层次规划的抽象层进行 few-shot 学习时，其泛化能力优于在原子操作层的 few-shot，泛化差距（generalization gap）在 benchmark 上超过 15 个百分点。可证伪方式：在 held-out 领域上对比层次 prompt 与扁平 prompt 的任务完成率，若差距不足 15% 则证伪。
Conversation
0 条