第十讲：HTN 分层任务网络

HTN（Hierarchical Task Network）把复杂任务拆解为有序的原始动作序列，提供 LLM 无法单独给出的确定性和可验证性：每一层分解都是显式的逻辑推断，而非统计采样——这正是 EICPS 用 HTN 约束 LLM 输出、保障任务级别安全性的数学基础。

符号	含义
$t$	任务（Task），可为复合或原始
$\mathcal{T}_c$	复合任务集（需进一步分解）
$\mathcal{T}_p$	原始任务集（可直接执行）
$m = (\text{name}, \text{pre}, \text{sub})$	方法（Method）：前置条件 + 子任务网络
$\mathcal{N} = (T, \prec, \alpha)$	任务网络：任务集、偏序约束、标签映射
$\delta$	分解（Decomposition）： $t \xrightarrow{m} \mathcal{N}'$
$\sigma$	完整任务解（原始任务的全序序列）

前言：理论发展沿革

1975 年，Sacerdoti 在 NOAH 系统中首次引入”程序网络”（Procedural Networks）的概念，允许任务按层次组织，而不是在单层状态空间中搜索。这是 AI 规划史上的范式转变：从”在状态空间搜索路径”转向”在任务空间递归分解”。

1994 年，Erol、Hendler 与 Nau 发表了 HTN 规划的奠基性形式化工作，严格定义了任务、方法和分解的语法与语义，证明了 HTN 规划的表达能力（严格超过 STRIPS），并建立了完备性定理。HTN 的核心直觉是：专家知识可以被编码为分解方法库，而不是依赖搜索发现。

2000 年代，SHOP 和 SHOP2 系统（Nau et al.）将 HTN 推向实用：SHOP2 在第一届 IPC（国际规划竞赛）中赢得多项冠军，并被美国军方用于后勤规划。此后 HTN 在游戏 AI、机器人任务规划和工业流程自动化中广泛应用。

2020 年代，大语言模型（LLM）的兴起带来了新的挑战与机会：LLM 能从自然语言推断高层任务意图，但其输出不具备 HTN 的形式化保证。EICPS 的创新在于 LLM + HTN 协同架构：LLM 负责从 Proposal（自然语言）提取高层任务参数，HTN 负责将其分解为满足物理约束和安全条件的原始动作序列，两者各司其职。

1 HTN 基本结构

任务分为两类：

复合任务 $t_c \in \mathcal{T}_c$ ：抽象意图，需用方法分解，如”更换防振锤”
原始任务 $t_p \in \mathcal{T}_p$ ：可直接执行的原子动作，如”移动关节到 $q^*$ ”、“夹爪闭合”

任务网络 $\mathcal{N} = (T, \prec, \alpha)$ 由三部分构成：

$T$ ：任务标签集合
$\prec \subseteq T \times T$ ：偏序约束（排序关系）
$\alpha: T \to \mathcal{T}_c \cup \mathcal{T}_p$ ：标签到任务的映射

方法 $m = (\text{name}(m),\; \text{task}(m),\; \text{pre}(m),\; \text{net}(m))$ ：

$\text{task}(m)$ ：适用的复合任务
$\text{pre}(m)$ ：前置条件（状态谓词集合）
$\text{net}(m)$ ：替换子任务网络 $\mathcal{N}'$

2 HTN 规划算法

HTN 规划从初始任务网络 $\mathcal{N}_0$ 出发，递归分解直到所有任务均为原始任务：

function HTN-PLAN(state s, task-network N):
  if N contains only primitive tasks:
    if all primitives are applicable in s:
      return linearization σ of N
    else: return FAIL
  
  选取 N 中无前驱的复合任务 t_c
  for each method m with task(m) = t_c:
    if pre(m) satisfied in s:
      N' = replace t_c with net(m) in N
      result = HTN-PLAN(s, N')
      if result ≠ FAIL: return result
  
  return FAIL   # 所有方法均不适用

方法选择的偏序搜索：当多个方法满足前置条件时，HTN 按优先级或领域知识排序，引导搜索效率。对 EICPS 的工程场景，方法库由领域专家设计，通常分解深度 $\leq 5$ ，搜索空间有限。

3 HTN 的形式化保证

相比 LLM 直接生成动作序列，HTN 提供三项工程关键保证：

1. 完备性（在有限分支假设下）：若存在合法分解，算法必然找到；不存在时明确返回 FAIL，而非生成”看起来合理但物理不可行”的序列。

2. 前置条件强制执行：每个方法的 $\text{pre}(m)$ 在分解时检验，确保动作序列的因果一致性：

$\text{pre}(m) \subseteq \text{state}(s) \Rightarrow m \text{ 可用}$

3. 偏序约束的传播： $\prec$ 保证任务间的时序依赖，如”先定位再操作”不会被搜索过程违反。

4 HTN 在 EICPS 中的工程化

4.1 EICPS 方法库结构

以架空线路运检为例，HTN 方法库的第一层分解：

compound: INSPECT_CLAMP(target_id)
  methods:
    m1: [pre: weather=OK ∧ battery>30%]
        → POSITION(target_id), VISUAL_CHECK(target_id),
           if defect: REPAIR(target_id)
    m2: [pre: weather=WIND ∧ battery>60%]
        → HOLD_POSITION, VISUAL_CHECK(target_id)  # 大风模式：不操作，只巡检

compound: REPAIR(target_id)
  methods:
    m_replace: [pre: tool=HAMMER ∧ accessible=True]
               → GRIP(old_clamp), REMOVE, INSTALL(new_clamp), VERIFY
    m_abort:   [pre: accessible=False]
               → SAFE_WITHDRAW, REPORT_FAIL

每个原始任务（POSITION、GRIP 等）对应 ETL 语言中的一条指令，最终由脊髓层执行。

4.2 LLM + HTN 协同接口

Brain 层的任务处理流程：

Proposal (自然语言):
  "请处理 3 号铁塔东侧第 2 片绝缘子上的防振锤，
   可能需要更换，电量 78%，风速 4 m/s"
      ↓  LLM（参数提取 + 意图解析）
HTN 输入:
  task = INSPECT_CLAMP(target_id=T3E2)
  state = {battery: 78%, weather: MILD_WIND, tool: HAMMER}
      ↓  HTN 分解（确定性推断）
ActionPlan（原始任务序列）:
  [POSITION(T3E2), VISUAL_CHECK(T3E2),
   GRIP(old_clamp), REMOVE, INSTALL(new_clamp), VERIFY]
  ordering: POSITION ≺ VISUAL_CHECK ≺ GRIP ≺ REMOVE ≺ INSTALL ≺ VERIFY
      ↓  STL 规约打包（第八讲）
  + stl_spec: G[0,T](dist_wire > 0.3m) ∧ G[0,T](τ < τ_max)

LLM 的职责：从非结构化自然语言提取结构化参数（target_id、状态谓词）。HTN 的职责：基于这些参数和当前状态进行形式化分解。两者分工明确，LLM 的不确定性被限制在参数提取层，不传播到规划逻辑。

4.3 Guard 评估的形式化

每个 HTN 方法的 $\text{pre}(m)$ 对应一组Guard 条件，在 EvidencePack 中记录选用了哪个方法及其前置条件的满足状态：

$\text{EvidencePack.method\_log} = \{(t_i,\; m_i,\; \text{pre}(m_i),\; \text{satisfied}_i)\}$

这使得事后审计可以追溯：为什么选择了方法 $m_i$ 而不是 $m_j$ ？前置条件在分解时是否真实满足？

5 与其他模块的数学联系

相关模块	联系方式
STL（第八讲）	HTN 每个原始任务对应一条 STL 规约；任务成功 $\Leftrightarrow$ 对应规约 $\rho > 0$
CBF（第九讲）	HTN 分解后，每个原始任务的执行期间由 CBF 提供实时安全保证
Flow-Jump（第三讲）	HTN 方法选择失败（所有 pre 不满足）触发 Jump，切换到安全退出模式
EKF（第十一讲）	HTN 前置条件中的状态谓词（如 battery > 30%）依赖 EKF 的状态估计

Notebook

本讲配套 Colab Notebook 包含：①HTN 任务分解树可视化；②方法库设计与回溯搜索演示；③LLM 参数提取 + HTN 分解协同流程模拟；④Guard 条件满足率统计与 EvidencePack 生成。