Planning Algorithms 学习站 首页 › Part I › 第 2 章 离散规划

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\) 给出:

$$x' = f(x, u). \tag{2.1}$$

\(U(x)\) 是在状态 \(x\) 可以施加的所有动作,称为动作空间。不同状态的 \(U(x)\) 不一定互不相交——同一个动作可能在很多状态下都能用,所以定义所有动作的集合

$$U = \bigcup_{x \in X} U(x). \tag{2.2}$$

再给定一个目标集合 \(X_G \subset X\)。规划算法的任务:找到一个有限的动作序列,把初始状态 \(x_I\) 变换到 \(X_G\) 中的某个状态。

Formulation 2.1(离散可行规划)
  1. 一个非空的状态空间 \(X\),是有限或可数无限的状态集合。
  2. 对每个状态 \(x \in X\),一个有限的动作空间 \(U(x)\)。
  3. 一个状态转移函数 \(f\):对每个 \(x\in X\)、\(u \in U(x)\) 给出 \(f(x,u)\in X\);由它得到状态转移方程 \(x' = f(x,u)\)。
  4. 一个初始状态 \(x_I \in X\)。
  5. 一个目标集合 \(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 机)动作 = 状态机的输入,输出就是报告当前状态。可行规划 = 是否存在一串输入,使状态机最终报告想要的输出。规划算法知道机器转移的完整说明,并且随时能读出当前状态。
确定性有限自动机 DFADFA 的接受状态 ↔ 目标集合 \(X_G\);输入串 ↔ 动作序列。可行规划 ⟺ 是否存在一个被 DFA 接受的输入串 ⟺ DFA 的语言是否非空。
网格例子里 \(X = \mathbb{Z}^2\) 是无限集合,它怎么能作为算法的「输入」?
输入的不是图本身,而是生成图的规则:动作集合 \(U\) 和公式 \(f(x,u)=x+u\)。这只需要有限长度就能写下来。搜索时图被逐步展开,只有被访问到的那一小部分才真的存在于内存中。

2.2 搜索可行计划 Searching for Feasible Plans

本节的方法其实就是图搜索算法,只不过要记住:状态转移图是通过施加动作逐步揭示的,而不是事先完整给出的。所以可以把本节看成「从规划的视角重新审视图搜索」。

系统性(systematic)

任何搜索算法都有一个重要要求:系统性。

注意

反过来不成立:一个算法即使朝多个方向扩展、甚至按某种波前扩展,也可能不系统。每个算法都要具体分析。好消息是:图有限时情况简单得多——几乎任何搜索算法只要标记已访问状态、不无限重访,就是系统的。

2.2.1 通用前向搜索

图 2.4 · FORWARD SEARCH(通用前向搜索模板)
Q.Insert(xI) and mark xI as visited while Q not empty do x ← Q.GetFirst() if x ∈ XG return SUCCESS forall u ∈ U(x) x′ ← f(x, u) if x′ not visited Mark x′ as visited Q.Insert(x′) else Resolve duplicate x′ return FAILURE

搜索过程中的任何时刻,状态分为三类:

类别含义初始时
未访问 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 省略了一些实际中很重要的细节:

  1. 目标测试(第 4 行)有多快?取决于状态空间的大小以及 \(x\) 和 \(X_G\) 的具体表示。
  2. 怎么得到计划,而不只是「有/没有」?在第 7 行之后给 \(x'\) 记一个指向父节点 \(x\) 的指针(顺便记下用的动作)。找到目标后沿指针回溯到 \(x_I\) 就恢复出计划。
  3. 怎么判断 \(x'\) 是否访问过(第 8、9 行)?如果状态转移图恰好是一棵树,就根本不用判断——这很少见,但遇到就太好了。如果状态都在网格上,用查找表 \(O(1)\) 就能判断。一般情况下可能要和 Q 中及所有死亡状态比较;状态表示很长时代价很高。好的哈希方案能大大缓解。也可以干脆允许重复状态,但代价可能远超收益:即使图很小,也可能跑出指数时间,甚至在有限图上不终止。
  4. 第 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)\)。)

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\) 的总代价估计」。

补充(书中没有展开的细节)

像图 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 行最优?无限图上系统?
广度优先 BFSFIFO无事可做步数最少是
深度优先 DFSLIFO(栈)无事可做否否
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)\)(或深度)。

建议的实验(每次跑完都会自动记到「对比记录」里)
  1. BFS vs DFS(空旷地面):BFS 的波前一圈圈扩张;DFS 一头扎到底,找到的计划有多绕?
  2. 步数最少 ≠ 代价最小(泥地带):BFS 会直接蹚过泥地;Dijkstra 和 A* 会绕路。比较两者的「计划代价」。
  3. Dijkstra vs A*:同一张图上比较扩展数。再把启发函数换成「零」,A* 的行为和 Dijkstra 完全一样。
  4. 贪心的代价(U 形陷阱,习题 2 的二维版本):Best-first 先冲进 U 形口袋,碰壁后才绕出来。和 A* 比扩展数与计划代价。
  5. 习题 18:在空旷地面上,A* 分别用曼哈顿和欧氏启发函数,哪个扩展得更少?为什么?(提示:在四连通网格上,哪个估计离真实代价 \(G^*\) 更近?)
  6. 高估会怎样:把启发函数换成「曼哈顿 × 3」,在泥地带上 A* 还能找到最优计划吗?
  7. 双向搜索:两棵树在哪里相遇?扩展数比单向 BFS 少多少?
  8. 无解:每个算法都必须把可达区域全部探索完,才能报告 FAILURE。
  9. 迭代加深:看它一轮轮推倒重来,最后的扩展总数和 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}(x') = \{(x,u) \in U^{-1} \mid x' = f(x,u)\}. \tag{2.3}$$

记 \(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)\)——目前已探索的那部分状态转移图——并遵循同一个模板:

  1. 初始化:\(E\) 为空,\(V\) 包含一些起始状态:前向是 \(\{x_I\}\),反向是 \(\{x_G\}\),双向是 \(\{x_I, x_G\}\);多棵树就放更多。
  2. 选择顶点:选一个顶点 \(n_{cur}\in V\) 来扩展(通常靠优先队列),其状态记为 \(x_{cur}\)。
  3. 施加一个动作:前向得到 \(x_{new} = f(x,u)\);反向则是 \(x = f(x_{new}, u)\) 对某个 \(u\in U(x_{new})\)。
  4. 插入一条有向边:若通过了算法特定的测试,就加一条边(前向 \(x\to x_{new}\),反向 \(x_{new}\to x\));\(x_{new}\) 不在 \(V\) 中则一并插入。
  5. 检查是否有解:\(\mathcal{G}\) 中是否已有从 \(x_I\) 到 \(x_G\) 的路径?单棵树时很容易;两棵或更多树时可能很贵。
  6. 回到第 2 步,直到找到解或满足提前终止条件(报告失败)。

注意:图 2.4 对 Q 的一个元素尝试所有 \(k\) 个动作,相当于这个模板的 \(k\) 次迭代。这个模板会在 5.4 节再次出现——一大类基于采样的运动规划算法,就是把它从离散状态空间推广到连续的配置空间。

2.3 离散最优规划 Discrete Optimal Planning

现在不满足于随便哪个能到达目标的动作序列,而是要优化某个准则(时间、距离、能耗……)。相对 Formulation 2.1 有三个重要扩展:

  1. 用阶段下标(stage index)\(k\) 标记计划进行到了第几步;
  2. 引入代价泛函(cost functional),它像出租车计价器一样记录执行计划时累积了多少代价;
  3. 引入终止动作(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.2(离散固定长度最优规划)
  1. 直接继承 Formulation 2.1 的 \(X, U(x), f, x_I, X_G\),但这里假设 \(X\) 有限。
  2. 阶段数 \(K\):计划的确切长度(动作个数)。状态也带上阶段下标,例如 \(x_{k+1}\) 是施加 \(u_k\) 后得到的状态。
  3. 一个阶段可加(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_F\) 只是一个小技巧

它把「必须到达目标」这个可行性约束变成了普通的优化:\(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\) 累积的代价:

$$G^*_k(x_k) = \min_{u_k,\ldots,u_K}\left\{ \sum_{i=k}^{K} l(x_i,u_i) + l_F(x_F) \right\}. \tag{2.5}$$

min 里面正是代价泛函 (2.4) 的最后 \(F-k\) 项。边界条件 \(k=F\) 时没有动作可施加,直接拿到最终代价:

$$G^*_F(x_F) = l_F(x_F). \tag{2.6}$$

现在推导递推式。把 (2.5) 的第一项从求和里拿出来,并把对 \(u_k\) 的最小化和对其余动作的最小化分开:

$$G^*_k(x_k) = \min_{u_k}\left\{ \min_{u_{k+1},\ldots,u_K}\left\{ l(x_k,u_k) + \sum_{i=k+1}^{K} l(x_i,u_i) + l_F(x_F)\right\}\right\}. \tag{2.9}$$

内层的 min 不影响 \(l(x_k,u_k)\)(它只依赖 \(u_k\)),所以可以把它提到外面:

$$G^*_k(x_k) = \min_{u_k}\left\{ l(x_k,u_k) + \min_{u_{k+1},\ldots,u_K}\left\{ \sum_{i=k+1}^{K} l(x_i,u_i) + l_F(x_F)\right\}\right\}. \tag{2.10}$$

内层的 min 恰好就是 \(G^*_{k+1}\) 的定义!代进去得到递推式:

$$G^*_k(x_k) = \min_{u_k}\Big\{ l(x_k,u_k) + G^*_{k+1}(x_{k+1}) \Big\},\qquad x_{k+1} = f(x_k,u_k). \tag{2.11}$$

右边只依赖 \(x_k\)、\(u_k\) 和 \(G^*_{k+1}\),所以由 \(G^*_{k+1}\) 算出 \(G^*_k\) 只要 \(O(|X||U|)\) 时间——这一步就叫一次值迭代。整个过程

$$G^*_F \to G^*_K \to G^*_{K-1} \to \cdots \to G^*_k \to G^*_{k-1} \to \cdots \to G^*_2 \to G^*_1 \tag{2.12}$$

共需 \(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\),

$$C^*_1(x_1) = l_I(x_1). \tag{2.13}$$

对中间阶段 \(k\in\{2,\ldots,K\}\),最优代价到达是

$$C^*_k(x_k) = \min_{u_1,\ldots,u_{k-1}}\left\{ l_I(x_1) + \sum_{i=1}^{k-1} l(x_i,u_i) \right\}. \tag{2.14}$$

注意求和不包括 \(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)\):

$$C^*_k(x_k) = \min_{u^{-1}_k \in U^{-1}(x_k)}\Big\{ C^*_{k-1}(x_{k-1}) + l(x_{k-1},u_{k-1}) \Big\}, \tag{2.16}$$

其中 \(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.3(离散最优规划)
  1. 继承 Formulation 2.1 的 \(X, U(x), f, x_I, X_G\),以及 Formulation 2.2 中阶段的概念。
  2. 阶段可加的代价泛函 \(L\) 作用于任意 \(K\) 步计划:\(L(\pi_K) = \sum_{k=1}^{K} l(x_k,u_k) + l_F(x_F)\) (2.17)。这里 \(K\) 不再是预先给定的常数,而随计划长度变化,所以 \(L\) 的定义域大得多。
  3. 每个 \(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)\)。这时阶段下标可以去掉,递推式变成

$$G^*(x) = \min_{u\in U(x)}\Big\{ l(x,u) + G^*(f(x,u)) \Big\}. \tag{2.18}$$

(补充:这个不动点方程在最优控制和强化学习里通常叫 Bellman 方程。)

值迭代会不会永远不平稳,每一轮都有值在变?
如果所有 \(l(x,u)\ge 0\),不会。对任意固定的 \(K\),当然存在更长的计划,但最优计划不会无限变长:每个状态要么有到达 \(X_G\) 的有限代价计划,要么根本无解。在所有能到达 \(X_G\) 的状态中,取它们最优计划的最大步数——这就是迭代次数的上界。之后的迭代只会考虑更差的解(或者由于 \(u_T\) 和下标平移而等价的解)。
如果 \(l\) 有负值就可能出问题:若状态转移图里有一个总代价为负的环,就应该绕着它转无穷多圈,总代价趋于 \(-\infty\)。所以假设代价泛函定义得合理、不存在负环(否则优化模型本身就有毛病)。允许有负的 \(l\),只要没有负环;负环可以在值迭代之前检测出来并报告。

阶段下标不重要,所以约定 \(k=0\) 是最终阶段(反向值迭代从这里开始),\(G^*_0\) 直接由 \(l_F\) 得到;设到阶段 \(-K\) 时所有值平稳,记 \(G^* = G^*_{-K}\)。\(G^*(x)\) 就是从 \(x\) 到目标的最优代价。

从 \(G^*\) 恢复最优动作(不需要在迭代时存下 argmin):从任意 \(x\) 出发,最优的下一个动作是

$$u^* = \operatorname*{argmin}_{u\in U(x)} \Big\{ l(x,u) + G^*(f(x,u)) \Big\}. \tag{2.19}$$

施加 \(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\) 往回用

$$\operatorname*{argmin}_{u^{-1}\in U^{-1}(x)} \Big\{ C^*(f^{-1}(x,u^{-1})) + l(f^{-1}(x,u^{-1}), u') \Big\} \tag{2.20}$$

一步步回溯到 \(x_I\),就得到最优动作序列(\(u'\) 是在 \(f^{-1}(x,u^{-1})\) 施加后得到 \(x\) 的那个动作)。

Example 2.5:不定长度的值迭代

再看 Example 2.3,但这次计划长度不固定。图 2.13 把 \(u_T\) 画成代价为 0 的虚线边。乍一看好像没有动力去选非终止动作——但别忘了,任何不终止于 \(x_G = d\) 的计划都会得到无穷大代价。

2.3.3 Dijkstra 再探

到这里已经讲了两种动态规划:2.3.2 节的值迭代每一轮都扫遍整个状态空间;2.2.2 节的 Dijkstra 算法只流过状态空间一次,代价是要额外维护哪些状态是活跃的。

Dijkstra 可以从正向值迭代推出来:盯着 Example 2.5 的正向值迭代,找出「有意思的变化」究竟发生在哪里(Dijkstra 假设所有代价非负):

两种算法里,未访问的状态都停在 \(\infty\);Dijkstra 正确地插入第一次到达的状态(把代价从 \(\infty\) 变成有限值),值的修改方式和值迭代一样;最后两者都得到平稳的最优代价到达 \(C^*\)。Dijkstra 很像值迭代,只是它高效地维护了「代价值还可能改变的那些状态」的集合。

既然 Dijkstra 这么聪明,为什么还要学值迭代?
一是有些问题里维护有序队列太贵,值迭代反而更高效。更重要的是,值迭代能轻松推广到大得多的问题类:连续状态空间上的最优规划(8.5.2、14.5 节)、随机最优规划(10.2 节)、动态博弈均衡(10.5 节)。有时仍能通过只关注「有意思的」区域得到类 Dijkstra 的算法,但模型越复杂,维护这个区域就越低效甚至不可能。所以两种算法都要理解,才能判断哪个更适合手上的问题。

Dijkstra 属于更广的一族——标号修正算法(label-correcting algorithms),它们都是对图 2.4 通用前向搜索做一点小修改得到的最优算法(图 2.16):

图 2.16 · FORWARD LABEL CORRECTING(xG)
Set C(x) = ∞ for all x ≠ xI, and set C(xI) = 0 Q.Insert(xI) while Q not empty do x ← Q.GetFirst() forall u ∈ U(x) x′ ← f(x, u) if C(x) + l(x, u) < min{C(x′), C(xG)} then C(x′) ← C(x) + l(x, u) if x′ ≠ xG then Q.Insert(x′)

下面的实验室切到了「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 式表示有很多变体,这里是其中一种:

Formulation 2.4(STRIPS 式规划)
  1. 一个有限非空的实例(instance)集合 \(I\)。
  2. 一个有限非空的谓词(predicate)集合 \(P\):它们是一个或多个实例上的二值(部分)函数。谓词作用在具体实例上就得到一个正字面量(positive literal);正字面量取逻辑否定就是负字面量(negative literal)。
  3. 一个有限非空的算子(operator)集合 \(O\),每个算子有:1) 前提条件(preconditions),必须成立才能施加的正/负字面量;2) 效果(effects),施加后成立的正/负字面量。
  4. 一个初始集合 \(S\),用正字面量表示。没出现在 \(S\) 里的正字面量,默认其负字面量在初始时成立。
  5. 一个目标集合 \(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) 这种是没有意义的(也可以加进模型并恒为负,但很低效)——这就是「部分函数」的意思。

名称前提条件效果
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 节的搜索方法用在逻辑表示上;也能理解两种表示下算法复杂度的关系。

2.5 基于逻辑的规划方法 Logic-Based Planning Methods

几十年来,基于逻辑表示的规划积累了大量研究。这些方法通常利用表示特有的结构,并有大量来自实现经验的加速启发式。本节只讲几种最有影响的方法背后的主要思想,不讲具体的启发式。别忘了 2.2 节的搜索方法也适用:问题按 Formulation 2.4 给出后,状态转移图在搜索中逐步揭示——但搜索图相对问题描述可能巨大无比。早期的 STRIPS 规划算法大幅降低了分支因子,可惜不完备;本节的方法是在保持完备性的同时降低实际搜索复杂度的其他尝试。每种方法都有表现更好和更差的应用,不存在与具体用途无关的最佳选择。

2.5.1 在部分计划空间中搜索

不直接在 \(X\) 里搜索,而是不涉及具体状态地构造部分计划:利用算子表示逐步搭出部分计划,反复满足所需的子目标,同时保证不出现会破坏已有成果的冲突。一个部分计划 \(\sigma\) 定义为:

  1. 需要施加的算子集合 \(O_\sigma\)(变量可以已绑定也可以未绑定;同一个算子可以以不同变量值出现多次);
  2. \(O_\sigma\) 上的偏序关系 \(\prec_\sigma\):对某些算子对 \(o_1, o_2\) 规定 \(o_1 \prec_\sigma o_2\)(必须先于);
  3. 绑定约束集合 \(B_\sigma\):某些算子之间的变量必须取同一个值;
  4. 因果链接(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) 之前、且不破坏因果链接的计划。

图 2.19 · PLAN-SPACE PLANNING(找缺陷、修缺陷)
  1. 从任意一个初始部分计划 \(\sigma\) 开始。
  2. 在 \(\sigma\) 中找一个缺陷(flaw):1) 某个算子的前提还没被实现;或 2) \(O_\sigma\) 中某个算子威胁(threatens)\(C_\sigma\) 中的某条因果约束。
  3. 没有缺陷:报告 \(\sigma\) 是完整解,并算出一个满足所有约束的 \(O_\sigma\) 的线性顺序。
  4. 缺陷是某个算子 \(o_2\) 的未实现前提 \(l\):找一个实现它的算子 \(o_1\),记录新的因果约束 \((o_1, l, o_2)\)。
  5. 缺陷是对因果链接的威胁:更新 \(\prec_\sigma\) 引入适当的算子顺序,或更新 \(B_\sigma\) 以某种方式绑定算子,从而消除威胁。
  6. 回到第 2 步。

部分计划搜索图中的一个顶点是一个部分计划;一条边把一个部分计划扩展成另一个更接近完成的部分计划。模板虽然简单,性能却严重依赖初始计划的选择以及每轮修哪个缺陷。一个直接的推广是同时发展多个部分计划,每轮决定细化哪一个。早期这类方法看起来优势明显,但现在认为它们相比在状态空间里搜索的方法「竞争力不够」:没有对状态的显式引用,就更难设计针对应用的启发式;部分计划图的顶点维护和操作起来也比普通状态昂贵。

2.5.2 构造规划图

Blum 和 Furst 提出的规划图(planning graph)是一种编码「哪些状态可能可达」的强大数据结构。对 Formulation 2.4 做可达性分析:从初始状态做 BFS 展开状态转移图,能得到精确的可达信息、保证找到目标——但就输入表示而言,图的大小可能随阶段数指数增长。Blum 和 Furst 的想法是:构造一张小得多、只包含部分可达信息的图。规划图的大小是多项式的,对某些困难问题也能高效构造。代价是它只表示可能可达的状态——真正的可达集被过近似(overapproximated),但很多不可能的状态已经被排除,能在搜索中迅速剪掉不可能的选项。从规划图中提取计划在最坏情况下仍需指数时间(毕竟 Formulation 2.4 一般是 NP-hard 的),但在一些著名的规划基准上性能提升巨大。规划图也可以用来为特定问题设计搜索启发式。

定义与逐层构造

分层图:顶点被划分成一个层序列,边只连接相邻层。规划图是字面量层与算子层交替的分层图:

$$(L_1, O_1, L_2, O_2, L_3, O_3, \ldots, L_k, O_k, L_{k+1}). \tag{2.30}$$

互斥(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\) 一样——规划图稳定了。在下图里逐层扩展,并点击节点查看它和谁互斥、为什么:

提取计划

2.5.3 规划即可满足性

另一个有趣的思路:把规划问题转成一个巨大的布尔可满足性(SAT)问题——问是否存在一组变量赋值让某个布尔表达式为真。这样就能直接套用通用的 SAT 方法。最有名的是 Davis–Putnam 过程:通过依次尝试变量赋值、失败就回溯来做深度优先搜索;搜索中当前赋值能让表达式的大部分被消掉。它是完备的,也相当高效。实践中,随机局部搜索也是一个合理的替代。

构造方法:所有字面量和算子都带上阶段下标(同一个字面量出现在两个阶段就被看作两个不同的变量,类似情境演算 situation calculus,但那里下标可以是变量)。为了得到有限的布尔式,必须声明总阶段数:设 \(K\) 是可以施加算子的阶段数,第一阶段 \(k=1\),最终阶段 \(k=F=K+1\)。这是这个方法的一大缺点——求解前通常不知道 \(K\)。可以先假设一个小的 \(F\),表达式不可满足就逐渐增大;但如果问题无解,就会永远迭代下去。

布尔式是很多项的合取(逻辑与),这些项有五个来源:

  1. 初始状态:\(S\) 中所有字面量与不在 \(S\) 中的正字面量的否定的合取,都标上阶段 1。
  2. 目标状态:\(G\) 中所有字面量的合取,标上最终阶段 \(F = K+1\)。
  3. 算子编码:每个算子复制到每个阶段,\(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\),那么前提和效果都成立」。
  4. 框架公理(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}\) 为效果的算子。
  5. 完全排斥公理:每个阶段只施加一个算子。对每个阶段 \(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 算子。
12Example 2.7 隐式编码的全部计划先用「部分计划」组件看看只有 2 个算子时的线性化;再想:允许加入别的算子时,因果链接排除了什么?
13为什么 \(G\) 需要正负字面量,而 \(S\) 只需要正的?\(S\) 描述的是一个状态(没提到的默认为负);\(G\) 描述的是一个集合(没提到的 = 无所谓)。
14–16开灯问题:STRIPS 建模 → 规划图 → SAT可以照着手电筒的三个组件依次做。
17SAT 编码最坏要多少项按五类分别数:初始、目标、每阶段每个算子、每阶段每个字面量(正反两个方向)、每阶段每对算子。可以先用 SAT 组件验证手电筒的总数是 70。
18–24编程实现起点:part1/code/ch2_discrete_planning.py(含 BFS/DFS/Dijkstra/A*/Best-first 和值迭代,并复现了书中的表)。18、19、20 可以先在搜索实验室里观察现象。
习题 1 的答案(做完再看)
反向(\(X_G=\{e\}\)):\(G^* = (a,b,c,d,e) = (10, 8, 4, 1, 0)\)。正向(\(x_I=a\)):\(C^* = (0, 2, 6, 9, 10)\)。最优计划 \(a\to b\to c\to d\to e\),代价 10:直接走 \(c\to e\)(代价 7)比绕 \(c\to d\to e\)(3+1)贵。

本章速查表

概念要点
Formulation 2.1\(X\),\(U(x)\),\(x'=f(x,u)\),\(x_I\),\(X_G\);等价于一张有向状态转移图,通常隐式给出。
系统性有限图:访问所有可达状态;无限图:迭代次数 → ∞ 时每个可达状态都被探索。
通用前向搜索未访问 / 活跃(在 Q 中)/ 死亡;算法之间唯一的显著区别是 Q 的排序。
BFS / DFSFIFO / 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\)。

1 原书这里印成了「\(1 + G^*(c) = 1\)」。按图 2.14,\(G^*(c)=1\),所以应为 2;这不影响选择,因为另一个选项 \(4 + G^*(d) = 4\) 更大。↩

2 原书说「算出 \(C^*_3\) 之后一切都已确定」,但对照图 2.15,\(C^*_3(e)=5\)、\(C^*_4(e)=3\),所以应是算出 \(C^*_4\) 之后。可以在实验室的「不定长 · 正向」模式里亲自验证。↩