什么是 STRIPS 规划？

STRIPS 是 Richard Fikes 与 Nils Nilsson 于 1971 年在 SRI 为 Shakey 机器人创建的规划器和动作表示。每个动作有一个前提条件列表、一个列出它使之为真的事实的添加表，以及一个列出它使之为假的事实的删除表。几乎所有现代规划语言，包括 PDDL，都建立在这种表示之上。

STRIPS 和 PDDL 有什么区别？

STRIPS 是底层的动作模型：带有前提条件、添加表和删除表的动作。PDDL，即 1998 年推出的规划领域定义语言，是一种标准文件格式，用来表达 STRIPS 风格的领域和问题，并在此基础上扩展了类型、条件效果、数值、持续时间和偏好。PDDL 让规划器可以互换，也使国际规划竞赛成为可能。

什么是 HTN 规划？

分层任务网络规划从要完成的任务出发，而不是从要达成的事实出发。方法描述每个复合任务如何分解为子任务，规划器不断分解任务，直到只剩下可执行的动作。SHOP2 等 HTN 规划器在实践中很快，因为方法编码了关于事情该怎么做的专家知识。

什么是偏序规划？

偏序规划器构建一个步骤只部分有序的规划，只有当某一步否则会破坏另一步所需的条件时，才加入顺序约束。这种最小承诺的方法能解决 Sussman 异常这类问题：在那里，先彻底完成一个目标再开始下一个，会导致白费功夫或推翻已完成的工作。

什么是 Sussman 异常？

Sussman 异常是 Gerald Sussman 发现的一个三积木规划问题：积木 C 在 A 上，B 在桌上，目标是 A 在 B 上、B 在 C 上。一个把两个目标先后分别解决的规划器，无论选择哪种顺序，都必须推翻其中一个，所以最短的规划需要把两个目标交错进行。

AI 规划和搜索有什么不同？

规划是一种搜索，但它的状态和动作是用逻辑描述的，而不是藏在一个黑箱式的后继函数里。因为规划器能读懂前提条件和效果，它就能自动推导启发函数、从目标反向推理、分解问题，而这些是盲目搜索或手工调校的搜索做不到的。

自动规划今天还在使用吗？

在使用。用 PDDL 编写的 STRIPS 后代、HTN 规划器以及建立在 Fast Downward 之上的启发式规划器，被用于航天任务、物流、制造、机器人、电子游戏和软件自动化。规划器也与语言模型配合使用：语言模型提出或形式化一个规划，符号规划器则精确地找到或检验它。

符号 AI 技术 · 规划

AI 规划

符号 AI 如何算出一串动作，把世界从现在的样子变成你想要的样子：情境演算，STRIPS 及其添加表与删除表，框架问题，偏序规划与分层规划，Graphplan，可满足性规划，PDDL，以及今天占主导地位的启发式规划器。每种方法由谁构建、一个完整例子、在哪里使用、在哪里止步。

Perslis Research · 2026-09-26

AI 规划（automated planning，自动规划）是符号 AI 的一个分支：它计算一个动作序列，其中每个动作都由显式的前提条件和效果描述，使给定的初始状态变为满足目标的状态。由于每个动作的要求和后果都被写了下来，规划器的输出可以在执行任何动作之前逐步检验。

一段话说清

规划就是在用逻辑描述的世界状态上进行搜索。这一领域始于 McCarthy 的情境演算（1963）以及 Green 用定理证明器构造规划（1969）。STRIPS（Fikes 与 Nilsson，1971）确定了几乎所有规划器至今仍在使用的表示：一个动作有前提条件、它添加的事实和它删除的事实。随后二十年里出现了偏序规划器——只在不得不时才确定动作顺序——以及分层任务网络（HTN）规划器——把抽象任务逐步细化为具体步骤。20 世纪 90 年代中期，Graphplan 和 SATPlan 让规划器大幅提速；1998 年，PDDL 为这一领域提供了共同语言和一项竞赛。大约 2000 年以来，最强的通用规划器是 FF 和 Fast Downward 这类启发式搜索规划器，它们从问题描述中自行计算启发函数。一般问题是 PSPACE 完全的，而任何规划器都只和它所得到的动作模型一样好。

1. 什么是 AI 规划问题

最简单、研究最充分的设定是经典规划：单一智能体，唯一已知的初始状态，确定性的、不耗时的动作，以及由一组事实构成的目标。状态是一组基原子，例如 On(C, A)；当动作的前提条件成立时它可被执行，执行后会改变一些原子。经典规划是状态空间搜索的一个特例，其中的状态和动作不是黑箱，而是规划器可以读懂的逻辑描述。这个区别正是要点所在：因为规划器能看到一个动作为什么有用（它添加了目标需要的事实）以及它破坏了什么（它删除的事实），它就能计算启发函数、从目标反向推理、分解问题——盲目搜索做不到其中任何一件。各种扩展逐一放宽这些假设：时序规划（持续时间、并发）、数值规划、不确定与部分可观测条件下的规划。本页讲的是符号核心；Russell 与 Norvig 的教科书有完整论述 [1]，Ghallab、Nau 与 Traverso 的专著则更为专门 [2]。

2. 作为逻辑的规划：情境演算与框架问题

情境演算

由谁、何时。John McCarthy 于 1963 年提出情境演算，1969 年 McCarthy 与 Patrick Hayes 在《Some Philosophical Problems from the Standpoint of Artificial Intelligence》（从人工智能的角度看若干哲学问题）中对其加以发展 [3]。1969 年，SRI 的 Cordell Green 证明了归结定理证明器可以构造规划：证明存在一个目标情境，再从证明中读出规划 [4]。Ray Reiter 1991 年对框架问题的解决方案形成了今天使用的版本 [5]。

如何运作。情境是一段动作历史。 $S_{0}$ 是初始情境， $do (a, s)$ 是在 $s$ 中执行动作 $a$ 之后的情境。会变化的性质称为流（fluent），它们把情境作为额外参数： $On (b, y, s)$ 。前提公理说明一个动作何时可行，后继状态公理（Reiter）则精确说明一个流在动作之后何时为真。对于只有一个动作 $move (b, y)$ （“把积木 $b$ 放到 $y$ 上”，桌面始终是空的）的积木世界：

\begin{array}{l} Poss (move (b, y), s) \leftrightarrow Clear (b, s) \land Clear (y, s) \land b \neq y \\ On (b, y, do (a, s)) \leftrightarrow a = move (b, y) \lor (On (b, y, s) \land \neg \exists z (a = move (b, z) \land z \neq y)) \end{array}

用话来说：动作 $a$ 之后 $b$ 在 $y$ 上，当且仅当 $a$ 把它放在那里，或者它原本就在那里且 $a$ 没有把它移到别处。于是规划就成了演绎：找到一个项 $σ = do (a_{n}, \dots do (a_{1}, S_{0}))$ ，使得每个动作在执行处都可行，且目标在 $σ$ 中成立。今天的用途：主要在知识表示研究中，以及建立在它之上的逻辑程序设计语言 GOLOG。局限：一般的一阶定理证明太慢，无法成为实用的规划器，这正是 STRIPS 收窄语言的原因。

框架问题：它如何击中规划

McCarthy 与 Hayes 在同一篇 1969 年论文中命名了框架问题 [3]。效果公理说明一个动作改变了什么。逻辑并不假定其余一切保持不变，所以没有额外公理时，证明器无法得出“移动积木 B 之后积木 C 还在原处”。为每一对动作和不受影响的流单独写一条框架公理是可行的，但其数量随动作数与流数的乘积增长，而且每加一个新动作都得把它们全部重新审视一遍。Reiter 的后继状态公理（见上）把这些压缩为每个流一条公理，前提是列出的效果就是该流改变的全部方式。STRIPS 走的是过程化路线：一个动作没有明确删除的东西就保持不变。这个 STRIPS 假设是规划器在实践中能够工作的原因，也是一种承诺：动作模型中遗漏的效果不会引发警告，而是被默认为不会发生。更广义的、哲学层面的框架问题，以及由此产生的非单调逻辑，见非单调推理页面。

3. STRIPS 与积木世界完整例子

STRIPS

由谁、何时。SRI 国际的 Richard Fikes 与 Nils Nilsson，1971 年，作为移动机器人 Shakey 的规划器 [6]。其名称意为“斯坦福研究所问题求解器”（Stanford Research Institute Problem Solver）。它的规划算法是一种 GPS 风格的手段–目的搜索，早已被取代；而它的表示是今天几乎所有规划语言（包括 PDDL）的基础。

定义（STRIPS）。一个 STRIPS 问题是

⟨ P, O, I, G ⟩

：原子集合

P

，动作集合

O

，初始状态

I \subseteq P

和目标

G \subseteq P

。每个动作

a

有三个原子集合：前提条件

pre (a)

、添加表

add (a)

和删除表

del (a)

。一个状态就是为真的原子的集合；其余原子都为假。

γ (s, a) = {\begin{cases} (s ∖ del (a)) \cup add (a) & 若 pre (a) \subseteq s \\ 无定义 & 否则 \end{cases}

一个规划 $a_{1}, \dots, a_{n}$ 是有效的，当且仅当每个动作依次可执行，并且 $G \subseteq γ (\dots γ (I, a_{1}) \dots, a_{n})$ 。检验一个给定规划所需的时间与其长度成线性关系。找到一个规划却很难：Tom Bylander 于 1994 年证明，判定一个命题 STRIPS 问题是否存在规划是 PSPACE 完全的 [7]。

完整例子：积木世界。桌上有三块积木。动作写成带变量的模式（schema），代入积木名称即得具体动作：

\begin{array}{l} MoveToTable (b, x) : & pre = {On (b, x), Clear (b)} & add = {OnTable (b), Clear (x)} & del = {On (b, x)} \\ MoveFromTable (b, y) : & pre = {OnTable (b), Clear (b), Clear (y)} & add = {On (b, y)} & del = {OnTable (b), Clear (y)} \end{array}

（第三个模式——把积木从一块积木移到另一块上——这里用不到。）初始状态是 C 在 A 上，A 和 B 在桌上；目标是 A 在 B 上、B 在 C 上的一座塔：

\begin{array}{l} s_{0} = {On (C, A), OnTable (A), OnTable (B), Clear (C), Clear (B)} \\ G = {On (A, B), On (B, C)} \end{array}

用 γ 执行规划。每一行先对照当前状态检查前提条件，再删除、再添加。
步	动作	前提条件成立？	删除	添加	结果状态
1	MoveToTable(C, A)	On(C,A), Clear(C)	On(C,A)	OnTable(C), Clear(A)	OnTable(A), OnTable(B), OnTable(C), Clear(A), Clear(B), Clear(C)
2	MoveFromTable(B, C)	OnTable(B), Clear(B), Clear(C)	OnTable(B), Clear(C)	On(B,C)	OnTable(A), OnTable(C), On(B,C), Clear(A), Clear(B)
3	MoveFromTable(A, B)	OnTable(A), Clear(A), Clear(B)	OnTable(A), Clear(B)	On(A,B)	OnTable(C), On(B,C), On(A,B), Clear(A)

第 3 步之后， $G \subseteq s_{3}$ ：规划有效，检验的每一步都清晰可见。注意删除表做了什么：第 2 步删除了 Clear(C)，所以除非有东西重新添加它，之后任何动作都不能再往 C 上放东西。也注意删除表没有做什么：没有任何地方说第 2 步不会改变 On(C, …) 或 A 的颜色——这由 STRIPS 假设来保证。

图 1. 上表中的三步规划。这个初始状态与目标正是下一节讨论的 Sussman 异常。

今天的用途：作为 PDDL 的核心，因而也是几乎所有经典规划器的核心。局限：原始形式中没有持续时间、没有数值、没有不确定性、没有条件效果；ADL 以及后来的 PDDL 版本等扩展补上了这些。

4. 偏序规划与 Sussman 异常

Sussman 异常

上面的例子就是 Sussman 异常，由 Gerald Sussman 在 20 世纪 70 年代初的博士研究中发现 [8]。早期规划器是线性的：它们把合取目标拆成子目标，一个接一个地解决。在这里，两种顺序都会失败。先达成 On(A,B)（把 C 从 A 上移开，把 A 放到 B 上），那么为了把 B 放到 C 上，就必须再把 A 拿下来。先达成 On(B,C)（把 B 放到 C 上），那么 C 与 B 这一摞现在压在 A 上，不拆掉它就动不了 A。唯一的短规划是把子目标交错进行：先为第一个目标走一步，再完成整个第二个目标，最后完成第一个目标的其余部分。

偏序规划

由谁、何时。Earl Sacerdoti 的 NOAH（1975）是第一个把规划表示为动作的偏序网络的规划器 [9]；Austin Tate 的 NONLIN（1976–77）把偏序与分层分解结合起来 [10]。David Chapman 的 TWEAK（1987）为这一方法奠定了形式基础 [11]，SNLP（McAllester 与 Rosenblitt，1991）和 UCPOP（Penberthy 与 Weld，1992）成为教科书中的标准算法 [12]。

如何运作。偏序规划器不是在世界状态中搜索，而是在规划中搜索。一个规划由以下部分组成：一组步骤，一组顺序约束 $a_{i} ≺ a_{j}$ ，一组因果链 $a_{p} \overset{q}{\to} a_{c}$ （“步骤 $a_{p}$ 为步骤 $a_{c}$ 达成 $q$ ”），以及一份未满足前提条件的清单。规划器反复挑出一个未满足的前提条件，用已有步骤或新步骤来支持它。若某个步骤 $a_{t}$ 会删除 $q$ ，且可能落在 $a_{p}$ 与 $a_{c}$ 之间，它就构成威胁，解决办法是把它排在生产者之前（降级，demotion）或消费者之后（升级，promotion）：

a_{t} ≺ a_{p} 或 a_{c} ≺ a_{t}

在 Sussman 异常上：为支持目标 On(A,B)，加入步骤 MoveFromTable(A,B)；为 On(B,C) 加入 MoveFromTable(B,C)。前者删除后者需要的 Clear(B)，所以把 MoveFromTable(B,C) 排在前面。Clear(A) 仍未满足，于是加入 MoveToTable(C,A)；它需要 Clear(C)，而 MoveFromTable(B,C) 会删除它，所以把 MoveToTable(C,A) 排在其前。此时顺序已经完全确定，正是图 1 中那个交错的规划，而且从未尝试过错误的顺序：这就是最小承诺。遗产与局限：偏序规划在 20 世纪 90 年代初主导了研究，至今仍是对规划为什么有效最清晰的说明（因果链本身就是一种解释）。Graphplan 和启发式状态空间规划器出现后，它在速度上落败，因为在部分规划上很难计算出好的启发函数。它的思想在时序规划器和分层规划器中延续。

5. HTN 规划

分层任务网络（HTN）规划

由谁、何时。Sacerdoti 的 ABSTRIPS（1974）先在一个忽略次要前提条件的抽象层次中进行规划 [13]，NOAH 与 NONLIN 则对任务进行分层分解。Kutluhan Erol、James Hendler 与 Dana Nau 于 1994 年为 HTN 规划给出了形式语义和复杂性分析，证明它严格比 STRIPS 更具表达力，且在一般情况下不可判定 [14]。SHOP2（Nau 等，2003）是最著名的现代 HTN 规划器 [15]。

如何运作。目标不是一组事实，而是一项要完成的任务。原子任务就是普通动作。复合任务由方法来细化：每个方法说明在何种前提条件下、以怎样的子任务网络来完成该任务。规划就是不断分解顶层任务，直到只剩下可执行的原子动作，同时一路检查前提条件。一个出行领域：

\begin{array}{l} Travel (x, y) ⟹ [CallTaxi (x), Ride (x, y), Pay] & 若 Distance (x, y) < 50 公里 \\ Travel (x, y) ⟹ [Travel (x, {ap}_{x}), Fly ({ap}_{x}, {ap}_{y}), Travel ({ap}_{y}, y)] & 否则，经由机场 {ap}_{x}, {ap}_{y} \end{array}

方法编码的是关于事情该怎么做的专家经验，这极大地削减了搜索：规划器永远不会考虑坐飞机穿过市区。今天的用途：凡是存在标准作业程序的地方：SHOP2 曾被用于组合 Web 服务 [16]，HTN 规划器还用于军事与应急行动规划、制造业，以及电子游戏中角色的控制。局限：规划器只能找到方法所允许的规划。如果方法不完整，可行的规划就可能被漏掉；大部分智能由领域作者而不是规划器承担。

6. Graphplan 与 SATPlan

Graphplan

由谁、何时。Avrim Blum 与 Merrick Furst，IJCAI 1995；期刊版本 1997 年发表 [17]。在标准基准上，它比同时代的偏序规划器快得多，改变了这一领域的方向。

如何运作。Graphplan 构建一张由交替层组成的规划图：事实层 0 是初始状态；动作层 $i$ 包含前提条件都出现在事实层 $i$ 中的所有动作（外加把每个事实向前传递的“空操作”）；事实层 $i + 1$ 包含它们的全部效果。它还记录互斥关系：若一个动作删除另一个动作的前提条件或效果，或两者的前提条件互斥，则这两个动作互斥；若同时达成两个事实的每种方式都要用到互斥的动作，则这两个事实互斥。规划图的构建是多项式时间的。当所有目标事实都出现在某一层且两两不互斥时，Graphplan 从它们出发反向搜索，在每一层寻找一组互不互斥的动作；若失败，就扩展规划图再试。找到的第一个规划在并行时间步数上是最优的。遗产：事实证明，规划图作为启发函数的来源更有价值：一个目标首次出现的层数是它所需步数的可采纳估计，而 FF 的启发函数正是从一张松弛的规划图中计算出来的。

SATPlan（可满足性规划）

由谁、何时。Henry Kautz 与 Bart Selman 于 1992 年提出把规划当作可满足性问题，并在 1996 年的《Pushing the Envelope》中展示了它的实用威力 [18]。

如何运作。固定一个时域 $T$ 。为每个事实在每个时刻 $0 \leq t \leq T$ 建立布尔变量 $f_{t}$ ，为每个动作在每一步建立变量 $a_{t}$ 。把问题编码为子句，再交给 SAT 求解器：

\begin{array}{l} 初始状态与目标： & f_{0} 对 f \in I, \neg f_{0} 对 f \notin I, g_{T} 对 g \in G \\ 前提条件与效果： & a_{t} \to p_{t} (p \in pre (a)), a_{t} \to e_{t + 1} (e \in add (a)), a_{t} \to \neg d_{t + 1} (d \in del (a)) \\ 解释性框架公理： & \neg f_{t} \land f_{t + 1} \to \underset{a : f \in add (a)}{⋁} a_{t}, f_{t} \land \neg f_{t + 1} \to \underset{a : f \in del (a)}{⋁} a_{t} \\ 互斥： & \neg a_{t} \lor \neg b_{t} 对相互干扰的动作 a, b \end{array}

当且仅当存在至多 $T$ 步的规划时，该公式可满足，而一个满足赋值就是规划（读出为真的动作变量即可）。依次尝试 $T = 0, 1, 2, \dots$ 直到成功。解释性框架公理就是在命题逻辑中解决了的框架问题：一个事实只有在某个会改变它的动作发生时才能改变。为什么重要：SATPlan 让规划直接受益于 SAT 求解的每一项进步，同样的编码思想也是硬件验证中有界模型检测的基础。局限：公式随时域增长，所以长规划代价高昂，而优化动作代价不适合用纯 SAT 来做。

7. PDDL 与国际规划竞赛

PDDL（规划领域定义语言）

由谁、何时。Drew McDermott 及其同事于 1998 年发布 PDDL，主要是为了让第一届国际规划竞赛得以举行 [19]。PDDL2.1（Fox 与 Long，2003）为时序规划加入了数值流和持续动作 [20]；此后又有 PDDL2.2、PDDL3.0 与 PDDL3.1 服务于后来的竞赛。

如何运作。PDDL 的领域文件声明谓词和动作模式；问题文件列出对象、初始状态和目标。任何能读 PDDL 的规划器都能求解用它写成的任何领域。上面的 MoveFromTable 模式用 PDDL 写出来是：

(:action move-from-table
  :parameters (?b ?y)
  :precondition (and (on-table ?b) (clear ?b) (clear ?y))
  :effect (and (on ?b ?y)
               (not (on-table ?b)) (not (clear ?y))))

添加表变成正效果，删除表变成被否定的效果：这就是用类 Lisp 语法写的 STRIPS。今天的用途：作为研究型规划器和许多工业规划器的标准输入语言；也越来越多地被当作目标格式——让语言模型把规划问题形式化，再由经典规划器求解、由验证器检验。局限：写出一个正确的领域模型本身就很难，而且不加扩展，PDDL 无法表达实际应用所需的一切。

国际规划竞赛（IPC）

IPC 与 PDDL 一同始于 1998 年，此后定期举行，如今通常与 ICAPS 会议同期进行。PDDL1.2 是 1998 年和 2000 年竞赛的官方语言，PDDL2.1 用于 2002 年，PDDL2.2 用于 2004 年，PDDL3.0 用于 2006 年 [19]。共享的基准领域（物流、火星车、卫星、积木）和正面比较推动了下文所述的大部分进展。

8. 启发式搜索规划器：HSP、FF、Fast Downward

启发式搜索规划

由谁、何时。Blai Bonet 与 Héctor Geffner 的 HSP 证明了：使用自动推导的启发函数、朴素的前向状态空间搜索就很有竞争力 [21]。Jörg Hoffmann 与 Bernhard Nebel 的 FF（2001）完善了这一思想 [22]，Malte Helmert 的 Fast Downward（2006）则成为许多现代经典规划器共同的构建平台 [23]。

如何运作。关键技巧是删除松弛：假装动作没有删除表。松弛后的问题很容易（事实只会累积），它的解的代价可以估计真实代价。对状态 $s$ ，递归定义达成原子 $p$ 的代价：

Δ (s, p) = {\begin{cases} 0 & 若 p \in s \\ min_{a : p \in add (a)} [c (a) + max_{q \in pre (a)} Δ (s, q)] & 否则 \end{cases} h_{\max} (s) = max_{g \in G} Δ (s, g)

$h_{\max}$ 从不高估，因此它是可采纳的，配合它的 A* 会返回最优规划；把两处最大值都换成求和就得到 $h_{add}$ ，它信息更丰富，但可能高估。FF 的启发函数计数的是从规划图中提取的松弛规划里的动作数。在积木例子中，从 $s_{0}$ 出发、单位代价下， $h_{\max} = 2$ （On(A,B) 需要先有 Clear(A)），而真实代价是 3：正如所保证的，是一个低估。这个启发函数只从动作模式中计算出来，无须任何人手写。

Fast Downward 与 LAMA

Fast Downward 把 PDDL 翻译为多值状态表示，并提供一套搜索算法与启发函数库；它以 GPL 许可证开源。建立在 Fast Downward 之上的 LAMA（Richter 与 Westphal，2010）把 FF 启发函数与地标（landmark）——每个规划都必须在某个时刻使之为真的事实——结合起来 [24]。这一家族的规划器，加上抽象启发函数（模式数据库）以及后来的学习型启发函数，代表了经典规划的最高水平。局限：在最坏情况下，它们仍然都要面对 PSPACE 完全性；在删除本身就是全部难点的领域（例如资源稀缺的谜题）中，松弛启发函数可能严重误导。

9. AI 规划用在哪里

航天。NASA 的 Remote Agent 于 1999 年在深空一号（Deep Space 1）上飞行，其机载规划–调度器根据目标生成指令序列 [25]。哈勃空间望远镜的长期观测调度使用 Spike 系统。
物流、制造与运营。生产线调度、维护排序、军事与应急行动规划，通常使用 HTN 或时序规划器。
软件。Web 服务与工作流组合（见上文 SHOP2）。
机器人。在运动规划之上用 PDDL 进行任务级规划，这是 Shakey 与 STRIPS 的直系传承。
游戏。目标导向规划器和分层规划器在商业电子游戏中为非玩家角色选择动作。
语言模型系统。模型可以提出一个规划，或把一个请求翻译成 PDDL；再由符号规划器或规划验证器精确地找到或检验规划。详见神经符号 AI页面。

10. 时间线

AI 规划：本页技术的时间线。
年份	技术	人物	仍在使用？
1963 / 1969	情境演算；框架问题被命名	John McCarthy；McCarthy 与 Hayes	用于知识表示研究、GOLOG
1969	用归结定理证明做规划（QA3）	Cordell Green（SRI）	已被取代
1971	STRIPS	Richard Fikes、Nils Nilsson（SRI）	作为核心表示
20 世纪 70 年代初	Sussman 异常	Gerald Sussman（MIT）	经典测试用例
1974	ABSTRIPS（抽象层次）	Earl Sacerdoti	思想存在于 HTN 中
1975	NOAH：偏序规划	Earl Sacerdoti	—
1976–77	NONLIN：分层偏序规划	Austin Tate（爱丁堡）	—
1987	TWEAK	David Chapman	—
1991 / 1992	Reiter 的后继状态公理；SNLP；UCPOP	Ray Reiter；McAllester 与 Rosenblitt；Penberthy 与 Weld	用于知识表示与教学
1992 / 1996	SATPlan	Henry Kautz、Bart Selman	是
1994	HTN 的形式语义与复杂性；STRIPS 规划为 PSPACE 完全	Erol、Hendler、Nau；Tom Bylander	—
1995 / 1997	Graphplan	Avrim Blum、Merrick Furst	作为启发函数来源
1998	PDDL；第一届国际规划竞赛	Drew McDermott 等	是
1999	Remote Agent 在深空一号上飞行	NASA 艾姆斯研究中心与喷气推进实验室	—
2001	HSP；FF	Bonet 与 Geffner；Hoffmann 与 Nebel	是
2003	SHOP2；PDDL2.1	Nau 等；Fox 与 Long	是
2006 / 2010	Fast Downward；LAMA	Malte Helmert；Richter 与 Westphal	是

11. 局限

计算难度。命题 STRIPS 的规划存在性问题是 PSPACE 完全的，一般的 HTN 规划不可判定。规划器之所以成功，是因为真实领域有结构，而不是因为问题简单。
模型是瓶颈。规划器恰好与它的动作描述一样正确。写出完整、正确的前提条件与效果，是专家系统的知识获取问题换了一种形式；而 STRIPS 假设意味着被遗漏的副作用不会被标记出来，而是被默认为不存在。
世界不是经典的。动作会失败、会耗时、结果不确定，还与其他智能体同时发生。在经典设定之外，需要执行监控与重新规划，或者概率规划。
框架问题、资格问题与分枝问题。什么不会改变、什么会让动作失效、会随之产生哪些间接效果——这些永远无法被一个有限的模型完全刻画。

12. AI 规划与失效安全模型

失效安全模型是这样一种 AI 模型：失效会把它推向一个受控的安全状态，而不是一个自信的错误。规划为这一思想贡献了一个精确的版本：针对 STRIPS 或 PDDL 模型写出的规划可以被机械地验证。每个前提条件都对照它必须成立的那个状态进行检查，就像第 3 节中的表格那样；未通过检查的规划会被拒绝，并指明出错的步骤和缺失的事实。无论规划是谁提出的——一个搜索过程、一个人，还是一个语言模型——检查都是一样的。这正是我们在意的权限划分：模型可以提议；只有底层（floor）才能接纳一个事实；在这里，只有验证器才能接纳一个规划。

诚实的局限就是第 11 节所说的那一条：验证是相对于模型而言的。一个规划可以通过每一项检查，却仍然在模型没有描述的世界里失败；所以失效安全的设计必须把“无法从模型中证明”当作停下来的理由，而不是去猜。Perslis Research 的 Peel 把这一纪律用于知识：在做决定的回路中没有神经网络，知识是带类型、有来源的卡片，学习是可读的计数。据我们所知，它是第一个失效安全模型；确切的主张以及最接近的先前工作，见什么是失效安全模型？ Peel 是一个研究原型。另见什么是符号 AI？、符号 AI 的历史，以及全部符号 AI 技术指南。

13. 常见问题

什么是 AI 规划？: AI 规划，又称自动规划，是人工智能中计算一串动作以达成目标的部分。每个动作都由显式的前提条件和效果描述，因此规划器可以推理哪些动作有帮助、哪些会相互干扰，以及一个提议的规划在执行前是否有效。
什么是 STRIPS 规划？: STRIPS 是 Richard Fikes 与 Nils Nilsson 于 1971 年在 SRI 为 Shakey 机器人创建的规划器和动作表示。每个动作有一个前提条件列表、一个列出它使之为真的事实的添加表，以及一个列出它使之为假的事实的删除表。几乎所有现代规划语言，包括 PDDL，都建立在这种表示之上。
STRIPS 和 PDDL 有什么区别？: STRIPS 是底层的动作模型：带有前提条件、添加表和删除表的动作。PDDL，即 1998 年推出的规划领域定义语言，是一种标准文件格式，用来表达 STRIPS 风格的领域和问题，并在此基础上扩展了类型、条件效果、数值、持续时间和偏好。PDDL 让规划器可以互换，也使国际规划竞赛成为可能。
什么是 HTN 规划？: 分层任务网络规划从要完成的任务出发，而不是从要达成的事实出发。方法描述每个复合任务如何分解为子任务，规划器不断分解任务，直到只剩下可执行的动作。SHOP2 等 HTN 规划器在实践中很快，因为方法编码了关于事情该怎么做的专家知识。
什么是偏序规划？: 偏序规划器构建一个步骤只部分有序的规划，只有当某一步否则会破坏另一步所需的条件时，才加入顺序约束。这种最小承诺的方法能解决 Sussman 异常这类问题：在那里，先彻底完成一个目标再开始下一个，会导致白费功夫或推翻已完成的工作。
什么是 Sussman 异常？: Sussman 异常是 Gerald Sussman 发现的一个三积木规划问题：积木 C 在 A 上，B 在桌上，目标是 A 在 B 上、B 在 C 上。一个把两个目标先后分别解决的规划器，无论选择哪种顺序，都必须推翻其中一个，所以最短的规划需要把两个目标交错进行。
AI 规划和搜索有什么不同？: 规划是一种搜索，但它的状态和动作是用逻辑描述的，而不是藏在一个黑箱式的后继函数里。因为规划器能读懂前提条件和效果，它就能自动推导启发函数、从目标反向推理、分解问题，而这些是盲目搜索或手工调校的搜索做不到的。
自动规划今天还在使用吗？: 在使用。用 PDDL 编写的 STRIPS 后代、HTN 规划器以及建立在 Fast Downward 之上的启发式规划器，被用于航天任务、物流、制造、机器人、电子游戏和软件自动化。规划器也与语言模型配合使用：语言模型提出或形式化一个规划，符号规划器则精确地找到或检验它。

14. 参考文献

S. Russell, P. Norvig. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2020.
M. Ghallab, D. Nau, P. Traverso. Automated Planning: Theory and Practice. Morgan Kaufmann, 2004.
J. McCarthy, P. J. Hayes. Some Philosophical Problems from the Standpoint of Artificial Intelligence. Machine Intelligence 4, Edinburgh University Press, 1969.
C. Green. Application of Theorem Proving to Problem Solving. Proceedings of IJCAI-69, 1969; also SRI technical report, 1969.
R. Reiter. The Frame Problem in the Situation Calculus: A Simple Solution (Sometimes) and a Completeness Result for Goal Regression. In V. Lifschitz (ed.), Artificial Intelligence and Mathematical Theory of Computation. Academic Press, 1991.
R. E. Fikes, N. J. Nilsson. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence 2(3–4):189–208, 1971. doi:10.1016/0004-3702(71)90010-5
T. Bylander. The Computational Complexity of Propositional STRIPS Planning. Artificial Intelligence 69(1–2):165–204, 1994. doi:10.1016/0004-3702(94)90081-7
G. J. Sussman. A Computer Model of Skill Acquisition. American Elsevier, 1975.
E. D. Sacerdoti. The Nonlinear Nature of Plans. Proceedings of IJCAI-75, 1975; and A Structure for Plans and Behavior, Elsevier, 1977.
A. Tate. Generating Project Networks. Proceedings of IJCAI-77, pp. 888–893, 1977.
D. Chapman. Planning for Conjunctive Goals. Artificial Intelligence 32(3):333–377, 1987. doi:10.1016/0004-3702(87)90092-0
D. McAllester, D. Rosenblitt. Systematic Nonlinear Planning. Proceedings of AAAI-91, 1991; J. S. Penberthy, D. S. Weld. UCPOP: A Sound, Complete, Partial Order Planner for ADL. Proceedings of KR-92, 1992.
E. D. Sacerdoti. Planning in a Hierarchy of Abstraction Spaces. Artificial Intelligence 5(2):115–135, 1974. doi:10.1016/0004-3702(74)90026-5
K. Erol, J. Hendler, D. S. Nau. HTN Planning: Complexity and Expressivity. Proceedings of AAAI-94, 1994.
D. S. Nau, T.-C. Au, O. Ilghami, U. Kuter, J. W. Murdock, D. Wu, F. Yaman. SHOP2: An HTN Planning System. Journal of Artificial Intelligence Research 20:379–404, 2003. doi:10.1613/jair.1141
E. Sirin, B. Parsia, D. Wu, J. Hendler, D. Nau. HTN Planning for Web Service Composition Using SHOP2. Journal of Web Semantics 1(4), 2004. doi:10.1016/j.websem.2004.06.005
A. L. Blum, M. L. Furst. Fast Planning Through Planning Graph Analysis. Artificial Intelligence 90(1–2):281–300, 1997 (conference version IJCAI-95). doi:10.1016/S0004-3702(96)00047-1
H. Kautz, B. Selman. Planning as Satisfiability. Proceedings of ECAI-92, pp. 359–363, 1992; Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search. Proceedings of AAAI-96, pp. 1194–1201, 1996.
D. McDermott et al. PDDL: The Planning Domain Definition Language. Technical Report CVC TR-98-003 / DCS TR-1165, Yale Center for Computational Vision and Control, 1998.
M. Fox, D. Long. PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains. Journal of Artificial Intelligence Research 20:61–124, 2003. doi:10.1613/jair.1129
B. Bonet, H. Geffner. Planning as Heuristic Search. Artificial Intelligence 129(1–2):5–33, 2001. doi:10.1016/S0004-3702(01)00108-4
J. Hoffmann, B. Nebel. The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research 14:253–302, 2001. doi:10.1613/jair.855
M. Helmert. The Fast Downward Planning System. Journal of Artificial Intelligence Research 26:191–246, 2006. doi:10.1613/jair.1705
S. Richter, M. Westphal. The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks. Journal of Artificial Intelligence Research 39:127–177, 2010. doi:10.1613/jair.2972
N. Muscettola, P. P. Nayak, B. Pell, B. C. Williams. Remote Agent: To Boldly Go Where No AI System Has Gone Before. Artificial Intelligence 103(1–2):5–47, 1998. doi:10.1016/S0004-3702(98)00068-X