Part I · 第 2 章
离散规划 Discrete Planning
这是全书最简单、也最「通用」的一章:状态空间有限(最多可数无限),不需要几何模型和微分方程,也没有任何不确定性——模型完全已知、完全可预测。这里建立的语言——状态、动作、状态转移函数、搜索、代价到达 / 代价到目标、值迭代——会在后面每一部分反复出现。
- 2.1–2.2 可行规划:只关心能不能到达目标。这些搜索方法会在全书很多地方再用,包括连续状态空间里的运动规划 → 去 Part II 最重要。
- 2.3 最优规划:最优性原理(动态规划原理)、值迭代、它和 Dijkstra 算法的关系 → 去 Part III 还需要这一节。
- 2.4–2.5 基于逻辑的表示和方法(STRIPS、部分计划、规划图、SAT)→ 后面的章节不再用到,做 AI 规划的同学重点看。
书里还顺带讨论了一个历史问题:AI 里「问题求解(problem solving)」和「规划(planning)」到底有什么区别?Russell & Norvig 的教材对两者的定义几乎一样,STRIPS 名字里的 PS 也是 Problem Solver。所以本书不区分二者,统称规划。
怎么用这一页:读正文 → 玩嵌在正文里的互动图 → 做「?」自测。所有数字都可以和原书的表对照。配套的 Python 参考实现在 part1/code/ch2_discrete_planning.py,它会打印出书中图 2.9、2.12、2.14、2.15 的表。
2.1 离散可行规划 Introduction to Discrete Feasible Planning
2.1.1 问题形式化
世界的每一种不同情形叫做一个状态 \(x\),所有可能状态组成状态空间 \(X\)。离散规划要求 \(X\) 是可数的,多数情况下是有限的。
不要把无关信息编码进状态:一个在法国移动机器人的问题,不应该编码「中国某些灯泡是否亮着」。无关信息很容易把一个能高效求解的问题变成难以求解的问题。但另一方面,\(X\) 又必须大到足以包含求解任务所需的全部信息。
规划器选择动作来改变世界。在当前状态 \(x\) 施加动作 \(u\),得到新状态 \(x'\),由状态转移函数 \(f\) 给出:
\(U(x)\) 是在状态 \(x\) 可以施加的所有动作,称为动作空间。不同状态的 \(U(x)\) 不一定互不相交——同一个动作可能在很多状态下都能用,所以定义所有动作的集合
再给定一个目标集合 \(X_G \subset X\)。规划算法的任务:找到一个有限的动作序列,把初始状态 \(x_I\) 变换到 \(X_G\) 中的某个状态。
- 一个非空的状态空间 \(X\),是有限或可数无限的状态集合。
- 对每个状态 \(x \in X\),一个有限的动作空间 \(U(x)\)。
- 一个状态转移函数 \(f\):对每个 \(x\in X\)、\(u \in U(x)\) 给出 \(f(x,u)\in X\);由它得到状态转移方程 \(x' = f(x,u)\)。
- 一个初始状态 \(x_I \in X\)。
- 一个目标集合 \(X_G \subset X\)。
Formulation 2.1 经常画成一张有向状态转移图:顶点集就是 \(X\);从 \(x\) 到 \(x'\) 有一条有向边,当且仅当存在 \(u \in U(x)\) 使得 \(x' = f(x,u)\)。初始状态和目标集合是图中被特别标出的顶点。
离散可行规划 = 在一张(往往巨大、只能隐式给出的)有向图里,找一条从 \(x_I\) 走到 \(X_G\) 的路径。路径上依次经过的边对应的动作,就是计划。
2.1.2 例子
Example 2.1:在二维网格上移动
机器人在整数格点 \((i,j)\) 上,每步向上、下、左、右走一格。用 Formulation 2.1 写出来:\(X = \mathbb{Z}^2\)(所有整数对),\(U = \{(0,1),(0,-1),(1,0),(-1,0)\}\),对所有 \(x\) 有 \(U(x) = U\),状态转移函数就是向量加法 \(f(x,u) = x + u\)。例如 \(x = (3,4)\)、\(u=(0,1)\) 时 \(f(x,u) = (3,5)\)。取 \(x_I = (0,0)\)、\(X_G = \{(100,100)\}\),很容易找到一个动作序列。
把一些格子涂黑当作障碍,就更有意思了:涂黑的格子对应的顶点和与它相连的边从状态转移图中删除。再围一圈外边界,\(X\) 就变成有限集合,可以构造很复杂的迷宫(图 2.2)。下面这个小网格可以直接玩:
Example 2.2:魔方
魔方是 3×3×3 的小方块,每个面涂一种颜色。一个动作是把某一层 3×3 的小方块转 90°。状态空间是魔方的所有构型(整个魔方的朝向无关),每个状态有 12 个动作。任务:从某个打乱的构型出发,找到一串动作,使六个面各自恢复成单一颜色。(补充,非书中内容:魔方可达构型约有 4.3 × 1019 个——不可能显式画出这张图。)
隐式表示,以及与自动机的关系
非常重要的一点:规划问题通常不会显式给出整张状态转移图,而是在规划过程中逐步揭示(revealed incrementally)。Example 2.1 只用了很少的信息就描述了一张无限大的图。所以做复杂度分析时要特别注意输入的编码:即使 \(X\) 无限,输入长度也必须有限。2.4 节的逻辑表示可以看成是一种「输入压缩方案」。
| 如果你学过…… | 对应关系(\(X\) 有限时) |
|---|---|
| 有限状态机(Mealy / Moore 机) | 动作 = 状态机的输入,输出就是报告当前状态。可行规划 = 是否存在一串输入,使状态机最终报告想要的输出。规划算法知道机器转移的完整说明,并且随时能读出当前状态。 |
| 确定性有限自动机 DFA | DFA 的接受状态 ↔ 目标集合 \(X_G\);输入串 ↔ 动作序列。可行规划 ⟺ 是否存在一个被 DFA 接受的输入串 ⟺ DFA 的语言是否非空。 |
网格例子里 \(X = \mathbb{Z}^2\) 是无限集合,它怎么能作为算法的「输入」?
2.2 搜索可行计划 Searching for Feasible Plans
本节的方法其实就是图搜索算法,只不过要记住:状态转移图是通过施加动作逐步揭示的,而不是事先完整给出的。所以可以把本节看成「从规划的视角重新审视图搜索」。
系统性(systematic)
任何搜索算法都有一个重要要求:系统性。
- 图有限时:算法必须访问每一个可达状态,从而能在有限时间内正确判断有没有解。为此要记录已访问的状态,否则可能在环里无限打转。只要保证没有冗余的重复探索,就足以保证系统性。
- 图无限时:要求放宽为——如果有解,必须在有限时间内报告;如果无解,允许永远搜下去。具体条件是:当迭代次数趋于无穷时,每个可达顶点都会被探索到。因为顶点是可数的,这总是做得到的。
反过来不成立:一个算法即使朝多个方向扩展、甚至按某种波前扩展,也可能不系统。每个算法都要具体分析。好消息是:图有限时情况简单得多——几乎任何搜索算法只要标记已访问状态、不无限重访,就是系统的。
2.2.1 通用前向搜索
搜索过程中的任何时刻,状态分为三类:
| 类别 | 含义 | 初始时 |
|---|---|---|
| 未访问 Unvisited | 还没被访问过。 | 除 \(x_I\) 外的所有状态 |
| 活跃 Alive | 已经遇到,但可能还有没访问过的后继状态。存放在优先队列 Q 里。 | 只有 \(x_I\) |
| 死亡 Dead | 已访问,而且它的每个后继状态(存在 \(u\in U(x)\) 使 \(x'=f(x,u)\) 的 \(x'\))也都已访问——它对找可行计划已经没有新线索可以贡献了。(2.3.3 节会有一个变体:为了求最优,死亡状态可以「复活」。) | 无 |
活跃状态放在优先队列 Q 里,各种搜索算法之间唯一显著的区别,就是 Q 的排序函数。
算法流程:Q 一开始只有 \(x_I\);每轮取出排名最高的 \(x\);若 \(x\in X_G\) 就报告 SUCCESS;否则尝试 \(U(x)\) 中的每个动作,对每个后继 \(x'=f(x,u)\) 判断是不是第一次遇到——是就插入 Q,不是就说明它要么已死亡要么已在 Q 中,不用再管(某些算法需要在第 12 行更新它)。Q 空了还没找到目标,说明整个可达部分都探索完了,报告 FAILURE(如果可达部分无限,算法就永远不会结束)。
图 2.4 省略了一些实际中很重要的细节:
- 目标测试(第 4 行)有多快?取决于状态空间的大小以及 \(x\) 和 \(X_G\) 的具体表示。
- 怎么得到计划,而不只是「有/没有」?在第 7 行之后给 \(x'\) 记一个指向父节点 \(x\) 的指针(顺便记下用的动作)。找到目标后沿指针回溯到 \(x_I\) 就恢复出计划。
- 怎么判断 \(x'\) 是否访问过(第 8、9 行)?如果状态转移图恰好是一棵树,就根本不用判断——这很少见,但遇到就太好了。如果状态都在网格上,用查找表 \(O(1)\) 就能判断。一般情况下可能要和 Q 中及所有死亡状态比较;状态表示很长时代价很高。好的哈希方案能大大缓解。也可以干脆允许重复状态,但代价可能远超收益:即使图很小,也可能跑出指数时间,甚至在有限图上不终止。
- 第 12 行「处理重复」:有些算法要给每个状态维护一个代价,同一状态被再次到达时可能要更新。也可以不存指针,而是给每个状态存它的最优代价到达值——从任一已访问状态出发,沿着代价下降最快的方向反向走就能回到 \(x_I\)。这要求代价具有某种单调性(Dijkstra 和 A* 能得到),更一般地要构成导航函数(8.2.2 节)。
2.2.2 具体的前向搜索方法
下面每个算法都是图 2.4 的特例,区别只在 Q 的排序。它们都会构造一棵搜索树。
广度优先 Breadth first
Q 是 FIFO 队列(先进先出)。搜索前沿均匀地向外长,所以叫广度优先。所有 \(k\) 步的计划都被穷尽之后,才会考察 \(k+1\) 步的计划——因此第一个找到的解步数最少。重复状态时第 12 行什么也不用做。因为按波前推进,它是系统的;事实上,即使不记录重复状态它也仍然系统(只是会在无关的环上浪费时间)。
运行时间 \(O(|V|+|E|)\)(假设判断是否访问等基本操作是常数时间;实际上这些操作往往更贵,也应计入复杂度)。注意图通常不是输入——比如输入可能只是魔方的规则——所以可以换成其他量来表达:\(|V| = |X|\);如果每个状态的动作集合都是同一个 \(U\),则 \(|E| = |U||X|\);如果任意两个状态的动作集合都互不相交,则 \(|E| = |U|\)。
深度优先 Depth first
Q 是栈(LIFO,后进先出),搜索会「激进地」往图里钻,偏向于很早就考察很长的计划。这看起来好像不错,但要注意:具体钻向哪条长计划是任意的,取决于 forall 循环里动作的排列顺序。重复状态时第 12 行同样不用做。DFS 对有限 \(X\) 是系统的,对无限 \(X\) 不系统——它可能像图 2.3(a) 那样只盯着一个「方向」,完全错过大片区域。运行时间也是 \(O(|V|+|E|)\)。
Dijkstra 算法
到目前为止,还没有理由偏爱某个动作。现在给状态转移图的每条边 \(e\) 一个非负代价 \(l(e)\),即施加该动作的代价,在状态空间里写作 \(l(x,u)\)。计划的总代价就是路径上边代价之和。
Q 按代价到达(cost-to-come)函数 \(C: X \to [0,\infty]\) 排序。\(C^*(x)\) 表示从 \(x_I\) 到 \(x\) 的最优代价到达:在所有从 \(x_I\) 到 \(x\) 的路径中,取边代价之和最小的那条。(星号 * 表示「最优」。不确定是否最优时写 \(C(x)\)。)
- 初始 \(C^*(x_I) = 0\)。每生成一个 \(x'\),计算 \(C(x') = C^*(x) + l(x,u)\)——这是目前已知的最好代价,还不确定是否最优。
- 所以第 12 行要干活:如果 \(x'\) 已在 Q 中,而新发现的路径更便宜,就降低 \(C(x')\) 并重排 Q。
- \(C(x)\) 何时变成 \(C^*(x)\)?当 \(x\) 被 GetFirst 取出、变成死亡状态时。归纳论证:\(x_I\) 是基础情形;假设所有死亡状态的值都已最优、不再改变。对 Q 的队首 \(x\),任何更便宜的路径都必须经过 Q 中的另一个状态,而那些状态的代价已经更高(边代价非负);只经过死亡状态的路径在计算 \(C(x)\) 时已经都考虑过了。(这还不是完整证明,更多论证见 2.3.3 节。)
- 用 Fibonacci 堆实现优先队列时,运行时间 \(O(|V|\lg|V| + |E|)\)。
Dijkstra 算法是动态规划的一种特殊形式,2.3 节会看到更一般的动态规划。
A*(读作 "ay star")
A* 是 Dijkstra 的扩展:加入对「从当前状态到目标还要花多少」的启发式估计,以减少探索的状态数。设 \(C(x)\) 是代价到达,\(G(x)\) 是从 \(x\) 到 \(X_G\) 的代价到目标(cost-to-go)。\(C^*\) 能用动态规划逐步算出来,但真正的最优 \(G^*\) 无法事先知道。幸运的是,很多应用里能构造一个合理的低估 \(\hat{G}^*(x) \le G^*(x)\)。
典型例子:在迷宫(图 2.2)里,代价是总步数,那么 \(|i'-i| + |j'-j|\)(曼哈顿距离)就是一个低估——它是忽略障碍物时最直接计划的长度,加上障碍只会让代价变大(甚至无法到达)。0 当然也是低估,但对算法毫无帮助。目标是让估计尽量接近 \(G^*\),同时保证不超过它。
A* 和 Dijkstra 完全一样,唯一的区别是 Q 按 \(C^*(x') + \hat{G}^*(x')\) 排序,即「从 \(x_I\) 经过 \(x'\) 到 \(X_G\) 的总代价估计」。
- 若 \(\hat{G}^*\) 对所有 \(x\) 都是低估,A* 保证找到最优计划。
- \(\hat{G}^*\) 越接近 \(G^*\),探索的顶点通常越少。但很多问题里很难找到既容易计算、又能有效引导搜索的启发函数。
- \(\hat{G}^* \equiv 0\) 时 A* 退化为 Dijkstra。A* 总是系统的。
像图 2.4 这样「死亡状态不再重开」的图搜索版本,严格来说需要启发函数满足一致性(consistency):\(\hat{G}^*(x) \le l(x,u) + \hat{G}^*(f(x,u))\)。一致性蕴含低估。只满足低估、不满足一致性时,要么允许死亡状态重新激活(就像 2.3.3 节的标号修正算法),要么可能得不到最优解。网格上的曼哈顿距离和欧氏距离都是一致的,所以下面的实验里不用担心。
最佳优先 Best first
Q 只按代价到目标的估计排序。得到的解不一定最优,所以估计是否高估无所谓(这一点对 A* 的最优性很关键,这里不在乎)。很多情况下探索的顶点少得多、跑得快得多——但没有保证。最坏情况比 A* 和动态规划都差:它太「贪心」了,会偏爱在搜索早期「看起来不错」的状态。图 2.5 是一个人为构造的例子:在三维世界里走小步,起点在一根螺旋管的开口里,目标就在螺旋管正下方,搜索会绕着螺旋走,而不是先出管再直奔目标;对任意给定的 \(k\),都能造出一个比 Dijkstra 至少多浪费 \(k\) 步的螺旋。最佳优先不是系统的。
迭代加深 Iterative deepening
当搜索树的分支因子很大(下一层的顶点远多于当前层,例如每个状态有很多动作、但很少重复访问)时,通常更好。做法:用深度优先找出所有离 \(x_I\) 距离 \(\le i\) 的状态;没找到目标,就丢弃之前所有结果,用深度优先找距离 \(\le i+1\) 的状态。一般从 \(i=1\) 开始,一直进行到找到目标为止。它可以看作把 DFS 变成系统性搜索的一种办法。
为什么敢丢弃之前的工作?因为距离 \(i+1\) 能到达的状态数预计远超距离 \(i\) 的(比如多 10 倍),一旦决定要到达第 \(i+1\) 层,之前所有轮次的代价就微不足道了。很多问题上它的最坏情况性能优于 BFS,而且空间需求小得多(BFS 的队列通常远大于 DFS 的栈):若最近的目标在第 \(i\) 步,BFS 最坏时可能在成功之前已经到达了几乎所有距离 \(i+1\) 的状态,因为每扩展一个距离为 \(i\) 的非目标状态,它的所有一步后继都会被放进 Q。把 A* 的想法和迭代加深结合就是 IDA*:把深度上限 \(i\) 换成 \(C^*(x') + \hat{G}^*(x')\),每一轮允许的总代价逐渐增大。
| 方法 | Q 的排序 | 第 12 行 | 最优? | 无限图上系统? |
|---|---|---|---|---|
| 广度优先 BFS | FIFO | 无事可做 | 步数最少 | 是 |
| 深度优先 DFS | LIFO(栈) | 无事可做 | 否 | 否 |
| Dijkstra | \(C(x)\) | 降低 \(C(x')\) 并重排 | 代价最小(\(l\ge0\)) | 是 |
| A* | \(C(x)+\hat{G}^*(x)\) | 同 Dijkstra | 是(\(\hat{G}^*\) 低估) | 是 |
| 最佳优先 | \(\hat{G}^*(x)\) | — | 否 | 否 |
| 迭代加深 | 深度受限的 LIFO | — | 步数最少 | 是 |
搜索实验室
下面的网格就是 Example 2.1(加上障碍和边界)。左边是搜索树的生长过程,右边是正在执行的伪代码行和 Q 的内容。勾选「逐行单步」可以一行一行地跟着图 2.4 走;勾选「显示数值」会在格子里显示 \(C(x)\)(或深度)。
- BFS vs DFS(空旷地面):BFS 的波前一圈圈扩张;DFS 一头扎到底,找到的计划有多绕?
- 步数最少 ≠ 代价最小(泥地带):BFS 会直接蹚过泥地;Dijkstra 和 A* 会绕路。比较两者的「计划代价」。
- Dijkstra vs A*:同一张图上比较扩展数。再把启发函数换成「零」,A* 的行为和 Dijkstra 完全一样。
- 贪心的代价(U 形陷阱,习题 2 的二维版本):Best-first 先冲进 U 形口袋,碰壁后才绕出来。和 A* 比扩展数与计划代价。
- 习题 18:在空旷地面上,A* 分别用曼哈顿和欧氏启发函数,哪个扩展得更少?为什么?(提示:在四连通网格上,哪个估计离真实代价 \(G^*\) 更近?)
- 高估会怎样:把启发函数换成「曼哈顿 × 3」,在泥地带上 A* 还能找到最优计划吗?
- 双向搜索:两棵树在哪里相遇?扩展数比单向 BFS 少多少?
- 无解:每个算法都必须把可达区域全部探索完,才能报告 FAILURE。
- 迭代加深:看它一轮轮推倒重来,最后的扩展总数和 BFS 比如何?在这种分支因子很小(≤ 4)、重复状态很多的网格上,它并不占优势——想想书里说它适合什么情况。
2.2.3 其他通用搜索模板:反向与双向
反向搜索 Backward search
2.2.2 节任何一种前向算法都可以做出反向版本(例如从 \(x_G\) 出发的反向 Dijkstra)。先假设只有一个目标状态 \(x_G\)。很多问题从 \(x_I\) 出发分支因子很大,这时从目标往回搜可能更高效。模板是图 2.6:把图 2.4 中的 \(x_I\) 与 \(x_G\) 对调,并用「反向的」转移函数。(目标是一个区域 \(X_G\) 时,第 1 行把所有 \(x_G\in X_G\) 都放进 Q 并标记为已访问即可。)
反向搜索经常要算:对某个 \(x'\),有哪些前驱状态 \(x\) 和动作 \(u\in U(x)\) 满足 \(x' = f(x,u)\)?为此定义所有状态-动作对的集合 \(U^{-1} = \{(x,u)\in X\times U \mid x\in X,\ u\in U(x)\}\)(它也是 \(f\) 的定义域),以及反向动作空间:
记 \(u^{-1}\) 为属于某个 \(U^{-1}(x')\) 的状态-动作对 \((x,u)\)。每个 \(u^{-1}\) 唯一确定一个 \(x\),于是有反向状态转移函数 \(x = f^{-1}(x', u^{-1})\),形式上和 \(x'=f(x,u)\) 非常像。
\(f^{-1}\) 就是把每条边反向。在反向图上做前向搜索 ≡ 在原图上做反向搜索。每个 \(u^{-1}\) 就是一条被反向的边。所以 2.2.2 节的所有变体都能直接搬到反向模板里——前提是 \(f^{-1}\) 已经定义好(通常最好预先计算出一个「反向」的 \(f\) 表示)。
双向搜索 Bidirectional search
前向、反向都有了,自然的想法是同时做:一棵树从 \(x_I\) 长,一棵树从 \(x_G\) 长(图 2.7),两棵树相遇即成功;任意一个队列耗尽即失败。很多问题上双向搜索能大幅减少探索量。Dijkstra 和 A* 都有双向版本,能得到最优解。最佳优先等变体很难保证两棵树快速相遇——它们可能挨得很近却连不上,需要额外的启发式把两棵树引到一起。甚至可以长任意多棵树,但连接它们会更复杂、更昂贵。
补充(非书中内容):为什么双向会省?在分支因子为 \(b\) 的树上,深度 \(d\) 的单向搜索要看约 \(b^d\) 个状态;两棵深度 \(d/2\) 的树合起来约 \(2b^{d/2}\) 个——指数级的差距。在二维网格上收益小得多(面积大约减半),可以在上面的实验室里验证。
2.2.4 搜索方法的统一视角
所有方法都在逐步构造一个搜索图 \(\mathcal{G}(V,E)\)——目前已探索的那部分状态转移图——并遵循同一个模板:
- 初始化:\(E\) 为空,\(V\) 包含一些起始状态:前向是 \(\{x_I\}\),反向是 \(\{x_G\}\),双向是 \(\{x_I, x_G\}\);多棵树就放更多。
- 选择顶点:选一个顶点 \(n_{cur}\in V\) 来扩展(通常靠优先队列),其状态记为 \(x_{cur}\)。
- 施加一个动作:前向得到 \(x_{new} = f(x,u)\);反向则是 \(x = f(x_{new}, u)\) 对某个 \(u\in U(x_{new})\)。
- 插入一条有向边:若通过了算法特定的测试,就加一条边(前向 \(x\to x_{new}\),反向 \(x_{new}\to x\));\(x_{new}\) 不在 \(V\) 中则一并插入。
- 检查是否有解:\(\mathcal{G}\) 中是否已有从 \(x_I\) 到 \(x_G\) 的路径?单棵树时很容易;两棵或更多树时可能很贵。
- 回到第 2 步,直到找到解或满足提前终止条件(报告失败)。
注意:图 2.4 对 Q 的一个元素尝试所有 \(k\) 个动作,相当于这个模板的 \(k\) 次迭代。这个模板会在 5.4 节再次出现——一大类基于采样的运动规划算法,就是把它从离散状态空间推广到连续的配置空间。
2.3 离散最优规划 Discrete Optimal Planning
现在不满足于随便哪个能到达目标的动作序列,而是要优化某个准则(时间、距离、能耗……)。相对 Formulation 2.1 有三个重要扩展:
- 用阶段下标(stage index)\(k\) 标记计划进行到了第几步;
- 引入代价泛函(cost functional),它像出租车计价器一样记录执行计划时累积了多少代价;
- 引入终止动作(termination action),直观上表示「该停了,把总代价定下来」。
讲解分三步:先解决固定长度的最优计划(2.3.1,值迭代),它本身用处不大,但比一般情况好懂得多;再推广到不定长度(2.3.2);最后解释值迭代和 Dijkstra 的密切关系(2.3.3)。
关于最大化还是最小化:代价是能量、开销时最小化更自然(机器人学、控制论的习惯);是奖励时(投资规划、大多数 AI 书)最大化更自然。本书一律最小化;想最大化,把代价乘以 −1、把 min 换成 max 即可。
固定长度的形式化
记 \(\pi_K\) 为一个 \(K\) 步计划,即动作序列 \((u_1, u_2, \ldots, u_K)\)。给定 \(\pi_K\) 和 \(x_I\),可以用 \(f\) 推出状态序列 \((x_1, \ldots, x_{K+1})\):\(x_1 = x_I\),\(x_{k+1} = f(x_k, u_k)\)。
- 直接继承 Formulation 2.1 的 \(X, U(x), f, x_I, X_G\),但这里假设 \(X\) 有限。
- 阶段数 \(K\):计划的确切长度(动作个数)。状态也带上阶段下标,例如 \(x_{k+1}\) 是施加 \(u_k\) 后得到的状态。
- 一个阶段可加(stage-additive)的代价(损失)泛函 \(L\),作用在 \(K\) 步计划上。记最终阶段 \(F = K+1\):
$$L(\pi_K) = \sum_{k=1}^{K} l(x_k,u_k) + l_F(x_F). \tag{2.4}$$\(l(x_k,u_k)\) 对每个 \(x_k\in X\)、\(u_k \in U(x_k)\) 给出一个实数。最终项 \(l_F\) 在求和之外:\(x_F \in X_G\) 时 \(l_F(x_F)=0\),否则 \(l_F(x_F) = \infty\)。
它把「必须到达目标」这个可行性约束变成了普通的优化:\(L(\pi_K)=\infty\) 表示不可行,\(L(\pi_K)<\infty\) 表示可行且代价为 \(L(\pi_K)\)。没到达 \(X_G\) 的计划被罚成无穷大,在任何最小化步骤中都会自动被淘汰。以后 \(l_F\) 让你糊涂的时候,记住它就是这个作用。
两个特例:令 \(l(x,u)\equiv 0\),就回到了只限 \(K\) 步计划的可行规划;令 \(l(x,u)\equiv 1\),就是最小化步数。还可以让 \(l_F(x)\) 在 \(X_G\) 内取不同的值,表示「不那么硬」的目标——这比可行规划一般得多,因为状态可以取任意值,而不只是「在/不在 \(X_G\) 里」。
2.3.1 固定长度的最优计划:值迭代
最朴素的办法:枚举所有长度为 \(K\) 的动作序列,挑代价最小的。这需要 \(O(|U|^K)\) 时间(想象 \(K\) 层嵌套循环),显然不行。
最优计划的一部分本身也是最优的。否则,把那一部分换成更便宜的,就得到了比「最优计划」还便宜的计划——矛盾。
这个原理直接导出一个迭代算法——值迭代(value iteration;这里的「值」指最优代价到目标或代价到达,所以也可以叫 cost-to-go iteration)。它能解决大量最优规划问题,包括不定长度计划、随机不确定性、不完美的状态测量等等。思路是在状态空间上迭代地计算最优代价函数。
反向值迭代
虽然从 \(x_I\) 往前推看起来更自然,但从 \(X_G\) 往回推在记号上更简单,所以先讲反向。关键是在 \(X\) 上构造最优代价到目标函数。对 \(k\) 从 1 到 \(F\),令 \(G^*_k\) 为执行最优计划时从阶段 \(k\) 到 \(F\) 累积的代价:
min 里面正是代价泛函 (2.4) 的最后 \(F-k\) 项。边界条件 \(k=F\) 时没有动作可施加,直接拿到最终代价:
现在推导递推式。把 (2.5) 的第一项从求和里拿出来,并把对 \(u_k\) 的最小化和对其余动作的最小化分开:
内层的 min 不影响 \(l(x_k,u_k)\)(它只依赖 \(u_k\)),所以可以把它提到外面:
内层的 min 恰好就是 \(G^*_{k+1}\) 的定义!代进去得到递推式:
右边只依赖 \(x_k\)、\(u_k\) 和 \(G^*_{k+1}\),所以由 \(G^*_{k+1}\) 算出 \(G^*_k\) 只要 \(O(|X||U|)\) 时间——这一步就叫一次值迭代。整个过程
共需 \(O(K|X||U|)\) 时间。\(G^*_1(x_I)\) 就是从 \(x_I\) 出发的最优代价;而且 \(G^*_1\) 顺便给出了从任何初始状态出发的最优代价(在 \(K\) 步内到不了 \(X_G\) 的状态是 \(\infty\))。每次迭代中有些状态得到 \(\infty\),只是因为不存在从 \(x_k\) 出发、\((K-k)\) 步到达 \(X_G\) 的计划。
怎么拿到计划本身?一种办法是在每个阶段、每个状态记下使 (2.11) 取到 min 的动作,需要 \(O(K|X|)\) 存储;2.3.2 节会讲怎么降到 \(O(|X|)\)。
Example 2.3:五状态例子
图 2.8:\(X=\{a,b,c,d,e\}\),\(K=4\),\(x_I=a\),\(X_G=\{d\}\)。给定 \(G^*_5\) 后要做四次值迭代,依次得到 \(G^*_4, G^*_3, G^*_2, G^*_1\)。算 \(G^*_4\) 时只有 \(b\) 和 \(c\) 得到有限值——只有它们能一步到 \(d\);算 \(G^*_3\) 时只有 \(G^*_4(b)=4\) 和 \(G^*_4(c)=1\) 有用——只有先到 \(b\) 或 \(c\) 的路径才可能在阶段 5 到达 \(d\)。(2.11) 的最小化总是选择「到达下一阶段某个顶点时总代价最低」的那个动作。
书里的图 2.10、2.11 把状态复制 \(K+1\) 份排成一列列(下面实验室里的「阶段图」),从左到右流动,就能一眼看出从任一初始状态到最终状态的所有走法——值迭代会自动选出最优路线。点阶段图里的任意圆圈,看看那个数字是怎么由 min{…} 算出来的。
正向值迭代
把上面的想法反过来,得到对称的方法:计算从初始阶段出发的最优代价到达函数。反向值迭代能同时找到从所有初始状态出发的最优计划(\(X_G\) 必须固定);正向值迭代则找到到达所有状态的最优计划(\(x_I\) 必须固定)。
正向时 \(l_F\) 不重要(可以在最后一次迭代用上,也可以对没有预定目标的问题干脆不用),但必须强制所有计划都从 \(x_I\) 出发。同样用加罚项的办法:令 \(l_I(x_I) = 0\),其余 \(l_I(x) = \infty\),
对中间阶段 \(k\in\{2,\ldots,K\}\),最优代价到达是
注意求和不包括 \(x_k\) 自己的项:\(l(x_k,u_k)\) 需要动作 \(u_k\),而它还没被选。递推时要从某个 \(x_{k-1}\) 出发、施加某个动作到达 \(x_k\)——这正好用上 2.2.3 节的反向状态转移方程 \(x_{k-1} = f^{-1}(x_k, u^{-1}_k)\):
其中 \(u_{k-1}\in U(x_{k-1})\) 是与 \(u^{-1}_k\) 对应的那个动作。同样 \(O(K|X||U|)\) 时间。最后一步得到 \(C^*_F\):它看起来和 \(k=1\) 时的 (2.5) 一样,只是用 \(l_I\) 代替了 \(l_F\),作用是只保留从 \(x_I\) 出发的计划。Example 2.4:在上面实验室里切到「固定 K · 正向」,对照图 2.12。
2.3.2 不定长度的最优计划
固定长度的值迭代可以很漂亮地推广到允许不同长度的计划,而且不再需要计划长度的上界——这才真正是 Formulation 2.1 的推广,因为可以尝试任意长的计划去到达 \(X_G\)。模型不再需要 \(K\),而是引入一个特殊动作 \(u_T\)。
- 继承 Formulation 2.1 的 \(X, U(x), f, x_I, X_G\),以及 Formulation 2.2 中阶段的概念。
- 阶段可加的代价泛函 \(L\) 作用于任意 \(K\) 步计划:\(L(\pi_K) = \sum_{k=1}^{K} l(x_k,u_k) + l_F(x_F)\) (2.17)。这里 \(K\) 不再是预先给定的常数,而随计划长度变化,所以 \(L\) 的定义域大得多。
- 每个 \(U(x)\) 都包含特殊的终止动作 \(u_T\)。一旦在 \(x_k\) 施加 \(u_T\),它就被永远重复施加,状态不再改变,也不再累积代价:对所有 \(i \ge k\),\(u_i = u_T\),\(x_i = x_k\),\(l(x_i,u_T)=0\)。
终止动作是允许不同长度计划的关键,全书还会反复出现。例如做 \(K=5\) 的值迭代,而问题有一个两步解 \((u_1,u_2)\):它等价于五步计划 \((u_1,u_2,u_T,u_T,u_T)\),状态和代价都一样。于是只要加上 \(u_T\),固定 \(K\) 的值迭代就自动优化了所有长度 \(\le K\) 的计划。
下一步是去掉对 \(K\) 的依赖:让反向值迭代一直跑下去,算完 \(G^*_1\) 后继续算 \(G^*_0, G^*_{-1},\ldots\)。反向值迭代根本不用 \(x_I\),所以不必关心计划从哪里开始;给所有阶段下标加上一个常数也不影响任何值,因为代价不依赖于阶段的具体编号——唯一重要的是迭代逐阶段、连续地往回推进。
迭代足够多次后,从每个能到达 \(X_G\) 的状态出发的最优计划都已知。此后代价到目标函数不再变化——称为平稳(stationary):对所有 \(i\le k\) 和所有 \(x\),\(G^*_{i-1}(x) = G^*_i(x)\)。这时阶段下标可以去掉,递推式变成
(补充:这个不动点方程在最优控制和强化学习里通常叫 Bellman 方程。)
值迭代会不会永远不平稳,每一轮都有值在变?
如果 \(l\) 有负值就可能出问题:若状态转移图里有一个总代价为负的环,就应该绕着它转无穷多圈,总代价趋于 \(-\infty\)。所以假设代价泛函定义得合理、不存在负环(否则优化模型本身就有毛病)。允许有负的 \(l\),只要没有负环;负环可以在值迭代之前检测出来并报告。
阶段下标不重要,所以约定 \(k=0\) 是最终阶段(反向值迭代从这里开始),\(G^*_0\) 直接由 \(l_F\) 得到;设到阶段 \(-K\) 时所有值平稳,记 \(G^* = G^*_{-K}\)。\(G^*(x)\) 就是从 \(x\) 到目标的最优代价。
从 \(G^*\) 恢复最优动作(不需要在迭代时存下 argmin):从任意 \(x\) 出发,最优的下一个动作是
施加 \(u^*\) 得到 \(x' = f(x,u^*)\),再对 \(x'\) 用 (2.19),如此直到进入 \(X_G\)。和 (2.11) 相比只是去掉了阶段下标、把 min 换成了 argmin。\(G^*\) 就像一个向导,从任何初始状态把系统最优地带进目标集合——这是第 8 章导航函数的一个特例。存储只要 \(O(|X|)\)。
正向版本同理:用 \(f^{-1}\) 和 \(l_I\),从 \(k=1\) 开始迭代到代价到达平稳,记 \(C^* = C^*_F\);\(u_T\) 保证早些时候已到达某状态的计划的代价被保留下来。正向时甚至不需要指定 \(X_G\)。对任意指定的 \(x_G\),从 \(x_G\) 往回用
一步步回溯到 \(x_I\),就得到最优动作序列(\(u'\) 是在 \(f^{-1}(x,u^{-1})\) 施加后得到 \(x\) 的那个动作)。
Example 2.5:不定长度的值迭代
再看 Example 2.3,但这次计划长度不固定。图 2.13 把 \(u_T\) 画成代价为 0 的虚线边。乍一看好像没有动力去选非终止动作——但别忘了,任何不终止于 \(x_G = d\) 的计划都会得到无穷大代价。
- 反向(图 2.14):几轮之后代价到目标就平稳了,此后从所有可达状态都执行 \(u_T\),不再累积代价。由于从 \(e\) 到不了 \(d\),\(G^*(e)=\infty\)。
- 用 (2.19) 恢复动作:从 \(a\) 出发,选通向 \(b\) 的动作,因为 \(2 + G^*(b) = 4\) 好于 \(2 + G^*(a) = 6\)(2 是动作代价)。从 \(b\) 出发选通向 \(c\) 的动作,总代价 \(1 + G^*(c) = 2\)1。再下一步到达 \(d\in X_G\),终止。
- 正向,取 \(x_I = b\)(图 2.15):某个有限值从一次迭代到下一次保持不变,就说明那里施加了终止动作。算出 \(C^*_4\) 时一切都已确定,最后一次迭代(\(C^*_5\))只是确认平稳,于是把最终的代价到达记作 \(C^*\)。2
2.3.3 Dijkstra 再探
到这里已经讲了两种动态规划:2.3.2 节的值迭代每一轮都扫遍整个状态空间;2.2.2 节的 Dijkstra 算法只流过状态空间一次,代价是要额外维护哪些状态是活跃的。
Dijkstra 可以从正向值迭代推出来:盯着 Example 2.5 的正向值迭代,找出「有意思的变化」究竟发生在哪里(Dijkstra 假设所有代价非负):
- 不可达的状态值一直是 \(\infty\) ⟷ Dijkstra 里的未访问状态;
- 最优代价到达已经平稳的状态 ⟷ 死亡状态;
- 其余状态已有一个有限的初始代价,但可能还会被降低一次或多次,直到最优 ⟷ 在 Q 里的状态。
两种算法里,未访问的状态都停在 \(\infty\);Dijkstra 正确地插入第一次到达的状态(把代价从 \(\infty\) 变成有限值),值的修改方式和值迭代一样;最后两者都得到平稳的最优代价到达 \(C^*\)。Dijkstra 很像值迭代,只是它高效地维护了「代价值还可能改变的那些状态」的集合。
既然 Dijkstra 这么聪明,为什么还要学值迭代?
Dijkstra 属于更广的一族——标号修正算法(label-correcting algorithms),它们都是对图 2.4 通用前向搜索做一点小修改得到的最优算法(图 2.16):
- 主要区别:找到更好的代价到达时,状态可以重新变成活跃,从而让其他状态的值也跟着改进。对 Dijkstra 和 A* 这不重要,它们每个状态只需访问一次;但标号修正算法对 Q 的任何排序都能得到最优解,包括 FIFO 和 LIFO,只要 \(X\) 有限。(\(X\) 无限时,系统性问题占主导:必须保证状态被重访足够多次,最终才能找到最优解。)
- 第 7 行用目标的代价 \(C(x_G)\) 剪枝:如果 \(x'\) 的新代价到达比 \(C(x_G)\) 还高,它不可能在改进到 \(x_G\) 的路径上,不必理会。第 10 行也不把 \(x_G\) 放进 Q,因为没必要考虑以 \(x_G\) 为中间状态的计划。所以它只适用于单个目标状态(可以改成多目标,但性能会下降)。
- 恢复计划:每次在第 7 行更新时存一个指针,或者用最终的 \(C^*\) 和 (2.20)。
下面的实验室切到了「Dijkstra / 标号修正」模式,默认载入一个自编的小图(不是书里的):从 \(a\) 到 \(d\) 有一条很贵的直达边,排在动作列表的最前面。先用「按 C(x)」跑一遍,再换成 FIFO,比较出队次数和复活次数:FIFO 会先按贵的代价处理 \(d\),等发现 \(a\to b\to c\to d\) 更便宜时,\(d\) 只好重新入队——但最后的 \(C^*(x_G)\) 一样。(图 2.8 太小,换任何排序都不会复活。)计数器里还对比了正向值迭代要做的候选计算次数。
2.4 用逻辑表述离散规划 Using Logic to Formulate Discrete Planning
很多我们想让计算机解的离散规划问题,状态空间大得惊人(比如 \(10^{100}\) 个状态)。于是人们花了大量精力构造问题的隐式编码,希望不必探索整个状态空间就能求解——这是贯穿全书的主题:要非常注意表示。一旦什么都显式给出了,很多规划问题看起来都很平凡。
逻辑表示一直很流行:一是历史原因,1950–1980 年代大部分 AI 研究都建立在它之上;二是它能非常紧凑地表示某些规划问题。可以把它想成压缩方案:像 010101010101… 这样的串可以压缩得很好,而随机比特串几乎无法压缩。规划也一样:有些问题有某种规律性,能紧凑地表达;有些则不可能。这也是几十年来出现了各种表示逻辑的原因。另外,大型规划系统最终要把完整计划交给并不关心内部细节的用户,逻辑表示便于给出「为什么这样一步步能达到目标」的解释。
缺点是:逻辑表示难以推广到连续空间、不可预测性、感知不确定性和多决策者。这就是本书主要用状态空间表示的原因——它容易扩展到书中所有问题。但理解逻辑表示仍然重要:它能帮你看清绝大部分离散规划研究与运动规划、微分约束规划等问题之间的联系——这些问题在历史上由不同的研究社区分别研究,却有很多共同的主题。
2.4.1 STRIPS 式表示
STRIPS(STanford Research Institute Problem Solver)被认为是最早的规划算法和表示之一。最初的表示用一阶逻辑,表达力强但技术困难很多,后来被限制为命题逻辑——和下面要讲的形式类似。STRIPS 式表示有很多变体,这里是其中一种:
- 一个有限非空的实例(instance)集合 \(I\)。
- 一个有限非空的谓词(predicate)集合 \(P\):它们是一个或多个实例上的二值(部分)函数。谓词作用在具体实例上就得到一个正字面量(positive literal);正字面量取逻辑否定就是负字面量(negative literal)。
- 一个有限非空的算子(operator)集合 \(O\),每个算子有:1) 前提条件(preconditions),必须成立才能施加的正/负字面量;2) 效果(effects),施加后成立的正/负字面量。
- 一个初始集合 \(S\),用正字面量表示。没出现在 \(S\) 里的正字面量,默认其负字面量在初始时成立。
- 一个目标集合 \(G\),由正字面量和负字面量组成。
- 实例刻画世界里所有不同的「东西」:书、车、树……
- 谓词是关于实例的基本性质或陈述,例如 Under(Book, Table)(书在桌子下面)、Under(Dirt, Rug)。它是部分函数:不一定允许把任意实例代入任意参数。
- 正字面量和它对应的负字面量(如 Under(Dirt, Rug) 与 ¬Under(Dirt, Rug))合称一个互补对(complementary pair)。
- 算子改变世界:前提条件必须全部满足;前提里没提到的互补对取什么值都不影响能否施加。施加后,世界按效果精确更新;没提到的互补对的真值保持不变。一个语句可以用变量同时定义多个算子,比如 Insert(i) 允许插入任意实例 \(i\in I\),这能大大缩短问题描述。
- 状态:给每个可能的互补对各选一个字面量(正或负)。\(S\) 只给出正字面量就确定了一个状态。\(G\) 实际上指的是一个状态集合——没被提到的互补对取正取负都算达成目标。
- 任务:找一个算子序列,依次施加(每次前提都满足),把初始状态变换成 \(G\) 中所有字面量都为真的状态。
Example 2.6:给手电筒装电池
实例 \(I\) = {Battery1, Battery2, Cap, Flashlight}(2.21)。两个谓词:On 只用于判断盖子是否盖在手电筒上,写作 On(Cap, Flashlight);In 有两种用法:In(Battery1, Flashlight)、In(Battery2, Flashlight)。像 In(Battery1, Battery1)、In(Flashlight, Battery2) 这种是没有意义的(也可以加进模型并恒为负,但很低效)——这就是「部分函数」的意思。
- 初始:\(S\) = {On(Cap, Flashlight)}(2.22)。于是两节电池都不在里面:¬In(Battery1, Flashlight)、¬In(Battery2, Flashlight)。
- 目标:\(G\) = {On(Cap, Flashlight), In(Battery1, Flashlight), In(Battery2, Flashlight)}(2.23):两节电池都要装进去,盖子也要盖上。
- 算子(图 2.18,Insert(i) 用变量写,所以三行定义了四个算子):
| 名称 | 前提条件 | 效果 |
|---|---|---|
| PlaceCap | {¬On(Cap, Flashlight)} | {On(Cap, Flashlight)} |
| RemoveCap | {On(Cap, Flashlight)} | {¬On(Cap, Flashlight)} |
| Insert(i) | {¬On(Cap, Flashlight), ¬In(i, Flashlight)} | {In(i, Flashlight)} |
步数最少的计划是 (RemoveCap, Insert(Battery1), Insert(Battery2), PlaceCap)(2.24):拿下盖子、装电池、盖上盖子。这个例子很简单,但加入更多实例(更多电池、更多手电筒、一堆与目标无关的物体)以及更多谓词和算子后,组合数就会多得让人崩溃。
复杂度。图搜索问题本身可以多项式时间求解,但这里输入不是状态转移图——用 Formulation 2.4 写的输入可能只用很少的实例、谓词和算子就描述了一张巨大的图。某种意义上模型被高度压缩了,更接近状态转移图的 Kolmogorov 复杂度(能完全恢复它的最短比特长度)。这让规划问题显得更难:简短的输入可以编码非常难的规划问题。在大多数形式化下,基于逻辑的规划是 NP-hard 的;具体难到什么程度(NP、PSPACE、EXPTIME……)取决于精确的问题条件:例如算子是事先固定的还是作为输入的一部分(后者难得多),算子的效果和前提里是否允许负字面量(两者都允许时一般更难)。
2.4.2 转换为状态空间表示
把 Formulation 2.4 和 Formulation 2.1 联系起来有两个好处:马上知道怎样把 2.2 节的搜索方法用在逻辑表示上;也能理解两种表示下算法复杂度的关系。
- 状态 = 位串。假设每个谓词有 \(k\) 个参数,每个参数都可以放任意实例,那么共有 \(|P|\,|I|^k\) 个互补对。在实例和谓词上规定一个线性顺序,每个互补对用一位表示:1 = 正字面量,0 = 负字面量。例如手电筒的状态 (On(Cap, Flashlight), ¬In(Battery1, Flashlight), In(Battery2, Flashlight)) 编码为 \(x = 101\)(2.25)。所有可区分的状态数是
$$2^{|P|\,|I|^k}. \tag{2.26}$$寥寥几个实例和谓词就能产生巨大的状态空间。2.2 节的搜索算法相对搜索图的大小看起来很高效,但相对 \(|P|\) 和 \(|I|\) 来说效率低得可怕——这正是 2.5 节那些利用表示结构的方法的动机。
- 初始状态 \(x_I\) 编码成一个串。目标集合 \(X_G\) 是与目标中正负字面量一致的所有串;可以在字母表里加一个「无所谓」符号 \(\delta\) 来压缩:正字面量写 1,负字面量写 0,其他写 \(\delta\),一个串就能表示任何用正负字面量表达的 \(X_G\)。
- 动作:\(U(x)\) 是前提被 \(x\) 满足的那些算子。不必预先对所有 \(x\) 算出 \(U(x)\),而是在搜索中第一次遇到 \(x\) 时再算。状态转移函数:从 \(x\) 出发,按算子的效果翻转相应的位,得到 \(f(x,u)\)。
- 这样 Formulation 2.1 的所有部件都从 Formulation 2.4 推出来了。扩展到最优规划也很直接:给每个算子(以及刻画当前状态的字面量集合)一个代价,就得到代价泛函里的 \(l(x,u)\),于是值迭代也能在逻辑表示上用,求出最优计划。
2.5 基于逻辑的规划方法 Logic-Based Planning Methods
几十年来,基于逻辑表示的规划积累了大量研究。这些方法通常利用表示特有的结构,并有大量来自实现经验的加速启发式。本节只讲几种最有影响的方法背后的主要思想,不讲具体的启发式。别忘了 2.2 节的搜索方法也适用:问题按 Formulation 2.4 给出后,状态转移图在搜索中逐步揭示——但搜索图相对问题描述可能巨大无比。早期的 STRIPS 规划算法大幅降低了分支因子,可惜不完备;本节的方法是在保持完备性的同时降低实际搜索复杂度的其他尝试。每种方法都有表现更好和更差的应用,不存在与具体用途无关的最佳选择。
2.5.1 在部分计划空间中搜索
不直接在 \(X\) 里搜索,而是不涉及具体状态地构造部分计划:利用算子表示逐步搭出部分计划,反复满足所需的子目标,同时保证不出现会破坏已有成果的冲突。一个部分计划 \(\sigma\) 定义为:
- 需要施加的算子集合 \(O_\sigma\)(变量可以已绑定也可以未绑定;同一个算子可以以不同变量值出现多次);
- \(O_\sigma\) 上的偏序关系 \(\prec_\sigma\):对某些算子对 \(o_1, o_2\) 规定 \(o_1 \prec_\sigma o_2\)(必须先于);
- 绑定约束集合 \(B_\sigma\):某些算子之间的变量必须取同一个值;
- 因果链接(causal link)集合 \(C_\sigma\),每个形如 \((o_1, l, o_2)\),表示 \(o_1\) 实现了字面量 \(l\),用来满足 \(o_2\) 的一个前提。
Example 2.7:沿用手电筒。\(O_\sigma\) = {RemoveCap, Insert(Battery1)},顺序约束 RemoveCap \(\prec_\sigma\) Insert(Battery1),因果链接 (RemoveCap, ¬On(Cap, Flashlight), Insert(Battery1))——RemoveCap 实现了 Insert(Battery1) 的前提 ¬On(Cap, Flashlight)。没有绑定约束。每个部分计划编码了一个计划集合:这里是所有 RemoveCap 出现在 Insert(Battery1) 之前、且不破坏因果链接的计划。
- 从任意一个初始部分计划 \(\sigma\) 开始。
- 在 \(\sigma\) 中找一个缺陷(flaw):1) 某个算子的前提还没被实现;或 2) \(O_\sigma\) 中某个算子威胁(threatens)\(C_\sigma\) 中的某条因果约束。
- 没有缺陷:报告 \(\sigma\) 是完整解,并算出一个满足所有约束的 \(O_\sigma\) 的线性顺序。
- 缺陷是某个算子 \(o_2\) 的未实现前提 \(l\):找一个实现它的算子 \(o_1\),记录新的因果约束 \((o_1, l, o_2)\)。
- 缺陷是对因果链接的威胁:更新 \(\prec_\sigma\) 引入适当的算子顺序,或更新 \(B_\sigma\) 以某种方式绑定算子,从而消除威胁。
- 回到第 2 步。
部分计划搜索图中的一个顶点是一个部分计划;一条边把一个部分计划扩展成另一个更接近完成的部分计划。模板虽然简单,性能却严重依赖初始计划的选择以及每轮修哪个缺陷。一个直接的推广是同时发展多个部分计划,每轮决定细化哪一个。早期这类方法看起来优势明显,但现在认为它们相比在状态空间里搜索的方法「竞争力不够」:没有对状态的显式引用,就更难设计针对应用的启发式;部分计划图的顶点维护和操作起来也比普通状态昂贵。
2.5.2 构造规划图
Blum 和 Furst 提出的规划图(planning graph)是一种编码「哪些状态可能可达」的强大数据结构。对 Formulation 2.4 做可达性分析:从初始状态做 BFS 展开状态转移图,能得到精确的可达信息、保证找到目标——但就输入表示而言,图的大小可能随阶段数指数增长。Blum 和 Furst 的想法是:构造一张小得多、只包含部分可达信息的图。规划图的大小是多项式的,对某些困难问题也能高效构造。代价是它只表示可能可达的状态——真正的可达集被过近似(overapproximated),但很多不可能的状态已经被排除,能在搜索中迅速剪掉不可能的选项。从规划图中提取计划在最坏情况下仍需指数时间(毕竟 Formulation 2.4 一般是 NP-hard 的),但在一些著名的规划基准上性能提升巨大。规划图也可以用来为特定问题设计搜索启发式。
定义与逐层构造
分层图:顶点被划分成一个层序列,边只连接相邻层。规划图是字面量层与算子层交替的分层图:
- 边:对每个算子 \(o_i\in O_i\),从它的每个前提 \(l_i \in L_i\) 连一条有向边到它;对每个字面量 \(l_i\in L_i\),从每个以它为效果的算子 \(o_{i-1}\in O_{i-1}\) 连一条边到它。
- 不允许变量:带变量的算子要展开成每种代入方式各一份(所以 Insert(i) 变成 I1、I2 两个算子)。
- 逐层构造:\(L_1\) 表示初始状态——\(S\) 里的正字面量,加上所有不在 \(S\) 里的正字面量的否定。第 \(i\) 步:\(O_i\) 是前提都 \(\subseteq L_i\) 的所有算子;\(L_{i+1}\) 是 \(O_i\) 中所有算子效果的并集。迭代到规划图稳定(\(O_{i+1}=O_i\) 且 \(L_{i+1}=L_i\))为止——这和 2.3.2 节值迭代的平稳非常像。
- 平凡算子(trivial operator):和终止动作 \(u_T\) 的作用类似,需要一个技巧让不同长度的计划被正确处理。对每个可能的字面量 \(l\),构造一个以 \(l\) 为唯一前提和唯一效果的平凡算子。这保证字面量一旦出现,就会在之后每一层字面量里一直保留,从而规划图会达到稳态。
互斥(mutex)条件
构造过程中,同一层内算子之间、字面量之间的冲突信息也被维护下来。冲突叫做互斥条件:一对字面量或一对算子不能同时被选,否则会导致某种冲突。每层都定义一个互斥关系。
| 对象 | 互斥条件(满足任一即互斥) |
|---|---|
| 一对算子 \(o, o' \in O_i\) |
1. 效果不一致(inconsistent effects):\(o\) 的某个效果是 \(o'\) 某个效果的否定; 2. 干扰(interference):\(o\) 的某个效果是 \(o'\) 某个前提的否定; 3. 需求冲突(competing needs):分别来自 \(o\) 和 \(o'\) 的一对前提在 \(L_i\) 中互斥。 |
| 一对字面量 \(l, l' \in L_i\) |
1. 互为否定:\(l\) 和 \(l'\) 是一个互补对; 2. 支持不一致(inconsistent support):\(O_{i-1}\) 中每一对分别实现 \(l\) 和 \(l'\) 的算子都互斥。(如果有一个算子同时实现两者,这一条就不成立。) 注意互斥的字面量对不一定是互补对。 |
由于互斥定义依赖于层,所以在构造规划图时逐层计算。
Example 2.8:手电筒的规划图(图 2.20)。\(L_1\) 表示初始状态;唯一可用的算子是 RemoveCap,所以 \(O_1\) 里是 RemoveCap 和三个平凡算子(用来保持 \(L_1\) 的字面量)。¬On(Cap, Flashlight) 的出现让装电池的算子可以施加——因为规划图不允许变量,出现两个不同的算子 I1、I2。盖子也可以重新盖上,所以 PlaceCap 进了 \(O_2\)。到 \(L_3\) 所有可能的字面量都出现了,\(O_3\) 包含所有可能的算子(含平凡算子)。最后 \(L_4 = L_3\),\(O_4\) 也会和 \(O_3\) 一样——规划图稳定了。在下图里逐层扩展,并点击节点查看它和谁互斥、为什么:
提取计划
- 规划图建到 \(L_i\) 后,就可以在里面搜索解。如果没找到解而且规划图已经稳定,那么问题一般无解;如果还没稳定,就再加一层 \(O_i\)、\(L_{i+1}\),再搜。扩展与搜索交替进行:要么某时报告一个解,要么在规划图稳定后正确地报告无解——算法是完备的。完备性的一个关键观察是:字面量层和算子层随 \(i\) 单调增大,互斥对单调减少,直到所有可能的冲突都被消解。
- 规划图给出的不是完全确定的计划,而是一个分层计划(layered plan)\((A_1, A_2, \ldots, A_k)\)(2.31),是部分计划的一种特殊形式:每个 \(A_i\) 是一组互不互斥的算子,可以以任意顺序施加而不改变结果;唯一的约束是 \(A_i\) 里的算子都要在 \(A_{i+1}\) 之前施加。手电筒的分层计划是 ({RemoveCap}, {Insert(Battery1), Insert(Battery2)}, {PlaceCap})(2.32),线性化后就是 (2.24)。复杂问题里实际执行的步数通常远多于规划图的层数:一层可以塞进多个不互斥的算子,所以层数很少的规划图也能考虑很长的计划。
- 搜索方式:从 \(L_i\) 开始做反向的 and/or 搜索。开始前,目标字面量 \(G\) 必须 \(\subseteq L_i\),并且两两不互斥,否则立即失败。对 \(G\) 中每个字面量,「或」:尝试能把它作为效果的算子;「与」:选中的算子的所有前提都必须被实现,这又引出下一层的「或」……递归直到回到 \(L_1\)。计算好的互斥关系能立即剪掉一些分支;常常还会检查三元组及更高阶组合是否一起互斥(即使它们两两不互斥),并用哈希表存起来,因为同样的信息会被多次查询。提取计划很昂贵,最坏情况可能指数时间(否则就为一个 NP-hard 问题找到了多项式算法)。
2.5.3 规划即可满足性
另一个有趣的思路:把规划问题转成一个巨大的布尔可满足性(SAT)问题——问是否存在一组变量赋值让某个布尔表达式为真。这样就能直接套用通用的 SAT 方法。最有名的是 Davis–Putnam 过程:通过依次尝试变量赋值、失败就回溯来做深度优先搜索;搜索中当前赋值能让表达式的大部分被消掉。它是完备的,也相当高效。实践中,随机局部搜索也是一个合理的替代。
构造方法:所有字面量和算子都带上阶段下标(同一个字面量出现在两个阶段就被看作两个不同的变量,类似情境演算 situation calculus,但那里下标可以是变量)。为了得到有限的布尔式,必须声明总阶段数:设 \(K\) 是可以施加算子的阶段数,第一阶段 \(k=1\),最终阶段 \(k=F=K+1\)。这是这个方法的一大缺点——求解前通常不知道 \(K\)。可以先假设一个小的 \(F\),表达式不可满足就逐渐增大;但如果问题无解,就会永远迭代下去。
布尔式是很多项的合取(逻辑与),这些项有五个来源:
- 初始状态:\(S\) 中所有字面量与不在 \(S\) 中的正字面量的否定的合取,都标上阶段 1。
- 目标状态:\(G\) 中所有字面量的合取,标上最终阶段 \(F = K+1\)。
- 算子编码:每个算子复制到每个阶段,\(o_k\) 表示在阶段 \(k\) 施加 \(o\):
$$\neg o_k \vee (p_1 \wedge p_2 \wedge \cdots \wedge p_m \wedge e_1 \wedge e_2 \wedge \cdots \wedge e_n), \tag{2.33}$$其中 \(p_1,\ldots,p_m\) 是 \(o_k\) 的前提(阶段 \(k\)),\(e_1,\ldots,e_n\) 是它的效果(阶段 \(k+1\))。意思是:「如果执行了 \(o_k\),那么前提和效果都成立」。
- 框架公理(frame axioms):编码「不是所施加算子效果的字面量,下一阶段保持不变」这个隐含假设。换个说法:如果字面量 \(l\) 变成了 \(\neg l\),那么一定执行了某个以 \(\neg l\) 为效果的算子。对每个阶段、每个字面量,设 \(l_k\) 和 \(l_{k+1}\) 是同一字面量的两个阶段版本:
$$(l_k \vee \neg l_{k+1}) \vee (o_{k,1} \vee o_{k,2} \vee \cdots \vee o_{k,j}), \tag{2.34}$$其中 \(o_{k,1},\ldots,o_{k,j}\) 是阶段 \(k\) 中以 \(l_{k+1}\) 为效果的算子。
- 完全排斥公理:每个阶段只施加一个算子。对每个阶段 \(k\) 和任意一对算子:\(\neg o_k \vee \neg o'_k\)(2.35),等价于 \(\neg(o_k \wedge o'_k)\)——「不能在同一阶段同时执行」。
可以证明:存在解计划,当且仅当得到的布尔式可满足。Example 2.9 给出手电筒问题的完整编码(取 \(F=5\),因为已经知道 (2.24) 的解;更大的 \(k\) 也能正确工作)。下面可以自己给变量赋值,实时看哪些项被违反;按阶段下标读出为真的算子变量,就是计划。(读原书的小提示:(2.40) 里的 O1k、O2k 指的就是 I1k、I2k。)
习题指南 Exercises
原书习题在 PDF 第 75–76 页(及其后的 Implementations)。下面是每题的定位和提示——先自己想,提示只帮你起步。
| 题号 | 内容 | 提示 / 用哪个工具 |
|---|---|---|
| 1 | 图 2.21:用反向 / 正向值迭代求平稳的代价函数(\(x_I=a\),目标 \(e\)) | 在任意一个值迭代实验室里把「问题」切换成图 2.21,下面会出现自测框。别忘了 \(d\) 有一条自环。 |
| 2 | 为最佳优先搜索构造二维网格上的「最坏情况」 | 搜索实验室的「U 形陷阱」就是一个起点:目标在一堵墙后面,口袋越深,浪费越多——让浪费随参数 \(k\) 任意增长。 |
| 3 | 代价改成 \(l(x_k,u_k,x_{k+1})\) | \(x_{k+1}\) 由 \(x_k,u_k\) 唯一确定。对比推导 (2.9)→(2.11) 的每一步:哪一步用到了「\(l\) 只依赖 \(x_k,u_k\)」? |
| 4 | 阶段相关的代价 \(l(x_k,u_k,k)\) | 固定长度时递推式几乎不变;想一想为什么 2.3.2 节「平移阶段下标不影响值」的论证在这里不再成立。 |
| 5 | 用终止状态 \(x_T\) 代替终止动作 | \(X' = X\cup\{x_T\}\);施加 \(u_T\) 就进入 \(x_T\);进入时付多少代价才能代替 \(l_F\)?\(x_T\) 自己需要什么样的动作和代价? |
| 6 | 反向 Dijkstra、它与反向值迭代的关系、反向 A* | 在反向图上做前向 Dijkstra;与 2.3.3 节「Dijkstra 是只维护有意思状态的正向值迭代」逐句对照。反向 A* 的启发函数应该估计什么? |
| 7 | 用 STRIPS 表示改写图 2.4 | 哪些东西要显式构造(当前状态的位串、\(U(x)\)),哪些只是隐式存在(整张状态转移图)?参考 2.4.2 节。 |
| 8 | 基于集合(而非位串)的表示 | 状态 = 为真的正字面量集合;施加算子 = 删掉一些、加入一些。 |
| 9 | 析取目标 | 多个可选的字面量集合 → 多个带 \(\delta\) 的串的并。 |
| 10 | 为手电筒加 Remove 算子(电池可能被另一节挡住) | 现在的模型不知道电池的先后顺序——需要新的谓词来描述「谁挡住了谁」。 |
| 11 | 用 STRIPS 表示滑块拼图 | 想想实例(方块、位置)、谓词(At、Blank、Adjacent……)和带变量的 Move 算子。 |
| 12 | Example 2.7 隐式编码的全部计划 | 先用「部分计划」组件看看只有 2 个算子时的线性化;再想:允许加入别的算子时,因果链接排除了什么? |
| 13 | 为什么 \(G\) 需要正负字面量,而 \(S\) 只需要正的? | \(S\) 描述的是一个状态(没提到的默认为负);\(G\) 描述的是一个集合(没提到的 = 无所谓)。 |
| 14–16 | 开灯问题:STRIPS 建模 → 规划图 → SAT | 可以照着手电筒的三个组件依次做。 |
| 17 | SAT 编码最坏要多少项 | 按五类分别数:初始、目标、每阶段每个算子、每阶段每个字面量(正反两个方向)、每阶段每对算子。可以先用 SAT 组件验证手电筒的总数是 70。 |
| 18–24 | 编程实现 | 起点:part1/code/ch2_discrete_planning.py(含 BFS/DFS/Dijkstra/A*/Best-first 和值迭代,并复现了书中的表)。18、19、20 可以先在搜索实验室里观察现象。 |
习题 1 的答案(做完再看)
本章速查表
| 概念 | 要点 |
|---|---|
| Formulation 2.1 | \(X\),\(U(x)\),\(x'=f(x,u)\),\(x_I\),\(X_G\);等价于一张有向状态转移图,通常隐式给出。 |
| 系统性 | 有限图:访问所有可达状态;无限图:迭代次数 → ∞ 时每个可达状态都被探索。 |
| 通用前向搜索 | 未访问 / 活跃(在 Q 中)/ 死亡;算法之间唯一的显著区别是 Q 的排序。 |
| BFS / DFS | FIFO / LIFO;都是 \(O(|V|+|E|)\);BFS 步数最少且系统,DFS 在无限图上不系统。 |
| Dijkstra | 按 \(C(x)\) 排序,\(l\ge0\);出队即最优;\(O(|V|\lg|V|+|E|)\)。 |
| A* / Best-first | 按 \(C+\hat{G}^*\)(\(\hat{G}^*\) 低估则最优)/ 只按 \(\hat{G}^*\)(贪心,不最优,不系统)。 |
| 反向 / 双向 | \(U^{-1}(x')\),\(x=f^{-1}(x',u^{-1})\):把边反向;双向在两棵树相遇时成功。 |
| 代价泛函 | \(L = \sum l(x_k,u_k) + l_F(x_F)\),\(l_F\) 把不可行罚成 ∞。 |
| 反向值迭代 | \(G^*_k(x) = \min_u\{l(x,u) + G^*_{k+1}(f(x,u))\}\),每轮 \(O(|X||U|)\)。 |
| 正向值迭代 | \(C^*_k(x) = \min_{u^{-1}}\{C^*_{k-1}(x_{prev}) + l(x_{prev},u)\}\),用 \(l_I\) 强制从 \(x_I\) 出发。 |
| 不定长度 | 终止动作 \(u_T\)(原地不动、代价 0);迭代到平稳:\(G^*(x) = \min_u\{l(x,u)+G^*(f(x,u))\}\);用 argmin 恢复计划。 |
| Dijkstra 再探 | = 只维护「值还会变的状态」的正向值迭代;标号修正对任意 Q 排序都最优(\(X\) 有限)。 |
| STRIPS | 实例、谓词、字面量、算子(前提/效果)、\(S\)(正字面量)、\(G\)(正负字面量);状态数 \(2^{|P||I|^k}\)。 |
| 部分计划 | \((O_\sigma, \prec_\sigma, B_\sigma, C_\sigma)\);缺陷 = 未实现的前提 / 对因果链接的威胁。 |
| 规划图 | \(L_1,O_1,L_2,\ldots\);平凡算子;算子互斥 3 条、字面量互斥 2 条;分层计划;扩展与提取交替,完备。 |
| SAT | 五类项:初始、目标、算子编码、框架公理、完全排斥;须预先固定 \(K\)。 |