图1-3　积木世界的场景。Shrdlu（Winograd, 1972）刚刚完成了一个命令——“找到一块比你所持有的积木块更高的积木块，并把它放进盒子里”

图2-16　表示状态及其之间转移的3种方法：（a）原子表示一个状态（如B或C）是没有内部结构的黑盒；（b）因子化表示状态由属性值向量组成，值可以是布尔值、实值或一组固定符号中的一个；（c）结构化表示状态包括对象，每个对象可能有自己的属性以及与其他对象的关系

图3-4　3棵部分搜索树，用于寻找从Arad到Bucharest的路线。已扩展节点用淡紫色和粗体字母表示；边界上已生成但未被扩展的节点用绿色表示；对应于这两种类型节点的状态集被称为已达。接下来可能生成的节点用虚线表示。注意，在最下面的树中，有一个从Arad到Sibiu再到Arad的环，这不可能是最优路径，因此搜索不应该从那里继续

图3-4　3棵部分搜索树，用于寻找从Arad到Bucharest的路线。已扩展节点用淡紫色和粗体字母表示；边界上已生成但未被扩展的节点用绿色表示；对应于这两种类型节点的状态集被称为已达。接下来可能生成的节点用虚线表示。注意，在最下面的树中，有一个从Arad到Sibiu再到Arad的环，这不可能是最优路径，因此搜索不应该从那里继续（续）

图3-5　由图3-1中的罗马尼亚问题的图搜索生成的搜索树序列。在每一阶段，我们扩展边界上的每个节点，使用所有不指向已达状态的可用动作延伸每条路径。需要注意的是，在第三阶段，最高位置的城市（Oradea）有两个后继城市，这两个城市都已经有其他路径到达，所以没有路径可以从Oradea延伸

图3-6　以矩形网格问题为例说明图搜索的分离性质。边界（绿色）分离了内部（淡紫色）和外部（虚线）。边界是已达但尚未扩展的节点（及相应的状态）的集合；内部是已被扩展的节点（及相应的状态）的集合；外部是尚未到达的状态的集合。在（a）中，只有根节点被扩展。在（b）中，上面的边界节点被扩展。在（c）中，按顺时针顺序扩展根节点的其他后继节点

图3-8　简单二叉树上的广度优先搜索。每个阶段接下来要扩展的节点用三角形标记表示

图3-11　二叉树的深度优先搜索过程中，从开始状态A到目标M，共12步（从左到右，从上到下）。边界节点为绿色，用三角形表示下一步要扩展的节点。已扩展的节点为淡紫色，潜在的未来节点用模糊的虚线表示。边界中没有后继的已扩展节点（用非常模糊的线表示）可以丢弃

图3-13　二叉树上的迭代加深搜索的4次迭代（目标为M），深度界限从0到3。注意，内部节点形成了一条路径。三角形标记下一步要扩展的节点，边界为加粗轮廓的绿色节点，非常模糊的节点可被证明不可能是这种深度界限下的解的一部分

图3-13　二叉树上的迭代加深搜索的4次迭代（目标为M），深度界限从0到3。注意，内部节点形成了一条路径。三角形标记下一步要扩展的节点，边界为加粗轮廓的绿色节点，非常模糊的节点可被证明不可能是这种深度界限下的解的一部分（续）

图3-17　基于直线距离启发式函数h_SLD的贪心最佳优先树状搜索的各个阶段（目标为Bucharest）。节点上标有h值

图3-18　A*搜索的各个阶段（目标为Bucharest）。节点上标有，h值为图3-16中得到的到Bucharest的直线距离

图3-21　同一网格上的两种搜索：（a）A*搜索，（b）加权A*搜索，权重W = 2。灰色线条表示障碍，紫色线是一条从绿色起始点到红色目标点的路径，较小的点是每次搜索到达的状态。在这个特定问题上，加权A*搜索探索的状态数不到A*搜索探索的状态数的七分之一，找到的路径的代价只比最优代价大了5%

图3-23　使用RBFS搜索到Bucharest的最短路线的各个阶段。每次递归调用的f_limit值标注在每个当前节点的上方，每个节点上都标有它的f代价。（a）沿着经过Rimnicu Vilcea的路径前进，直到当前最优叶节点（Pitesti）的值比最优备选路径（Fagaras）差。（b）递归回溯，被遗忘子树的最优叶节点值（417）被备份到Rimnicu Vilcea；接着扩展Fagaras，得到最优叶节点值450。（c）递归回溯，被遗忘子树的最优叶节点值（450）被备份到Fagaras；然后扩展Rimnicu Vilcea。这一次，因为最优备选路径（经由Timisoara）的代价至少为447，所以继续扩展Bucharest

图3-23　使用RBFS搜索到Bucharest的最短路线的各个阶段。每次递归调用的f_limit值标注在每个当前节点的上方，每个节点上都标有它的f代价。（a）沿着经过Rimnicu Vilcea的路径前进，直到当前最优叶节点（Pitesti）的值比最优备选路径（Fagaras）差。（b）递归回溯，被遗忘子树的最优叶节点值（417）被备份到Rimnicu Vilcea；接着扩展Fagaras，得到最优叶节点值450。（c）递归回溯，被遗忘子树的最优叶节点值（450）被备份到Fagaras；然后扩展Rimnicu Vilcea。这一次，因为最优备选路径（经由Timisoara）的代价至少为447，所以继续扩展Bucharest（续）

图4-4　岭为爬山法带来困难的示意图。状态网格（蓝色圆点）叠加在从左到右上升的岭上，形成了一个彼此不直接相连的局部极大值序列。从每个局部极大值出发，所有可选动作都指向下坡。这样的拓扑在低维状态空间中很常见，例如二维平面中的点。但是在具有成百上千个维度的状态空间中，这种直观图并不成立，而且通常至少存在几个维度使得算法有可能漏掉岭和平台区

图4-7　对应于图4-6c中前两个亲本和图4-6d中第一个后代的8皇后状态。在杂交步中，丢弃绿色列，保留红色列。（图4-6中数字的解释：第1行是最下面一行，第8行是最上面一行）

图4-23　一维状态空间上LRTA*的5次迭代。每个状态都标有H(s)，即到达目标的当前代价估计值，每个连接的动作代价为1。红色状态表示智能体的位置，每次迭代所更新的代价估计值以双圈标记

图5-4　三人博弈的博弈树的前三层，3个玩家为A、B、C。每个节点都标有3个玩家各自的效用值。最佳移动标示在根节点上

图5-10　使用蒙特卡罗树搜索（MCTS）选择移动的算法的一次迭代，该算法使用“应用于树搜索的置信上界”法（UCT）作为选择度量，此时已完成了100次迭代。（a）选择移动，沿着树一直向下，到标记为27/35（35次模拟中黑方赢了27次）的叶节点结束。（b）扩展所选节点并进行模拟，最终黑方获胜。（c）将模拟结果沿树反向传播

图6-6　图6-1中地图着色问题的部分搜索树

图6-7　带前向检验的地图着色搜索过程。首先赋值WA = red；然后前向检验从其相邻变量NT和SA的域中删除red。赋值Q = green后，从NT、SA和NSW的域中删除green。赋值V = blue后，从NSW和SA的域中删除blue，此时SA没有合法值

图7-6　语句是智能体的物理结构，而推理是从旧结构构建新结构的过程。逻辑推理应当确保新结构所表示的部分世界确实能够从旧结构所表示的部分世界推得

图9-10　归结证明韦斯特有罪。每个归结步骤中，合一文字用加粗字体表示，带有正文字的子句用蓝底表示

图9-11　好奇心害死猫的归结证明。注意，在推导子句Loves(G(Jack), Jack)时使用了因子分解。还要注意，在右上角，合一Loves(x, F(x))和Loves(Jack, x)只有在变量标准化分离后才可以进行

图11-6　使用忽略删除列表启发式方法的规划问题的两个状态空间。底部平面以上的高度是一个状态的启发式得分；底部平面的状态是目标。由于不存在局部极小值，所以搜索目标很简单直接。图片来自（Hoffmann, 2005）

图11-9　可达集的语义示例。目标状态集用紫色阴影表示。黑色和红色箭头分别表示h₁和h₂的可能实现。（a）在状态s中HLA h₁的可达集。（b）序列[h₁, h₂]的可达集。因为它与目标集相交，所以序列实现了目标

图11-10　具有近似描述的高层规划的目标达成。目标状态集用紫色阴影表示。对于每个规划将显示悲观（实线，浅蓝色）和乐观（虚线，浅绿色）可达集。（a）黑色箭头所指的规划的确达成了目标，而红色箭头所指的规划完全没有达成目标。（b）可能达成目标（乐观可达集相交的目标）但未必会达成目标（悲观可达集与目标不相交）的规划。该规划需要进一步细化，以确定它是否真的达成了目标

图13-4　（a）给定父节点（浅紫色区域中所示的U_i），节点X条件独立于它的非子孙节点（例如，Z_{i j}）。（b）给定它的马尔可夫毯（浅紫色区域），节点X条件独立于网络中的所有其他节点

图13-9　用于评估汽车保险申请的贝叶斯网络

图13-14　3-CNF语句的贝叶斯网络编码

图14-14　（a）红色曲线：除t = 21和t = 22为0外，其他观测都为5的观测序列的Battery_t期望值轨迹，采用简单高斯误差模型。绿色曲线：从t = 21开始观测值维持在0的轨迹。（b）瞬时故障模型运行了同样的实验。瞬时故障处理良好，但持续故障导致对电池电量的过度悲观

图14-15　（a）一个显示建模电池传感器持续故障要求的传感器状态变量的动态贝叶斯网络片段。（b）上方曲线为对“瞬时故障”与“持续故障”的Battery_t的期望值轨迹，下方曲线为给定两个观测序列的BMBroken的概率轨迹

图14-18　N=10的雨伞动态贝叶斯网络的粒子滤波更新循环，显示每个状态的样本总体。（a）在时刻t，有8个样本表示rain，有2个样本表示。每个状态通过转移模型采样下一个状态向前传播。在时刻t+1，有6个样本表示rain，有4个样本表示。（b）在时刻t+1观测到。每个样本通过这个观测的似然来进行加权，权重如圆的大小所示。（c）从当前的集合中通过加权随机选择产生一个新的集合，共有10个样本，其中2个样本表示rain，8个样本表示

图14-21　（a）具有1000个粒子的标准粒子滤波算法的性能，在不同的灰尘持久性p下，显示与精确推断相比边际灰尘概率的均方根（RMS）误差。（b）Rao-Blackwellized粒子滤波（100个粒子）性能与真实情况的比较，包含精确的位置传感和噪声墙传感，灰尘是确定性的。数据是超过20次运行的平均值

图15-1　（a）在一阶逻辑的标准语义下，具有两个常量符号R和J以及一个二元关系符号的语言的全部可能世界的集合的部分成员。（b）数据库语义下的可能世界。常量符号的解释是固定的，每个常量符号都对应唯一的对象

图15-7　（a）上图：在澳大利亚艾利斯斯普林斯市记录的地震波形实例。下图：用于检测地震波到达时间的处理后的波形。蓝线是自动检测的地震波到达，红线是真正的地震波到达。（b） 2013年2月12日朝鲜核试验地点估计：联合国CTBTO最新事件公报（左上角绿色三角形），NET-VISA（中间蓝色方块）。地下试验设施的入口（以“x”标记）距离NET-VISA的估计0.75公里。轮廓线显示NET-VISA的后验位置分布。图片由CTBTO筹备委员会提供

图16-3　选择k个选项中的最佳选项引起的不合理的乐观：我们假设每个选项的真实效用为0，但效用估计是单位正态分布（棕色曲线）。其他曲线展示了k = 3、10和30时估计最大值的分布

图17-5　（a）俄罗斯方块游戏。位于顶部中心的T型块可以落在任何方向和任何水平位置。如果某一行被补全，则该行消失，上方的行向下移动，智能体得1分。下一块（这里是右上方的L形块）成为当前的一块，并出现一个新的下一块，从7种类型中随机选择。如果棋盘被填满，游戏结束。（b）俄罗斯方块MDP的DDN

图17-7　（a）显示被选择状态使用价值迭代的效用演变的图。（b）对于c不同的值，为保证误差最多为所需的价值迭代次数，作为折扣因子的函数

图17-12　（a）一个简单的有两个臂的确定性老虎机问题。臂可以以任何顺序拉动，每个臂产生所示的奖励序列。（b）关于（a）中的老虎机的一个更普遍的情况，其中第一个臂给出任意奖励序列，第二个臂给出一个固定的奖励λ

图17-14　（a）伯努利老虎机的状态、奖励与转移概率。（b）伯努利老虎机过程的状态的基廷斯指数

图17-17　具有均匀初始信念状态的4×3 POMDP的最大化期望树的一部分。信念状态用与存在于每个位置的概率成正比的深浅来描述

图17-18　墙传感误差的4×3 POMDP中感知、信念状态和动作的序列。注意，之前的Left是安全的，它们不太可能落入(4, 2)，并迫使智能体的位置变成少量的可能位置。Up移动后，智能体认为它可能在(3, 3)中，但也可能在(1, 3)中。幸运的是，Right在这两种情况下都是一个好主意，所以它选择Right，发现它之前在(1, 3)，现在在(2, 3)，然后继续Right，达到目标