自动规划 — PDDL、启发式与分层
这一章讲三件事: 一句带参数的动作描述怎么顶上万个具体动作; 为什么规划领域的启发式能「自动推导」;以及动作多到几十亿步时 怎么靠分层活下来。 读完你会明白:规划语言的本质是为搜索算法预装结构。
1. 这一章讲什么
经典规划的定义:在离散、确定、静态、完全可观测的环境中找到完成目标的 动作序列。第 2 章的问题求解和第 7 章的命题逻辑 agent 都能干这事, 但有两个共同的限制:每个新领域都要手工调启发式;状态空间要显式展开 (命题化一个 wumpus 世界,移动公理要按 4 个朝向 × T 个时刻 × n² 个位置重复)1。
PDDL(规划领域定义语言)对两症的药方是同一个:动作模式。 一个带参数的 Fly(p,from,to) 表示了全部 4Tn² 个具体动作,且不依赖 任何领域知识2。
2. 顶层全景
表示:状态=基本流的合取(数据库语义)
动作模式 = 名称+参数+前提+效果
执行 = 删删除列表 + 加添加列表
│
三条算法路线
前向状态空间搜索(主流:启发式好做)
反向/回归搜索(相关动作;ISBN 例:1 步 vs 1 万亿)
SATPlan(命题化+后继状态公理;偏序规划/Graphplan 在旁)
│
启发式(松弛问题)
忽略前提 ≈ 未满足目标数
忽略删除列表 → FF(爬山+BFS 逃逸)
对称约简 / 可序列化子目标 / 状态抽象
│
扩展:分层(HTN/HLA/天使语义)· 时间与调度(CPM/关键路径)
图说:中段的「启发式自动推导」是全章的枢纽——前向搜索的复兴全靠它。
3. 核心原理
3.1 动作模式:一句话的形态
航空货运领域只需要三个模式。Load(c,p,a):前提是货 c、机 p 都在机场 a, 效果是 ¬At(c,a)∧In(c,p)。一个细节见功力:PDDL 没有全称量词, 「飞机飞走时货物跟着走」没法量化(对所有货物统一陈述)表达,于是改语义——At 的真正含义是 「在给定地点可以取用」:货装进飞机就不再 At 任何地方,卸货才重新 At3。
执行一个动作 = 从状态里删掉删除列表、加进添加列表。 前提与效果都是文字合取;效果里的变量必须都出现在前提里, 这样实例化后才不会漏变量4。
换胎问题演示了「负效果」的用法:LeaveOvernight(车停在烂街区) 的前提为空、效果是备胎和瘪胎的位置全部变空——一个「什么都不做」的动作 也能毁掉所有备选方案5。积木世界则演示谓词设计:用 Clear(x) 替代「b 头上没东西」的全称否定,还要为 Table 打补丁 (Clear(Table) 恒真,但得防住 Move(b,x,Table) 的滥用)6。
3.2 三条算法路线
前向搜索直觉但贵。10 个机场、50 架飞机、200 件货物的货运问题: 解只要 41 步(装 20 件、飞、卸 20 件),但平均每个状态约 2000 个合法动作, 搜索图约 2000^41 个节点——没有好启发式,连这种玩具都绝望7。
反向(回归)搜索从目标倒推,只考虑相关动作(效果与目标合一、 且不否定目标的任何部分)。它的杀手锏是带变量的目标: 目标是 Own(9780134610993)(一本特定 ISBN 的书),动作模式是 Buy(i):前向搜索得先枚举一万亿个具体的 Buy;反向搜索把目标与 效果 Own(i′) 合一,一次回归直接得到前驱条件 ISBN(9780134610993)—— 考虑了一个动作而不是一万个8。但回归用含变量的状态描述, 启发式难做——这是多数实用系统选择前向的主因9。
SATPlan 把整个问题命题化:动作加时间上标、动作排除公理、 前提公理、初始状态、目标的析取、每个流的后继状态公理, 然后交给现代 SAT 求解器10。老对手偏序规划(动作做成图、 不排死顺序,「80 个装载动作硬排顺序毫无意义」)在 2000 年前称王, 之后被「前向搜索+自动启发式」反超——但航天器与火星车的作业规划 仍用它,因为偏序规划人能读懂、执行前可以人工审查11。
3.3 启发式:因子化表示的分红
原子状态上定义不出通用启发式(没有内部结构可分析); CSP 和规划用的因子化表示可以——从动作模式机械地推导松弛问题12:
- 忽略前提:所有动作处处可用,松弛解≈未满足目标数。 精确化要解一个集合覆盖问题(NP 难,贪心给 log 倍近似,但不可容许)13。
- 忽略删除列表:所有动作只加不删,任何进展都不会被抵消, 状态空间变得「下坡一片坦途」——爬山都能解。FF(FastForward) 用规划图估计这个启发式,再用改造版爬山搜真解;卡住就切换贪心最佳优先14。
- 8 数码回归:删掉「与 空格相邻」前提得错位数启发式;只删「目标格为空」 得曼哈顿距离——第 2 章手工想出的两个 h,在这里是自动生成的特例15。
两个结构化的省力技巧:对称约简(12 块积木里挑 x、y 垫 A,110 种组合 本质是同一种,只留一个)16;可序列化(排定顺序一次做完、无需返工)的子目标(积木塔自底向上做完 不用返工;NASA「深空一号」的远程智能体把航天器的命题设计成可序列化, 快到能实时控制飞行器)17。状态抽象则把「子目标独立假设」量化: max_i Cost(P_i) 是可容许的,Σ Cost(P_i) 通常更准但不可容许18。
3.4 分层:当动作数是十亿级
「从旧金山飞火奴鲁鲁」是一个动作;「左膝弯曲 5 度」也是一个动作; 两者之间差着几亿个基元步骤。分层任务网络(HTN)引入高层动作(HLA): 每个 HLA 有一到多个细化(refinement)——「去机场」可以是 [开车到长期停 车场, 摆渡] 或 [打车]19。
真正有趣的是天使语义:HLA 的多个实现不是「环境的捣乱」(恶魔非确定), 而是「agent 自己的选择」(天使非确定)。于是 HLA 的效果可以写成 「可达/必达」两档:「只要 HaveCash 则可能 At(Agent,SFO)」—— 高层规划可以先证明「有一条路能到」,再回头细化,免掉指数级的 基元搜索20。
3.5 时间与调度:关键路径法
给动作加持续时间后,问题变成调度。关键路径法(CPM):按顺序约束 建图,正推算最早开始 ES、反推算最晚开始 LS;LS−ES 是松弛, 零松弛的动作链就是关键路径——缩短别处不缩短总工期, 拖延它一分钟总工期就多一分钟。书里的作业车间:总工期 85 分钟, 顶部作业每个动作有 15 分钟松弛21。对资源(人、机器、时间)的限制:机器不能同时干两活 再把它变成 CSP,用最小松弛等启发式解。
4. 作者的判断与证据
- (书内数据) 2000^41 个节点、ISBN 的 1 万亿 vs 1、85 分钟的关键路径 ——三个数字分别钉住前向搜索的困境、回归的优势、调度的结构7821。
- (书内历史判断) 偏序规划 80 年代称王、2000 年被反超,原因是双重的: 前向搜索的启发式成熟了,SATPlan 还吃到了内存涨 1 万倍的红利22。 这是「算法复兴 = 表示不变 + 硬件/启发式变化」的范例。
- (作者的观察) 规划启发式研究是经验科学,FF 的成功靠实测而非证明23。
5. 边界与局限
- 经典规划的四个假设在真实世界全要打折;非确定域的无传感器规划、 应变规划、在线(监控+重规划)三条路线都在本章后半,代价依次上升24。
- 天使语义要求 HLA 描述满足「向下细化性质」:声称能达成目标的高层规划 必须真有实现能达成——写坏描述,高层证明就是空头支票25。
- 调度以关键路径为核心,但资源冲突让它回落到 CSP 搜索; CPM 本身不处理不确定性。
6. 可带走的
- 动作模式 =「参数化 + 前提/效果」:为搜索算法预装结构的第一手段。
- At 的改写(「可取用」)示范了表示设计的核心技巧: 与其增强语言,不如重定义谓词。
- 回归搜索赢在「带变量的目标」,输在「启发式难做」——先看你的目标能不能写成变量。
- 松弛问题三连:忽略前提、忽略删除列表、删规则——上一章的 h1/h2 就是它。
- max 可容许、Σ 通常更准:分解子目标时的经典取舍。
- 动作超过几千步,先想分层;高层证明可行性,低层负责可执行。
- LS−ES=松弛,零松弛链=关键路径:任何多任务项目的地图。
7. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 经典规划定义 | 11.1 | text/10-fm.txt:11322(搜「经典规划」) |
| PDDL | 11.1 | text/10-fm.txt:11329(搜「PDDL」) · text/10-fm.txt:11331(搜「4Tn2」) |
| 动作模式/删除列表 | 11.1 | text/10-fm.txt:11345(搜「动作模式」) · text/10-fm.txt:11355(搜「删除列表」) |
| 航空货运 | 11.1.1 | text/10-fm.txt:11368(搜「航空货物运输」) · text/10-fm.txt:11375(搜「才可以使用」) |
| 备用轮胎 | 11.1.2 | text/10-fm.txt:11393(搜「备用轮胎」) · text/10-fm.txt:11407(搜「LeaveOvernight」) |
| 积木世界 | 11.1.3 | text/10-fm.txt:11414(搜「积木世界」) · text/10-fm.txt:11451(搜「容纳积木」) |
| 前向搜索 2000^41 | 11.2.1 | text/10-fm.txt:11487(搜「450 种动作」) · text/10-fm.txt:11490(搜「200041」) |
| 回归与相关动作 | 11.2.2 | text/10-fm.txt:11497(搜「回归搜索」) · text/10-fm.txt:11499(搜「相关动作」) |
| ISBN 例子 | 11.2.2 | text/10-fm.txt:11520(搜「9780134610993」) · text/10-fm.txt:11526(搜「1 万亿」) |
| 前向为主因 | 11.2.2 | text/10-fm.txt:1193(搜「主要原因」) |
| SATPlan 翻译 | 11.2.3 | text/10-fm.txt:11538(搜「命题化」) · text/10-fm.txt:11552(搜「后继状态公理」) |
| 偏序规划兴衰 | 11.2.4 | text/10-fm.txt:11577(搜「偏序规划」) · text/10-fm.txt:11591(搜「火星车」) |
| 启发式自动推导 | 11.3 | text/10-fm.txt:1222(搜「领域特定」) · text/10-fm.txt:11601(搜「领域无关」) |
| 忽略前提/集合覆盖 | 11.3 | text/10-fm.txt:11607(搜「忽略前提」) · text/10-fm.txt:11615(搜「集合覆盖」) |
| 忽略删除列表与 FF | 11.3 | text/10-fm.txt:11628(搜「忽略删除列表」) · text/10-fm.txt:11706(搜「FastForward」) |
| 8 数码回归 | 11.3 | text/10-fm.txt:11621(搜「Slide」) |
| 对称约简 | 11.3.1 | text/10-fm.txt:11653(搜「对称约简」) |
| 可序列化子目标/深空一号 | 11.3.1 | text/10-fm.txt:11662(搜「serializable subgoal」) · text/10-fm.txt:11670(搜「深空一号」) |
| 状态抽象 | 11.3.2 | text/10-fm.txt:11678(搜「状态抽象（state abstraction）」) · text/10-fm.txt:11697(搜「max」) |
| HTN/HLA | 11.4.1 | text/10-fm.txt:11734(搜「分层任务网络」) · text/10-fm.txt:11734(搜「分层任务网络」) |
| 天使语义 | 11.4.3 | text/10-fm.txt:11860(搜「恶魔」) · text/10-fm.txt:11861(搜「天使」) |
| 向下细化性质 | 11.4.3 | text/10-fm.txt:11845(搜「向下细化」) |
| 非确定域三路线 | 11.5 | text/10-fm.txt:12037(搜「无传感器规划」) · text/10-fm.txt:12140(搜「应变规划」) · text/10-fm.txt:12172(搜「在线规划」) |
| CPM 与松弛 | 11.6.2 | text/10-fm.txt:12323(搜「关键路径方法」) · text/10-fm.txt:12339(搜「15 分钟的松弛」) |
| 85 分钟例子 | 11.6.2 | text/10-fm.txt:12339(搜「85 分钟」) |