第 III 部分 · 知识、推理与规划
第 11 章 自动规划
Chapter 11 · Automated Planning
本章导读
规划 = 自动构造达成目标的动作序列。以 PDDL 为形式语言，在显式状态、因子表示与图 / SAT 编码之间权衡，是机器人与流程自动化的算法核心。
学习要点
- 经典规划：PDDL 与 STRIPS 传统——状态 = 谓词合取，动作 = 前提 + 效果。
- 状态空间搜索：前向 / 后向搜索；忽略删除列表的松弛启发式。
- 规划图与 GRAPHPLAN：命题层 / 动作层交替扩张，互斥约束传播，多项式构造 + 解提取。
- 把规划编码为 SAT / CSP：现代规划器的另一条主线；时序与资源扩展。
- 更现代的方向：分层任务网络 HTN 与基于学习的规划概览。
核心概念
| 术语 | English | 一句话解释 |
|---|---|---|
| PDDL | Planning Domain Definition Language | 规划领域与问题的标准描述语言 |
| STRIPS | STRIPS | 经典规划表示：前提 / 添加列表 / 删除列表 |
| 规划图 | Planning Graph | 命题与动作交替分层的推理结构 |
| 互斥关系 | Mutex | 同一层内不可同时成立 / 执行的约束 |
| 松弛启发式 | Delete-Relaxation Heuristic | 忽略负效果后求得的代价下界 |
| GRAPHPLAN | GraphPlan | 利用规划图提取并行规划的算法 |
| 后向搜索 | Backward (Regression) Search | 从目标向初始状态逆推的相关动作搜索 |
| 分层任务网络 | HTN | 通过任务分解缩小搜索空间的规划方法 |
| 时序规划 | Temporal Planning | 动作带持续时间与并发的扩展 |
配套代码（aima-python）
aima-python 是官方维护的开源算法库（MIT 协议），建议每学完一章就跑一遍对应模块的示例。