第11章 自动规划

摘要：本章系统介绍了自动规划的核心理论与方法。从经典规划的形式化定义和PDDL建模语言出发，深入探讨了状态空间搜索（前向/后向）、规划启发式（忽略删除效果、状态抽象等）、偏序规划、规划图与GraphPlan、基于SAT的规划以及分层任务网络（HTN）等核心算法。文章重点分析了各种启发式方法（如h^FF、hmax、PDB、LM-cut）的原理与优劣，并比较了不同规划方法的适用场景。最后，文章将经典规划技术与现代AI发展（如LLM规划、多模态具身规划、AI对齐）联系起来，探讨了符号规划在当今AI系统中的价值与挑战。核心思想是：规划的全部技术进步都源于对“如何在指数级状态空间中利用问题结构”这一问题的不同回答。

对应 Artificial Intelligence: A Modern Approach, 4th Edition 第 11 章 Automated Planning

---

1. 章节概述

前面章节给了我们两套解决"如何达成目标"的工具：

• 第 3–4 章的搜索：状态是黑盒（原子表示），需要人工提供后继函数与启发式。搜索算法看不见状态内部，因此无法自动导出启发式。
• 第 7–10 章的逻辑：能精确描述世界，但通用定理证明的搜索空间过大，直接用归结做规划效率极低（第 7 章 SATPlan 已初见端倪）。

自动规划（automated planning）的核心思想是取两者之长：

用因子化的逻辑表示描述状态与动作（使规划器能"看见"状态内部结构），同时用专门的搜索算法（而非通用定理证明）求解。

这个"表示透明"带来的最大红利是：规划器可以自动从问题描述中导出启发式函数。这是规划相对于纯搜索的决定性优势——第 3 章需要人类为八数码设计曼哈顿距离，而规划器能对任意 PDDL 领域自动生成可采纳启发式。

本章主线：

1. 经典规划的定义：状态、动作、目标的因子化表示。
2. PDDL（Planning Domain Definition Language）：标准建模语言。
3. 规划即状态空间搜索：前向（progression）与后向（regression）。
4. 规划启发式：忽略前提、忽略删除效果、状态抽象、集合覆盖。
5. 偏序规划（partial-order planning）：最小承诺原则。
6. 规划图与 GraphPlan：互斥关系、层次扩展、解抽取。
7. 其他经典方法：SATPlan、答案集编程、一阶逻辑推理规划。
8. 分层任务网络 HTN（hierarchical task network）：用领域知识分解任务。
9. 非确定性、部分可观测、在线规划：应急规划、无传感规划、执行监控与重规划。
10. 调度（scheduling）：时间、资源、关键路径。

核心直觉：

经典规划的全部技术进展，都可以看作对"如何在指数级状态空间中利用问题结构"这一问题的不同回答：启发式利用松弛结构，偏序规划利用独立性，GraphPlan 利用可达性与互斥性，HTN 利用人类给的分解知识。

---

2. 关键概念与定义

2.1 经典规划问题的形式化

经典规划（classical planning）的标准假设（合称 STRIPS 假设）：

假设	含义
完全可观测	智能体确切知道当前状态
确定性	动作效果唯一确定
静态	世界只因智能体动作而变化
离散	状态、时间、动作、对象都是离散的
单智能体	无其他行动者
有限	对象数量有限

规划问题是一个四元组 $\Pi =⟨\mathcal{F},\mathcal{A},s_0,g⟩$：

• $\mathcal{F}$：流（fluents）/ 命题的有限集合。
• $\mathcal{A}$：动作集合。
• $s_0\subseteq \mathcal{F}$：初始状态。
• $g$：目标条件（文字的合取）。

状态表示：状态 $s$ 是一个基原子（ground atom）的合取，如：

$$At(Truc{k}_1,Melbourne)\wedge At(Truc{k}_2,Sydney)$$

采用封闭世界假设（closed-world assumption）：未提及的原子为假。因此状态可等价地表示为为真的原子集合。

⚠️ 状态中不允许变量、函数符号、否定、析取。这是为效率所做的严格限制（对比第 8 章完整 FOL 的表达力）。

2.2 动作模式（Action Schema）

一个 动作模式（action schema / operator）由三部分构成：

Action(Fly(p, from, to),
    PRECOND: At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to)
    EFFECT:  ¬At(p, from) ∧ At(p, to))

• 变量：$p,from,to$，隐含全称量化。
• 前提（precondition）：动作可执行的条件，文字的合取。
• 效果（effect）：动作执行后状态的变化，文字的合取。

实例化（grounding / instantiation）：用常量替换变量得到基动作（ground action）：

$$Fly(P_1,SFO,JFK)$$

动作的适用性：动作 $a$ 在状态 $s$ 中适用（applicable），当且仅当 $s\models PRECOND(a)$，即前提的所有正文字都在 $s$ 中，所有负文字都不在 $s$ 中。

结果状态（转移函数）：

$$RESULT(s,a)=(s\setminus DEL(a))\cup ADD(a)$$

其中：

• $ADD(a)$（添加列表 add list）：$EFFECT(a)$ 中的正文字集合。
• $DEL(a)$（删除列表 delete list）：$EFFECT(a)$ 中负文字对应的原子集合。

⚠️ 注意顺序：先删后加。若某原子同时在 ADD 和 DEL 中，最终它为真。

这个定义优雅地解决了框架问题：任何未在 $ADD$ 或 $DEL$ 中提及的流自动保持不变。这是 STRIPS 表示相对于第 7 章"后继状态公理"的巨大简化——不需要写任何框架公理。

2.3 PDDL（Planning Domain Definition Language）

PDDL 是规划领域的标准语言（1998 年为 IPC 国际规划竞赛设计），把问题分为两个文件。

领域文件（domain file）—— 描述动作与谓词：

(define (domain air-cargo)
  (:requirements :strips :typing)
  (:types cargo plane airport)
  (:predicates
     (at ?x - (either cargo plane) ?a - airport)
     (in ?c - cargo ?p - plane))

  (:action load
     :parameters (?c - cargo ?p - plane ?a - airport)
     :precondition (and (at ?c ?a) (at ?p ?a))
     :effect (and (not (at ?c ?a)) (in ?c ?p)))

  (:action unload
     :parameters (?c - cargo ?p - plane ?a - airport)
     :precondition (and (in ?c ?p) (at ?p ?a))
     :effect (and (at ?c ?a) (not (in ?c ?p))))

  (:action fly
     :parameters (?p - plane ?from - airport ?to - airport)
     :precondition (at ?p ?from)
     :effect (and (not (at ?p ?from)) (at ?p ?to))))

问题文件（problem file）—— 描述具体实例：

(define (problem cargo-1)
  (:domain air-cargo)
  (:objects C1 C2 - cargo
            P1 P2 - plane
            SFO JFK - airport)
  (:init (at C1 SFO) (at C2 JFK)
         (at P1 SFO) (at P2 JFK))
  (:goal (and (at C1 JFK) (at C2 SFO))))

PDDL 的演进（表达力扩展）：

版本/特性	增加的能力
STRIPS（基础）	命题前提与效果
ADL（Action Description Language）	否定前提、析取、量化效果、条件效果、等词、开放世界
PDDL 2.1	数值流（numeric fluents）、持续动作（durative actions）、metric 优化目标
PDDL 2.2	派生谓词（derived predicates）、定时初始文字
PDDL 3	轨迹约束（trajectory constraints）、软目标与偏好（preferences）
PDDL+	连续过程与外生事件（混合系统）

条件效果（conditional effect）示例：

:effect (and (at ?p ?to) (not (at ?p ?from))
             (forall (?c - cargo)
                (when (in ?c ?p)
                   (and (at ?c ?to) (not (at ?c ?from))))))

⚠️ 条件效果显著增加表达力（一个动作可根据状态产生不同效果），但也使后向搜索与启发式计算复杂化。

2.4 经典规划领域示例

书中的标准基准领域：

领域	描述	教学价值
Air Cargo	飞机运货，Load/Unload/Fly	展示多类型对象与状态耦合
Blocks World	积木堆叠，Move/MoveToTable	经典的子目标交互问题（Sussman 异常）
Spare Tire	换备胎，Remove/PutOn/LeaveOvernight	展示"有害动作"（LeaveOvernight 移除所有轮胎）
Shakey’s World	机器人推箱子开灯	早期规划系统的真实场景

Blocks World 定义：

(:action Move
   :parameters (?b ?x ?y)
   :precondition (and (On ?b ?x) (Clear ?b) (Clear ?y)
                      (Block ?b) (Block ?y) (≠ ?b ?x) (≠ ?b ?y) (≠ ?x ?y))
   :effect (and (On ?b ?y) (Clear ?x)
                (not (On ?b ?x)) (not (Clear ?y))))

(:action MoveToTable
   :parameters (?b ?x)
   :precondition (and (On ?b ?x) (Clear ?b) (Block ?b) (≠ ?b ?x))
   :effect (and (On ?b Table) (Clear ?x) (not (On ?b ?x))))

⚠️ 为什么需要两个动作？因为 $Table$ 不是 $Block$，永远 $Clear$，不能用统一的 $Move$ 处理（否则 $\neg Clear(Table)$ 会被错误地添加）。这类建模细节是 PDDL 实践中的常见陷阱。

Sussman 异常（Sussman Anomaly）：

初始：  C          目标：  A
       A  B               B
    ━━━━━━━━            C
                      ━━━━━━━━
目标 = On(A,B) ∧ On(B,C)

若先达成 $On(A,B)$，必须拆掉才能达成 $On(B,C)$；反之亦然。这证明了目标不可独立求解，是早期"线性规划器"（linear planner，指按顺序逐个满足子目标）的反例，推动了偏序规划的发展。

2.5 复杂度

问题	复杂度
PlanSAT（是否存在方案）	PSPACE-完全
Bounded PlanSAT（是否存在长度 ≤ k 的方案）	PSPACE-完全
无删除效果（delete-free）的规划	NP-完全
最优 delete-free 规划	NP-难
STRIPS 无负前提且效果为正	多项式（可达性分析）

为什么是 PSPACE 而非 NP：方案长度可能是状态数（指数级）的量级，因此无法在多项式时间内"猜测并验证"一个方案。但可以用多项式空间逐步搜索。

实践意义：最坏情形复杂度很高，但真实规划问题往往有大量结构（子目标近似独立、状态空间稀疏连通），使得好的启发式极为有效。IPC 竞赛中的现代规划器能处理数百万个基动作的问题。

---

3. 核心理论与算法

3.1 规划即状态空间搜索

3.1.1 前向状态空间搜索（Forward / Progression Search）

function FORWARD-SEARCH(problem) returns 方案或 failure
    // 就是第 3 章的图搜索，只是状态与后继由 PDDL 定义
    初始状态 ← s₀
    后继函数 ← λs. {(a, RESULT(s,a)) : a 在 s 中适用}
    目标测试 ← λs. s ⊨ g
    动作代价 ← 通常为 1（或 PDDL 指定的 metric）

    return A*-SEARCH(以上定义的搜索问题, h)

优势：

• 实现简单，直接复用 A*、GBFS、加权 A*、Enforced Hill Climbing。
• 状态是完全指定的，容易检查目标与去重。
• 现代规划器的主流（FF、FastDownward、LAMA 均基于前向搜索）。

劣势：

• 分支因子巨大：一个状态可能有数千个适用动作。
• 大量无关动作（如买牛奶任务中，"去纽约"也是适用的）。

这就是为什么启发式是规划的生命线：没有启发式的前向搜索毫无希望；有了好的启发式，同样的搜索能解决工业规模问题。

动作实例化的效率问题：
从动作模式生成基动作是一次合一/模式匹配（第 9 章 §3.2.3），本质是 CSP。现代规划器用规划器预处理（如 Fast Downward 的 translator）把 PDDL 转为有限域表示（SAS+），大幅压缩状态空间。

3.1.2 后向状态空间搜索（Backward / Regression Search）

从目标出发，反向搜索到初始状态。

关键概念：回归（regression）

给定目标描述 $g$ 和动作 $a$，$a$ 的前驱（predecessor）状态描述：

$$g^{\prime }=(g\setminus ADD(a))\cup PRECOND(a)$$

即：把 $a$ 能达成的部分从目标中去掉，把 $a$ 的前提加进去。

相关性检查（relevance）：
只考虑相关动作——即 $a$ 至少达成 $g$ 中的一个文字，且不删除 $g$ 中的任何文字：

$$ADD(a)\cap g\ne \varnothing \wedge DEL(a)\cap g=\varnothing$$

示例（Air Cargo）：

目标 $g=At(C_1,JFK)$。相关动作 $Unload(C_1,p,JFK)$，回归得：

$$g^{\prime }=In(C_1,p)\wedge At(p,JFK)$$

⚠️ 注意 $p$ 仍是变量——后向搜索处理的是部分实例化的状态描述，这带来了灵活性但也增加了复杂性。

优势：

• 分支因子小：只考虑相关动作，大幅剪枝。对目标少、动作多的问题特别有效。

劣势：

• 处理的是状态集合（部分描述）而非单一状态，难以设计精确的启发式。
• 部分实例化的变量处理复杂。
• 可能生成不可达的子目标（回归得到的描述可能对应无任何真实状态）。

现代实践：后向搜索在纯经典规划中已较少作为主搜索方向，但它的回归思想在以下地方仍然核心：

• 计算启发式（如 $h^m$ 系列）
• 偏序规划（§3.3）
• 反例引导的抽象精化

3.2 规划启发式（Planning Heuristics）

这是规划领域最重要的技术贡献。核心思路：通过松弛（relaxation）问题自动导出启发式。

回顾第 3 章：$h$ 若来自松弛问题的最优解，则一定是可采纳的（admissible），因为松弛问题的最优解不会比原问题差。

3.2.1 松弛 1：忽略前提（Ignore Preconditions）

去掉所有动作的前提，则每个动作总是可执行。

• 若同时忽略删除效果，问题退化为集合覆盖问题（set-cover）：选最少的动作，使其 ADD 列表的并集覆盖目标。
• 集合覆盖是 NP-难，但有贪心近似算法，比率为 $O(\log n)$。
• 更粗但极快的近似：$h=|g\setminus s|$（未满足的目标文字数）。

⚠️ 贪心近似不保证可采纳（可能高估）。若要可采纳性，需精确求解或用下界。

3.2.2 松弛 2：忽略删除效果（Ignore Delete Lists）—— 最重要的松弛

核心思想：去掉所有动作的 DEL 列表。

后果：状态单调增长（原子只增不减），因此永不需要撤销——没有子目标冲突，没有死锁。

性质：

• 松弛问题的解一定存在（若原问题可解）。
• 松弛问题的最优解仍是 NP-难，但可用贪心/近似快速计算。
• 松弛问题的可达性分析是多项式时间的（不断应用所有适用动作直到不动点）。

这催生了几个关键启发式：

$h^{add}$（加性启发式）：假设子目标完全独立

$$h^{add}(s)=\sum _{p\in g}\Delta (s,p)$$

其中 $\Delta (s,p)$ 是达成单个原子 $p$ 的估计代价，递归定义：

$$\Delta (s,p)=\{\begin{array}{ll}0& p\in s\\ \underset{a:p\in ADD(a)}{\min }[cost(a)+\sum _{q\in PRE(a)}\Delta (s,q)]& \text{否则}\end{array}$$

• 不可采纳（重复计算共享子目标的代价，可能高估）。
• 但信息量大，实践中引导性强。

$h^{max}$（最大启发式）：

$${\Delta }^{max}(s,p)=\underset{a:p\in ADD(a)}{\min }[cost(a)+\underset{q\in PRE(a)}{\max }{\Delta }^{max}(s,q)]$$

• 可采纳（取 max 而非 sum，是下界）。
• 但过于乐观，信息量弱。

$h^{FF}$（FF 启发式，Hoffmann & Nebel 2001）：

计算松弛问题的一个实际方案（relaxed plan），取其长度作为启发式。

function H-FF(s, g) returns 启发式值
    // 阶段 1：前向构建松弛规划图（无删除效果）
    P₀ ← s
    i ← 0
    while g ⊄ Pᵢ do
        Aᵢ ← {a : PRECOND(a) ⊆ Pᵢ}
        P_{i+1} ← Pᵢ ∪ ⋃_{a∈Aᵢ} ADD(a)
        if P_{i+1} = Pᵢ then return ∞      // 目标不可达（死锁检测！）
        i ← i + 1

    // 阶段 2：后向抽取松弛方案
    RelaxedPlan ← {}
    Goals ← g
    for layer = i down to 1 do
        for each p in Goals at layer do
            选择一个 a ∈ A_{layer-1} 使 p ∈ ADD(a)   // 贪心选择
            RelaxedPlan ← RelaxedPlan ∪ {a}
            Goals ← Goals ∪ PRECOND(a)
    return |RelaxedPlan|

$h^{FF}$ 的特点：

• 不可采纳（贪心抽取，非最优松弛方案），但实践中极其有效。
• 免费提供死锁检测：若松弛问题不可解，原问题必然不可解 ⇒ 返回 $\infty$，剪掉整个分支。
• 副产品：有帮助的动作（helpful actions）—— 松弛方案第一层用到的动作，优先扩展这些动作可大幅加速搜索（preferred operators）。

FF 规划器（Fast-Forward）用 $h^{FF}$ + Enforced Hill Climbing（EHC）+ helpful actions，在 IPC-2000 上大幅领先，开启了"启发式搜索规划"的时代。

3.2.3 松弛 3：状态抽象（State Abstraction）

抽象：把多个具体状态映射到一个抽象状态，从而缩小状态空间。

模式数据库（Pattern Database, PDB）：

1. 选择流的一个子集（模式 pattern），如只关心积木 A、B 的位置。
2. 忽略其余流，得到一个小得多的抽象状态空间。
3. 穷举抽象空间，用逆向 BFS 计算每个抽象状态到抽象目标的精确距离，存表。
4. 搜索时，把具体状态投影到抽象状态，查表得启发式值。

可采纳性：抽象是松弛（去掉了约束），所以 PDB 值是下界，可采纳。✓

多 PDB 组合：

• 若两个模式不相交（没有共享的动作影响），可以相加（additive PDB），得到更强的可采纳启发式。
• 否则只能取 $\max$。

其他抽象方法：

• Merge-and-Shrink：自动构造抽象，逐步合并变量并压缩状态，是 PDB 的泛化。
• 笛卡尔抽象（Cartesian abstraction）+ CEGAR（反例引导抽象精化）。
• Landmark 启发式（$h^{LM}$）：识别任何方案都必须经过的中间事实或动作（landmark），用其数量或代价划分（LM-cut）作为可采纳启发式。LM-cut 是当前最优规划的主力启发式之一。

3.2.4 启发式对比总结

启发式	可采纳	计算代价	信息量	典型用途
$h=\Vert g\setminus s\Vert$	有时	$O(\Vert g\Vert )$ 极低	很弱	baseline
$h^{max}$	✓	多项式	弱	最优规划的下界
$h^{add}$	✗	多项式	强	满意规划（satisficing）
$h^{FF}$	✗	多项式	很强	满意规划主力
PDB	✓	预处理指数、查询 $O(1)$	中~强	最优规划
LM-cut	✓	多项式（较贵）	强	最优规划主力
Merge-and-Shrink	✓	可调	可调	最优规划

两条不同的赛道：

• 最优规划（optimal planning）：必须用可采纳启发式 + A*。主力：LM-cut、M&S、Symbolic search。
• 满意规划（satisficing planning）：只求快速找到较好的解。主力：$h^{FF}$ + GBFS + preferred operators + 多队列（LAMA）。

3.3 偏序规划（Partial-Order Planning, POP）

3.3.1 核心思想：最小承诺（Least Commitment）

状态空间搜索必须为每个动作确定精确位置（全序），即使很多动作之间顺序无关。

偏序规划只在必要时才承诺顺序，保持方案为一个偏序集（partial order），可展开为多个等价的全序方案（线性化 linearization）。

优势场景：多个独立子目标。例如"穿左袜+左鞋"与"穿右袜+右鞋"，POP 只需承诺 2 个必要的顺序约束，而全序搜索要探索 $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 种交错。

3.3.2 表示：偏序规划的"计划"结构

一个偏序计划是一个四元组 $⟨A,O,L,B⟩$：

• $A$：动作集合，含两个虚拟动作：
  • $Start$：无前提，效果 = 初始状态
  • $Finish$：前提 = 目标，无效果
• $O$：顺序约束集合，形如 $a\prec b$（$a$ 必须在 $b$ 之前）。
• $L$：因果链接（causal link）集合，形如 $a\stackrel{p}{\to }b$，读作"$a$ 为 $b$ 提供前提 $p$"。
• $B$：变量绑定约束。

因果链接的作用：它是一个受保护的承诺——记录了"$b$ 的前提 $p$ 由 $a$ 提供"，任何威胁这个链接的动作都必须被处理。

3.3.3 威胁与解决（Threats and Resolution）

威胁（threat）：动作 $c$ 威胁因果链接 $a\stackrel{p}{\to }b$，若：

• $c$ 的效果包含 $\neg p$，且
• $c$ 可以被排在 $a$ 与 $b$ 之间（顺序上不矛盾）。

两种解决方式：

     a ──p──→ b
        ↑
        c  (效果含 ¬p，威胁)

方案 1：降级（demotion）        方案 2：提升（promotion）
   c ≺ a ──p──→ b                  a ──p──→ b ≺ c
   把 c 排到 a 之前                  把 c 排到 b 之后

（若涉及变量，还有第三种：分离（separation）—— 添加不等约束使 $c$ 的效果不与 $p$ 合一。）

3.3.4 POP 算法

function POP(initial, goal, actions) returns 偏序计划或 failure
    plan ← MAKE-MINIMAL-PLAN(initial, goal)
        // A = {Start, Finish}, O = {Start ≺ Finish}, L = {}, B = {}

    loop do
        if SOLUTION?(plan) then return plan
            // 所有前提都有因果链接支持，且无未解决威胁

        // 1. 选择一个未满足的前提（open precondition）
        Sneed, c ← SELECT-SUBGOAL(plan)

        // 2. 选择一个动作来达成它（非确定性选择点 ⇒ 需回溯）
        CHOOSE-OPERATOR(plan, actions, Sneed, c):
            选择 Sadd ∈ A 或新实例化一个动作，使 c ∈ EFFECT(Sadd)
            if 无此动作 then return failure
            添加因果链接 Sadd --c--> Sneed 到 L
            添加顺序约束 Sadd ≺ Sneed 到 O
            if Sadd 是新动作 then
                添加 Sadd 到 A
                添加 Start ≺ Sadd ≺ Finish 到 O

        // 3. 解决所有威胁
        RESOLVE-THREATS(plan):
            for each 因果链接 Si --c--> Sj in L do
                for each 动作 Sk in A that 效果含 ¬c do
                    if Sk 可能位于 Si 与 Sj 之间 then
                        选择：添加 Sk ≺ Si（降级）
                           或：添加 Sj ≺ Sk（提升）
                        if 顺序约束不一致（产生环） then return failure

在"计划空间"中搜索：
⚠️ 注意 POP 搜索的节点是部分计划，而非状态。这是与前向搜索的根本区别（plan-space search vs state-space search）。

性质：

• 可靠（sound）：任何完全的偏序计划的任意线性化都是有效方案。
• 完备（complete）：若使用系统的回溯，POP 能找到所有解。
• 产生灵活方案：偏序计划可以在执行时根据资源可用性选择线性化顺序——对多智能体执行、调度特别有价值。

局限：

• 启发式设计困难（部分计划的"距离目标多远"不好估计）。
• 1990s 曾是主流（UCPOP、SNLP），但在 2000 年后被 $h^{FF}$ 驱动的前向搜索全面超越——因为前向搜索的启发式太强了。
• 现代地位：POP 的思想在时序规划（temporal planning）与多智能体规划中仍然核心，因为那些领域天然需要偏序表示。

Sussman 异常的 POP 解：POP 能正确处理，因为它不强制子目标的求解顺序，威胁检测机制自动发现 $Move(A,B)$ 与 $Move(B,C)$ 的冲突并排序。

3.4 规划图与 GraphPlan

3.4.1 规划图（Planning Graph）

规划图是一个分层的有向图，交替出现状态层（level $S_i$）和动作层（level $A_i$）：

S₀        A₀         S₁         A₁         S₂  ...
├ p       ├ act1     ├ p        ├ act3     ├ p
├ q       ├ act2     ├ q        ├ act4     ├ q
├ ¬r      ├ 持续动作  ├ r                    ├ r
          │(persist) ├ ¬r                   ├ s

构造规则：

1. $S_0$ = 初始状态的所有文字（正的与负的，封闭世界下补全）。
2. $A_i$ = 所有前提在 $S_i$ 中出现且两两不互斥的基动作，外加每个文字的持续动作（persistence action / no-op，前提 = 效果 = 该文字）。
3. $S_{i+1}$ = $A_i$ 中所有动作的所有效果。
4. 计算 $A_i$ 与 $S_{i+1}$ 中的互斥关系（mutex）。

关键性质：规划图是多项式规模、多项式时间构造的，但它是原问题的松弛近似——它同时表示了所有可能并行执行的动作，忽略了很多约束。

3.4.2 互斥关系（Mutual Exclusion, Mutex）

动作层互斥（两个动作 $a,b$ 在 $A_i$ 中互斥）：

类型	条件
不一致效果（inconsistent effects）	一个动作的效果否定另一个的效果
干扰（interference）	一个动作的效果否定另一个的前提
竞争需求（competing needs）	两个动作的前提在 $S_i$ 中互斥

状态层互斥（两个文字 $p,q$ 在 $S_{i+1}$ 中互斥）：

类型	条件
不一致支持（inconsistent support）	$p$ 与 $q$ 互为否定，或 产生 $p$ 的每对动作与产生 $q$ 的动作都互斥

示例（Spare Tire 领域）：

• $Remove(Spare,Trunk)$ 与 $Remove(Flat,Axle)$ 不互斥（可并行）。
• $Remove(Spare,Trunk)$ 与 $PutOn(Spare,Axle)$ 互斥——干扰：前者删除 $At(Spare,Trunk)$，而后者需要它。

⚠️ 重要：mutex 关系是单调递减的——若两个文字在 $S_i$ 不互斥，则在 $S_j(j>i)$ 也不互斥。这保证了规划图会收敛到不动点（level off）。

3.4.3 规划图作为启发式来源

$h_{levelsum}$（level sum 启发式）：

$$h_{levelsum}(s)=\sum _{p\in g}level(p)$$

其中 $level(p)$ 是 $p$ 首次出现在规划图中的层数。

• 不可采纳（子目标独立假设），但信息量好。

$h_{maxlevel}$：${\max }_{p\in g}level(p)$，可采纳。

$h_{setlevel}$：$g$ 中所有文字两两不互斥地出现的最早层数，可采纳且比 $h_{maxlevel}$ 更强。

死锁检测（关键价值）：

若规划图收敛到不动点（level off，即 $S_i=S_{i+1}$ 且 mutex 也不变）后，目标文字仍未全部出现或仍互斥，则原问题不可解。

这是一个可靠的不可解性证明，代价只是多项式时间。

3.4.4 GraphPlan 算法

function GRAPHPLAN(problem) returns 方案或 failure
    graph ← INITIAL-PLANNING-GRAPH(problem)
    goals ← CONJUNCTS(problem.GOAL)
    nogoods ← 空哈希表           // 记录失败的 (goals, level) 对，避免重复搜索

    for tl = 0 to ∞ do
        if goals 全部非互斥地出现在 S_tl of graph then
            solution ← EXTRACT-SOLUTION(graph, goals, NUMLEVELS(graph), nogoods)
            if solution ≠ failure then return solution

        if graph 与 nogoods 都已 leveled off then
            return failure          // 可靠的不可解性判定
        graph ← EXPAND-GRAPH(graph, problem)

两个阶段的交替：

阶段 1：扩展（EXPAND-GRAPH）

• 多项式时间，构造下一层动作与状态，计算 mutex。

阶段 2：解抽取（EXTRACT-SOLUTION）

• 从最后一层的目标出发，后向搜索：为每个目标文字选择一个产生它的动作，要求所选动作两两不互斥；这些动作的前提成为下一层的目标集。
• 这是一个 CSP：变量 = 每个目标文字，值域 = 能产生它的动作，约束 = 不互斥。
• 可用 CSP 技术（第 6 章）：变量排序、约束传播、回溯。
• 或看作在"层次化的与或图"中做后向搜索。

nogood 记录（关键优化）：
记录"在第 $i$ 层，目标集 $G$ 无解"。若后续再遇到同样的 $(G,i)$，直接失败，无需重搜。这是记忆化 / no-good learning，与第 6 章 CSP 和第 7 章 CDCL 同源。

终止性保证：

1. 规划图必然收敛到不动点（文字集单调增、mutex 单调减，且都有界）。
2. nogood 集合也会收敛。
3. 两者都收敛且仍无解 ⇒ 可靠地返回 failure。

GraphPlan 的历史意义：

• Blum & Furst (1995) 提出，比当时的 POP 快几个数量级，震动了规划领域。
• 引入了并行方案（parallel plan）的概念：一层中的多个非互斥动作可同时执行。GraphPlan 找到的是层数最少的方案（并行最优），不一定是动作数最少的。
• 它的规划图后来被 FF 借用（去掉 mutex，只做可达性）作为启发式来源 —— 规划图从"求解器"变成了"启发式生成器"，这是领域内一次重要的思想转移。

局限：

• 只适用于 STRIPS（原始版本不支持条件效果、量化效果，虽有扩展）。
• 规划图规模随对象数增长可能很大。
• 解抽取阶段仍可能指数爆炸。
• 在最优（动作数最少）规划上不占优势。

3.5 基于 SAT 的规划（SATPlan / Planning as Satisfiability）

见第 7 章 §3.8 的基础，此处展开编码细节。

目标：把"存在长度为 $T$ 的方案"编码为一个 CNF 公式，交给 SAT 求解器。

命题变量：

• $p^t$：流 $p$ 在时刻 $t$ 为真（$t=\mathrm{0..}T$）
• $a^t$：动作 $a$ 在时刻 $t$ 执行（$t=\mathrm{0..}T-1$）

约束（子句）：

约束类型	公式	说明
初始状态	${\bigwedge }_{p\in s_0}{p}^0\wedge {\bigwedge }_{p\notin s_0}\neg p^0$	完全指定 $t=0$
目标	${\bigwedge }_{p\in g}{p}^T$	$T$ 时刻满足目标
前提公理	$a^t\Rightarrow {\bigwedge }_{p\in PRE(a)}{p}^t$	执行则前提成立
效果公理	$a^t\Rightarrow {\bigwedge }_{p\in ADD(a)}{p}^{t+1}\wedge {\bigwedge }_{p\in DEL(a)}\neg p^{t+1}$	效果生效
后继状态公理 （解释性框架公理）	$(p^t\wedge \neg p^{t+1})\Rightarrow {\bigvee }_{a:p\in DEL(a)}{a}^t$ $(\neg p^t\wedge p^{t+1})\Rightarrow {\bigvee }_{a:p\in ADD(a)}{a}^t$	状态改变必有原因
动作互斥	$\neg (a^t\wedge b^t)$ 对互斥的 $a,b$	防止并行执行冲突动作

互斥的两种粒度：

• 串行编码（sequential）：任意两个动作互斥 ⇒ 每步一个动作，公式小但需要更多时间步。
• ∀-step / ∃-step 编码：只对真正冲突的动作加互斥 ⇒ 允许并行，时间步少但子句多。$\exists$-step 编码通常最优。

求解流程：

for T = 0, 1, 2, ... do
    cnf ← ENCODE(problem, T)
    if SAT-SOLVE(cnf) returns model then
        return EXTRACT-PLAN(model)      // 读出所有为真的 aᵗ

优势：

• 直接受益于 SAT 求解器的工业级优化（CDCL、VSIDS、重启、子句学习）。
• 对某些结构化领域（并行度高、时间步少）极为高效。
• 易于加入额外约束（时间窗、资源上限）。

局限：

• 公式规模 $O(T\times |A|)$，$|A|$ 是基动作数，可能百万级。
• 必须逐步增大 $T$，无法证明不可解（除非另有上界论证）。
• 对长方案（$T$ 大）表现差——每增加一步，公式线性增长而搜索空间指数增长。
• 代价优化困难（需要 MaxSAT 或 PB 约束）。

相关路线：

• 答案集编程（Answer Set Programming, ASP）：用 clingo 等 ASP 求解器，语义更适合表达默认与非单调（第 10 章 §3.3），编码更简洁。
• CP / MIP 编码：用约束规划或整数规划求解器，适合数值与资源约束。
• 符号搜索（symbolic search）：用 BDD 表示状态集合，做双向 BFS。在某些最优规划任务上是当前最强方法之一。

3.6 分层任务网络规划（Hierarchical Task Network, HTN）

3.6.1 动机

经典规划从原语动作（primitive action）出发搜索，忽略了人类拥有的分解知识：

“去机场"可以分解为"叫车 → 上车 → 到达”，或"开车 → 停车 → 走到航站楼"。

HTN 让规划器利用这些领域特定的分解方法，把搜索从"原语动作序列"提升到"任务分解树"层面，指数级地缩小搜索空间。

3.6.2 核心概念

概念	说明
原语动作（primitive action）	可直接执行，有 PDDL 式的前提与效果
高层动作 / 复合任务（HLA / compound task）	不可直接执行，必须分解
方法（method）	把一个 HLA 分解为子任务序列/偏序集的规则
精化（refinement）	把 HLA 替换为其某个方法的子任务
实现（implementation）	HLA 的一个完全展开为原语动作的序列

方法示例：

Refinement(Go(Home, SFO),
    STEPS: [Drive(Home, SFOLongTermParking),
            Shuttle(SFOLongTermParking, SFO)])

Refinement(Go(Home, SFO),
    STEPS: [Taxi(Home, SFO)])

高层动作的语义（本章的关键理论贡献）：

HLA 的效果不是唯一的——不同的实现有不同的效果。因此 HLA 的效果用可达状态集合描述：

REACH(s,h)=⋃implementations i of h{RESULT(s,i)}REACH(s, h) = \bigcup_{\text{implementations } i \text{ of } h} \{RESULT(s, i)\}REACH(s,h)=implementations i of h⋃​{RESULT(s,i)}

两种语义：

语义	含义	用途
天使语义（angelic semantics）	智能体可以选择哪个实现 ⇒ 只要存在一个实现达成目标即可	HLA 是"能力"的抽象
恶魔语义（demonic semantics）	环境选择实现 ⇒ 必须所有实现都达成目标	保守/对抗设定

可达集合的近似：精确 $REACH$ 集合可能极大，实用做法是乐观（optimistic）近似（超集）与悲观（pessimistic）近似（子集）：

$$REAC{H}^{-}(s,h)\subseteq REACH(s,h)\subseteq REAC{H}^{+}(s,h)$$

剪枝规则（这是 HTN 效率的核心）：

• 若 $REAC{H}^{+}(s,h)\cap g=\varnothing$ ⇒ 该高层计划必然不可行，剪枝（无需展开）。
• 若 $REAC{H}^{-}(s,h)\cap g\ne \varnothing$ ⇒ 该高层计划必然可行，无需进一步搜索，可直接提交（后续再细化）。
• 否则 ⇒ 需要精化后重新判断。

这两条规则使 HTN 能在抽象层面就完成大部分剪枝，避免展开到原语层。

3.6.3 HTN 规划算法

方案 1：分层前向搜索（Hierarchical Forward Search）

function HIERARCHICAL-SEARCH(problem, hierarchy) returns 方案或 failure
    frontier ← 队列，初始含 [Act]        // Act 是顶层 HLA
    loop do
        if EMPTY?(frontier) then return failure
        plan ← POP(frontier)             // plan = [a₀, a₁, ..., aₙ]
        hla ← plan 中第一个 HLA（若无则 plan 全为原语）
        prefix, suffix ← hla 之前/之后的部分

        outcome ← RESULT(problem.INITIAL, prefix)
        if hla is null then              // plan 已全是原语动作
            if outcome ⊨ problem.GOAL then return plan
        else
            for each sequence in REFINEMENTS(hla, outcome, hierarchy) do
                frontier ← INSERT(prefix + sequence + suffix, frontier)

方案 2：带天使语义的分层搜索（Angelic Search）

function ANGELIC-SEARCH(problem, hierarchy, initialPlan) returns 方案或 failure
    frontier ← 队列，初始含 initialPlan
    loop do
        if EMPTY?(frontier) then return failure
        plan ← POP(frontier)

        // 用乐观可达集合剪枝
        if REACH⁺(problem.INITIAL, plan) ∩ problem.GOAL = {} then
            continue                     // 剪枝：绝不可能成功

        // 用悲观可达集合提前接受
        if REACH⁻(problem.INITIAL, plan) ∩ problem.GOAL ≠ {} then
            if plan 全是原语 then return plan
            guaranteed ← REACH⁻(...) ∩ problem.GOAL
            finalState ← 从 guaranteed 中任选一个
            return DECOMPOSE(hierarchy, problem.INITIAL, plan, finalState)

        hla ← plan 中第一个 HLA
        prefix, suffix ← ...
        for each sequence in REFINEMENTS(hla, outcome, hierarchy) do
            frontier ← INSERT(prefix + sequence + suffix, frontier)

效率分析：

设一个任务分解为 $b$ 个子任务，深度 $d$，则原语动作数 $\approx b^d$。

• 平坦搜索（flat search）：搜索空间 $O(k^{b^d})$（$k$ 为分支因子）。
• HTN 搜索：若每层只需在少数方法间选择，搜索空间 $O(k^d)$ 量级。

⇒ 指数级改善，但代价是需要人工提供分解知识。

适用场景：

• ✓ 领域知识丰富、任务有天然层次（军事任务规划、制造流程、web 服务组合、游戏 AI）。
• ✓ 需要生成人类可理解的方案（分解树天然可读）。
• ✗ 领域知识稀缺（HTN 退化为普通搜索，且写方法的成本高）。

局限：

• 方法库的编写成本高，且质量决定性能。
• 完备性依赖方法库：若方法库不完整（缺少某种分解），HTN 找不到本可行的方案。
• 与自动启发式方法相比，可迁移性差。

实用系统：SHOP/SHOP2（最广泛使用的 HTN 规划器）、O-Plan、SIPE-2、PANDA。

3.7 HTN 规划实战示例：旅行规划案例

本节通过一个具体的旅行规划案例，展示如何使用分层任务网络（HTN）进行规划。我们将使用Python风格的伪代码来定义领域知识（高层任务、分解方法、原语动作），并演示一个简单的HTN规划器如何工作。

3.7.1 领域定义：旅行规划HTN

首先定义旅行规划领域的原语动作（Primitive Actions），这些是可直接执行的基本操作：

# 原语动作（可直接执行）
class PrimitiveAction:
    def __init__(self, name, preconditions, effects):
        self.name = name
        self.preconditions = preconditions  # 前提条件列表
        self.effects = effects              # 效果列表

# 具体原语动作定义
travel_actions = {
    # 交通方式
    "drive_car": PrimitiveAction(
        "drive_car",
        preconditions=["has_car", "at_location(?from)", "road_connected(?from, ?to)"],
        effects=["at_location(?to)", "not at_location(?from)"]
    ),
    "take_train": PrimitiveAction(
        "take_train",
        preconditions=["has_train_ticket", "at_station(?from)", "train_route(?from, ?to)"],
        effects=["at_location(?to)", "not at_location(?from)"]
    ),
    "take_flight": PrimitiveAction(
        "take_flight",
        preconditions=["has_flight_ticket", "at_airport(?from)", "flight_route(?from, ?to)"],
        effects=["at_location(?to)", "not at_location(?from)"]
    ),
    
    # 准备动作
    "book_hotel": PrimitiveAction(
        "book_hotel",
        preconditions=["has_money", "hotel_available(?city)"],
        effects=["hotel_booked(?city)"]
    ),
    "buy_train_ticket": PrimitiveAction(
        "buy_train_ticket",
        preconditions=["has_money", "train_service_available(?from, ?to)"],
        effects=["has_train_ticket"]
    ),
    "buy_flight_ticket": PrimitiveAction(
        "buy_flight_ticket",
        preconditions=["has_money", "flight_available(?from, ?to)"],
        effects=["has_flight_ticket"]
    ),
    
    # 其他动作
    "pack_bags": PrimitiveAction(
        "pack_bags",
        preconditions=["has_luggage"],
        effects=["bags_packed"]
    ),
    "check_weather": PrimitiveAction(
        "check_weather",
        preconditions=[],
        effects=["weather_checked"]
    )
}

接下来定义高层任务（High-Level Tasks, HLAs）和它们的分解方法（Methods）。每个方法将一个高层任务分解为更简单的子任务序列：

# HTN方法库：将高层任务分解为子任务序列
htn_methods = {
    # 方法1：旅行任务分解
    "travel(?from, ?to)": [
        # 方法1.1：短途自驾
        {
            "name": "drive_method",
            "preconditions": ["distance_short(?from, ?to)", "has_car"],
            "decomposition": [
                "prepare_for_trip",
                "drive_car(?from, ?to)"
            ]
        },
        # 方法1.2：中程火车
        {
            "name": "train_method",
            "preconditions": ["distance_medium(?from, ?to)", "train_service_available(?from, ?to)"],
            "decomposition": [
                "prepare_for_trip",
                "buy_train_ticket(?from, ?to)",
                "take_train(?from, ?to)"
            ]
        },
        # 方法1.3：长途飞行
        {
            "name": "flight_method",
            "preconditions": ["distance_long(?from, ?to)"],
            "decomposition": [
                "prepare_for_trip",
                "buy_flight_ticket(?from, ?to)",
                "take_flight(?from, ?to)"
            ]
        }
    ],
    
    # 方法2：旅行准备任务分解
    "prepare_for_trip": [
        {
            "name": "basic_preparation",
            "preconditions": [],
            "decomposition": [
                "check_weather",
                "pack_bags"
            ]
        },
        {
            "name": "preparation_with_accommodation",
            "preconditions": ["stay_overnight"],
            "decomposition": [
                "check_weather",
                "pack_bags",
                "book_hotel(?destination)"
            ]
        }
    ],
    
    # 方法3：多城市旅行（复合任务）
    "multi_city_tour(?cities)": [
        {
            "name": "sequential_tour",
            "preconditions": ["list_length(?cities) > 1"],
            "decomposition": [
                "travel(?cities[0], ?cities[1])",
                "travel(?cities[1], ?cities[2])",
                # ... 可继续添加更多城市
            ]
        }
    ]
}

3.7.2 初始状态与目标

定义旅行规划问题的初始状态和目标：

# 初始状态（事实集合）
initial_state = {
    "at_location(home)",
    "has_car",
    "has_money",
    "has_luggage",
    "road_connected(home, city_a)",
    "train_service_available(home, city_b)",
    "flight_available(home, city_c)",
    "distance_short(home, city_a)",      # 短途：适合自驾
    "distance_medium(home, city_b)",     # 中程：适合火车
    "distance_long(home, city_c)",       # 长途：适合飞机
    "hotel_available(city_c)",
    "stay_overnight"                     # 需要在city_c过夜
}

# 目标：到达city_c并入住酒店
goal = {
    "at_location(city_c)",
    "hotel_booked(city_c)"
}

3.7.3 HTN规划算法实现

下面是一个简化的HTN规划器，采用深度优先搜索进行任务分解：

def htn_planner(current_task, state, plan, hierarchy):
    """
    简化的HTN规划器（深度优先搜索）
    
    参数：
        current_task: 当前要分解的任务（HLA或原语动作）
        state: 当前状态（事实集合）
        plan: 当前已生成的原语动作序列
        hierarchy: HTN方法库
    
    返回：
        (success, updated_plan, updated_state)
    """
    
    # 基础情况：当前任务是原语动作
    if current_task in travel_actions:
        action = travel_actions[current_task]
        
        # 检查前提条件是否满足
        if all(precond in state for precond in action.preconditions):
            # 执行动作：更新状态
            new_state = state.copy()
            for effect in action.effects:
                if effect.startswith("not "):
                    # 删除效果
                    fact = effect[4:]  # 移除"not "
                    new_state.discard(fact)
                else:
                    # 添加效果
                    new_state.add(effect)
            
            plan.append(current_task)  # 添加到方案
            return True, plan, new_state
        else:
            return False, plan, state  # 前提不满足
    
    # 递归情况：当前任务是高层任务（HLA）
    elif current_task in hierarchy:
        methods = hierarchy[current_task]
        
        # 尝试每个可用的分解方法
        for method in methods:
            # 检查方法的前提条件
            if all(precond in state for precond in method["preconditions"]):
                
                # 递归分解每个子任务
                temp_plan = plan.copy()
                temp_state = state.copy()
                success = True
                
                for subtask in method["decomposition"]:
                    # 替换参数（简化处理）
                    # 实际实现需要处理变量绑定?from, ?to等
                    subtask_instance = subtask  # 这里应进行参数实例化
                    
                    success, temp_plan, temp_state = htn_planner(
                        subtask_instance, temp_state, temp_plan, hierarchy
                    )
                    
                    if not success:
                        break  # 当前方法失败，尝试下一个方法
                
                if success:
                    return True, temp_plan, temp_state
        
        # 所有方法都失败
        return False, plan, state
    
    else:
        # 未知任务
        return False, plan, state

# 运行规划器
initial_plan = []
success, final_plan, final_state = htn_planner(
    "travel(home, city_c)",  # 顶层任务：从home到city_c
    set(initial_state),
    initial_plan,
    htn_methods
)

if success:
    print("HTN规划成功！")
    print("生成的原语动作序列：")
    for i, action in enumerate(final_plan, 1):
        print(f"{i}. {action}")
    print(f"\n最终状态：{final_state}")
else:
    print("HTN规划失败：无法找到可行方案")

3.7.4 规划过程与结果分析

运行上述规划器，可能的输出如下：

HTN规划成功！
生成的原语动作序列：
1. check_weather
2. pack_bags
3. book_hotel(city_c)
4. buy_flight_ticket(home, city_c)
5. take_flight(home, city_c)

最终状态：{
    'at_location(city_c)', 'hotel_booked(city_c)', 'weather_checked', 
    'bags_packed', 'has_flight_ticket', ...（其他状态）
}

规划过程解释：

1. 顶层任务分解：travel(home, city_c) 有三个可用方法。根据初始状态中的 distance_long(home, city_c)，规划器选择了 flight_method（长途飞行方法）。

2. 递归分解：

   • flight_method 分解为：prepare_for_trip → buy_flight_ticket(home, city_c) → take_flight(home, city_c)
   • prepare_for_trip 进一步分解。由于初始状态包含 stay_overnight，规划器选择了 preparation_with_accommodation 方法，生成：check_weather → pack_bags → book_hotel(city_c)

3. 原语动作执行：规划器按顺序检查每个原语动作的前提条件，执行满足条件的动作，并更新状态。

4. 目标达成：最终状态包含 at_location(city_c) 和 hotel_booked(city_c)，满足目标。

3.7.5 关键HTN概念在本例中的体现

1. 高层任务与分解方法：

   • travel(?from, ?to) 是高层任务，有三个不同的实现方法（自驾、火车、飞机）。
   • 方法选择基于前提条件（距离、可用服务等），体现了HTN的领域知识引导搜索。

2. 天使语义与可达集合：

   • 每个方法都有前提条件，规划器只考虑当前状态下可用的方法。
   • 方法的 decomposition 字段定义了乐观可达集合——如果这个方法被选择，这些子任务必须全部完成。

3. 变量与参数绑定：

   • 任务中的 ?from、?to、?city 等变量在实际规划时需要绑定到具体对象（如 home、city_c）。
   • 完整的HTN规划器需要维护变量绑定约束（本例中已简化）。

4. 与经典规划对比：

   • 经典规划器（如FF、FastDownward）需要搜索所有可能的动作序列。
   • HTN规划器利用领域知识（方法库）大幅剪枝搜索空间：从 travel(home, city_c) 直接聚焦到飞行方案，而不是尝试所有交通方式的排列组合。

3.7.6 扩展：PDDL风格的HTN表示

上述Python伪代码可等价转换为PDDL风格的HTN表示。PDDL 3.0+ 支持任务网络（Task Network）语法：

;; 领域文件：travel-htn-domain.pddl
(define (domain travel-htn)
  (:requirements :typing :htn)
  
  (:types location city - object)
  
  (:predicates
    (at ?loc - location)
    (has_car) (has_money) (has_luggage)
    (distance_short ?from ?to - location)
    (distance_medium ?from ?to - location)
    (distance_long ?from ?to - location)
    (road_connected ?from ?to - location)
    (train_service_available ?from ?to - location)
    (flight_available ?from ?to - location)
    (hotel_available ?city - city)
    (hotel_booked ?city - city)
    (has_train_ticket) (has_flight_ticket)
    (bags_packed) (weather_checked)
    (stay_overnight)
  )
  
  ;; 原语动作
  (:action take_flight
    :parameters (?from ?to - location)
    :precondition (and (at ?from) (has_flight_ticket)
                       (flight_available ?from ?to))
    :effect (and (at ?to) (not (at ?from)))
  )
  
  (:action book_hotel
    :parameters (?city - city)
    :precondition (and (has_money) (hotel_available ?city))
    :effect (hotel_booked ?city)
  )
  
  ;; 更多原语动作定义...
  
  ;; HTN方法
  (:method travel-by-flight
    :parameters (?from ?to - location)
    :task (travel ?from ?to)
    :precondition (distance_long ?from ?to)
    :subtasks (and
      (prepare_for_trip)
      (buy_flight_ticket ?from ?to)
      (take_flight ?from ?to)
    )
  )
  
  (:method prepare-with-hotel
    :task (prepare_for_trip)
    :precondition (stay_overnight)
    :subtasks (and
      (check_weather)
      (pack_bags)
      (book_hotel ?destination)  ; ?destination需从上层任务传递
    )
  )
  
  ;; 更多方法定义...
)

;; 问题文件：travel-htn-problem.pddl
(define (problem travel-to-city-c)
  (:domain travel-htn)
  (:objects
    home city_a city_b - location
    city_c - city
  )
  (:htn
    :tasks ((travel home city_c))
    :ordering ()
  )
  (:init
    (at home) (has_car) (has_money) (has_luggage)
    (distance_long home city_c)
    (flight_available home city_c)
    (hotel_available city_c)
    (stay_overnight)
  )
  (:goal (and (at city_c) (hotel_booked city_c)))
)

3.7.7 总结

本示例展示了HTN规划的核心要素：

1. 层次化表示：将复杂任务（旅行）分解为子任务（准备、购票、交通），子任务可进一步分解。
2. 方法选择：基于当前状态选择合适的方法（如根据距离选择交通方式）。
3. 搜索空间剪枝：HTN利用领域知识大幅减少搜索分支，相比经典规划的状态空间搜索更高效。
4. 可读性与可维护性：HTN方案天然对应人类的任务分解思维，易于理解和修改。

HTN规划特别适合领域知识丰富且任务有天然层次结构的场景，如工作流编排、机器人任务规划、游戏AI、业务流程自动化等。当方法库设计良好时，HTN能生成既高效又可解释的方案，是连接高层目标与底层执行的有效桥梁。

3.7 现实世界的复杂化

3.7.1 时间、调度与资源

经典规划假设动作瞬时、无资源约束。现实需要：

规划与调度的分离（plan first, schedule later）：

1. 规划阶段：生成偏序计划（动作及其顺序约束）。
2. 调度阶段：为每个动作分配开始时间，满足持续时间与资源约束。

关键路径法（Critical Path Method, CPM）：

对偏序计划，定义每个动作的：

• $ES$（earliest start）：最早开始时间
• $LS$（latest start）：最晚开始时间
• $Slack=LS-ES$：松弛

递推公式：

$$\begin{array}{rl}ES(Start)& =0\\ ES(b)& =\underset{a\prec b}{\max }[ES(a)+Duration(a)]\\ LS(Finish)& =ES(Finish)\\ LS(a)& =\underset{b\succ a}{\min }[LS(b)-Duration(a)]\end{array}$$

关键路径（critical path）= 所有 $Slack=0$ 的动作构成的路径。它决定了整个计划的最短总时长（makespan）。延迟关键路径上任何动作，整体完工时间就延迟。

复杂度：无资源约束时，CPM 是 $O(|A|+|O|)$ 线性时间。

⚠️ 加入资源约束后（如"只有 1 台机器"），调度问题变为 NP-难（job-shop scheduling）。常用启发式：

• 最小松弛优先（minimum slack）：优先调度松弛最小的动作。
• 分支定界、约束规划（CP 求解器在调度上非常强）。

资源建模：

• 可重用资源（reusable resource）：机器、工人——用完释放。
• 消耗性资源（consumable resource）：燃料、原料——用掉不还。
• 聚合（aggregation）：把 10 个相同的螺丝钉当作数量 10 而非 10 个独立对象，大幅减少状态空间。这是调度中的关键建模技巧。

3.7.2 非确定性与部分可观测

环境类型	方法	方案形式
确定 + 完全可观测	经典规划	动作序列
非确定 + 完全可观测	AND-OR 搜索	应急计划（contingent plan），含条件分支
确定 + 无传感器	信念状态搜索	一致性方案（conformant plan），单一序列在所有初始状态下都有效
非确定 + 部分可观测	信念状态 + AND-OR	应急计划 + 信念状态更新
未知环境	在线规划	执行监控 + 重规划

无传感规划（sensorless / conformant planning）：

• 在信念状态空间（belief state space）搜索：信念状态 = 可能的物理状态集合。
• 关键洞察：某些动作有强制效果（coercion），可以缩小信念状态。例：“把桌上所有杯子推到左边”——无论初始位置如何，之后都在左边。
• 信念状态可能指数大，实用做法是只保留文字合取表示（1-CNF 近似）。

应急规划（contingent planning）：

• 加入传感动作（sensing action / observation），其效果是获得信息而非改变世界。
• 用 AND-OR 搜索：OR 节点是智能体的动作选择，AND 节点是环境/观察的可能结果（都要处理）。
• 方案是一棵树：[Check(Tire); if Intact then [Inflate] else [Replace]]。

在线规划与重规划：

function ONLINE-PLANNING-AGENT(percept) returns action
    persistent: plan, 当前计划
                belief, 当前信念状态

    belief ← UPDATE-BELIEF(belief, percept)     // 执行监控
    if plan 为空 or plan 的前提在 belief 下不再成立 then
        plan ← REPLAN(belief, goal)             // 重规划
    action ← POP(plan)
    return action

三种执行监控：

监控类型	检查内容	代价	何时失败
动作监控（action monitoring）	下一个动作的前提是否成立	低	直到执行到该动作才发现问题
计划监控（plan monitoring）	剩余计划的所有前提是否仍成立	中	尽早发现失败
目标监控（goal monitoring）	目标本身是否还值得追求	高	支持机会主义（发现更好的目标）

重规划的智慧：

与其构造一个考虑所有可能情况的巨大应急计划（可能指数大），不如构造一个乐观计划 + 快速重规划。这就是 replanning agent 的思想，也是现代机器人系统的主流架构（对比第 12 章）。

循环计划（looping plan）：某些问题需要"重复尝试直到成功"，如"拧螺丝直到拧紧"。这要求方案含循环，AND-OR 搜索需要检测并允许回到已访问的信念状态。

---

4. 关键图示/表格说明

4.1 规划图结构（对应原书 Figure 11.9）

以 “Have Cake and Eat Cake Too” 问题为例：

      S₀              A₀                S₁              A₁               S₂
  ┌─────────┐    ┌──────────┐     ┌──────────┐    ┌───────────┐   ┌──────────┐
  │Have(C)  │────│ Eat(C)   │────→│¬Have(C)  │────│  Eat(C)   │──→│¬Have(C)  │
  │         │────│ [持续]    │────→│ Have(C)  │────│  Bake(C)  │──→│ Have(C)  │
  │¬Eaten(C)│────│ [持续]    │────→│¬Eaten(C) │────│ [持续×4]  │──→│¬Eaten(C) │
  │         │    │          │     │ Eaten(C) │    │           │──→│ Eaten(C) │
  └─────────┘    └──────────┘     └──────────┘    └───────────┘   └──────────┘
                                     ╎mutex╎                          ╎无mutex╎
                              Have(C) ⟷ ¬Have(C)              Have(C) 与 Eaten(C)
                              Have(C) ⟷ Eaten(C)              在 S₂ 不再互斥 ✓

读图要点：

1. 持续动作（no-op） 是把文字从一层传到下一层的"虚拟动作"，用虚线或方框表示。没有它们，规划图无法表达"什么都不做"。
2. Mutex 是单调递减的：$Have(C)$ 与 $Eaten(C)$ 在 $S_1$ 互斥（不一致支持），但在 $S_2$ 不再互斥（因为 $Bake$ 与 $Eat$ 的持续动作提供了非互斥的支持对）。
3. 目标 $Have(C)\wedge Eaten(C)$ 在 $S_2$ 首次非互斥出现 ⇒ 开始尝试解抽取 ⇒ 找到方案 [Eat(Cake), Bake(Cake)]。
4. 规划图的层数下界性质：目标首次非互斥出现的层数是最优并行方案长度的下界（因为规划图是松弛的）。

4.2 偏序计划示例：穿鞋（对应原书 Figure 11.6）

                    ┌──────────┐
                    │  Start   │
                    └────┬─────┘
              ┌──────────┴──────────┐
              ↓                     ↓
      ┌───────────────┐    ┌────────────────┐
      │ LeftSock      │    │  RightSock     │
      └───────┬───────┘    └────────┬───────┘
              │ LeftSockOn          │ RightSockOn
              ↓                     ↓
      ┌───────────────┐    ┌────────────────┐
      │ LeftShoe      │    │  RightShoe     │
      └───────┬───────┘    └────────┬───────┘
              │ LeftShoeOn          │ RightShoeOn
              └──────────┬──────────┘
                         ↓
                  ┌──────────────┐
                  │   Finish     │
                  └──────────────┘

因果链接 L = { Start→LeftSock, LeftSock--LeftSockOn-->LeftShoe,
               LeftShoe--LeftShoeOn-->Finish, ...（右侧对称）}
顺序约束 O = { LeftSock ≺ LeftShoe, RightSock ≺ RightShoe, ... }

读图要点：

• 只有 2 条必要的顺序约束（袜子在鞋之前），左右两支完全独立。
• 这个偏序计划有 6 个线性化（$\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 种交错方式），全都有效。
• 若用全序前向搜索，需要探索这 6 种排列中的多个才能找到解——这就是 POP 的价值。
• 执行时的灵活性：若右手先空出来，可以先穿右袜——偏序计划支持这种运行时决策。

4.3 Sussman 异常图解

初始状态                目标状态
   ┌─┐
   │C│                    ┌─┐
   ├─┤  ┌─┐               │A│
   │A│  │B│               ├─┤
   └─┘  └─┘               │B│
 ━━━━━━━━━━              ├─┤
                          │C│
                        ━━━━━━━━
On(C,A), OnTable(A),     On(A,B) ∧ On(B,C)
OnTable(B), Clear(C), Clear(B)

错误做法（先满足 On(A,B)）：
  Move(C, Table)  → Move(A, B)
  现在 A 在 B 上，但要把 B 放到 C 上，必须先把 A 拿开 ⇒ 撤销已完成的子目标 ✗

正确方案：
  MoveToTable(C)     // C 从 A 上拿下
  Move(B, C)         // B 放到 C 上
  Move(A, B)         // A 放到 B 上      ✓

读图要点：

• 两个子目标相互干扰（deleted-condition interaction）。
• 早期"线性规划器"（按顺序独立求解子目标）在此失败。
• POP 通过威胁检测正确处理；现代启发式搜索（$h^{FF}$）也能处理，因为它在完整状态空间中搜索。
• ⚠️ 这个例子说明为什么"忽略删除效果"的松弛会低估——松弛后 Sussman 异常消失了（不需要撤销），所以 $h^{FF}$ 会低估真实代价。

4.4 启发式松弛的层次关系

         原问题（PSPACE-完全）
              │
     ┌────────┼────────┬──────────────┐
     ↓        ↓        ↓              ↓
 忽略前提   忽略删除   状态抽象      分解子目标
     │        │        │              │
     ↓        ↓        ↓              ↓
 集合覆盖  delete-free  PDB        landmark
 (NP-难)   (NP-难)   (预处理)      (LM-cut)
     │        │        │              │
     └────────┴────────┴──────────────┘
              ↓
        多项式近似算法
              ↓
      h_add, h_max, h_FF, h_PDB, h_LMcut

读图要点：所有规划启发式都遵循同一个配方：

松弛（去掉某些约束）→ 松弛问题仍难 → 再近似求解 → 得到启发式值

可采纳性取决于：松弛 ✓ 保证下界，但近似求解若不是下界（如 $h^{FF}$ 的贪心抽取、$h^{add}$ 的求和）则失去可采纳性。

4.5 规划方法对比总表

方法	搜索空间	完备	最优	需要启发式	需要领域知识	现代地位
前向状态空间搜索	状态	✓	取决于算法	必需	否	主流（FF, LAMA, FD）
后向状态空间搜索	状态描述	✓	取决于算法	必需	否	用于启发式计算
偏序规划（POP）	部分计划	✓	✓（可扩展）	困难	否	时序/多智能体规划
GraphPlan	规划图 + CSP	✓	并行最优	内建	否	启发式来源（$h^{FF}$ 源头）
SATPlan	SAT 赋值	有界完备	步数最优	SAT 求解器内建	否	并行度高的领域
符号搜索（BDD）	状态集合	✓	✓	可选	否	最优规划竞争力强
HTN	分解树	依赖方法库	依赖方法库	可选	必需	工业应用（SHOP2）

4.6 关键路径示例

动作:    A(3)      C(2)
       ┌────→ ●  ────→ ●
Start ─┤              ↑ ─→ Finish
       └────→ ● ──────┘
        B(5)      D(1)

ES(A)=0, ES(B)=0
ES(C)=3 (A结束), ES(D)=5 (B结束)
ES(Finish) = max(3+2, 5+1) = 6      ← makespan

LS(Finish)=6
LS(C)=6-2=4, LS(D)=6-1=5
LS(A)=4-3=1, LS(B)=5-5=0

Slack(A)=1-0=1     ← 有 1 单位松弛
Slack(B)=0-0=0     ← 关键路径！
Slack(C)=4-3=1
Slack(D)=5-5=0     ← 关键路径！

关键路径: Start → B → D → Finish  (总时长 6)

读图要点：延迟 A 或 C 一个单位不影响总时长；延迟 B 或 D 会直接延长 makespan。资源应优先保障关键路径。

---

5. 与其他章节的关联

5.1 承前

章节	关联
第 3 章 搜索	前向规划直接是 A*/GBFS 的应用；松弛问题产生可采纳启发式的原理在此大规模自动化；第 3 章需人工设计启发式，本章自动生成
第 4 章 局部搜索	Enforced Hill Climbing（FF 使用）是局部搜索在规划中的应用；在线规划呼应第 4 章的在线搜索（LRTA*）
第 6 章 CSP	GraphPlan 的解抽取是 CSP；动作实例化是模式匹配 CSP；调度问题用 CP 求解器；nogood 学习同源
第 7 章 逻辑	SATPlan 直接沿用第 7 章 §3.8；后继状态公理在 SAT 编码中重现；命题化的规模问题在此再次出现
第 8–9 章 FOL	PDDL 是 FOL 的受限片段（封闭世界、无嵌套量词、无函数符号）；动作模式的实例化用合一；这是"牺牲表达力换效率"的经典案例
第 10 章 KR	PDDL 的 :types 是轻量本体；框架问题在 STRIPS 中被 ADD/DEL 列表优雅解决；限定问题在规划中表现为"前提不完整"

5.2 启后

章节	关联
第 12 章 机器人 KR	情境演算/事件演算是规划的逻辑基础（更表达力强但更难求解）；本章的执行监控、重规划直接服务于机器人
第 17 章 MDP	非确定性规划 → 概率规划；MDP 是"非确定 + 概率 + 效用"的规划；本章的应急计划 ≈ MDP 的策略（policy）
第 17 章 POMDP	信念状态规划的概率版本；本章的 conformant/contingent planning 是 POMDP 的确定性特例
第 22 章 强化学习	RL 是"模型未知"的规划；Dyna 架构 = 学习模型 + 规划；MCTS 结合了搜索与采样
第 26 章 机器人学	运动规划（motion planning）是连续空间的规划；任务与运动规划（TAMP）结合本章的符号规划与连续几何规划

5.3 一条核心主线：如何利用问题结构

问题：状态空间指数爆炸（PSPACE-完全）
   │
   ├─→ 利用「松弛后的可达性」  →  h_FF, h_add, h_max
   │
   ├─→ 利用「子问题的独立性」  →  偏序规划、additive PDB
   │
   ├─→ 利用「必经的中间点」    →  landmark, LM-cut
   │
   ├─→ 利用「层次可达性+互斥」 →  GraphPlan
   │
   ├─→ 利用「SAT 求解器的工程优化」 → SATPlan
   │
   └─→ 利用「人类的分解知识」  →  HTN

每种方法都在回答同一个问题：这个问题的什么结构可以被利用？

---

6. 延伸思考

6.1 LLM 作为规划器：符号规划的"重新发现"

2023 年以来，"LLM 做规划"成为热点：ReAct、Tree of Thoughts、Plan-and-Solve、LLM+P、Voyager、AutoGPT 系列。用本章的框架审视这些工作，会发现很多似曾相识：

LLM Agent 技术	本章对应概念
Chain-of-Thought	线性方案（全序）
Tree of Thoughts	搜索树 + 自评估作启发式
ReAct（推理+行动交替）	在线规划 + 执行监控 + 重规划（§3.7.2）
任务分解（task decomposition）	HTN 的方法（§3.6）
Reflexion / self-critique	失败后的重规划 + nogood 记录
LLM+P（LLM 生成 PDDL）	显式承认符号规划器的优势

LLM 规划的实证发现（值得深思）：

多项研究（Valmeekam et al., “PlanBench”）表明：

• GPT-4 级模型在 Blocks World 这样的经典基准上，零样本成功率不到 30%——而一个 1998 年的规划器能秒解。
• 但 LLM 在开放域、常识密集的任务上（“策划一次生日派对”）远超任何符号规划器——因为后者需要完整的 PDDL 领域模型，而这个模型在开放域中根本无法编写。

这构成了一个清晰的互补关系：

能力	符号规划器	LLM
长序列的正确性	✓✓ 保证（可靠、可验证）	✗ 容易在 8+ 步后出错
最优性保证	✓（A* + 可采纳启发式）	✗ 无
死锁检测	✓（$h^{FF}=\infty$、规划图不动点）	✗ 会自信地给出不可行方案
领域模型获取	✗ 需人工编写 PDDL	✓✓ 从常识中涌现
处理未建模情况	✗ 完全失效	✓ 优雅降级
生成 HTN 方法库	✗ 需专家	✓ 可自动生成候选

开放性问题 1：

LLM+P 架构（LLM 把自然语言任务翻译成 PDDL，交给 Fast Downward 求解，再把方案翻译回自然语言）已被证明在经典基准上远优于纯 LLM。但它要求领域模型（domain file）事先存在。能否让 LLM 同时生成 domain 与 problem 文件，并通过与环境交互迭代修正领域模型？

这实质上是把领域模型获取——符号规划几十年来最大的瓶颈——交给 LLM。技术挑战：

1. LLM 生成的 PDDL 常有语法/语义错误。需要验证-修复循环（用规划器的报错作为反馈）。
2. 领域模型的正确性无法自动验证（除非在环境中试执行）。这是 §3.7.2 执行监控的用武之地：用执行失败来精化领域模型。
3. 这条路线与 model learning / action model learning（如 ARMS、FAMA 算法）殊途同归——但 LLM 提供了强大的先验。

开放性问题 2（关于 HTN）：

HTN 的最大障碍是方法库的人工编写成本。而 LLM 恰恰极擅长任务分解（“去机场” → “叫车/开车/地铁”）。能否用 LLM 自动生成 HTN 方法库，再用符号 HTN 规划器保证组合的正确性？

这里有一个微妙但重要的技术点：§3.6.2 的天使语义与可达集合近似给出了 HTN 剪枝的形式化基础。若 LLM 生成的方法带有"这个方法能达成什么"的（近似）描述，就可以套用 $REAC{H}^{+}/REAC{H}^{-}$ 的剪枝规则。LLM 提供分解知识，符号引擎提供组合保证——这与第 9 章 §6.2 讨论的 AlphaGeometry 范式完全同构。

6.2 启发式的本质：学习 vs 推导

本章 §3.2 的所有启发式都是推导出来的（从松弛问题）。而深度学习提供了另一条路：学习启发式。

已有工作：

• 神经网络启发式：用 GNN 学习 $h(s)$，在 PDDL 图结构上做消息传递。
• 学习 preferred operators：预测哪些动作值得优先扩展。
• AlphaZero 式规划：策略网络 + 价值网络 + MCTS（第 5、22 章）。

关键权衡：

	推导的启发式（$h^{FF}$, LM-cut）	学习的启发式
可采纳性	可保证（$h^{max}$, PDB, LM-cut）	通常无保证
跨领域泛化	完美（对任意 PDDL 领域都工作）	需要领域内训练数据
计算代价	每个状态都要重算（可能很贵）	一次前向传播（快）
信息量上限	受松弛质量限制	理论上可达完美（$h^{\ast }$）
冷启动	立即可用	需要训练

开放性问题：

能否设计一种混合启发式：用可采纳的推导启发式（LM-cut）保证 A* 的最优性，同时用学习的启发式指导节点扩展顺序（不影响最优性，只影响效率）？

这在理论上是可行的——A* 的最优性只依赖 $h$ 的可采纳性，而 tie-breaking 与扩展顺序可以任意。已有工作（“learning to rank” for planning）沿此方向，但尚未成为主流。

更激进的思路：学习松弛本身。当前的松弛（忽略删除效果）是人工设计的、领域无关的。能否让模型学习"对这个领域，应该忽略哪些约束才能得到既容易求解又信息量大的松弛"？这将是"元级"的启发式学习。

6.3 多模态与具身规划：符号接地的老问题

本章的规划器工作在符号层：$At(C_1,JFK)$ 是一个原子，其真值由外部提供。真实机器人必须自己判断这个原子是否为真——从摄像头图像、力反馈、激光雷达中。

这是 §5.2 提到的 TAMP（Task and Motion Planning）的核心难题：

符号层（本章）:  Pick(cup) → Move(table) → Place(cup)
                     ↕  接地（grounding）
几何层:         逆运动学求解、碰撞检测、抓取姿态采样
                     ↕  感知
像素层:         RGB-D 图像 → 物体分割 → 6D 姿态估计

难点在于双向依赖：

• 符号规划需要知道"这个抓取动作在几何上可行吗"——但这要求求解运动规划（昂贵）。
• 运动规划需要知道"应该抓哪里"——但这由符号规划决定。

⇒ 天真的分层（先符号后几何）会导致大量回溯：符号方案在几何层不可行，退回重新规划。

当前方案：

• 交错式 TAMP：符号规划器在关键点调用几何求解器验证。
• 学习几何可行性预测器：用神经网络快速判断"这个符号动作在几何上大概率可行吗"，作为符号层的启发式/剪枝器。

开放性问题：

多模态大模型能否直接充当符号-几何的桥梁——即从图像直接判断 PDDL 谓词的真值（visual grounding of predicates），并预测动作的可行性？

这将解决符号规划最大的实用障碍：状态估计。当前的机器人系统需要精心设计的感知管线来维护符号状态；若 VLM 能可靠地回答"$Clear(BlockA)$ 现在为真吗？"，符号规划器就能直接部署在真实场景。

但要警惕误差传播：符号规划器假设其输入状态是确定正确的。若 VLM 的谓词判断有 5% 错误率，一个 20 步的方案就有 64% 概率至少一步基于错误状态。这必须用第 17 章的 POMDP 框架或本章 §3.7.2 的执行监控 + 重规划来处理。确定性规划 + 不确定感知 = 危险组合。

6.4 AI 对齐视角：规划能力与可控性

规划能力是 AI Agent 的核心，也是风险的核心来源。一个能做长程规划的系统，本质上是一个能"为达成目标而组合动作"的系统——这正是工具性趋同（instrumental convergence）担忧的技术基础。

本章提供了几个直接相关的技术抓手：

1. 可验证性：符号方案是可审计的

一个 PDDL 方案是一个明确的动作序列，每一步的前提与效果都可检查。这与 LLM 的"我打算做 X"形成鲜明对比：

• 符号方案：可以在执行前用形式化方法验证"这个方案不会进入禁止状态"。
• LLM 意图：只能事后观察。

这提示了一个具体的 Agent 安全架构：

强制 Agent 把行动计划表达为结构化的、可验证的形式（PDDL 或类似），在执行前用模型检验器验证安全性质（如"永不删除用户文件"、“永不发送外部请求”），验证通过才允许执行。

这与第 7 章 §6.2 讨论的"逻辑用在接口层"完全一致，且本章给出了更具体的载体。

2. 目标监控：什么时候应该停下来重新思考？

§3.7.2 的三种监控中，目标监控（goal monitoring）最有对齐意义：

智能体不仅检查"我的计划还能执行吗"，还检查"这个目标还值得追求吗"。

这在技术上是"机会主义"（发现更好的目标就切换），但在对齐语境下，它对应一个关键能力：可中断性（interruptibility）与目标可修正性（corrigibility）。一个只做动作监控的 Agent 会顽固地执行原计划；一个做目标监控的 Agent 天然具备"停下来问问是否还应该做这件事"的结构。

开放性问题：

能否把"人类可能想要修改我的目标"显式建模为规划问题的一部分？即，让 Agent 的规划过程内建对目标不确定性的处理（这正是 CIRL / assistance games 的思路，第 17–18 章）。

3. HTN 与人类监督的粒度

HTN 的分层结构提供了一个自然的人类监督接口：

• 人类在高层（HLA 层）审批：批准"预订机票"这个任务。
• Agent 在低层自主执行原语动作。
• 关键决策点（如涉及金钱、不可逆操作）强制上升到人类审批。

这比"审批每一个 API 调用"（太细，人类无法处理）和"授权整个任务"（太粗，风险不可控）都更合理。HTN 的抽象层次天然对应人类监督的合适粒度。

4. 一个警示：$REAC{H}^{+}$ 剪枝的双刃性

§3.6.2 的天使语义假设"智能体可以选择哪个实现"。这个假设在能力评估中是乐观的——它意味着"只要存在一条成功路径，Agent 就能找到"。

在安全评估中，我们应该用恶魔语义的对偶：评估一个 Agent 的危险能力时，应假设它能找到最有效的实现路径（天使语义），而不是平均路径。这意味着：

能力评估应该用 $REAC{H}^{+}$（乐观上界），安全保证应该用 $REAC{H}^{-}$（悲观下界）。

用错了方向，就会系统性地低估风险或高估安全性。这个看似技术性的语义区分，实际上是能力评估方法论的重要原则。

收束：自动规划是 AI 中"从思考到行动"的桥梁。本章的技术——启发式、抽象、分解、监控——在 LLM Agent 时代不但没有过时，反而提供了评估与约束这些 Agent 的概念框架。当我们问"这个 Agent 能规划多远"、“它的方案可验证吗”、"它会在什么时候重新考虑目标"时，我们问的正是本章的问题。# 第11章 自动规划

对应 Artificial Intelligence: A Modern Approach, 4th Edition 第 11 章 Automated Planning

---

1. 章节概述

前面章节给了我们两套解决"如何达成目标"的工具：

• 第 3–4 章的搜索：状态是黑盒（原子表示），需要人工提供后继函数与启发式。搜索算法看不见状态内部，因此无法自动导出启发式。
• 第 7–10 章的逻辑：能精确描述世界，但通用定理证明的搜索空间过大，直接用归结做规划效率极低（第 7 章 SATPlan 已初见端倪）。

自动规划（automated planning）的核心思想是取两者之长：

用因子化的逻辑表示描述状态与动作（使规划器能"看见"状态内部结构），同时用专门的搜索算法（而非通用定理证明）求解。

这个"表示透明"带来的最大红利是：规划器可以自动从问题描述中导出启发式函数。这是规划相对于纯搜索的决定性优势——第 3 章需要人类为八数码设计曼哈顿距离，而规划器能对任意 PDDL 领域自动生成可采纳启发式。

本章主线：

1. 经典规划的定义：状态、动作、目标的因子化表示。
2. PDDL（Planning Domain Definition Language）：标准建模语言。
3. 规划即状态空间搜索：前向（progression）与后向（regression）。
4. 规划启发式：忽略前提、忽略删除效果、状态抽象、集合覆盖。
5. 偏序规划（partial-order planning）：最小承诺原则。
6. 规划图与 GraphPlan：互斥关系、层次扩展、解抽取。
7. 其他经典方法：SATPlan、答案集编程、一阶逻辑推理规划。
8. 分层任务网络 HTN（hierarchical task network）：用领域知识分解任务。
9. 非确定性、部分可观测、在线规划：应急规划、无传感规划、执行监控与重规划。
10. 调度（scheduling）：时间、资源、关键路径。

核心直觉：

经典规划的全部技术进展，都可以看作对"如何在指数级状态空间中利用问题结构"这一问题的不同回答：启发式利用松弛结构，偏序规划利用独立性，GraphPlan 利用可达性与互斥性，HTN 利用人类给的分解知识。

---

2. 关键概念与定义

2.1 经典规划问题的形式化

经典规划（classical planning）的标准假设（合称 STRIPS 假设）：

假设	含义
完全可观测	智能体确切知道当前状态
确定性	动作效果唯一确定
静态	世界只因智能体动作而变化
离散	状态、时间、动作、对象都是离散的
单智能体	无其他行动者
有限	对象数量有限

规划问题是一个四元组 $\Pi =⟨\mathcal{F},\mathcal{A},s_0,g⟩$：

• $\mathcal{F}$：流（fluents）/ 命题的有限集合。
• $\mathcal{A}$：动作集合。
• $s_0\subseteq \mathcal{F}$：初始状态。
• $g$：目标条件（文字的合取）。

状态表示：状态 $s$ 是一个基原子（ground atom）的合取，如：

$$At(Truc{k}_1,Melbourne)\wedge At(Truc{k}_2,Sydney)$$

采用封闭世界假设（closed-world assumption）：未提及的原子为假。因此状态可等价地表示为为真的原子集合。

⚠️ 状态中不允许变量、函数符号、否定、析取。这是为效率所做的严格限制（对比第 8 章完整 FOL 的表达力）。

2.2 动作模式（Action Schema）

一个 动作模式（action schema / operator）由三部分构成：

Action(Fly(p, from, to),
    PRECOND: At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to)
    EFFECT:  ¬At(p, from) ∧ At(p, to))

• 变量：$p,from,to$，隐含全称量化。
• 前提（precondition）：动作可执行的条件，文字的合取。
• 效果（effect）：动作执行后状态的变化，文字的合取。

实例化（grounding / instantiation）：用常量替换变量得到基动作（ground action）：

$$Fly(P_1,SFO,JFK)$$

动作的适用性：动作 $a$ 在状态 $s$ 中适用（applicable），当且仅当 $s\models PRECOND(a)$，即前提的所有正文字都在 $s$ 中，所有负文字都不在 $s$ 中。

结果状态（转移函数）：

$$RESULT(s,a)=(s\setminus DEL(a))\cup ADD(a)$$

其中：

• $ADD(a)$（添加列表 add list）：$EFFECT(a)$ 中的正文字集合。
• $DEL(a)$（删除列表 delete list）：$EFFECT(a)$ 中负文字对应的原子集合。

⚠️ 注意顺序：先删后加。若某原子同时在 ADD 和 DEL 中，最终它为真。

这个定义优雅地解决了框架问题：任何未在 $ADD$ 或 $DEL$ 中提及的流自动保持不变。这是 STRIPS 表示相对于第 7 章"后继状态公理"的巨大简化——不需要写任何框架公理。

2.3 PDDL（Planning Domain Definition Language）

PDDL 是规划领域的标准语言（1998 年为 IPC 国际规划竞赛设计），把问题分为两个文件。

领域文件（domain file）—— 描述动作与谓词：

(define (domain air-cargo)
  (:requirements :strips :typing)
  (:types cargo plane airport)
  (:predicates
     (at ?x - (either cargo plane) ?a - airport)
     (in ?c - cargo ?p - plane))

  (:action load
     :parameters (?c - cargo ?p - plane ?a - airport)
     :precondition (and (at ?c ?a) (at ?p ?a))
     :effect (and (not (at ?c ?a)) (in ?c ?p)))

  (:action unload
     :parameters (?c - cargo ?p - plane ?a - airport)
     :precondition (and (in ?c ?p) (at ?p ?a))
     :effect (and (at ?c ?a) (not (in ?c ?p))))

  (:action fly
     :parameters (?p - plane ?from - airport ?to - airport)
     :precondition (at ?p ?from)
     :effect (and (not (at ?p ?from)) (at ?p ?to))))

问题文件（problem file）—— 描述具体实例：

(define (problem cargo-1)
  (:domain air-cargo)
  (:objects C1 C2 - cargo
            P1 P2 - plane
            SFO JFK - airport)
  (:init (at C1 SFO) (at C2 JFK)
         (at P1 SFO) (at P2 JFK))
  (:goal (and (at C1 JFK) (at C2 SFO))))

PDDL 的演进（表达力扩展）：

版本/特性	增加的能力
STRIPS（基础）	命题前提与效果
ADL（Action Description Language）	否定前提、析取、量化效果、条件效果、等词、开放世界
PDDL 2.1	数值流（numeric fluents）、持续动作（durative actions）、metric 优化目标
PDDL 2.2	派生谓词（derived predicates）、定时初始文字
PDDL 3	轨迹约束（trajectory constraints）、软目标与偏好（preferences）
PDDL+	连续过程与外生事件（混合系统）

条件效果（conditional effect）示例：

:effect (and (at ?p ?to) (not (at ?p ?from))
             (forall (?c - cargo)
                (when (in ?c ?p)
                   (and (at ?c ?to) (not (at ?c ?from))))))

⚠️ 条件效果显著增加表达力（一个动作可根据状态产生不同效果），但也使后向搜索与启发式计算复杂化。

2.4 经典规划领域示例

书中的标准基准领域：

领域	描述	教学价值
Air Cargo	飞机运货，Load/Unload/Fly	展示多类型对象与状态耦合
Blocks World	积木堆叠，Move/MoveToTable	经典的子目标交互问题（Sussman 异常）
Spare Tire	换备胎，Remove/PutOn/LeaveOvernight	展示"有害动作"（LeaveOvernight 移除所有轮胎）
Shakey’s World	机器人推箱子开灯	早期规划系统的真实场景

Blocks World 定义：

(:action Move
   :parameters (?b ?x ?y)
   :precondition (and (On ?b ?x) (Clear ?b) (Clear ?y)
                      (Block ?b) (Block ?y) (≠ ?b ?x) (≠ ?b ?y) (≠ ?x ?y))
   :effect (and (On ?b ?y) (Clear ?x)
                (not (On ?b ?x)) (not (Clear ?y))))

(:action MoveToTable
   :parameters (?b ?x)
   :precondition (and (On ?b ?x) (Clear ?b) (Block ?b) (≠ ?b ?x))
   :effect (and (On ?b Table) (Clear ?x) (not (On ?b ?x))))

⚠️ 为什么需要两个动作？因为 $Table$ 不是 $Block$，永远 $Clear$，不能用统一的 $Move$ 处理（否则 $\neg Clear(Table)$ 会被错误地添加）。这类建模细节是 PDDL 实践中的常见陷阱。

Sussman 异常（Sussman Anomaly）：

初始：  C          目标：  A
       A  B               B
    ━━━━━━━━            C
                      ━━━━━━━━
目标 = On(A,B) ∧ On(B,C)

若先达成 $On(A,B)$，必须拆掉才能达成 $On(B,C)$；反之亦然。这证明了目标不可独立求解，是早期"线性规划器"（linear planner，指按顺序逐个满足子目标）的反例，推动了偏序规划的发展。

2.5 复杂度

问题	复杂度
PlanSAT（是否存在方案）	PSPACE-完全
Bounded PlanSAT（是否存在长度 ≤ k 的方案）	PSPACE-完全
无删除效果（delete-free）的规划	NP-完全
最优 delete-free 规划	NP-难
STRIPS 无负前提且效果为正	多项式（可达性分析）

为什么是 PSPACE 而非 NP：方案长度可能是状态数（指数级）的量级，因此无法在多项式时间内"猜测并验证"一个方案。但可以用多项式空间逐步搜索。

实践意义：最坏情形复杂度很高，但真实规划问题往往有大量结构（子目标近似独立、状态空间稀疏连通），使得好的启发式极为有效。IPC 竞赛中的现代规划器能处理数百万个基动作的问题。

---

3. 核心理论与算法

3.1 规划即状态空间搜索

3.1.1 前向状态空间搜索（Forward / Progression Search）

function FORWARD-SEARCH(problem) returns 方案或 failure
    // 就是第 3 章的图搜索，只是状态与后继由 PDDL 定义
    初始状态 ← s₀
    后继函数 ← λs. {(a, RESULT(s,a)) : a 在 s 中适用}
    目标测试 ← λs. s ⊨ g
    动作代价 ← 通常为 1（或 PDDL 指定的 metric）

    return A*-SEARCH(以上定义的搜索问题, h)

优势：

• 实现简单，直接复用 A*、GBFS、加权 A*、Enforced Hill Climbing。
• 状态是完全指定的，容易检查目标与去重。
• 现代规划器的主流（FF、FastDownward、LAMA 均基于前向搜索）。

劣势：

• 分支因子巨大：一个状态可能有数千个适用动作。
• 大量无关动作（如买牛奶任务中，"去纽约"也是适用的）。

这就是为什么启发式是规划的生命线：没有启发式的前向搜索毫无希望；有了好的启发式，同样的搜索能解决工业规模问题。

动作实例化的效率问题：
从动作模式生成基动作是一次合一/模式匹配（第 9 章 §3.2.3），本质是 CSP。现代规划器用规划器预处理（如 Fast Downward 的 translator）把 PDDL 转为有限域表示（SAS+），大幅压缩状态空间。

3.1.2 后向状态空间搜索（Backward / Regression Search）

从目标出发，反向搜索到初始状态。

关键概念：回归（regression）

给定目标描述 $g$ 和动作 $a$，$a$ 的前驱（predecessor）状态描述：

$$g^{\prime }=(g\setminus ADD(a))\cup PRECOND(a)$$

即：把 $a$ 能达成的部分从目标中去掉，把 $a$ 的前提加进去。

相关性检查（relevance）：
只考虑相关动作——即 $a$ 至少达成 $g$ 中的一个文字，且不删除 $g$ 中的任何文字：

$$ADD(a)\cap g\ne \varnothing \wedge DEL(a)\cap g=\varnothing$$

示例（Air Cargo）：

目标 $g=At(C_1,JFK)$。相关动作 $Unload(C_1,p,JFK)$，回归得：

$$g^{\prime }=In(C_1,p)\wedge At(p,JFK)$$

⚠️ 注意 $p$ 仍是变量——后向搜索处理的是部分实例化的状态描述，这带来了灵活性但也增加了复杂性。

优势：

• 分支因子小：只考虑相关动作，大幅剪枝。对目标少、动作多的问题特别有效。

劣势：

• 处理的是状态集合（部分描述）而非单一状态，难以设计精确的启发式。
• 部分实例化的变量处理复杂。
• 可能生成不可达的子目标（回归得到的描述可能对应无任何真实状态）。

现代实践：后向搜索在纯经典规划中已较少作为主搜索方向，但它的回归思想在以下地方仍然核心：

• 计算启发式（如 $h^m$ 系列）
• 偏序规划（§3.3）
• 反例引导的抽象精化

3.2 规划启发式（Planning Heuristics）

这是规划领域最重要的技术贡献。核心思路：通过松弛（relaxation）问题自动导出启发式。

回顾第 3 章：$h$ 若来自松弛问题的最优解，则一定是可采纳的（admissible），因为松弛问题的最优解不会比原问题差。

3.2.1 松弛 1：忽略前提（Ignore Preconditions）

去掉所有动作的前提，则每个动作总是可执行。

• 若同时忽略删除效果，问题退化为集合覆盖问题（set-cover）：选最少的动作，使其 ADD 列表的并集覆盖目标。
• 集合覆盖是 NP-难，但有贪心近似算法，比率为 $O(\log n)$。
• 更粗但极快的近似：$h=|g\setminus s|$（未满足的目标文字数）。

⚠️ 贪心近似不保证可采纳（可能高估）。若要可采纳性，需精确求解或用下界。

3.2.2 松弛 2：忽略删除效果（Ignore Delete Lists）—— 最重要的松弛

核心思想：去掉所有动作的 DEL 列表。

后果：状态单调增长（原子只增不减），因此永不需要撤销——没有子目标冲突，没有死锁。

性质：

• 松弛问题的解一定存在（若原问题可解）。
• 松弛问题的最优解仍是 NP-难，但可用贪心/近似快速计算。
• 松弛问题的可达性分析是多项式时间的（不断应用所有适用动作直到不动点）。

这催生了几个关键启发式：

$h^{add}$（加性启发式）：假设子目标完全独立

$$h^{add}(s)=\sum _{p\in g}\Delta (s,p)$$

其中 $\Delta (s,p)$ 是达成单个原子 $p$ 的估计代价，递归定义：

$$\Delta (s,p)=\{\begin{array}{ll}0& p\in s\\ \underset{a:p\in ADD(a)}{\min }[cost(a)+\sum _{q\in PRE(a)}\Delta (s,q)]& \text{否则}\end{array}$$

• 不可采纳（重复计算共享子目标的代价，可能高估）。
• 但信息量大，实践中引导性强。

$h^{max}$（最大启发式）：

$${\Delta }^{max}(s,p)=\underset{a:p\in ADD(a)}{\min }[cost(a)+\underset{q\in PRE(a)}{\max }{\Delta }^{max}(s,q)]$$

• 可采纳（取 max 而非 sum，是下界）。
• 但过于乐观，信息量弱。

$h^{FF}$（FF 启发式，Hoffmann & Nebel 2001）：

计算松弛问题的一个实际方案（relaxed plan），取其长度作为启发式。

function H-FF(s, g) returns 启发式值
    // 阶段 1：前向构建松弛规划图（无删除效果）
    P₀ ← s
    i ← 0
    while g ⊄ Pᵢ do
        Aᵢ ← {a : PRECOND(a) ⊆ Pᵢ}
        P_{i+1} ← Pᵢ ∪ ⋃_{a∈Aᵢ} ADD(a)
        if P_{i+1} = Pᵢ then return ∞      // 目标不可达（死锁检测！）
        i ← i + 1

    // 阶段 2：后向抽取松弛方案
    RelaxedPlan ← {}
    Goals ← g
    for layer = i down to 1 do
        for each p in Goals at layer do
            选择一个 a ∈ A_{layer-1} 使 p ∈ ADD(a)   // 贪心选择
            RelaxedPlan ← RelaxedPlan ∪ {a}
            Goals ← Goals ∪ PRECOND(a)
    return |RelaxedPlan|

$h^{FF}$ 的特点：

• 不可采纳（贪心抽取，非最优松弛方案），但实践中极其有效。
• 免费提供死锁检测：若松弛问题不可解，原问题必然不可解 ⇒ 返回 $\infty$，剪掉整个分支。
• 副产品：有帮助的动作（helpful actions）—— 松弛方案第一层用到的动作，优先扩展这些动作可大幅加速搜索（preferred operators）。

FF 规划器（Fast-Forward）用 $h^{FF}$ + Enforced Hill Climbing（EHC）+ helpful actions，在 IPC-2000 上大幅领先，开启了"启发式搜索规划"的时代。

3.2.3 松弛 3：状态抽象（State Abstraction）

抽象：把多个具体状态映射到一个抽象状态，从而缩小状态空间。

模式数据库（Pattern Database, PDB）：

1. 选择流的一个子集（模式 pattern），如只关心积木 A、B 的位置。
2. 忽略其余流，得到一个小得多的抽象状态空间。
3. 穷举抽象空间，用逆向 BFS 计算每个抽象状态到抽象目标的精确距离，存表。
4. 搜索时，把具体状态投影到抽象状态，查表得启发式值。

可采纳性：抽象是松弛（去掉了约束），所以 PDB 值是下界，可采纳。✓

多 PDB 组合：

• 若两个模式不相交（没有共享的动作影响），可以相加（additive PDB），得到更强的可采纳启发式。
• 否则只能取 $\max$。

其他抽象方法：

• Merge-and-Shrink：自动构造抽象，逐步合并变量并压缩状态，是 PDB 的泛化。
• 笛卡尔抽象（Cartesian abstraction）+ CEGAR（反例引导抽象精化）。
• Landmark 启发式（$h^{LM}$）：识别任何方案都必须经过的中间事实或动作（landmark），用其数量或代价划分（LM-cut）作为可采纳启发式。LM-cut 是当前最优规划的主力启发式之一。

3.2.4 启发式对比总结

启发式	可采纳	计算代价	信息量	典型用途
$h=\Vert g\setminus s\Vert$	有时	$O(\Vert g\Vert )$ 极低	很弱	baseline
$h^{max}$	✓	多项式	弱	最优规划的下界
$h^{add}$	✗	多项式	强	满意规划（satisficing）
$h^{FF}$	✗	多项式	很强	满意规划主力
PDB	✓	预处理指数、查询 $O(1)$	中~强	最优规划
LM-cut	✓	多项式（较贵）	强	最优规划主力
Merge-and-Shrink	✓	可调	可调	最优规划

两条不同的赛道：

• 最优规划（optimal planning）：必须用可采纳启发式 + A*。主力：LM-cut、M&S、Symbolic search。
• 满意规划（satisficing planning）：只求快速找到较好的解。主力：$h^{FF}$ + GBFS + preferred operators + 多队列（LAMA）。

3.3 偏序规划（Partial-Order Planning, POP）

3.3.1 核心思想：最小承诺（Least Commitment）

状态空间搜索必须为每个动作确定精确位置（全序），即使很多动作之间顺序无关。

偏序规划只在必要时才承诺顺序，保持方案为一个偏序集（partial order），可展开为多个等价的全序方案（线性化 linearization）。

优势场景：多个独立子目标。例如"穿左袜+左鞋"与"穿右袜+右鞋"，POP 只需承诺 2 个必要的顺序约束，而全序搜索要探索 $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 种交错。

3.3.2 表示：偏序规划的"计划"结构

一个偏序计划是一个四元组 $⟨A,O,L,B⟩$：

• $A$：动作集合，含两个虚拟动作：
  • $Start$：无前提，效果 = 初始状态
  • $Finish$：前提 = 目标，无效果
• $O$：顺序约束集合，形如 $a\prec b$（$a$ 必须在 $b$ 之前）。
• $L$：因果链接（causal link）集合，形如 $a\stackrel{p}{\to }b$，读作"$a$ 为 $b$ 提供前提 $p$"。
• $B$：变量绑定约束。

因果链接的作用：它是一个受保护的承诺——记录了"$b$ 的前提 $p$ 由 $a$ 提供"，任何威胁这个链接的动作都必须被处理。

3.3.3 威胁与解决（Threats and Resolution）

威胁（threat）：动作 $c$ 威胁因果链接 $a\stackrel{p}{\to }b$，若：

• $c$ 的效果包含 $\neg p$，且
• $c$ 可以被排在 $a$ 与 $b$ 之间（顺序上不矛盾）。

两种解决方式：

     a ──p──→ b
        ↑
        c  (效果含 ¬p，威胁)

方案 1：降级（demotion）        方案 2：提升（promotion）
   c ≺ a ──p──→ b                  a ──p──→ b ≺ c
   把 c 排到 a 之前                  把 c 排到 b 之后

（若涉及变量，还有第三种：分离（separation）—— 添加不等约束使 $c$ 的效果不与 $p$ 合一。）

3.3.4 POP 算法

function POP(initial, goal, actions) returns 偏序计划或 failure
    plan ← MAKE-MINIMAL-PLAN(initial, goal)
        // A = {Start, Finish}, O = {Start ≺ Finish}, L = {}, B = {}

    loop do
        if SOLUTION?(plan) then return plan
            // 所有前提都有因果链接支持，且无未解决威胁

        // 1. 选择一个未满足的前提（open precondition）
        Sneed, c ← SELECT-SUBGOAL(plan)

        // 2. 选择一个动作来达成它（非确定性选择点 ⇒ 需回溯）
        CHOOSE-OPERATOR(plan, actions, Sneed, c):
            选择 Sadd ∈ A 或新实例化一个动作，使 c ∈ EFFECT(Sadd)
            if 无此动作 then return failure
            添加因果链接 Sadd --c--> Sneed 到 L
            添加顺序约束 Sadd ≺ Sneed 到 O
            if Sadd 是新动作 then
                添加 Sadd 到 A
                添加 Start ≺ Sadd ≺ Finish 到 O

        // 3. 解决所有威胁
        RESOLVE-THREATS(plan):
            for each 因果链接 Si --c--> Sj in L do
                for each 动作 Sk in A that 效果含 ¬c do
                    if Sk 可能位于 Si 与 Sj 之间 then
                        选择：添加 Sk ≺ Si（降级）
                           或：添加 Sj ≺ Sk（提升）
                        if 顺序约束不一致（产生环） then return failure

在"计划空间"中搜索：
⚠️ 注意 POP 搜索的节点是部分计划，而非状态。这是与前向搜索的根本区别（plan-space search vs state-space search）。

性质：

• 可靠（sound）：任何完全的偏序计划的任意线性化都是有效方案。
• 完备（complete）：若使用系统的回溯，POP 能找到所有解。
• 产生灵活方案：偏序计划可以在执行时根据资源可用性选择线性化顺序——对多智能体执行、调度特别有价值。

局限：

• 启发式设计困难（部分计划的"距离目标多远"不好估计）。
• 1990s 曾是主流（UCPOP、SNLP），但在 2000 年后被 $h^{FF}$ 驱动的前向搜索全面超越——因为前向搜索的启发式太强了。
• 现代地位：POP 的思想在时序规划（temporal planning）与多智能体规划中仍然核心，因为那些领域天然需要偏序表示。

Sussman 异常的 POP 解：POP 能正确处理，因为它不强制子目标的求解顺序，威胁检测机制自动发现 $Move(A,B)$ 与 $Move(B,C)$ 的冲突并排序。

3.4 规划图与 GraphPlan

3.4.1 规划图（Planning Graph）

规划图是一个分层的有向图，交替出现状态层（level $S_i$）和动作层（level $A_i$）：

S₀        A₀         S₁         A₁         S₂  ...
├ p       ├ act1     ├ p        ├ act3     ├ p
├ q       ├ act2     ├ q        ├ act4     ├ q
├ ¬r      ├ 持续动作  ├ r                    ├ r
          │(persist) ├ ¬r                   ├ s

构造规则：

1. $S_0$ = 初始状态的所有文字（正的与负的，封闭世界下补全）。
2. $A_i$ = 所有前提在 $S_i$ 中出现且两两不互斥的基动作，外加每个文字的持续动作（persistence action / no-op，前提 = 效果 = 该文字）。
3. $S_{i+1}$ = $A_i$ 中所有动作的所有效果。
4. 计算 $A_i$ 与 $S_{i+1}$ 中的互斥关系（mutex）。

关键性质：规划图是多项式规模、多项式时间构造的，但它是原问题的松弛近似——它同时表示了所有可能并行执行的动作，忽略了很多约束。

3.4.2 互斥关系（Mutual Exclusion, Mutex）

动作层互斥（两个动作 $a,b$ 在 $A_i$ 中互斥）：

类型	条件
不一致效果（inconsistent effects）	一个动作的效果否定另一个的效果
干扰（interference）	一个动作的效果否定另一个的前提
竞争需求（competing needs）	两个动作的前提在 $S_i$ 中互斥

状态层互斥（两个文字 $p,q$ 在 $S_{i+1}$ 中互斥）：

类型	条件
不一致支持（inconsistent support）	$p$ 与 $q$ 互为否定，或 产生 $p$ 的每对动作与产生 $q$ 的动作都互斥

示例（Spare Tire 领域）：

• $Remove(Spare,Trunk)$ 与 $Remove(Flat,Axle)$ 不互斥（可并行）。
• $Remove(Spare,Trunk)$ 与 $PutOn(Spare,Axle)$ 互斥——干扰：前者删除 $At(Spare,Trunk)$，而后者需要它。

⚠️ 重要：mutex 关系是单调递减的——若两个文字在 $S_i$ 不互斥，则在 $S_j(j>i)$ 也不互斥。这保证了规划图会收敛到不动点（level off）。

3.4.3 规划图作为启发式来源

$h_{levelsum}$（level sum 启发式）：

$$h_{levelsum}(s)=\sum _{p\in g}level(p)$$

其中 $level(p)$ 是 $p$ 首次出现在规划图中的层数。

• 不可采纳（子目标独立假设），但信息量好。

$h_{maxlevel}$：${\max }_{p\in g}level(p)$，可采纳。

$h_{setlevel}$：$g$ 中所有文字两两不互斥地出现的最早层数，可采纳且比 $h_{maxlevel}$ 更强。

死锁检测（关键价值）：

若规划图收敛到不动点（level off，即 $S_i=S_{i+1}$ 且 mutex 也不变）后，目标文字仍未全部出现或仍互斥，则原问题不可解。

这是一个可靠的不可解性证明，代价只是多项式时间。

3.4.4 GraphPlan 算法

function GRAPHPLAN(problem) returns 方案或 failure
    graph ← INITIAL-PLANNING-GRAPH(problem)
    goals ← CONJUNCTS(problem.GOAL)
    nogoods ← 空哈希表           // 记录失败的 (goals, level) 对，避免重复搜索

    for tl = 0 to ∞ do
        if goals 全部非互斥地出现在 S_tl of graph then
            solution ← EXTRACT-SOLUTION(graph, goals, NUMLEVELS(graph), nogoods)
            if solution ≠ failure then return solution

        if graph 与 nogoods 都已 leveled off then
            return failure          // 可靠的不可解性判定
        graph ← EXPAND-GRAPH(graph, problem)

两个阶段的交替：

阶段 1：扩展（EXPAND-GRAPH）

• 多项式时间，构造下一层动作与状态，计算 mutex。

阶段 2：解抽取（EXTRACT-SOLUTION）

• 从最后一层的目标出发，后向搜索：为每个目标文字选择一个产生它的动作，要求所选动作两两不互斥；这些动作的前提成为下一层的目标集。
• 这是一个 CSP：变量 = 每个目标文字，值域 = 能产生它的动作，约束 = 不互斥。
• 可用 CSP 技术（第 6 章）：变量排序、约束传播、回溯。
• 或看作在"层次化的与或图"中做后向搜索。

nogood 记录（关键优化）：
记录"在第 $i$ 层，目标集 $G$ 无解"。若后续再遇到同样的 $(G,i)$，直接失败，无需重搜。这是记忆化 / no-good learning，与第 6 章 CSP 和第 7 章 CDCL 同源。

终止性保证：

1. 规划图必然收敛到不动点（文字集单调增、mutex 单调减，且都有界）。
2. nogood 集合也会收敛。
3. 两者都收敛且仍无解 ⇒ 可靠地返回 failure。

GraphPlan 的历史意义：

• Blum & Furst (1995) 提出，比当时的 POP 快几个数量级，震动了规划领域。
• 引入了并行方案（parallel plan）的概念：一层中的多个非互斥动作可同时执行。GraphPlan 找到的是层数最少的方案（并行最优），不一定是动作数最少的。
• 它的规划图后来被 FF 借用（去掉 mutex，只做可达性）作为启发式来源 —— 规划图从"求解器"变成了"启发式生成器"，这是领域内一次重要的思想转移。

局限：

• 只适用于 STRIPS（原始版本不支持条件效果、量化效果，虽有扩展）。
• 规划图规模随对象数增长可能很大。
• 解抽取阶段仍可能指数爆炸。
• 在最优（动作数最少）规划上不占优势。

3.5 基于 SAT 的规划（SATPlan / Planning as Satisfiability）

见第 7 章 §3.8 的基础，此处展开编码细节。

目标：把"存在长度为 $T$ 的方案"编码为一个 CNF 公式，交给 SAT 求解器。

命题变量：

• $p^t$：流 $p$ 在时刻 $t$ 为真（$t=\mathrm{0..}T$）
• $a^t$：动作 $a$ 在时刻 $t$ 执行（$t=\mathrm{0..}T-1$）

约束（子句）：

约束类型	公式	说明
初始状态	${\bigwedge }_{p\in s_0}{p}^0\wedge {\bigwedge }_{p\notin s_0}\neg p^0$	完全指定 $t=0$
目标	${\bigwedge }_{p\in g}{p}^T$	$T$ 时刻满足目标
前提公理	$a^t\Rightarrow {\bigwedge }_{p\in PRE(a)}{p}^t$	执行则前提成立
效果公理	$a^t\Rightarrow {\bigwedge }_{p\in ADD(a)}{p}^{t+1}\wedge {\bigwedge }_{p\in DEL(a)}\neg p^{t+1}$	效果生效
后继状态公理 （解释性框架公理）	$(p^t\wedge \neg p^{t+1})\Rightarrow {\bigvee }_{a:p\in DEL(a)}{a}^t$ $(\neg p^t\wedge p^{t+1})\Rightarrow {\bigvee }_{a:p\in ADD(a)}{a}^t$	状态改变必有原因
动作互斥	$\neg (a^t\wedge b^t)$ 对互斥的 $a,b$	防止并行执行冲突动作

互斥的两种粒度：

• 串行编码（sequential）：任意两个动作互斥 ⇒ 每步一个动作，公式小但需要更多时间步。
• ∀-step / ∃-step 编码：只对真正冲突的动作加互斥 ⇒ 允许并行，时间步少但子句多。$\exists$-step 编码通常最优。

求解流程：

for T = 0, 1, 2, ... do
    cnf ← ENCODE(problem, T)
    if SAT-SOLVE(cnf) returns model then
        return EXTRACT-PLAN(model)      // 读出所有为真的 aᵗ

优势：

• 直接受益于 SAT 求解器的工业级优化（CDCL、VSIDS、重启、子句学习）。
• 对某些结构化领域（并行度高、时间步少）极为高效。
• 易于加入额外约束（时间窗、资源上限）。

局限：

• 公式规模 $O(T\times |A|)$，$|A|$ 是基动作数，可能百万级。
• 必须逐步增大 $T$，无法证明不可解（除非另有上界论证）。
• 对长方案（$T$ 大）表现差——每增加一步，公式线性增长而搜索空间指数增长。
• 代价优化困难（需要 MaxSAT 或 PB 约束）。

相关路线：

• 答案集编程（Answer Set Programming, ASP）：用 clingo 等 ASP 求解器，语义更适合表达默认与非单调（第 10 章 §3.3），编码更简洁。
• CP / MIP 编码：用约束规划或整数规划求解器，适合数值与资源约束。
• 符号搜索（symbolic search）：用 BDD 表示状态集合，做双向 BFS。在某些最优规划任务上是当前最强方法之一。

3.6 分层任务网络规划（Hierarchical Task Network, HTN）

3.6.1 动机

经典规划从原语动作（primitive action）出发搜索，忽略了人类拥有的分解知识：

“去机场"可以分解为"叫车 → 上车 → 到达”，或"开车 → 停车 → 走到航站楼"。

HTN 让规划器利用这些领域特定的分解方法，把搜索从"原语动作序列"提升到"任务分解树"层面，指数级地缩小搜索空间。

3.6.2 核心概念

概念	说明
原语动作（primitive action）	可直接执行，有 PDDL 式的前提与效果
高层动作 / 复合任务（HLA / compound task）	不可直接执行，必须分解
方法（method）	把一个 HLA 分解为子任务序列/偏序集的规则
精化（refinement）	把 HLA 替换为其某个方法的子任务
实现（implementation）	HLA 的一个完全展开为原语动作的序列

方法示例：

Refinement(Go(Home, SFO),
    STEPS: [Drive(Home, SFOLongTermParking),
            Shuttle(SFOLongTermParking, SFO)])

Refinement(Go(Home, SFO),
    STEPS: [Taxi(Home, SFO)])

高层动作的语义（本章的关键理论贡献）：

HLA 的效果不是唯一的——不同的实现有不同的效果。因此 HLA 的效果用可达状态集合描述：

REACH(s,h)=⋃implementations i of h{RESULT(s,i)}REACH(s, h) = \bigcup_{\text{implementations } i \text{ of } h} \{RESULT(s, i)\}REACH(s,h)=implementations i of h⋃​{RESULT(s,i)}

两种语义：

语义	含义	用途
天使语义（angelic semantics）	智能体可以选择哪个实现 ⇒ 只要存在一个实现达成目标即可	HLA 是"能力"的抽象
恶魔语义（demonic semantics）	环境选择实现 ⇒ 必须所有实现都达成目标	保守/对抗设定

可达集合的近似：精确 $REACH$ 集合可能极大，实用做法是乐观（optimistic）近似（超集）与悲观（pessimistic）近似（子集）：

$$REAC{H}^{-}(s,h)\subseteq REACH(s,h)\subseteq REAC{H}^{+}(s,h)$$

剪枝规则（这是 HTN 效率的核心）：

• 若 $REAC{H}^{+}(s,h)\cap g=\varnothing$ ⇒ 该高层计划必然不可行，剪枝（无需展开）。
• 若 $REAC{H}^{-}(s,h)\cap g\ne \varnothing$ ⇒ 该高层计划必然可行，无需进一步搜索，可直接提交（后续再细化）。
• 否则 ⇒ 需要精化后重新判断。

这两条规则使 HTN 能在抽象层面就完成大部分剪枝，避免展开到原语层。

3.6.3 HTN 规划算法

方案 1：分层前向搜索（Hierarchical Forward Search）

function HIERARCHICAL-SEARCH(problem, hierarchy) returns 方案或 failure
    frontier ← 队列，初始含 [Act]        // Act 是顶层 HLA
    loop do
        if EMPTY?(frontier) then return failure
        plan ← POP(frontier)             // plan = [a₀, a₁, ..., aₙ]
        hla ← plan 中第一个 HLA（若无则 plan 全为原语）
        prefix, suffix ← hla 之前/之后的部分

        outcome ← RESULT(problem.INITIAL, prefix)
        if hla is null then              // plan 已全是原语动作
            if outcome ⊨ problem.GOAL then return plan
        else
            for each sequence in REFINEMENTS(hla, outcome, hierarchy) do
                frontier ← INSERT(prefix + sequence + suffix, frontier)

方案 2：带天使语义的分层搜索（Angelic Search）

function ANGELIC-SEARCH(problem, hierarchy, initialPlan) returns 方案或 failure
    frontier ← 队列，初始含 initialPlan
    loop do
        if EMPTY?(frontier) then return failure
        plan ← POP(frontier)

        // 用乐观可达集合剪枝
        if REACH⁺(problem.INITIAL, plan) ∩ problem.GOAL = {} then
            continue                     // 剪枝：绝不可能成功

        // 用悲观可达集合提前接受
        if REACH⁻(problem.INITIAL, plan) ∩ problem.GOAL ≠ {} then
            if plan 全是原语 then return plan
            guaranteed ← REACH⁻(...) ∩ problem.GOAL
            finalState ← 从 guaranteed 中任选一个
            return DECOMPOSE(hierarchy, problem.INITIAL, plan, finalState)

        hla ← plan 中第一个 HLA
        prefix, suffix ← ...
        for each sequence in REFINEMENTS(hla, outcome, hierarchy) do
            frontier ← INSERT(prefix + sequence + suffix, frontier)

效率分析：

设一个任务分解为 $b$ 个子任务，深度 $d$，则原语动作数 $\approx b^d$。

• 平坦搜索（flat search）：搜索空间 $O(k^{b^d})$（$k$ 为分支因子）。
• HTN 搜索：若每层只需在少数方法间选择，搜索空间 $O(k^d)$ 量级。

⇒ 指数级改善，但代价是需要人工提供分解知识。

适用场景：

• ✓ 领域知识丰富、任务有天然层次（军事任务规划、制造流程、web 服务组合、游戏 AI）。
• ✓ 需要生成人类可理解的方案（分解树天然可读）。
• ✗ 领域知识稀缺（HTN 退化为普通搜索，且写方法的成本高）。

局限：

• 方法库的编写成本高，且质量决定性能。
• 完备性依赖方法库：若方法库不完整（缺少某种分解），HTN 找不到本可行的方案。
• 与自动启发式方法相比，可迁移性差。

实用系统：SHOP/SHOP2（最广泛使用的 HTN 规划器）、O-Plan、SIPE-2、PANDA。

3.7 现实世界的复杂化

3.7.1 时间、调度与资源

经典规划假设动作瞬时、无资源约束。现实需要：

规划与调度的分离（plan first, schedule later）：

1. 规划阶段：生成偏序计划（动作及其顺序约束）。
2. 调度阶段：为每个动作分配开始时间，满足持续时间与资源约束。

关键路径法（Critical Path Method, CPM）：

对偏序计划，定义每个动作的：

• $ES$（earliest start）：最早开始时间
• $LS$（latest start）：最晚开始时间
• $Slack=LS-ES$：松弛

递推公式：

$$\begin{array}{rl}ES(Start)& =0\\ ES(b)& =\underset{a\prec b}{\max }[ES(a)+Duration(a)]\\ LS(Finish)& =ES(Finish)\\ LS(a)& =\underset{b\succ a}{\min }[LS(b)-Duration(a)]\end{array}$$

关键路径（critical path）= 所有 $Slack=0$ 的动作构成的路径。它决定了整个计划的最短总时长（makespan）。延迟关键路径上任何动作，整体完工时间就延迟。

复杂度：无资源约束时，CPM 是 $O(|A|+|O|)$ 线性时间。

⚠️ 加入资源约束后（如"只有 1 台机器"），调度问题变为 NP-难（job-shop scheduling）。常用启发式：

• 最小松弛优先（minimum slack）：优先调度松弛最小的动作。
• 分支定界、约束规划（CP 求解器在调度上非常强）。

资源建模：

• 可重用资源（reusable resource）：机器、工人——用完释放。
• 消耗性资源（consumable resource）：燃料、原料——用掉不还。
• 聚合（aggregation）：把 10 个相同的螺丝钉当作数量 10 而非 10 个独立对象，大幅减少状态空间。这是调度中的关键建模技巧。

3.7.2 非确定性与部分可观测

环境类型	方法	方案形式
确定 + 完全可观测	经典规划	动作序列
非确定 + 完全可观测	AND-OR 搜索	应急计划（contingent plan），含条件分支
确定 + 无传感器	信念状态搜索	一致性方案（conformant plan），单一序列在所有初始状态下都有效
非确定 + 部分可观测	信念状态 + AND-OR	应急计划 + 信念状态更新
未知环境	在线规划	执行监控 + 重规划

无传感规划（sensorless / conformant planning）：

• 在信念状态空间（belief state space）搜索：信念状态 = 可能的物理状态集合。
• 关键洞察：某些动作有强制效果（coercion），可以缩小信念状态。例：“把桌上所有杯子推到左边”——无论初始位置如何，之后都在左边。
• 信念状态可能指数大，实用做法是只保留文字合取表示（1-CNF 近似）。

应急规划（contingent planning）：

• 加入传感动作（sensing action / observation），其效果是获得信息而非改变世界。
• 用 AND-OR 搜索：OR 节点是智能体的动作选择，AND 节点是环境/观察的可能结果（都要处理）。
• 方案是一棵树：[Check(Tire); if Intact then [Inflate] else [Replace]]。

在线规划与重规划：

function ONLINE-PLANNING-AGENT(percept) returns action
    persistent: plan, 当前计划
                belief, 当前信念状态

    belief ← UPDATE-BELIEF(belief, percept)     // 执行监控
    if plan 为空 or plan 的前提在 belief 下不再成立 then
        plan ← REPLAN(belief, goal)             // 重规划
    action ← POP(plan)
    return action

三种执行监控：

监控类型	检查内容	代价	何时失败
动作监控（action monitoring）	下一个动作的前提是否成立	低	直到执行到该动作才发现问题
计划监控（plan monitoring）	剩余计划的所有前提是否仍成立	中	尽早发现失败
目标监控（goal monitoring）	目标本身是否还值得追求	高	支持机会主义（发现更好的目标）

重规划的智慧：

与其构造一个考虑所有可能情况的巨大应急计划（可能指数大），不如构造一个乐观计划 + 快速重规划。这就是 replanning agent 的思想，也是现代机器人系统的主流架构（对比第 12 章）。

循环计划（looping plan）：某些问题需要"重复尝试直到成功"，如"拧螺丝直到拧紧"。这要求方案含循环，AND-OR 搜索需要检测并允许回到已访问的信念状态。

---

4. 关键图示/表格说明

4.1 规划图结构（对应原书 Figure 11.9）

以 “Have Cake and Eat Cake Too” 问题为例：

      S₀              A₀                S₁              A₁               S₂
  ┌─────────┐    ┌──────────┐     ┌──────────┐    ┌───────────┐   ┌──────────┐
  │Have(C)  │────│ Eat(C)   │────→│¬Have(C)  │────│  Eat(C)   │──→│¬Have(C)  │
  │         │────│ [持续]    │────→│ Have(C)  │────│  Bake(C)  │──→│ Have(C)  │
  │¬Eaten(C)│────│ [持续]    │────→│¬Eaten(C) │────│ [持续×4]  │──→│¬Eaten(C) │
  │         │    │          │     │ Eaten(C) │    │           │──→│ Eaten(C) │
  └─────────┘    └──────────┘     └──────────┘    └───────────┘   └──────────┘
                                     ╎mutex╎                          ╎无mutex╎
                              Have(C) ⟷ ¬Have(C)              Have(C) 与 Eaten(C)
                              Have(C) ⟷ Eaten(C)              在 S₂ 不再互斥 ✓

读图要点：

1. 持续动作（no-op） 是把文字从一层传到下一层的"虚拟动作"，用虚线或方框表示。没有它们，规划图无法表达"什么都不做"。
2. Mutex 是单调递减的：$Have(C)$ 与 $Eaten(C)$ 在 $S_1$ 互斥（不一致支持），但在 $S_2$ 不再互斥（因为 $Bake$ 与 $Eat$ 的持续动作提供了非互斥的支持对）。
3. 目标 $Have(C)\wedge Eaten(C)$ 在 $S_2$ 首次非互斥出现 ⇒ 开始尝试解抽取 ⇒ 找到方案 [Eat(Cake), Bake(Cake)]。
4. 规划图的层数下界性质：目标首次非互斥出现的层数是最优并行方案长度的下界（因为规划图是松弛的）。

4.2 偏序计划示例：穿鞋（对应原书 Figure 11.6）

                    ┌──────────┐
                    │  Start   │
                    └────┬─────┘
              ┌──────────┴──────────┐
              ↓                     ↓
      ┌───────────────┐    ┌────────────────┐
      │ LeftSock      │    │  RightSock     │
      └───────┬───────┘    └────────┬───────┘
              │ LeftSockOn          │ RightSockOn
              ↓                     ↓
      ┌───────────────┐    ┌────────────────┐
      │ LeftShoe      │    │  RightShoe     │
      └───────┬───────┘    └────────┬───────┘
              │ LeftShoeOn          │ RightShoeOn
              └──────────┬──────────┘
                         ↓
                  ┌──────────────┐
                  │   Finish     │
                  └──────────────┘

因果链接 L = { Start→LeftSock, LeftSock--LeftSockOn-->LeftShoe,
               LeftShoe--LeftShoeOn-->Finish, ...（右侧对称）}
顺序约束 O = { LeftSock ≺ LeftShoe, RightSock ≺ RightShoe, ... }

读图要点：

• 只有 2 条必要的顺序约束（袜子在鞋之前），左右两支完全独立。
• 这个偏序计划有 6 个线性化（$\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 种交错方式），全都有效。
• 若用全序前向搜索，需要探索这 6 种排列中的多个才能找到解——这就是 POP 的价值。
• 执行时的灵活性：若右手先空出来，可以先穿右袜——偏序计划支持这种运行时决策。

4.3 Sussman 异常图解

初始状态                目标状态
   ┌─┐
   │C│                    ┌─┐
   ├─┤  ┌─┐               │A│
   │A│  │B│               ├─┤
   └─┘  └─┘               │B│
 ━━━━━━━━━━              ├─┤
                          │C│
                        ━━━━━━━━
On(C,A), OnTable(A),     On(A,B) ∧ On(B,C)
OnTable(B), Clear(C), Clear(B)

错误做法（先满足 On(A,B)）：
  Move(C, Table)  → Move(A, B)
  现在 A 在 B 上，但要把 B 放到 C 上，必须先把 A 拿开 ⇒ 撤销已完成的子目标 ✗

正确方案：
  MoveToTable(C)     // C 从 A 上拿下
  Move(B, C)         // B 放到 C 上
  Move(A, B)         // A 放到 B 上      ✓

读图要点：

• 两个子目标相互干扰（deleted-condition interaction）。
• 早期"线性规划器"（按顺序独立求解子目标）在此失败。
• POP 通过威胁检测正确处理；现代启发式搜索（$h^{FF}$）也能处理，因为它在完整状态空间中搜索。
• ⚠️ 这个例子说明为什么"忽略删除效果"的松弛会低估——松弛后 Sussman 异常消失了（不需要撤销），所以 $h^{FF}$ 会低估真实代价。

4.4 启发式松弛的层次关系

         原问题（PSPACE-完全）
              │
     ┌────────┼────────┬──────────────┐
     ↓        ↓        ↓              ↓
 忽略前提   忽略删除   状态抽象      分解子目标
     │        │        │              │
     ↓        ↓        ↓              ↓
 集合覆盖  delete-free  PDB        landmark
 (NP-难)   (NP-难)   (预处理)      (LM-cut)
     │        │        │              │
     └────────┴────────┴──────────────┘
              ↓
        多项式近似算法
              ↓
      h_add, h_max, h_FF, h_PDB, h_LMcut

读图要点：所有规划启发式都遵循同一个配方：

松弛（去掉某些约束）→ 松弛问题仍难 → 再近似求解 → 得到启发式值

可采纳性取决于：松弛 ✓ 保证下界，但近似求解若不是下界（如 $h^{FF}$ 的贪心抽取、$h^{add}$ 的求和）则失去可采纳性。

4.5 规划方法对比总表

方法	搜索空间	完备	最优	需要启发式	需要领域知识	现代地位
前向状态空间搜索	状态	✓	取决于算法	必需	否	主流（FF, LAMA, FD）
后向状态空间搜索	状态描述	✓	取决于算法	必需	否	用于启发式计算
偏序规划（POP）	部分计划	✓	✓（可扩展）	困难	否	时序/多智能体规划
GraphPlan	规划图 + CSP	✓	并行最优	内建	否	启发式来源（$h^{FF}$ 源头）
SATPlan	SAT 赋值	有界完备	步数最优	SAT 求解器内建	否	并行度高的领域
符号搜索（BDD）	状态集合	✓	✓	可选	否	最优规划竞争力强
HTN	分解树	依赖方法库	依赖方法库	可选	必需	工业应用（SHOP2）

4.6 关键路径示例

动作:    A(3)      C(2)
       ┌────→ ●  ────→ ●
Start ─┤              ↑ ─→ Finish
       └────→ ● ──────┘
        B(5)      D(1)

ES(A)=0, ES(B)=0
ES(C)=3 (A结束), ES(D)=5 (B结束)
ES(Finish) = max(3+2, 5+1) = 6      ← makespan

LS(Finish)=6
LS(C)=6-2=4, LS(D)=6-1=5
LS(A)=4-3=1, LS(B)=5-5=0

Slack(A)=1-0=1     ← 有 1 单位松弛
Slack(B)=0-0=0     ← 关键路径！
Slack(C)=4-3=1
Slack(D)=5-5=0     ← 关键路径！

关键路径: Start → B → D → Finish  (总时长 6)

读图要点：延迟 A 或 C 一个单位不影响总时长；延迟 B 或 D 会直接延长 makespan。资源应优先保障关键路径。

---

5. 与其他章节的关联

5.1 承前

章节	关联
第 3 章 搜索	前向规划直接是 A*/GBFS 的应用；松弛问题产生可采纳启发式的原理在此大规模自动化；第 3 章需人工设计启发式，本章自动生成
第 4 章 局部搜索	Enforced Hill Climbing（FF 使用）是局部搜索在规划中的应用；在线规划呼应第 4 章的在线搜索（LRTA*）
第 6 章 CSP	GraphPlan 的解抽取是 CSP；动作实例化是模式匹配 CSP；调度问题用 CP 求解器；nogood 学习同源
第 7 章 逻辑	SATPlan 直接沿用第 7 章 §3.8；后继状态公理在 SAT 编码中重现；命题化的规模问题在此再次出现
第 8–9 章 FOL	PDDL 是 FOL 的受限片段（封闭世界、无嵌套量词、无函数符号）；动作模式的实例化用合一；这是"牺牲表达力换效率"的经典案例
第 10 章 KR	PDDL 的 :types 是轻量本体；框架问题在 STRIPS 中被 ADD/DEL 列表优雅解决；限定问题在规划中表现为"前提不完整"

5.2 启后

章节	关联
第 12 章 机器人 KR	情境演算/事件演算是规划的逻辑基础（更表达力强但更难求解）；本章的执行监控、重规划直接服务于机器人
第 17 章 MDP	非确定性规划 → 概率规划；MDP 是"非确定 + 概率 + 效用"的规划；本章的应急计划 ≈ MDP 的策略（policy）
第 17 章 POMDP	信念状态规划的概率版本；本章的 conformant/contingent planning 是 POMDP 的确定性特例
第 22 章 强化学习	RL 是"模型未知"的规划；Dyna 架构 = 学习模型 + 规划；MCTS 结合了搜索与采样
第 26 章 机器人学	运动规划（motion planning）是连续空间的规划；任务与运动规划（TAMP）结合本章的符号规划与连续几何规划

5.3 一条核心主线：如何利用问题结构

问题：状态空间指数爆炸（PSPACE-完全）
   │
   ├─→ 利用「松弛后的可达性」  →  h_FF, h_add, h_max
   │
   ├─→ 利用「子问题的独立性」  →  偏序规划、additive PDB
   │
   ├─→ 利用「必经的中间点」    →  landmark, LM-cut
   │
   ├─→ 利用「层次可达性+互斥」 →  GraphPlan
   │
   ├─→ 利用「SAT 求解器的工程优化」 → SATPlan
   │
   └─→ 利用「人类的分解知识」  →  HTN

每种方法都在回答同一个问题：这个问题的什么结构可以被利用？

---

6. 延伸思考

6.1 LLM 作为规划器：符号规划的"重新发现"

2023 年以来，"LLM 做规划"成为热点：ReAct、Tree of Thoughts、Plan-and-Solve、LLM+P、Voyager、AutoGPT 系列。用本章的框架审视这些工作，会发现很多似曾相识：

LLM Agent 技术	本章对应概念
Chain-of-Thought	线性方案（全序）
Tree of Thoughts	搜索树 + 自评估作启发式
ReAct（推理+行动交替）	在线规划 + 执行监控 + 重规划（§3.7.2）
任务分解（task decomposition）	HTN 的方法（§3.6）
Reflexion / self-critique	失败后的重规划 + nogood 记录
LLM+P（LLM 生成 PDDL）	显式承认符号规划器的优势

LLM 规划的实证发现（值得深思）：

多项研究（Valmeekam et al., “PlanBench”）表明：

• GPT-4 级模型在 Blocks World 这样的经典基准上，零样本成功率不到 30%——而一个 1998 年的规划器能秒解。
• 但 LLM 在开放域、常识密集的任务上（“策划一次生日派对”）远超任何符号规划器——因为后者需要完整的 PDDL 领域模型，而这个模型在开放域中根本无法编写。

这构成了一个清晰的互补关系：

能力	符号规划器	LLM
长序列的正确性	✓✓ 保证（可靠、可验证）	✗ 容易在 8+ 步后出错
最优性保证	✓（A* + 可采纳启发式）	✗ 无
死锁检测	✓（$h^{FF}=\infty$、规划图不动点）	✗ 会自信地给出不可行方案
领域模型获取	✗ 需人工编写 PDDL	✓✓ 从常识中涌现
处理未建模情况	✗ 完全失效	✓ 优雅降级
生成 HTN 方法库	✗ 需专家	✓ 可自动生成候选

开放性问题 1：

LLM+P 架构（LLM 把自然语言任务翻译成 PDDL，交给 Fast Downward 求解，再把方案翻译回自然语言）已被证明在经典基准上远优于纯 LLM。但它要求领域模型（domain file）事先存在。能否让 LLM 同时生成 domain 与 problem 文件，并通过与环境交互迭代修正领域模型？

这实质上是把领域模型获取——符号规划几十年来最大的瓶颈——交给 LLM。技术挑战：

1. LLM 生成的 PDDL 常有语法/语义错误。需要验证-修复循环（用规划器的报错作为反馈）。
2. 领域模型的正确性无法自动验证（除非在环境中试执行）。这是 §3.7.2 执行监控的用武之地：用执行失败来精化领域模型。
3. 这条路线与 model learning / action model learning（如 ARMS、FAMA 算法）殊途同归——但 LLM 提供了强大的先验。

开放性问题 2（关于 HTN）：

HTN 的最大障碍是方法库的人工编写成本。而 LLM 恰恰极擅长任务分解（“去机场” → “叫车/开车/地铁”）。能否用 LLM 自动生成 HTN 方法库，再用符号 HTN 规划器保证组合的正确性？

这里有一个微妙但重要的技术点：§3.6.2 的天使语义与可达集合近似给出了 HTN 剪枝的形式化基础。若 LLM 生成的方法带有"这个方法能达成什么"的（近似）描述，就可以套用 $REAC{H}^{+}/REAC{H}^{-}$ 的剪枝规则。LLM 提供分解知识，符号引擎提供组合保证——这与第 9 章 §6.2 讨论的 AlphaGeometry 范式完全同构。

6.2 启发式的本质：学习 vs 推导

本章 §3.2 的所有启发式都是推导出来的（从松弛问题）。而深度学习提供了另一条路：学习启发式。

已有工作：

• 神经网络启发式：用 GNN 学习 $h(s)$，在 PDDL 图结构上做消息传递。
• 学习 preferred operators：预测哪些动作值得优先扩展。
• AlphaZero 式规划：策略网络 + 价值网络 + MCTS（第 5、22 章）。

关键权衡：

	推导的启发式（$h^{FF}$, LM-cut）	学习的启发式
可采纳性	可保证（$h^{max}$, PDB, LM-cut）	通常无保证
跨领域泛化	完美（对任意 PDDL 领域都工作）	需要领域内训练数据
计算代价	每个状态都要重算（可能很贵）	一次前向传播（快）
信息量上限	受松弛质量限制	理论上可达完美（$h^{\ast }$）
冷启动	立即可用	需要训练

开放性问题：

能否设计一种混合启发式：用可采纳的推导启发式（LM-cut）保证 A* 的最优性，同时用学习的启发式指导节点扩展顺序（不影响最优性，只影响效率）？

这在理论上是可行的——A* 的最优性只依赖 $h$ 的可采纳性，而 tie-breaking 与扩展顺序可以任意。已有工作（“learning to rank” for planning）沿此方向，但尚未成为主流。

更激进的思路：学习松弛本身。当前的松弛（忽略删除效果）是人工设计的、领域无关的。能否让模型学习"对这个领域，应该忽略哪些约束才能得到既容易求解又信息量大的松弛"？这将是"元级"的启发式学习。

6.3 多模态与具身规划：符号接地的老问题

本章的规划器工作在符号层：$At(C_1,JFK)$ 是一个原子，其真值由外部提供。真实机器人必须自己判断这个原子是否为真——从摄像头图像、力反馈、激光雷达中。

这是 §5.2 提到的 TAMP（Task and Motion Planning）的核心难题：

符号层（本章）:  Pick(cup) → Move(table) → Place(cup)
                     ↕  接地（grounding）
几何层:         逆运动学求解、碰撞检测、抓取姿态采样
                     ↕  感知
像素层:         RGB-D 图像 → 物体分割 → 6D 姿态估计

难点在于双向依赖：

• 符号规划需要知道"这个抓取动作在几何上可行吗"——但这要求求解运动规划（昂贵）。
• 运动规划需要知道"应该抓哪里"——但这由符号规划决定。

⇒ 天真的分层（先符号后几何）会导致大量回溯：符号方案在几何层不可行，退回重新规划。

当前方案：

• 交错式 TAMP：符号规划器在关键点调用几何求解器验证。
• 学习几何可行性预测器：用神经网络快速判断"这个符号动作在几何上大概率可行吗"，作为符号层的启发式/剪枝器。

开放性问题：

多模态大模型能否直接充当符号-几何的桥梁——即从图像直接判断 PDDL 谓词的真值（visual grounding of predicates），并预测动作的可行性？

这将解决符号规划最大的实用障碍：状态估计。当前的机器人系统需要精心设计的感知管线来维护符号状态；若 VLM 能可靠地回答"$Clear(BlockA)$ 现在为真吗？"，符号规划器就能直接部署在真实场景。

但要警惕误差传播：符号规划器假设其输入状态是确定正确的。若 VLM 的谓词判断有 5% 错误率，一个 20 步的方案就有 64% 概率至少一步基于错误状态。这必须用第 17 章的 POMDP 框架或本章 §3.7.2 的执行监控 + 重规划来处理。确定性规划 + 不确定感知 = 危险组合。

6.4 AI 对齐视角：规划能力与可控性

规划能力是 AI Agent 的核心，也是风险的核心来源。一个能做长程规划的系统，本质上是一个能"为达成目标而组合动作"的系统——这正是工具性趋同（instrumental convergence）担忧的技术基础。

本章提供了几个直接相关的技术抓手：

1. 可验证性：符号方案是可审计的

一个 PDDL 方案是一个明确的动作序列，每一步的前提与效果都可检查。这与 LLM 的"我打算做 X"形成鲜明对比：

• 符号方案：可以在执行前用形式化方法验证"这个方案不会进入禁止状态"。
• LLM 意图：只能事后观察。

这提示了一个具体的 Agent 安全架构：

强制 Agent 把行动计划表达为结构化的、可验证的形式（PDDL 或类似），在执行前用模型检验器验证安全性质（如"永不删除用户文件"、“永不发送外部请求”），验证通过才允许执行。

这与第 7 章 §6.2 讨论的"逻辑用在接口层"完全一致，且本章给出了更具体的载体。

2. 目标监控：什么时候应该停下来重新思考？

§3.7.2 的三种监控中，目标监控（goal monitoring）最有对齐意义：

智能体不仅检查"我的计划还能执行吗"，还检查"这个目标还值得追求吗"。

这在技术上是"机会主义"（发现更好的目标就切换），但在对齐语境下，它对应一个关键能力：可中断性（interruptibility）与目标可修正性（corrigibility）。一个只做动作监控的 Agent 会顽固地执行原计划；一个做目标监控的 Agent 天然具备"停下来问问是否还应该做这件事"的结构。

开放性问题：

能否把"人类可能想要修改我的目标"显式建模为规划问题的一部分？即，让 Agent 的规划过程内建对目标不确定性的处理（这正是 CIRL / assistance games 的思路，第 17–18 章）。

3. HTN 与人类监督的粒度

HTN 的分层结构提供了一个自然的人类监督接口：

• 人类在高层（HLA 层）审批：批准"预订机票"这个任务。
• Agent 在低层自主执行原语动作。
• 关键决策点（如涉及金钱、不可逆操作）强制上升到人类审批。

这比"审批每一个 API 调用"（太细，人类无法处理）和"授权整个任务"（太粗，风险不可控）都更合理。HTN 的抽象层次天然对应人类监督的合适粒度。

4. 一个警示：$REAC{H}^{+}$ 剪枝的双刃性

§3.6.2 的天使语义假设"智能体可以选择哪个实现"。这个假设在能力评估中是乐观的——它意味着"只要存在一条成功路径，Agent 就能找到"。

在安全评估中，我们应该用恶魔语义的对偶：评估一个 Agent 的危险能力时，应假设它能找到最有效的实现路径（天使语义），而不是平均路径。这意味着：

能力评估应该用 $REAC{H}^{+}$（乐观上界），安全保证应该用 $REAC{H}^{-}$（悲观下界）。

用错了方向，就会系统性地低估风险或高估安全性。这个看似技术性的语义区分，实际上是能力评估方法论的重要原则。

收束：自动规划是 AI 中"从思考到行动"的桥梁。本章的技术——启发式、抽象、分解、监控——在 LLM Agent 时代不但没有过时，反而提供了评估与约束这些 Agent 的概念框架。当我们问"这个 Agent 能规划多远"、“它的方案可验证吗”、"它会在什么时候重新考虑目标"时，我们问的正是本章的问题。