第 10 章标志着从通用搜索向专门化规划的范式转换。如果说前几章讨论的搜索（第 3～5 章）依赖于通用的问题形式化（状态、动作、目标），那么经典规划则引入了专门的表示语言（如 PDDL）来更紧凑地描述问题，并设计了针对规划任务特征的高效算法，如前向搜索、后向搜索以及创新的规划图方法。

本章的核心目标有四个：理解为什么需要专门的规划语言；掌握 PDDL 如何描述规划问题；掌握前向、后向状态空间搜索及其依赖的启发式设计方法；掌握规划图如何同时支持启发式估计与规划提取。

核心假设（经典规划的简化模型）

规划问题被形式化为一个 4 元组：初始状态、动作集合、目标测试、路径代价函数。整个章节建立在简化的世界模型之上，其核心假设包括：

• 感知是确定的、正确的、完全的
• 动作模型是确定的、有结果的
• 在规划和动作执行过程中，环境是保持不变的

规划问题的表示（PDDL）

要素化表示：本章采用要素化表示（Factored Representation）来描述世界状态，即用一个变量集合及其赋值来表示状态。

PDDL 的核心思想：PDDL 是对规划问题的声明性描述，你只描述「世界是什么」和「动作能做什么」，而不规定「如何做」。它包含两个文件：

• 域文件：定义谓词（关系）和动作模式（Action Schema）
• 问题文件：定义特定问题的对象、初始状态和目标

动作模式：PDDL 中的动作包含两部分：

• PRECOND（前提）：执行动作前必须成立的条件
• EFFECT（效果）：动作执行后必然成立的条件

其中，使用 and、not 等关键字来描述状态变化。一个动作的执行会从状态中添加一些谓词（add list）并删除一些谓词（delete list，需要在效果中用 not 显式标记），这被称为 STRIPS 假设（Stanford Research Institute Problem Solver）。

状态与流：状态被表示为基元的、无变量的、无函数的合取式集合，每个合取式被称为一个流。

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

这是将规划问题转化为搜索问题的最直接方式。

• 过程：从初始状态出发，在当前状态下应用所有适用的（前提为真）动作，生成后继状态，重复这个过程直到达到一个满足目标的状态
• 特点：搜索过程与问题的表述方式非常直观，但由于分支因子可能很大，搜索空间也很大

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

从目标状态开始，反向思考寻找能达成目标的动作序列。

• 过程：从目标出发，找到相关动作，即那些效果与当前目标集有重叠的动作，然后生成这些动作的前提作为新的目标集
• 核心优势：后向搜索的分支因子通常比前向搜索小得多

规划图的启发式（Heuristics from Planning Graphs）

由于简单的状态空间搜索很容易出现组合爆炸，实用系统中引入了非常强大的启发式。

规划图（Planning Graph）：规划图是一种双向交替的层次图，其基本构建过程需要理解两个核心概念：

• 互斥关系（Mutual Exclusion，简称 Mutex）：在同一层中两个相互矛盾的命题（Literals）或动作（Actions）不能同时成立
• 忽略删除列表：在构建规划图时，为了快速估计目标距离，常用的技巧是忽略所有效果的负文字（即删除列表），因为这可以放宽问题，使得状态转换单调递增，从而可采纳地估计实际规划距离

其他重要规划算法

• 规划图提取：一种基于规划图的反向链搜索，从最后一层开始，递归地选择不互斥的动作来支持所有目标，直到回溯到初始层；若失败，则扩展图继续搜寻
• SATPLAN：将规划问题转化为 SAT 问题（命题逻辑可满足性），然后调用高效的 SAT 求解器（如 MiniSat、Glucose），在大规模问题上往往表现优异

经典规划可以看作是第 3 章确定性搜索的逻辑延伸，而从第 10 章到第 11 章的演进，则是逐步放松本章所做的简化假设，为第 17 章的 MDP 与 POMDP 奠定基础。