系列第四篇，深入解析全序向前分解算法。如果你还没读过前面的文章，建议先从[任务规划概述]开始。
一、开篇：从STN到TFD
在上一篇文章中，我们讨论了STN与HTN的核心区别：STN仅支持顺序约束和变量绑定约束，而HTN额外支持状态维持约束。这个差异直接导致了两者在算法层面的不同——STN使用TFD算法，而HTN需要更复杂的偏序规划（POP）。
那么，TFD算法到底是什么？为什么它能成为航天任务规划的主流方法？本文将从算法思想到代码实现，全面解析TFD。
二、TFD是什么？
2.1 名称解析
TFD 全称 Total-order Forward Decomposition，翻译为"全序向前分解"。这三个词分别对应算法的三个核心特征：
| 术语 | 含义 |
|---|---|
| Total-order（全序） | 任务网络中的所有任务始终保持完全确定的执行顺序 |
| Forward（向前） | 按照执行顺序，从第一个任务开始依次处理 |
| Decomposition（分解） | 用方法（Method）将复合任务展开为子任务 |
2.2 核心思想
TFD的核心理念可以用一句话概括：
在分解任务的每一步，我们都确切知道"世界当前是什么状态"。
这句话听起来简单，但它带来的工程价值是巨大的：
- 数值计算可行：知道当前状态，就能精确计算"剩余电量""剩余时间"
- 约束传播简单：不需要复杂的约束满足（CSP）技术
- 搜索空间可控：全序使得搜索树相对紧凑
2.3 与偏序规划（POP）的对比
为了更好理解TFD的特点，我们对比一下偏序规划：
| 特性 | TFD（全序） | POP（偏序） |
|---|---|---|
| 任务顺序 | 完全确定 | 部分确定（有并行） |
| 当前状态 | 已知 | 未知（需区间估计） |
| 约束处理 | 简单 | 复杂（CSP） |
| 搜索效率 | 较高 | 较低 |
| 表达能力 | 受限 | 更强 |
简单来说：TFD用表达能力的限制换取了计算效率的提升。这在工程实践中往往是值得的。
三、TFD算法核心流程
3.1 算法输入
TFD算法需要四个输入：
| 输入 | 符号 | 说明 |
|---|---|---|
| 初始状态 | $s_0$ | 世界状态的完整描述 |
| 目标任务网络 | $tn$ | 待分解的任务集合及其顺序关系 |
| 方法集合 | $M$ | 复合任务的分解规则 |
| 操作集合 | $O$ | 原子任务的具体执行方式 |
3.2 算法伪代码
下面是TFD的核心伪代码（参考Ghallab等人的《Automated Planning》）：
function TFD(s, tn, M, O):
输入: 当前状态 s, 任务网络 tn, 方法集合 M, 操作集合 O
输出: 操作序列（解）或 fail
1. if tn 为空:
2. return [] # 空解，成功
3. # 选择第一个待处理任务（全序的关键！）
4. t = tn[0] # 第一个任务
5. tn' = tn[1:] # 剩余任务（列表切片）
6. if t 是原子任务:
7. # 尝试所有可能的操作
8. for o in O:
9. if o.name == t.name:
10. if preconditions(o) 满足于 s:
11. # 执行操作，更新状态
12. s_new = apply(o, s)
13. # 递归处理剩余任务
14. result = TFD(s_new, tn', M, O)
15. if result ≠ fail:
16. return [o] + result
17. return fail # 所有操作都不可行
18. else: # t 是复合任务
19. # 尝试所有可能的方法
20. for m in M:
21. if m.name == t.name:
22. if preconditions(m) 满足于 s:
23. # 分解任务：用方法的子任务替换当前任务
24. subtasks = substitute(m.subtasks, t.variables)
25. # 将子任务插入到任务网络前端
26. tn_new = subtasks + tn'
27. # 递归处理（注意：状态不变！）
28. result = TFD(s, tn_new, M, O)
29. if result ≠ fail:
30. return result
31. return fail # 所有方法都不可行
3.3 关键步骤解读
第4行：选择第一个任务
这是TFD"全序"的核心体现。我们始终选择任务网络中的第一个任务进行处理，这意味着任务的执行顺序在分解过程中就已经确定了。
第6-17行：原子任务处理
当遇到原子任务时，我们需要找到一个可执行的操作：
- 检查操作名称是否匹配
- 检查前提条件是否满足
- 执行操作，更新状态
- 递归处理剩余任务
第18-31行：复合任务处理
当遇到复合任务时，我们需要找到一个可行的方法：
- 检查方法名称是否匹配
- 检查前提条件是否满足
- 用方法的子任务替换当前任务
- 注意：状态不变！ 分解只是"展开"，还没执行
第14行 vs 第28行：状态变化的时机
这是一个重要的区别：
- 原子任务执行后，状态会改变
- 复合任务分解后，状态不变（只是任务网络变了）
四、一个完整示例
4.1 问题设定
考虑一个简化的卫星对地观测任务：
初始状态：
- 卫星姿态：指向东
- 电量：100%
目标：拍摄地面目标A
4.2 领域定义
# 操作（Operators）
Operators:
- Slew(target):
名称: Slew
参数: target（目标指向）
前提: power > 10
效果: pointing = target, power -= 10 # 消耗10单位电量
- TakePhoto(target):
名称: TakePhoto
参数: target（拍摄目标）
前提: pointing == target, power > 5
效果: has_image(target) = true, power -= 5 # 消耗5单位电量
# 方法（Methods）
Methods:
- Observe(target):
名称: Observe
参数: target（观测目标）
前提: true（无条件）
子任务: [Slew(target), TakePhoto(target)]
4.3 TFD执行过程
让我们一步步追踪TFD算法的执行：
========================================
初始状态:
s = {pointing=east, power=100}
tn = [Observe(A)]
Step 1: 处理第一个任务 Observe(A)
----------------------------------------
任务类型: 复合任务
匹配方法: Observe(target)
- 前提检查: true ✓
- 变量绑定: target = A
- 子任务: [Slew(A), TakePhoto(A)]
分解结果: tn = [Slew(A), TakePhoto(A)]
状态不变: s = {pointing=east, power=100}
Step 2: 处理第一个任务 Slew(A)
----------------------------------------
任务类型: 原子任务
匹配操作: Slew(target)
- 前提检查: power=100 > 10 ✓
- 执行效果: pointing=A, power=90
状态更新: s = {pointing=A, power=90}
剩余任务: tn = [TakePhoto(A)]
Step 3: 处理第一个任务 TakePhoto(A)
----------------------------------------
任务类型: 原子任务
匹配操作: TakePhoto(target)
- 前提检查:
- pointing=A == target=A ✓
- power=90 > 5 ✓
- 执行效果: has_image(A)=true, power=85
状态更新: s = {pointing=A, power=85, has_image(A)=true}
剩余任务: tn = []
Step 4: 任务网络为空，成功！
----------------------------------------
返回解: [Slew(A), TakePhoto(A)]
========================================
4.4 执行过程图解
初始
│
▼
[Observe(A)]
│
方法分解 (状态不变)
│
▼
[Slew(A)] → [TakePhoto(A)]
│ │
执行操作 执行操作
(状态改变) (状态改变)
│ │
▼ ▼
pointing=A has_image(A)
解: [Slew(A), TakePhoto(A)]
五、TFD的搜索树与回溯
前面的例子只有一条路径成功，但实际情况往往更复杂。当某条路径失败时，TFD会回溯尝试其他选项。
5.1 回溯场景示例
假设我们有两个拍摄目标A和B，但电量有限：
初始状态: power=15
目标任务: [Observe(A), Observe(B)]
搜索过程:
├─ Observe(A) → [Slew(A), TakePhoto(A)]
│ ├─ Slew(A) 执行成功, power=5
│ ├─ TakePhoto(A) 前提失败 (power=5 不满足 >5)
│ └─ 回溯：尝试其他方法？无其他方法
│ └─ Observe(A) 失败
│
└─ 无其他选项，规划失败
这个例子说明了TFD的一个重要特点：它是一种搜索算法，会尝试所有可能的分解路径。
5.2 搜索树结构
根节点
[Observe(A)]
│
┌───────────┴───────────┐
│ │
方法1: Observe 方法2: ...（无）
│
▼
[Slew(A), TakePhoto(A)]
│
┌─────┴─────┐
│ │
成功路径 失败路径
(前提满足) (前提不满足)
六、TFD的优缺点分析
6.1 优点
1. 状态确定性
这是TFD最大的工程优势。在分解的每一步，我们都精确知道当前状态：
# TFD可以精确计算
current_power = 100
after_slew = current_power - 10 # 确定的
after_photo = after_slew - 5 # 确定的
# 对比：偏序规划中状态是区间
current_power = [50, 100] # 不确定范围
after_slew = [40, 90] # 只能估计区间
2. 数值计算友好
航天任务规划中大量涉及数值计算：
- 轨道动力学
- 能源预算
- 数据存储容量
- 通信窗口
TFD的状态确定性使得这些计算可以直接嵌入规划过程。
3. 搜索效率较高
全序约束使得搜索空间相对紧凑，不需要处理复杂的偏序关系。
4. 工程可维护
算法逻辑清晰，代码实现简单，便于调试和验证。
6.2 缺点
1. 表达能力受限
无法表达"状态维持约束"，例如：
- "在整个数据传输期间，天线必须始终指向地面站"
- "任务执行过程中，电量必须保持在20%以上"
2. 并行性受限
全序约束限制了任务的并行执行：
# HTN可以表达
任务A || 任务B # A和B可以并行
# TFD只能表达
任务A → 任务B # 或者
任务B → 任务A # 必须有顺序
3. 完备性问题
某些问题在TFD下可能找不到解，但在偏序规划下有解。
6.3 工程中的折中
实际工程中，常用以下方法弥补TFD的短板：
| 问题 | 工程解决方案 |
|---|---|
| 状态维持约束 | 资源锁定机制 |
| 并行性受限 | 预定义的任务模板 |
| 数值约束 | 外部约束求解器 |
七、TFD的工程实现
7.1 SHOP/SHOP2
SHOP（Simple Hierarchical Ordered Planner）是最早实现TFD的规划器，由UMCP团队开发。
SHOP2是其后继版本，在TFD基础上增加了：
- 更灵活的变量绑定
- 外部函数调用
- 数值计算支持
;; SHOP2 领域定义示例
(defdomain satellite (
;; 操作
(:operator (!slew ?target)
:precondition (power ?p) (call > ?p 10)
:effect (pointing ?target)
(power (call - ?p 10)))
;; 方法
(:method (observe ?target)
:precondition ()
:tasks (!slew ?target) (!take-photo ?target))
))
7.2 PyHOP：Python实现
PyHOP是一个简洁的Python HTN规划器，非常适合学习和实验：
# PyHOP 领域定义示例
def slew(state, target):
"""俯仰机动操作"""
if state.power > 10:
state.pointing = target
state.power -= 10
return state
return False
def take_photo(state, target):
"""拍照操作"""
if state.pointing == target and state.power > 5:
state.has_image[target] = True
state.power -= 5
return state
return False
def observe(state, target):
"""观测方法"""
return [('slew', target), ('take_photo', target)]
# 注册
pyhop.declare_operators(slew, take_photo)
pyhop.declare_methods('observe', observe)
# 规划
state = State()
state.pointing = 'east'
state.power = 100
state.has_image = {}
plan = pyhop.plan(state, [('observe', 'A')])
# 输出: [('slew', 'A'), ('take_photo', 'A')]
7.3 实现要点
如果你要自己实现TFD，注意以下几点：
1. 任务表示
class Task:
name: str # 任务名称
args: list # 参数列表
is_primitive: bool # 是否为原子任务
2. 状态表示
class State:
fluents: dict # 状态变量字典
resources: dict # 数值资源字典
3. 方法/操作表示
class Method:
name: str
preconditions: Callable # 前提条件函数
subtasks: list # 子任务列表
class Operator:
name: str
preconditions: Callable # 前提条件函数
effects: Callable # 效果函数
八、总结
8.1 核心要点
| 概念 | 要点 |
|---|---|
| TFD本质 | 全序 + 向前 + 分解 |
| 状态确定性 | 分解过程中始终知道当前状态 |
| 算法流程 | 选任务 → 尝试操作/方法 → 递归 |
| 工程价值 | 数值计算友好、搜索高效、易于实现 |
| 表达限制 | 无状态维持约束、并行性受限 |
8.2 什么时候用TFD？
推荐使用TFD：
- 任务之间有自然的顺序关系
- 需要精确的数值计算
- 对规划效率有较高要求
- 工程实现需要简洁可控
考虑其他方法：
- 任务之间有复杂的并行关系
- 需要表达状态维持约束
- 对理论完备性有更高要求
8.3 与前面文章的关系
[任务规划概述] → [HTN形式化定义] → [STN与HTN区别] → [本文: TFD算法]
↓
下一篇: HTN不可判定性
参考文献
- Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann. (Chapter 11)
- Nau, D. S., et al. (2003). SHOP2: An HTN planning system. Journal of Artificial Intelligence Research, 20, 379-404.
- Erol, K., Hendler, J., & Nau, D. S. (1996). Complexity results for HTN planning. Annals of Mathematics and Artificial Intelligence, 18(1), 69-93.