HTN规划的表达能力：为何它比经典规划更强大

系列第六篇，从表达能力角度深入对比HTN与经典规划。如果你还没读过前面的文章，建议先从[任务规划概述]、[HTN形式化定义]、[HTN不可判定性]开始。

一、开篇：为什么讨论表达能力？

在上一篇文章中，我们探讨了一个看似矛盾的现象：HTN规划是不可判定的——不存在通用算法能判断任意HTN问题是否有解。然而，现实中SHOP、SHOP2、SIADEX等HTN规划器却在航天、应急管理等实际应用中表现出色。

这引出了一个自然的问题：

既然HTN不可判定，为什么还要用它？它的独特价值在哪里？

答案就隐藏在"表达能力"（Expressivity）这个概念中。本文将从表达能力角度，系统地对比HTN与经典规划（STRIPS/PDDL），揭示HTN不可替代的根本原因。

二、什么是"表达能力"？

2.1 定义

在形式语言理论中，一个规划形式体系的表达能力指的是：

该体系能够表示（encode）的问题集合的范围。

通俗地说，表达能力回答的是：
- 这个规划语言"能说什么"？
- 这个规划语言"不能说什么"？

2.2 表达能力 vs 计算复杂性

表达能力与计算复杂性是两个不同维度：

维度	表达能力	计算复杂性
关注点	能表示哪些问题	解决问题的计算成本
度量	问题集合的包含关系	时间/空间复杂度
关系	表达能力强 ≠ 复杂性高	两者独立

关键洞察：一个体系可能表达能力很强（能表示很多问题），但计算复杂性可控（如STN）；也可能表达能力受限，但计算复杂性很高（如某些受限的经典规划问题）。

2.3 HTN vs 经典规划的核心问题

本文要回答的核心问题是：

HTN的表达能力是否严格包含经典规划的表达能力？

换句话说：是否存在某些问题，HTN可以表达，但经典规划（STRIPS/PDDL）无法表达？

答案是：是的，HTN严格比经典规划更具表达能力。

三、经典规划（STRIPS/PDDL）的表达能力

3.1 STRIPS的基本能力

STRIPS（Stanford Research Institute Problem Solver）是经典规划的奠基性形式体系，其核心特征包括：

状态表示：
- 状态是布尔变量（命题符号）的合取
- 例如：At(Robot, Room1) ∧ Clean(Room1) ∧ Powered(Robot)

操作表示：
- 操作由三部分组成：
- 前提条件（Preconditions）：执行操作前必须为真的命题
- 添加列表（Add List）：执行操作后变为真的命题
- 删除列表（Delete List）：执行操作后变为假的命题

目标表示：
- 目标是状态描述的合取
- 例如：At(Robot, Room2) ∧ Clean(Room2)

3.2 PDDL的扩展

PDDL（Planning Domain Definition Language）是STRIPS的扩展，增加了：

数值变量：支持数值计算和比较
时序操作：支持持续时间、时间约束
派生谓词：通过规则派生新的谓词
条件效果：根据条件产生不同效果
非确定性：支持不确定性规划

注意：即使有了这些扩展，PDDL仍然无法直接表达"任务层次分解"的结构——它扩展的是状态和操作的表达能力，而非任务组织的表达能力。

3.3 经典规划的表达局限

经典规划（包括STRIPS和PDDL）的根本局限在于：

它只能表达"状态转移"，无法直接表达"任务分解结构"。

在经典规划中，你只能定义：
- 世界是什么状态
- 操作如何改变状态
- 目标是什么状态

但你无法直接表达：
- "要完成'观测任务'，需要先'调整姿态'，再'拍摄图像'"
- "任务A可以分解为子任务B和C，且B必须在C之前执行"

这种层次化的任务结构是经典规划的表达盲区。

四、HTN的表达能力

4.1 HTN的核心能力

HTN（Hierarchical Task Network）规划的核心能力是任务层次分解（Hierarchical Task Decomposition）。

与经典规划关注"状态如何改变"不同，HTN关注"任务如何分解"。

4.2 表达能力的三大来源

HTN的表达能力来自三个关键机制：

4.3 为什么不能反向编译？

既然经典规划可以编译为HTN，那HTN能否编译为经典规划？

答案是：一般情况不行。

虽然我们可以把HTN"压平"为一组经典规划操作（通过枚举所有可能的分解路径），但这种编译是指数级膨胀的，且丢失了结构信息。

更重要的是，对于某些HTN问题，分解空间是无限的（递归方法），根本无法有限编译。

这就是为什么HTN的表达能力严格强于经典规划——有些问题只能用HTN表达，无法等价地转换为经典规划。

1. 方法（Method）

方法是HTN的核心创新。它将高层任务映射到子任务网络：

(:method (Observe ?target)
    :precondition (available ?target)
    :tasks (!Slew ?target) 
            (!TakePhoto ?target))

这表达了一个领域知识："要完成观测任务，需要先调整姿态，再拍摄图像"。

这种知识在经典规划中无法直接编码，只能通过复杂的动作序列间接实现。

2. 任务网络（Task Network）

任务网络允许表达任务间的结构关系：

顺序关系：任务A必须在任务B之前
并行关系：任务A和任务B可以并行执行
层次关系：父任务与子任务的分解关系

这些关系超越了经典规划的"状态-操作-状态"范式。

如我们在第五篇中讨论的，HTN支持状态维持约束：

(:method (TransferData ?ground-station)
    :precondition (pointing ?ground-station)
    :tasks (!InitiateTransfer ?ground-station)
            (!Transfer ?ground-station)
            (!EndTransfer ?ground-station)
    :constraints (during Transfer 
                   (maintain (pointing ?ground-station))))

这表达了："在传输期间，必须始终保持指向地面站"。

这种时序约束在经典规划中是极其难以表达的。

五、HTN严格强于经典规划的证明

现在我们来形式化地证明：HTN严格比经典规划更具表达能力。

5.1 定理陈述

定理（基于Erol et al., 1994）：

设 $\mathcal{L}{Classical}$ 为经典规划（STRIPS/PDDL）可表达的问题集合，$\mathcal{L}{HTN}$ 为HTN规划可表达的问题集合。则：
$$\mathcal{L}{Classical} \subsetneq \mathcal{L}{HTN}$$

即：HTN的表达能力严格包含经典规划的表达能力。

5.2 证明思路

证明分为两部分：

第一部分（平凡）：$\mathcal{L}{Classical} \subseteq \mathcal{L}{HTN}$

任何经典规划问题都可以编码为HTN问题：
- 将每个经典规划操作编码为HTN原子任务
- 将所有原子任务放在一个顶层复合任务中
- 使用一个方法将该复合任务分解为原子任务序列

因此，HTN至少能表达经典规划能表达的所有问题。

第二部分（非平凡）：$\mathcal{L}{Classical} \neq \mathcal{L}{HTN}$

我们需要证明：存在某些问题，HTN可以表达，但经典规划无法表达。

5.3 具体例子：航天器任务的层次分解

考虑一个航天器任务规划问题：

任务结构：

科学观测任务
├── 轨道机动
│   ├── 计算轨道参数
│   ├── 姿态调整
│   └── 执行机动
├── 目标观测
│   ├── 姿态调整
│   ├── 相机对准
│   └── 拍摄图像
└── 数据下传
    ├── 天线对准
    ├── 传输数据
    └── 验证完整性

关键观察：

这个任务有自然的层次结构：
- "科学观测任务"分解为三个子任务
- 每个子任务又有自己的子任务
- 某些子任务（如"姿态调整"）在多个地方出现

经典规划的表达困境：

在经典规划中，你无法直接表达这种层次结构。你只能通过定义一个巨大的动作序列来间接实现：

;; 经典规划中的笨拙表达
(:action do-science-observation
    :precondition (at-starting-orbit)
    :effect (and (done-calculate-params)
                 (done-attitude-adjust-1)
                 (done-execute-maneuver)
                 (done-attitude-adjust-2)
                 (done-camera-align)
                 (done-take-photo)
                 (done-antenna-point)
                 (done-transfer-data)
                 (done-verify-integrity)))

这种表达的问题：
1. 丢失结构信息："姿态调整"出现了两次，但经典规划无法表达它们是不同的实例还是同一个任务
2. 难以维护：如果要修改"姿态调整"的逻辑，需要在所有地方修改
3. 无法复用：无法定义一次"姿态调整"操作，然后在多处引用

HTN的优雅表达：

;; HTN方法定义
(:method (ScienceObservation ?target)
    :tasks (OrbitManeuver)
           (TargetObservation ?target)
           (DataDownlink ?target))

(:method (OrbitManeuver)
    :tasks (!CalculateParams)
           (!AttitudeAdjust)  ;; 第一次姿态调整
           (!ExecuteManeuver))

(:method (TargetObservation ?target)
    :tasks (!AttitudeAdjust)  ;; 第二次姿态调整（复用同一个操作）
           (!CameraAlign ?target)
           (!TakePhoto ?target))

(:method (DataDownlink ?target)
    :tasks (!AntennaPoint ?ground-station)
           (!TransferData ?target)
           (!VerifyIntegrity)
    :constraints (during TransferData
                   (maintain (pointing ?ground-station))))

额外的约束表达：

注意 :constraints 部分——这种"期间维持"约束在经典规划中几乎无法表达。你需要为每个可能的干扰动作添加复杂的时序逻辑，而在HTN中只需要一句话。

**关键优势**：
1. **结构清晰**：层次分解直接反映任务结构
2. **操作复用**：`!AttitudeAdjust` 被多处使用，但只定义一次
3. **易于维护**：修改方法定义即可影响所有使用处
4. **领域知识编码**：方法本身表达了领域专家的"如何做"知识

### 5.4 形式化论证

更形式化地说，存在HTN问题，其**解的结构**（层次化的任务分解树）无法被经典规划的问题表示所捕获。

经典规划的解是一个**线性动作序列**：
$$[a_1, a_2, ..., a_n]$$

而HTN的解是一个**层次化的任务树**：

  Task
 /    \

Task1 Task2
/ \
Task3 Task4

这种**树状结构**携带的信息（层次关系、分解关系）在经典规划的线性表示中丢失了。

**关键区别：解的表示形式**

经典规划的解是一组动作序列：$[a_1, a_2, ..., a_n]$

而HTN的解不仅包含动作序列，还包含**分解树结构**——每个动作是如何从高层任务分解而来的。

这意味着：即使我们能从HTN解中提取出动作序列，也无法从动作序列反推出原始的层次结构。**信息是单向丢失的**。

因此，某些HTN问题**本质上**无法被编码为经典规划问题——不是因为我们还没有找到编码方式，而是因为经典规划的表示语言**根本不具备表达能力**来描述这种层次结构。

---

## 六、实际意义：为什么表达能力重要？

理解HTN的表达能力优势，对工程实践有三重意义：

### 6.1 复杂任务的分解

现实世界的大型任务天然具有**层次结构**：
- 航天任务：轨道级 → 子系统级 → 操作级
- 应急指挥：战略级 → 战术级 → 执行级
- 项目管理：项目 → 阶段 → 任务 → 子任务

HTN的表达能力让我们能够**自然地**建模这种层次结构，而不是强行将其压平为状态转移序列。

### 6.2 领域知识的编码

HTN的**方法**本质上是在编码领域专家的"如何做"知识：

```lisp
(:method (TreatPatient ?patient)
    :precondition (critical-condition ?patient)
    :tasks (EmergencyResponse ?patient)
           (Stabilize ?patient)
           (TransferToHospital ?patient))

这表达的是医生的专业知识："如果病人情况危急，先急救，再稳定，最后转院"。

这种知识的可维护性和可复用性远高于经典规划中的硬编码动作序列。

6.3 规划效率的提升

层次分解不仅是一种表达手段，更是一种搜索策略。

通过高层任务的分解，HTN规划器可以：
- 大幅剪枝搜索空间：在高层就排除不可能的分支
- 利用领域知识指导搜索：方法本身就是启发式
- 实现抽象层次上的推理：先规划高层，再细化细节

实验表明，对于复杂任务，HTN规划器往往比经典规划器快几个数量级——不是因为HTN算法本身更快，而是因为层次分解提供了强大的启发式信息。

七、总结

7.1 核心要点

HTN表达能力 > 经典规划表达能力（严格包含）
根本差异：HTN能表达任务层次结构，经典规划只能表达状态转移
关键机制：方法、任务网络、状态维持约束
实际价值：自然建模层次任务、编码领域知识、提升规划效率

7.2 与前面文章的关系

[任务规划概述] → [HTN形式化定义] → [STN与HTN区别] → [TFD算法] → [不可判定性] → [本文: 表达能力]
                                                                    ↓
                                        理解了为什么HTN不可替代——不仅是更强大，而且是不同的表达范式

我们用了六篇文章，构建了一个完整的认知框架：
1. HTN是什么（形式化定义）
2. HTN与STN的区别（约束差异）
3. HTN的算法（TFD）
4. HTN的理论边界（不可判定性）
5. HTN的独特价值（表达能力）

7.3 工程启示

不要试图用经典规划解决所有问题：有些问题天然具有层次结构，用HTN更合适
充分利用方法的表达能力：方法不仅是语法糖，更是领域知识的载体
在适当的时候引入层次抽象：即使是经典规划能解决的小问题，层次抽象也能提升效率

参考文献

Erol, K., Hendler, J., & Nau, D. S. (1994). HTN Planning: Complexity and Expressivity. Proceedings of the 12th National Conference on Artificial Intelligence (AAAI-94), 1123-1128.
Erol, K., Hendler, J., & Nau, D. S. (1996). Complexity results for HTN planning. Annals of Mathematics and Artificial Intelligence, 18(1), 69-93.
Geier, T., & Bercher, P. (2011). On the Decidability of HTN Planning. Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11).
Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann. (Chapters 2, 11)
Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson. (Chapter 11)