HTN规划的不可判定性：理论边界与工程启示

系列第五篇，深入探讨HTN规划的理论极限。如果你还没读过前面的文章，建议先从[任务规划概述]、[HTN形式化定义]、[STN与HTN的区别]、[TFD算法详解]开始。

一、开篇：从TFD到理论边界

在上一篇文章中，我们详细介绍了TFD（全序向前分解）算法——STN规划的核心方法。TFD的优势显而易见：状态确定性让数值计算变得简单，全序约束让搜索空间相对可控，清晰的算法流程让工程实现变得直接。

但如果我们把目光从STN转向更一般的HTN（分层任务网络），情况就变得复杂了。

HTN引入了状态维持约束（modal constraints / temporal constraints）——比如"在整个数据传输期间，天线必须始终指向地面站"。这种约束极大地增强了表达能力，但也带来了一个根本性的问题：

HTN规划问题是不可判定的。

这意味着什么？为什么STN可判定而HTN不可判定？这对我们的工程实践又有什么影响？本文将系统地回答这些问题。

二、什么是"不可判定性"？

在深入HTN之前，我们需要先理解"不可判定性"（Undecidability）这个概念。

2.1 可判定 vs 不可判定

在计算理论中，一个问题被称为可判定的（Decidable），如果存在一个算法，能够在有限时间内对任意输入给出"是"或"否"的答案。

相反，如果不存在这样的算法，这个问题就是不可判定的（Undecidable）。

注意：不可判定不等于"很难"。NP难问题虽然很难（需要指数时间），但至少存在算法可以解决。不可判定问题则是根本不存在这样的算法。

2.2 经典例子：停机问题

最著名的不可判定问题是停机问题（Halting Problem）：

给定一个程序P和输入I，判断P在输入I上是否会停机（结束运行），还是会无限循环。

图灵在1936年证明了：不存在一个通用算法能解决所有程序的停机问题。

证明思路很巧妙：假设存在这样的算法H(P, I)，我们可以构造一个程序Q：

Q(P):
    if H(P, P) == "会停机":
        无限循环
    else:
        立即停机

现在问：Q(Q)会停机吗？
- 如果H说Q(Q)会停机，那么Q就会无限循环——矛盾！
- 如果H说Q(Q)不会停机，那么Q就会立即停机——也矛盾！

所以H不可能存在。

2.3 计算复杂性层级

为了更好地理解不可判定性的位置，我们来看计算复杂性层级：

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ ... ⊆ 可判定问题 ⊆ 所有问题
                                              ↑
                                         不可判定问题在此之外

P：多项式时间可解
NP：多项式时间可验证
PSPACE：多项式空间可解
EXPTIME：指数时间可解
可判定问题：存在算法（无论多慢）
不可判定问题：不存在算法

HTN规划就位于这个层级的最外层——不可判定。

三、HTN为什么是不可判定的？

3.1 核心原因：状态维持约束

HTN与STN的根本区别在于状态维持约束（modal constraints）。这种约束要求：

在某个任务执行期间，某个条件必须始终保持成立。

例如：
- "在数据传输期间，天线必须始终指向地面站"
- "在机动过程中，电量必须始终保持在20%以上"

这种约束引入了时间维度上的复杂性。在STN中，我们知道每个任务执行时的确切状态；但在HTN中，我们需要考虑一段时间区间内的状态变化。

3.2 证明思路：归约到Post对应问题

Erol、Hendler和Nau在1996年的经典论文中证明了HTN的不可判定性。他们的证明思路是归约（reduction）：

证明：如果HTN规划是可判定的，那么Post对应问题（PCP）也是可判定的。但PCP是已知的不可判定问题，所以HTN也是不可判定的。

Post对应问题（Post Correspondence Problem, PCP）：

给定一组多米诺骨牌，每张骨牌上面有两个字符串（上串和下串）：

骨牌1: [aa, a]
骨牌2: [b, ab]
骨牌3: [bba, bb]

问：是否存在一个骨牌序列（允许重复），使得上串拼接结果等于下串拼接结果？

例如上面的例子，序列[1, 3]：
- 上串：aa + bba = aabba
- 下串：a + bb = abb
不相等。

PCP被证明是不可判定的——不存在通用算法能判断任意PCP实例是否有解。

3.3 HTN如何模拟PCP

关键在于：状态维持约束让HTN能够模拟PCP的字符串拼接过程。

大致思路：
1. 用状态变量表示当前的上串和下串
2. 用方法表示选择骨牌
3. 用状态维持约束确保字符串的"累积"过程
4. 用目标条件检查上串是否等于下串

简化示例（帮助理解，非严格证明）：

假设有一个简化的PCP实例：

骨牌1: [a, ab]
骨牌2: [b, a]

我们可以构造对应的HTN问题：

;; 状态变量
(current-top "")      ; 当前上串
(current-bottom "")   ; 当前下串

;; 方法：选择骨牌1
(:method (select-domino)
  :precondition ()
  :tasks (!append-top "a")
          (!append-bottom "ab")
  :constraint (during task current-top保持累积))

;; 方法：选择骨牌2  
(:method (select-domino)
  :precondition ()
  :tasks (!append-top "b")
          (!append-bottom "a")
  :constraint (during task current-top保持累积))

;; 目标：上串等于下串
(:goal (equal current-top current-bottom))

这里的核心在于:constraint (during ...)——状态维持约束让HTN能够在任务执行期间"记住"并累积字符串。正是这种约束使HTN具备了模拟图灵机的能力。

由于PCP不可判定，能模拟PCP的HTN也不可判定。

注：由于篇幅限制，此处为简化说明。严格的技术证明涉及将图灵机编码为HTN问题，感兴趣的读者请参考 Erol et al. (1996) 的原始论文。

3.4 关键定理

定理（Erol et al., 1996）：

HTN规划问题是不可判定的，即使限制为：
- 命题逻辑（无变量）
- 有限的方法集合
- 无递归（方法不直接或间接调用自身）

这个结论非常强烈：即使做了这么多限制，HTN仍然是不可判定的。

3.5 不可判定性的具体表现

不可判定性在实际中意味着什么？

无法判断问题是否有解：不存在通用算法能判断任意HTN问题是否有解
规划器可能永远运行：对于某些输入，规划器可能既找不到解，也无法证明无解
完备性与效率的权衡：我们必须在算法完备性（找到所有解）和计算效率之间做出选择

3.5.1 什么是完备性（Completeness）？

在规划领域，完备性指的是：

如果解存在，算法一定能找到；如果不存在，算法一定能证明无解。

对于可判定问题（如STN），我们可以设计完备算法。但对于不可判定问题（如HTN），不存在完备的通用算法。

3.5.2 SHOP2 为什么放弃完备性？

SHOP2 采用的是深度优先搜索，它：
- ✅ 优点：速度快，内存占用小，适合大规模问题
- ❌ 缺点：不是完备的——可能因为搜索顺序问题错过解

为什么做这种选择？

因为在实际工程应用中：
1. 时间比完备性更重要：用户通常愿意接受"大概率找到的解"，而不是等待"保证找到所有解"
2. 启发式剪枝非常有效：领域知识可以指导搜索到高质量解
3. 问题本身就有约束：实际任务规划问题通常有资源、时间限制，天然限制了搜索空间

3.5.3 追求完备性需要什么？

理论上，如果要设计一个完备的HTN规划器，需要：
- 广度优先搜索：保证找到最短解，但内存爆炸
- 无限时间和空间：对于不可判定问题，完备算法可能永不停止
- 严格的深度限制：人为限制搜索深度，但这又牺牲了完备性

所以在实践中，所有HTN规划器都在完备性和实用性之间做出了权衡。

四、STN为什么是可判定的？

4.1 核心区别：没有状态维持约束

STN（Simple Task Network）之所以可判定，是因为它不支持状态维持约束。STN只支持：
- 顺序约束（任务A在任务B之前）
- 变量绑定约束

这看似是一个很大的限制，但实际上让问题变得可处理。

4.2 可判定性来源

第一，可以转换为经典规划问题

STN问题可以转换为经典STRIPS规划问题：
- 每个任务对应一个操作
- 方法的分解对应于操作序列的展开
- 由于是全序的，可以预先展开所有可能的分解树

第二，TFD算法可以穷尽搜索

TFD算法的搜索空间虽然是指数级的，但是有限的：
- 每个复合任务只有有限个分解方法
- 每次分解都会增加任务数量
- 由于无递归（假设方法不循环调用），分解深度是有限的

所以TFD可以在有限时间内穷尽所有可能性，从而判定问题是否有解。

4.3 复杂度分析

虽然STN是可判定的，但它的复杂度仍然很高：

最坏情况下是EXPTIME-complete：搜索空间随任务数量指数增长
实际中通常是PSPACE-complete或更低：对于特定领域可以设计更高效算法

但至少，我们知道算法一定会停机——要么找到解，要么证明无解。

五、HTN vs STN 对比总结

特性	HTN	STN
状态维持约束	✅ 支持	❌ 不支持
可判定性	❌ 不可判定	✅ 可判定
表达能力	更强（可表达时序约束）	受限（仅顺序约束）
算法完备性	无法保证	可以保证
搜索空间	可能无限	有限（给定有限分解）
工程应用	需要启发式/近似	可精确求解

5.1 表达能力对比

HTN能表达STN不能表达的场景：

# HTN可以表达：在数据传输期间保持指向
[task: 传输数据]
constraint: during(task, pointing == ground_station)

# STN的表达局限：
# 只能分解为两个顺序任务，但无法保证"传输期间"始终指向
# 如果传输过程中姿态被其他任务改变，STN无法检测这种违规
[task1: 指向地面站]
[task2: 传输数据]
order: task1 < task2
# ❌ 没有机制确保 task2 执行期间 pointing 保持为 ground_station

4.4 复杂度对比表

特性	STN	HTN
可判定性	✅ 可判定	❌ 不可判定
最坏时间复杂度	EXPTIME-complete	不可判定（无上限）
实际常用算法	TFD（完备）	SHOP2（启发式，不完备）
状态维持约束	❌ 不支持	✅ 支持
搜索空间	有限（可穷尽）	可能无限
完备性保证	有	无
实际适用场景	航天器任务规划（顺序为主）	复杂时序约束场景

关键洞察：
- STN 牺牲表达能力换取可判定性和完备性
- HTN 保留表达能力但接受不可判定性和启发式求解

5.2 实际影响

在航天任务规划中，这种差异非常重要：
- 如果需要"姿态始终稳定"、"电量始终充足"这类约束，必须用HTN
- 如果只是"先做这个，再做那个"，STN就够了

六、这对工程实践意味着什么？

6.1 理论不可判定 ≠ 工程不可用

这是最重要的一点。不可判定性是一个理论结果，不意味着HTN在工程中不能用。

事实上，SHOP、SHOP2、SIADEX等HTN规划器在航天、应急管理等实际应用中表现很好。

6.2 实际应对策略

工程实践中，我们常用以下策略应对不可判定性：

策略1：限制方法深度（Bounded Depth）

设置最大分解深度，超过就停止搜索。这保证了算法会停机，但可能错过深层解。

def plan_htn(state, task_network, max_depth=10):
    if max_depth <= 0:
        return None  # 达到深度限制，放弃
    # ... 正常规划逻辑

策略2：使用启发式搜索（Heuristic Search）

用启发式函数指导搜索，优先探索更有希望的路径。这不保证找到最优解，但通常能找到满意解。

策略3：领域特定的约束检查

在问题定义阶段就加入领域知识，剪枝不可能的搜索分支。

策略4：超时机制（Timeout）

设置时间上限，超时则返回当前找到的最佳解（或报告失败）。

import time

def plan_with_timeout(state, task_network, timeout=60):
    start = time.time()
    while time.time() - start < timeout:
        solution = search_one_solution(state, task_network)
        if solution:
            return solution
    return None  # 超时，未找到解

6.3 SHOP/SHOP2的实践智慧

SHOP和SHOP2是HTN规划的经典实现，它们的作者Nau等人对不可判定性有深刻的理解：

"我们接受规划器的不完备性，以换取实用性。"

SHOP2的设计原则：
- 使用深度优先搜索（可能错过最优解，但速度快）
- 支持外部函数调用（用领域知识剪枝）
- 允许用户定义启发式函数

这些设计都是在"理论不可判定"的限制下，追求"工程可用"的折中。

6.4 选择HTN还是STN？

实际项目中如何选择？

选择STN，如果：
- 任务之间有明确的先后顺序，没有复杂的时序约束
- 需要算法的完备性保证
- 问题规模较小，可以接受指数级搜索

选择HTN，如果：
- 需要表达"期间维持"、"并行约束"等复杂时序关系
- 问题规模较大，需要启发式剪枝
- 可以接受不完备性，换取表达能力

七、总结

7.1 核心要点

HTN规划是不可判定的：不存在通用算法能判断任意HTN问题是否有解
根本原因是状态维持约束：这种约束让HTN能模拟图灵机，从而具有计算完备性
STN是可判定的：因为没有状态维持约束，搜索空间有限
理论不限制工程应用：通过限制深度、超时机制、启发式搜索等策略，HTN在实践中完全可用

7.2 与前面文章的关系

[任务规划概述] → [HTN形式化定义] → [STN与HTN区别] → [TFD算法] → [本文: 不可判定性]
                                                    ↓
                                           理解了为什么需要更复杂的算法

前面我们学了STN的TFD算法——简单、高效、可判定。本文解释了为什么要发明更复杂的HTN算法：因为STN的表达能力不够，而HTN虽然不可判定，但工程上可以通过各种策略来应对。

7.3 工程启示

理解HTN的不可判定性，对工程实践有几个重要启示：

不要追求理论完备性：在实际应用中，"足够好"的解往往比"最优"的解更有价值
充分利用领域知识：启发式函数、约束检查等都可以显著提高规划效率
设置合理的终止条件：超时、深度限制等都是必要的工程手段
选择合适的工具：不是所有问题都需要HTN的表达能力，有时候STN就够了

参考文献

Erol, K., Hendler, J., & Nau, D. S. (1996). Complexity results for HTN planning. Annals of Mathematics and Artificial Intelligence, 18(1), 69-93.
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.
Post, E. L. (1946). A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52(4), 264-268.
Nau, D. S., et al. (2003). SHOP2: An HTN planning system. Journal of Artificial Intelligence Research, 20, 379-404.
Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann. (Chapter 11)