开篇导语
在上一篇文章中，我们初步认识了 HTN 规划的基本思想和它相比经典规划的优势。但要真正掌握 HTN，就必须深入其形式化定义——这是理解算法、阅读论文、甚至自己实现规划器的必经之路。
本文将从数学角度详细拆解 HTN 的核心概念：任务、方法、分解机制，以及那个让人困惑的"不可判定性"。不用担心，我会用具体的例子和图示帮你理解这些抽象概念。
阅读提示：本文涉及一些形式化符号，但不需要深厚的数学基础。重点是理解概念之间的关系，而不是记住公式。
一、HTN 规划问题的形式化定义
1.1 基本组成部分
一个 HTN 规划问题可以形式化地表示为一个六元组：
$$ \mathcal{P} = (S, s_0, A, T, M, tn_I) $$
各元素的含义：
| 符号 | 名称 | 含义 |
|---|---|---|
| $S$ | 状态空间 | 所有可能的状态集合 |
| $s_0$ | 初始状态 | 规划开始时的世界状态 |
| $A$ | 原子动作集 | 可直接执行的基本动作 |
| $T$ | 任务集合 | 分为复合任务 $T_c$ 和原子任务 $T_p$ |
| $M$ | 方法集合 | 定义如何分解复合任务的"配方" |
| $tn_I$ | 初始任务网络 | 需要完成的顶层任务 |
一个直观的类比：想象你要做一道复杂的菜（复合任务）。你需要：
- 厨房现状（初始状态 $s_0$）：冰箱里有什么食材
- 基本操作（原子动作 $A$）：切、炒、煮等
- 菜谱步骤（方法 $M$）：先做什么、后做什么
- 最终目标（初始任务网络 $tn_I$）：做出这道菜
HTN 规划就是根据菜谱，把做这道菜分解为一系列具体操作的过程。
1.2 状态与状态空间
状态是规划世界在某一时刻的快照，通常用一组逻辑命题表示：
$$ s = {p_1, p_2, ..., p_n} $$
其中 $p_i$ 是基原子（ground atoms），即具体的、不包含变量的逻辑命题。
卫星规划的例子：
状态 s = {
pointing(sat1, targetA), // 卫星1指向目标A
instrument-on(camera1), // 相机1已开机
calibrated(camera1), // 相机已校准
data-stored(sat1) > 80%, // 存储空间使用率
power-level(sat1) = 85% // 电量
}
状态转移：执行动作 $a$ 会使状态从 $s$ 变为 $s'$，记为 $\gamma(s, a) = s'$。
例如，执行动作 turn-to(sat1, targetB) 后：
新状态 s' = {
pointing(sat1, targetB), // ✓ 改变了！
instrument-on(camera1), // 保持不变
...
}
💡 关键点：在 HTN 中，状态的作用和经典规划一样——用来判断动作是否可执行，以及记录执行后的效果。
二、任务（Task）的层次结构
HTN 的核心创新之一就是引入了任务的层次结构。这和经典规划有本质区别——经典规划只考虑"动作"，而 HTN 区分了"任务"和"动作"两个层次。
2.1 复合任务 vs 原子任务
复合任务（Compound Task）：
- 抽象的高层目标，不能直接执行
- 类似于编程中的"函数调用"，需要进一步展开
- 例：observe(targetA) — "观测目标A"（需要分解为具体操作）
- 例：handle-emergency() — "处理紧急情况"（需要判断情况类型再处理）
原子任务（Primitive Task）：
- 对应可直接执行的动作，类似编程中的"基本指令"
- 有明确的前置条件（precondition）和效果（effect）
- 例：turn-satellite(sat1, targetA) — 转动卫星（可直接执行）
- 例：take-image(camera1) — 拍摄图像（可直接执行）
对比示例：
| 类型 | 示例 | 能否直接执行 | 特点 |
|---|---|---|---|
| 复合任务 | observe(targetA) |
❌ 不能 | 抽象、高层、需分解 |
| 原子任务 | turn-satellite(sat1, targetA) |
✅ 能 | 具体、可执行、有前置条件和效果 |
💡 类比理解：
- 复合任务 = "去机场"（需要分解：出门→打车→到达）
- 原子任务 = "打开车门"（直接可执行的动作）
2.2 任务网络（Task Network）
单个任务是孤立的，但现实中任务之间有依赖关系。任务网络就是用来描述这些关系的结构。
任务网络表示任务之间的偏序关系：
$$ tn = (T, \prec, \alpha) $$
- $T$：任务节点集合
- $\prec$：偏序关系，表示任务间的执行顺序约束（$t_1 \prec t_2$ 表示 $t_1$ 必须在 $t_2$ 之前执行）
- $\alpha$：任务标签函数，将节点映射到具体任务
偏序 vs 全序：
- 全序：所有任务都有明确的先后顺序（如流水线）
- 偏序：只有部分任务有先后顺序约束，其他可以并行或任意顺序
可视化示例（卫星观测任务网络）：
[observe-targetA] ← 顶层复合任务
|
+-------+-------+
| |
[point-to-A] [prepare-camera] ← 可并行的子任务
| |
| +-----+-----+
| | |
| [power-on] [calibrate]
| | |
+---------+-----------+
|
[capture-image] ← 必须在前两个完成后才能执行
|
[downlink-data]
在这个例子中：
- point-to-A 和 prepare-camera 可以并行执行
- 但 capture-image 必须等待两者都完成后才能执行
- 这就是偏序关系的力量——它只约束必要的顺序，保留执行灵活性
三、方法（Method）：分解的配方
方法是 HTN 的灵魂。 它告诉规划器："遇到这种任务，在这种条件下，应该这样分解"。方法就是领域专家知识的显式编码。
3.1 方法的形式化定义
方法描述了"如何实现一个复合任务"：
$$ m = (t, \phi, tn) $$
- $t$：该方法能实现的复合任务（方法的头）
- $\phi$：适用条件（Condition），状态必须满足 $\phi$ 才能使用此方法
- $tn$：分解后的子任务网络（方法体）
结构类比：方法就像编程中的函数定义：
def method_observe(target): # t: 方法头
if pointing(sat, target) and calibrated(inst): # φ: 适用条件
# tn: 方法体（子任务网络）
calibrate(inst)
capture_image(inst, target)
downlink_data(inst)
3.2 方法示例
以卫星观测任务为例：
方法定义：
方法名: method-observe-standard
目标复合任务: observe(?target)
适用条件: pointing(?sat, ?target) ∧ instrument-ready(?inst)
分解子任务（按顺序）:
1. calibrate(?inst) // 校准仪器
2. capture-image(?inst, ?target) // 拍摄图像
3. downlink-data(?inst) // 下传数据
一个复合任务可以有多个方法：
假设观测任务有两种情况：
1. 标准观测：卫星已经指向目标，仪器就绪
2. 紧急观测：需要快速响应，跳过校准
我们可以定义两个方法：
方法1: method-observe-standard（标准观测）
适用条件: pointing(?sat, ?target) ∧ calibrated(?inst)
子任务: calibrate → capture → downlink
方法2: method-observe-rapid（快速观测）
适用条件: is-emergency() ∧ pointing(?sat, ?target)
子任务: capture → downlink // 跳过校准！
方法3: method-observe-with-alignment（需对准）
适用条件: ¬pointing(?sat, ?target)
子任务: turn-to → power-on → calibrate → capture → downlink
规划器的选择逻辑：
if 状态满足 method-observe-standard.条件:
使用方法1（最快路径）
elif 状态满足 method-observe-rapid.条件:
使用方法2（应急路径）
elif 状态满足 method-observe-with-alignment.条件:
使用方法3（完整路径）
else:
当前无法完成 observe 任务
💡 为什么多个方法很重要？
- 它允许领域专家编码不同的策略
- 规划器可以根据当前状态动态选择最佳方法
- 这大大增强了 HTN 的灵活性和表达能力
3.3 方法非确定性
当存在多个适用的方法时，规划器需要搜索或选择：
$$ methods(t, s) = {m \in M \mid head(m) = t \land s \models cond(m)} $$
这是 HTN 规划的复杂性来源之一。
四、HTN 规划的核心机制
理解了基本概念后，让我们看看 HTN 规划是如何工作的。
4.1 任务分解（Task Decomposition）
分解是 HTN 的核心操作。简单来说，分解就是用一个子任务网络替换一个复合任务。
形式化地：
给定任务网络 $tn$ 中的复合任务 $t$，如果方法 $m = (t, \phi, tn')$ 适用，则：
$$ decompose(tn, t, m) = tn \setminus {t} \cup tn' $$
公式解读：用方法的子任务网络 $tn'$ 替换原任务网络中的复合任务 $t$。
分解过程示例：
初始任务网络: [observe(targetA)]
↓
应用 method-observe-standard:
[observe(targetA)] → [calibrate] → [capture] → [downlink]
↓
calibrate是原子任务，无需分解
↓
capture是原子任务，无需分解
↓
downlink是原子任务，无需分解
最终: [calibrate] → [capture] → [downlink] (全是原子任务，完成！)
分解的终止条件：当任务网络中所有任务都是原子任务时，分解完成。此时得到一个可执行的动作序列。
4.2 规划解（Solution）的定义
一个 HTN 规划的解是一个动作序列 $\pi = [a_1, a_2, ..., a_n]$，必须满足以下四个条件：
| 条件 | 含义 | 说明 |
|---|---|---|
| 1. 可执行性 | 从 $s_0$ 出发，执行 $\pi$ 能得到状态序列 | 动作序列必须在物理上可行 |
| 2. 前置条件满足 | 每个 $a_i$ 执行前，状态满足其前置条件 | 不能"在空中"执行动作 |
| 3. 分解可达 | 存在分解序列，将 $tn_I$ 完全分解为 $\pi$ | 必须通过合法的方法分解得到 |
| 4. 偏序约束满足 | $\pi$ 满足任务网络中的所有偏序关系 | 必须遵守任务间的顺序约束 |
解的示例：
初始状态: {pointing(sat1, targetA), calibrated(camera1)}
初始任务网络: [observe(targetA)]
分解过程:
1. observe(targetA) --[method-observe-standard]--> [capture, downlink]
2. capture, downlink 都是原子任务，无需进一步分解
最终动作序列 π: [capture-image(camera1, targetA), downlink-data(camera1)]
验证:
✓ 可执行性: 从初始状态出发，执行这两个动作可行
✓ 前置条件: capture需要calibrated(camera1)，满足；downlink需要data-captured，capture后会满足
✓ 分解可达: 通过method-observe-standard合法分解得到
✓ 偏序约束: capture必须在downlink之前，π中顺序正确
结论: π 是该 HTN 问题的一个有效解！
4.3 与经典规划的区别
| 特性 | 经典规划 | HTN 规划 |
|---|---|---|
| 输入 | 初始状态 + 目标状态 | 初始状态 + 初始任务网络 |
| 搜索空间 | 状态空间 | 任务网络空间 |
| 终止条件 | 达到目标状态 | 完全分解为原子任务 |
| 领域知识 | 只能通过启发函数隐式利用 | 通过方法显式编码 |
| 表达能力 | 可判定 | 不可判定（更强大） |
五、不可判定性与理论边界
5.1 表达能力
HTN 规划比经典规划更强大。研究表明：
- 经典规划：EXPTIME-complete
- HTN 规划：不可判定（Undecidable）
这意味着不存在一个算法，能够在有限时间内判断任意 HTN 问题是否有解。
5.2 为什么是不可判定的？
核心原因在于方法的递归性和非确定性：
- 复合任务 A 可以用方法分解出子任务 B
- 子任务 B 又可能用另一个方法分解出任务 A
- 这种循环可能导致无限分解链
这类似于图灵机的停机问题，因此 HTN 规划的通用判定问题是不可解的。
5.3 实践中的限制
虽然理论上不可判定，但在实际应用中，我们通常：
- 限制方法的应用深度
- 禁止循环分解
- 使用启发式搜索
这使得实际 HTN 规划器能够高效工作。
六、HTN 的形式化表示：PDDL 与 HDDL
6.1 PDDL 的局限
标准 PDDL（Planning Domain Definition Language）主要用于经典规划，对 HTN 的支持有限。
6.2 HDDL：HTN 规划领域定义语言
HDDL（Hierarchical Domain Definition Language）是专门用于 HTN 的形式化语言：
(define (domain satellite-htn)
(:types satellite instrument target)
(:predicates
(pointing ?s - satellite ?t - target)
(on ?i - instrument)
(calibrated ?i - instrument))
;; 原子动作
(:action turn-to
:parameters (?s - satellite ?t - target)
:precondition (not (pointing ?s ?t))
:effect (pointing ?s ?t))
;; 复合任务
(:task observe :parameters (?t - target))
;; 方法
(:method method-observe
:parameters (?t - target ?s - satellite ?i - instrument)
:task (observe ?t)
:precondition (and (pointing ?s ?t) (calibrated ?i))
:subtasks (and
(capture ?i ?t)
(downlink ?i))))
6.3 主要 HTN 规划器
- SHOP2：经典的 HTN 规划器，支持完全有序任务网络
- PyHOP：Python 实现的轻量级 HTN 框架
- PandaPi：支持部分有序任务网络（POT）
- Tree-REX：基于模型检测的 HTN 规划器
七、总结
核心要点回顾
- 形式化定义：HTN 问题 = 状态 + 动作 + 任务 + 方法 + 初始任务网络
- 任务层次：复合任务通过方法分解，原子任务直接执行
- 规划解：完全分解后的原子动作序列，满足可执行性和约束
- 理论边界：HTN 是不可判定的，但实践中可有效求解
参考文献
- Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
- Erol, K., Hendler, J., & Nau, D. S. (1996). Complexity results for HTN planning. Annals of Mathematics and Artificial Intelligence, 18(1), 69-93.
- Höller, D., et al. (2020). The HDDL planning domain definition language. ICAPS 2020.