开篇导语
在上一篇文章中，我们详细拆解了 HTN 规划的形式化定义——六元组、任务层次、方法分解。当你真正开始阅读《Automated Planning: Theory and Practice》第11章时，会发现一个有趣的现象：书中花了大量篇幅讲 STN（Simple Task Network），然后才过渡到 HTN。
这引出了几个关键问题：
- STN 和 HTN 是什么关系？
- 为什么要有两个概念？
- 为什么实际工程中的 HTN 规划器（如 SHOP2、PyHOP）本质上解的是 STN 问题？
- 通用的 HTN 既然更强大，为什么工程中反而用得少？
本文将深入对比这两个概念，从约束能力、规划算法、理论性质三个维度展开，并结合航天任务规划的工程实践，解释背后的取舍逻辑。
一、前置知识回顾
在深入对比之前，快速回顾几个核心概念（详细内容见上篇）：
HTN 规划问题的六元组：
$$
\mathcal{P} = (S, s_0, A, T, M, tn_I)
$$
任务网络：包含任务节点集合 $T$、偏序关系 $\prec$、任务标签函数 $\alpha$
方法（Method）：$m = (t, \phi, tn)$，描述如何将复合任务 $t$ 分解为子任务网络
有了这些基础，我们就可以理解 STN 是如何从 HTN "简化"而来的。
二、STN 是什么？HTN 的简化版本
2.1 定义：Simple Task Network
STN（Simple Task Network）是 HTN 的一个受限版本。书中为了理论推导的严谨性，特意区分出了这个简化版本。绝大多数现代 HTN 规划器（包括 SHOP、SHOP2、HDDL 的多数实现）在严格定义下，实际上解的是 STN 问题。
2.2 "Simple" 在哪里？
STN 的"简单"体现在约束类型的限制：
| 约束类型 | STN | HTN |
|---|---|---|
| 顺序约束（Ordering） | ✅ | ✅ |
| 变量绑定（Variable Binding） | ✅ | ✅ |
| 状态维持约束（State Constraints） | ❌ | ✅ |
STN 仅支持：
1. 顺序约束：任务 $A$ 必须在任务 $B$ 之前（$A \prec B$）
2. 变量绑定约束：任务参数之间的相等关系
HTN 额外支持：
- 状态维持约束（State Constraints）：在执行某个任务及其所有子任务的整个过程中，某个状态必须一直保持为真
这个差异看似细微，却是两者在理论性质和工程适用性上分道扬镳的根源。
2.3 为什么书中先讲 STN？
从教学角度，STN 是理解 HTN 的"垫脚石"：
- STN 约束简单，可以用全序向前分解（TFD）算法高效求解
- STN 是可判定的（Decidable），有明确的复杂度边界
- 实际工程中，STN 的逻辑加上特定扩展（如资源锁定）已经足够强大
三、核心区别对比
3.1 约束能力：最本质的区别
STN：离散检查
STN 中的约束是瞬时的、离散的。以卫星数传任务为例：
Method: DoDownlink(station)
Precondition: Pointing == station ← 只在任务开始时检查
Subtasks: [Slew, Start_Transmitter, Wait, Stop_Transmitter]
Precondition 只在执行 DoDownlink 的那一瞬间检查。如果在 Start_Transmitter 和 Stop_Transmitter 之间，有其他任务插入了 Slew(Supernova)，STN 不会阻止——因为那不是检查点。
HTN：持续监控
HTN 引入了状态维持约束（State Constraints）：
Method: DoDownlink(station)
State-Constraint: Maintain(Pointing == station) ← 全程约束
Subtasks: [Slew, Transmit_Sequence]
这条约束告诉规划器：在整个 DoDownlink 任务执行期间（包括所有子任务），卫星必须始终指向地面站。如果规划器试图在这个时间段内插入任何改变指向的动作，约束检查器会直接报错。
类比理解：
- STN 的 Precondition 像门口的保安——只在进门时查证件，进门后不管
- HTN 的 State Constraint 像全程陪同——从开始到结束，一直监控
3.2 规划算法：TFD vs POP
约束能力的差异直接决定了求解算法的选择：
STN：全序向前分解（TFD）
TFD（Total-Order Forward Decomposition）是 STN 的核心算法：
输入：当前状态 s，待办任务列表 w（按顺序排列）
循环：
如果 w 为空 → 成功
取出 w 中的第一个任务 t
如果 t 是原子任务：
检查在当前状态 s 下是否可行
如果可行：应用效果更新状态，加入最终计划
如果不可行：回溯
如果 t 是复合任务：
找到所有适用的方法
对每个方法：用子任务替换 t，递归求解
TFD 的关键优势：
- 因为是按执行顺序分解，始终知道"当前状态"是什么
- 便于处理数值资源（电量、燃料、存储空间）
- 算法简单高效，易于工程实现
HTN：偏序规划（POP）
通用的 HTN 需要处理复杂的偏序关系，通常使用偏序规划（Partial-Order Planning, POP）或约束满足（CSP）技术：
- 任务之间只有部分顺序约束，其他可以并行
- 状态不确定——不知道任务 A 执行后的具体状态值
- 需要复杂的冲突检测和约束传播
代价：搜索空间更大，资源计算困难（需要做区间运算而非精确值计算）
3.3 理论性质：可判定性与表达能力
这是最反直觉的部分：
| 理论性质 | STN | HTN |
|---|---|---|
| 可约简性 | 可转化为经典规划问题 | 不可约简 |
| 复杂度 | 可判定（Decidable） | 不可判定（Undecidable） |
| 表达能力 | 正则语言（Regular） | 上下文无关语言（Context-Free） |
为什么 HTN 是不可判定的？
核心原因：递归性。
HTN 允许方法递归定义：
方法 A → 子任务 B
方法 B → 子任务 A
这可能导致无限分解链。规划器无法区分：
1. 真的无解：无论如何分解，最后都行不通
2. 还需要再分解一层：也许再分解一次就能遇到原子动作
这就像图灵机的停机问题，因此通用的 HTN 规划问题是不可判定的。
表达能力差距：$a^n b^n$ 问题
经典的计算机理论问题：执行 $n$ 次动作 $A$，然后必须紧接着执行 $n$ 次动作 $B$。
- HTN 解法：递归方法天然保证 $A$ 和 $B$ 数量相等
- 经典规划/STN：无法表达"无论 $n$ 是多少"，只能对固定的 $n$ 写死
这说明 HTN 的表达能力超越了正则语言，达到了上下文无关语言的级别。
四、工程实践中的选择
理解了理论差异后，关键问题是：实际工程中应该选哪个？
4.1 为什么实际大多用 STN？
尽管 HTN 理论更强大，但工程实践中（尤其是航天任务规划）STN/TFD 是主流。原因有三：
原因1：状态确定性
航天任务规划需要精确知道"此时此刻电量剩多少"、"存储空间还够不够"。
TFD 按执行顺序向前规划，第 3 步规划时确切知道第 1、2 步执行后的状态。这解决了数值资源的精确计算问题。
POP 的偏序特性让状态不确定——你不知道任务 A 到底在任务 B 之前还是之后执行，无法做精确值计算。
原因2：工程可维护性
STN 的约束简单（主要是顺序），代码实现清晰，易于：
- 调试和验证
- 与外部系统（轨道预报、资源计算）集成
- 团队协作和维护
原因3：性能可控
STN 的复杂度是可判定的，可以通过限制递归深度、方法应用次数来控制搜索空间。
4.2 STN 的"短板"如何弥补？
STN 最大的短板是无法表达持续状态约束。工程中的解决方案是：资源锁定（Resource Locking）。
示例：卫星数传的工程实现
# STN + 资源锁定 的工程折中方案
Method: DoDownlink(station)
Precondition:
# 检查姿控系统在未来10分钟是否空闲
IsResourceAvailable(ADCS, duration=10)
Subtasks:
1. BookResource(ADCS, 10 mins) # 显式锁定姿控系统
2. Slew(station)
3. Start_Transmitter()
4. Wait(10 mins)
5. Stop_Transmitter()
6. ReleaseResource(ADCS)
原理：
- 将"天线必须始终指向地面"转化为"姿控系统（ADCS）被锁定10分钟"
- 其他任务想转动卫星，必须先申请 ADCS 资源
- 发现被锁，只能排队等待
这不是理论上的 State Constraint，但工程效果等价，且计算高效。
4.3 什么时候需要 HTN？
虽然 STN 是主流，但以下场景 HTN 更有优势：
- 复杂的时间区间约束
- 任务 A 必须在任务 B 开始后 10-20 分钟内结束
-
多个任务之间的时间窗口约束复杂
-
复杂的并行和同步关系
- 多个并行子任务之间的复杂约束
-
需要表达"期间"关系的场景
-
理论研究场景
- 需要证明规划器的完备性
- 探索理论边界和表达能力
五、从理论到代码：一个完整示例
为了让你更直观地理解差异，下面用 Python 伪代码展示同一卫星数传任务的三种实现方式。
5.1 场景设定
任务：卫星将观测数据下行传回地面站
要求：传输期间（10分钟）天线必须始终指向地面站
干扰：可能有突发任务（如观测超新星）需要转动卫星
5.2 STN 实现（风险版本）
def method_do_downlink_simple(state, sat, station):
"""
纯STN实现：只在开始时检查指向
风险：中间可能被其他任务打断
"""
# 只在开始时检查一次
if not state.pointing[sat] == station:
return False
return [
('slew', sat, station), # 转动卫星（可能重复）
('start_transmitter', sat), # 开机
('wait', 600), # 等待10分钟
('stop_transmitter', sat) # 关机
]
# 潜在问题：
# 如果在wait期间，调度器插入了一个高优先级任务：
# ('slew', sat, 'supernova') ← 天线转走了！
# STN不会在中间检查，任务失败。
5.3 HTN 理想实现（理论上）
def method_do_downlink_htn(state, sat, station):
"""
HTN理想实现：全程状态约束
注意：这是伪代码，展示概念，大多数规划器不支持这种语法
"""
# State Constraint：在整个任务期间必须保持
state_constraint = {
'type': 'maintain',
'condition': lambda s: s.pointing[sat] == station,
'duration': 600 # 10分钟
}
return {
'subtasks': [
('slew', sat, station),
('transmit_sequence', sat, station)
],
'state_constraints': [state_constraint]
}
# 如果规划器试图插入 ('slew', sat, 'supernova')，
# 约束检查器会检测到冲突，阻止插入。
5.4 工程折中方案（STN + 资源锁定）
class SatellitePlanner:
def __init__(self):
self.resources = {
'ADCS': Resource('ADCS', capacity=1) # 姿控系统，容量为1
}
def method_do_downlink_engineering(self, state, sat, station):
"""
工程实现：STN + 资源锁定
"""
# 检查资源是否可用（未来10分钟）
if not self.resources['ADCS'].is_available(duration=600):
return False
# 锁定资源，防止其他任务占用
self.resources['ADCS'].book(duration=600)
return [
('book_resource', 'ADCS', 600),
('slew', sat, station),
('start_transmitter', sat),
('transmit_data', sat, station, 600),
('stop_transmitter', sat),
('release_resource', 'ADCS')
]
def method_observe_supernova(self, state, sat, target):
"""
突发任务：观测超新星
"""
# 必须先申请姿控系统
if not self.resources['ADCS'].is_available(duration=300):
return False # 资源被锁，无法执行
return [
('book_resource', 'ADCS', 300),
('slew', sat, target),
('capture_image', sat, target),
('release_resource', 'ADCS')
]
# 结果：如果数传任务已锁定ADCS，突发任务会等待或失败，
# 避免了天线在传输中途被转走的风险。
六、总结：一张表看懂 STN vs HTN
| 对比维度 | STN (Simple Task Network) | HTN (Hierarchical Task Network) |
|---|---|---|
| 全称 | Simple Task Network | Hierarchical Task Network |
| 核心约束 | 顺序约束 + 变量绑定 | 顺序约束 + 变量绑定 + 状态维持约束 |
| 世界状态 | 分解时已知（全序TFD） | 分解时未知（偏序POP） |
| 典型算法 | TFD（全序向前分解） | POP（偏序规划）或 CSP |
| 理论复杂度 | 可判定（Decidable） | 不可判定（Undecidable） |
| 表达能力 | 正则语言（Regular） | 上下文无关语言（Context-Free） |
| 数值资源计算 | ✅ 精确（状态确定） | ⚠️ 困难（区间运算） |
| 工程适用性 | ✅ 强（航天调度主流） | ⚠️ 较弱（理论价值高） |
| 规划器代表 | SHOP, SHOP2, PyHOP | 理论框架，工程实现少 |
选型建议
- 选 STN：如果你的应用场景需要精确的状态计算、数值资源管理、工程可维护性（大多数航天任务规划场景）
- 选 HTN：如果你的应用场景有复杂的时间区间约束、并行同步关系、理论研究需求
参考文献
- Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann. (Chapter 11)
- Erol, K., Hendler, J., & Nau, D. S. (1996). Complexity results for HTN planning. Annals of Mathematics and Artificial Intelligence, 18(1), 69-93.
- Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49(1-3), 61-95.
- Nau, D., et al. (2003). SHOP2: An HTN planning system. Journal of Artificial Intelligence Research, 20, 379-404.