第4章 复杂环境中的搜索
在本章中，我们放宽了第3章的简化假设，以更接近真实世界。
第3章讨论了完全可观测的、确定性的、静态的、已知的环境中的问题，问题的解是一个动作序列。在本章中，我们将放宽这些限制。首先，我们考虑这样一个问题，即寻找一个好的状态而不考虑到达该状态的路径，状态包括离散状态（4.1节）和连续状态（4.2节）。然后，我们放宽了确定性假设（4.3节）和可观测性假设（4.4节）。在一个非确定性的世界中，智能体将需要一个条件规划，并根据它所观测到的情况执行不同的动作——例如，红灯停，绿灯行。对于部分可观测性环境，智能体还需要记录它的可能状态。最后，4.5节将指导智能体使用在线搜索（online search）通过一个未知空间，在未知空间中一边前进一边学习。
4.1 局部搜索和最优化问题
在第3章的搜索问题中，我们希望找到一条通过搜索空间的路径，如一条从Arad到Bucharest的路径。但有时我们只关心最终状态，而不是到达状态的路径。例如，在8皇后问题中（图4-3），我们只关心如何找到8个皇后的有效最终配置（因为如果知道配置，重构它的创建步骤就非常简单）。这也适用于许多重要应用，例如集成电路设计、工厂车间布局、作业车间调度、自动编程、电信网络优化、农作物种植规划和投资组合管理。
局部搜索（local search）算法的操作是从一个起始状态搜索到其相邻状态，它不记录路径，也不记录已达状态集。这意味着它们不是系统性的——可能永远不会探索问题的解实际所在的那部分搜索空间。但是，它们有两个主要优点：（1）使用很少的内存；（2）通常可以在系统性算法不适用的大型或无限状态空间中找到合理的解。
局部搜索算法也可以求解最优化问题（optimization problem），其目标是根据目标函数（objective function）找到最优状态。
为了理解局部搜索，我们考虑在状态空间地形图（state-space landscape）中布局的问题状态，如图4-1所示。地形图中的每个点（状态）都有一个“标高”，由目标函数值定义。如果标高对应于目标函数，那么目的就是找到最高峰——全局极大值（global maximum）——我们称这个过程为爬山（hill climbing）；如果标高对应于代价，那么目的就是找到最低谷——全局极小值（global minimum）——我们称之为梯度下降（gradient descent）。
图4-1 一维状态空间地形图，其标高对应于目标函数。目的是找到全局极大值
4.1.1 爬山搜索
爬山搜索算法如图4-2所示。它记录当前状态并在每次迭代中移动到值最大的相邻状态，也就是说，它朝最陡上升（steepest ascent）的方向前进。当它到达一个没有邻居具有更高值的“峰值”时，算法终止。爬山法不会考虑超出当前状态的直接邻居之外的状态。这就像是一个健忘的人在大雾中试图找到珠穆朗玛峰的顶峰。注意，使用爬山搜索的一种方法是使用启发式代价函数的负值作为目标函数；算法将局部地爬升至到目标的启发式距离最小的状态。
图4-2 爬山搜索算法是最基本的局部搜索技术。在每一步中，当前节点被其最优邻居节点替换
我们将使用8皇后问题（图4-3）进一步说明爬山法。我们将使用一个完整状态形式化（complete-state formulation），即每个状态都包含解的所有组成部分，但它们可能并不都在正确的位置。在这种情况下，每个状态都包括在棋盘上放置8个皇后，每列一个。初始状态是随机选择的，状态后继是通过将一个皇后移动到同一列中的另一格所生成的所有可能状态（所以每个状态有8×7 = 56个后继）。启发式代价函数h是可相互攻击的皇后对的数量；只有当该状态是一个解时，h值才是0。（如果两个皇后在同一条线上，即使它们之间存在一个中间棋子，这两个皇后也会被视为形成相互攻击。）图4-3b展示了一个h = 17的状态以及它所有后继的h值。
爬山法有时被称为贪心局部搜索（greedy local search），因为它只是选择最优的邻居状态，而不事先考虑下一步该如何走。虽然贪婪被视为七宗罪之一，但事实证明，贪心算法往往相当有效。爬山法可以在求解问题时取得快速进展，因为它通常可以很容易地改善一个差的状态。例如，只需5步就可以从图4-3b的状态到达图4-3a的状态，该状态的h = 1，与解非常接近。遗憾的是，爬山法可能会由于以下原因而陷入困境。
● 局部极大值（local maxima）：局部极大值是一个比它每个相邻状态都高但比全局极大值低的峰顶。爬山法到达局部极大值附近就会被向上拉向峰顶，但随后将困在局部极大值处无路可走。图4-1示意性地说明了这一问题。更具体地说，图4-3a中的状态是一个局部极大值（即代价h的局部极小值）；不管移动哪个皇后都会让情况变得更差。
图4-3 （a）8皇后问题：在棋盘上放置8个皇后，使得它们不能互相攻击。（皇后会攻击同一行、同一列或对角线上的任何棋子。）当前状态非常接近于一个解，除了第4列和第7列的两个皇后会沿对角线互相攻击。（b）一个8皇后状态，其启发式代价估计值h = 17。棋盘显示了通过在同一列移动皇后而获得的每一个可能后继的h值。有8个移动并列最优，其h = 12。爬山法将选择它们中的一个
● 岭（ridge）：如图4-4 所示。岭的存在将导致一系列局部极大值，对于贪心算法，这是很难处理的。
图4-4 岭为爬山法带来困难的示意图。状态网格（蓝色圆点）叠加在从左到右上升的岭上，形成了一个彼此不直接相连的局部极大值序列。从每个局部极大值出发，所有可选动作都指向下坡。这样的拓扑在低维状态空间中很常见，例如二维平面中的点。但是在具有成百上千个维度的状态空间中，这种直观图并不成立，而且通常至少存在几个维度使得算法有可能漏掉岭和平台区
● 平台区（plateau）：平台区是指状态空间地形图中的平坦区域。它可能是一块平坦的局部极大值，不存在上坡的出口；也可能是一个山肩（shoulder），从山肩出发还有可能继续前进（参见图4-1）。爬山搜索可能会迷失在平台区上。
在每种情况下，算法都会到达一个无法再取得进展的点。从一个随机生成的8皇后状态开始，在86%的情况下，最陡上升爬山法会被卡住，它只能解决14%的问题实例。但是，它求解速度很快，成功找到解时平均步数为4，被卡住时平均步数为3，这对一个具有
万个状态的状态空间来说不算糟糕。
我们怎么才能求解更多问题？一个答案是当我们到达一个平台区时继续前进——允许横向移动（sideways move），希望这个平台区真的是一个山肩，如图4-1所示。但如果我们实际上位于一块平坦的局部极大值上，那么算法就会陷入死循环。因此，我们可以限制连续横向移动的次数，如在100次连续横向移动之后停止。这种方法将爬山法成功求解问题实例的百分比从14%提高到了94%。成功是有代价的：平均下来，对每个成功实例算法需要运行约21步，失败实例约64步。
爬山法存在很多变体。随机爬山法（stochastic hill climbing）在上坡行动中随机选择一个；被选中的概率随着上坡陡度的变化而变化。这种方法通常比最陡上升法收敛得更慢，但在某些状态地形图中，它能找到更好的解。首选爬山法（first-choice hill climbing）通过不断随机地生成后继直到生成一个比当前状态更好的后继为止来实现随机爬山。当一个状态存在众多（如数千个）后继时，这是一个很好的策略。
另一种变体是随机重启爬山法（random-restart hill climbing），它来自于一句格言：“如果一开始没有成功，那么尝试，再尝试。”它从随机生成的初始状态开始，执行一系列爬山搜索，直到找到目标。算法完备的概率为1，因为它最终会生成一个目标状态作为初始状态。如果每一次爬山搜索成功的概率为p，那么需要重启的期望次数为1 / p。对于不允许横向移动的8皇后实例，
，所以大概需要7次迭代才能找到一个目标（6次失败，1次成功）。所需步数的期望为一次成功迭代的代价加上(1−p)/p倍的失败代价，总共约为22步。当允许横向移动时，平均需要
次迭代，
步。因此，对于8皇后问题，随机重启爬山法是非常有效的。即使有300万个皇后，这种方法也能在很短的时间内找到解。[1]
[1] 卢比等人（Luby et al., 1993）建议在搜索固定次数之后重启，并表明这比让每次搜索都无限期地继续下去要有效得多。
爬山法是否能成功在很大程度上取决于状态空间地形图的形状：如果几乎不存在局部极大值和平台区，那么随机重启爬山法可以很快找到一个好的解。但是，许多实际问题的地形图看起来更像是平地上散布着一群秃顶豪猪，每个豪猪的刺上还住着微型豪猪。NP困难问题（参见附录 A）通常存在指数级数量的局部极大值。尽管如此，在几次重启后，通常也可以找到相当好的局部极大值。
4.1.2 模拟退火
从不“下坡”，即从不向值较低（或代价较高）的状态移动的爬山算法总是很容易陷入局部极大值。相比之下，纯粹的随机游走算法不考虑状态值，而是随机移动到一个后继状态，它最终能够找到全局极大值，但它的效率非常低。因此，尝试将爬山法和随机游走结合起来以同时获得高效性和完备性，似乎是合理的。
模拟退火（simulated annealing）就是这样一种算法。在冶金学中，退火（annealing）是一种通过将金属或玻璃加热到高温然后逐渐冷却的方法使材料达到低能量结晶态以进行回火或硬化的过程。为了更好地解释模拟退火，我们将关注点从爬山转换为梯度下降（gradient descent）（即，最小化代价），想象这样一项任务，把一个乒乓球放入一个崎岖表面的最深的裂缝中。如果只是让球滚动，它会停在一个局部极小值。如果晃动平面，乒乓球会从局部极小值中弹出来——也许会弹到更深的局部极小值中，在那里它将耗费更多的时间。诀窍是晃动幅度要足够大，以使球从局部极小值中弹出，但又不能太大，以至于从全局极小值中弹出。模拟退火就是开始时用力晃动（即高温），然后逐渐降低晃动强度（即降低温度）。
模拟退火算法的总体结构（图4-5）与爬山法类似。然而，它不是选择最佳移动，而是选择随机移动。如果该移动使得情况改善，那么它总是会被接受。否则，算法以小于1的概率接受该移动。概率随着该移动的“坏的程度”——评估值变差的量
——呈指数级下降。概率也会随“温度”T的降低而减小：开始时T较高，“坏”的移动更有可能被接受，当T降低时，可能性也逐渐降低。如果schedule所设置的T降到0的速度足够慢，那么玻尔兹曼分布
的一个性质是所有概率都集中在全局极大值上，即算法将以接近1的概率找到全局极大值。
图4-5 模拟退火算法，一种允许某些下坡移动的随机爬山法。输入的schedule是关于时间的函数，它决定了“温度”T的值
从20世纪80年代开始，模拟退火就被用于求解VLSI布图问题。它已广泛应用于工厂调度和其他大规模优化任务。
4.1.3 局部束搜索
对于内存限制问题，在内存中只保存一个节点似乎有些极端。局部束搜索（local beam search）算法记录k个状态而不是只记录一个。它从k个随机生成的状态开始。在每一步中，生成全部k个状态的所有后继状态。如果其中任意一个是目标状态，那么算法停止。否则，它将从完整列表中选择k个最佳后继并重复上述操作。
从第一印象来看，具有k个状态的局部束搜索似乎只不过是并行（而非串行）地运行k次随机重启。事实上，这两种算法是完全不同的。在随机重启搜索中，每个搜索进程独立运行。而在局部束搜索中，有用信息将在并行的搜索线程之间传递。实际上，生成最佳后继的那些状态会对其他状态说：“过来，这里的草更绿！”算法将很快放弃那些没有效果的搜索并把资源转移到取得最大进展的路径上。
如果k个状态之间缺乏多样性，局部束搜索可能会受到影响——k个状态可能聚集在状态空间的一块小区域内，导致搜索只不过是k倍慢版本的爬山法。一种被称作随机束搜索（stochastic beam search）的变体可以帮助缓解这个问题，它类似于随机爬山法。随机束搜索不是选择最佳的k个后继状态，而是选择概率与它对应的目标函数值成正比的后继状态，从而增加了多样性。
4.1.4 进化算法
进化算法（evolutionary algorithm）可以看作随机束搜索的变体，算法的动机明显来自生物学中自然选择的隐喻：一个由个体（状态）组成的种群，其中最适应环境（值最高）的个体可以生成后代（后继状态）来繁衍下一代，这个过程被称为重组（recombination）。进化算法存在无数种形式，它们按照以下方式变化。
● 种群规模。
● 每个个体的表示。在遗传算法（genetic algorithm）中，每个个体都是有限字母表上的一个字符串（通常是一个布尔字符串），就像DNA是字母表ACGT上的一个字符串一样。在进化策略（evolution strategy）中，个体是实数序列，而在遗传编程（genetic programming）中，个体是计算机程序。
● 混合数，
，是一起形成后代的亲本的数量。最常见的情况是
：双亲结合它们的“基因”（它们表示的一部分）来形成后代。当
时，为随机束搜索（可以看作无性繁殖）。
也是可能的，这在自然界中很少发生，但很容易在计算机上进行模拟。
● 选择（selection）过程。选择将成为下一代亲本的个体：一种可能是从所有个体中选择，被选中的概率与其适应度得分成正比。另一种可能是随机选择n个个体（
），然后选择最适合的个个体作为亲本。
● 重组过程。一种常见的方法（假设）是随机选择一个杂交点（crossover point）来分割每个父字符串，并将这些部分重新组合以形成两个子串，一个是亲本1的第一部分和亲本2的第二部分的组合；另一个是亲本1的第二部分和亲本2的第一部分的组合。
● 突变率（mutation rate），它决定了后代在其表示上发生随机突变的频率。一旦产生了一个后代，其组成中的每位都将以与突变率相等的概率被翻转。
● 下一代的构成。可能只包括新形成的后代，也可能还包括一些上一代中得分最高的个体［这种做法被称为精英主义（elitism），它确保总体适应度永远不会随着时间的推移而下降］。而淘汰（culling），即丢弃所有分数低于给定阈值的个体，会使得进化加速（Baum et al., 1995）。
图4-6a为由4个8位数字符串组成的种群，每个字符串代表8皇后问题的一个状态：第c位数字表示第c列中皇后的行号。在图4-6b中，每个状态根据适应度函数进行评级。适应度越高越好，所以对于8皇后问题，我们使用非攻击皇后对的数量作为适应度，解的适应度为8×7/2 = 28。图4-6b中4个状态的值分别为24、23、20和11。然后将适应度得分归一化为概率，结果显示在图4-6b中的适应度旁边。
图4-6 遗传算法，图示为表示8皇后状态的数字字符串。（a）中的初始种群根据（b）中的适应度函数进行排序从而得到（c）中的配对，（d）是产生的后代，（e）是可能发生的突变
在图4-6c中，根据图4-6b中的概率选出两对父字符串。注意，有一个个体被选择了两次，还有一个没有被选择。对于每一对被选择的亲本，随机选择一个杂交点（虚线）。在图4-6d中，我们在杂交点处交叉两个父串，以生成新的后代。例如，第一对亲本中的第一个子串从第一个父串获得前三个数字（327），从第二个父串获得剩余数字（48552）。这一重组步骤中所包含的8皇后状态如图4-7所示。
图4-7 对应于图4-6c中前两个亲本和图4-6d中第一个后代的8皇后状态。在杂交步中，丢弃绿色列，保留红色列。（图4-6中数字的解释：第1行是最下面一行，第8行是最上面一行）
最后，在图4-6e中，每个字符串中的每个位置都以某个很小的独立概率发生随机突变。第一个、第三个和第四个后代的某个位发生了突变。在8皇后问题中，这相当于随机选择一个皇后，并将其随机移动到它所在列的某个位置。通常情况下，早期的种群是多样化的，所以在搜索过程的早期阶段，杂交常常在状态空间中采取较大的步调（类似于模拟退火）。在经过许多代选择提高了适应度后，种群的多样性减少，步调也随之变小。图4-8介绍了实现所有这些步骤的算法。
图4-8 遗传算法。在这个函数中，population是种群中个体的有序列表，weights是每个个体所对应的适应度值的列表，而fitness是计算这些值的函数
遗传算法类似于随机束搜索，但增加了杂交操作。如果存在可以执行有用功能的区域，杂交操作是有利的。例如，将前3列皇后分别放在第2行、第4行和第6行（在这些位置上它们不会互相攻击），就组成了一个有用的区域，它可以与其他个体中出现的其他有用区域相结合，从而形成一个解。数学上可以证明，如果这些区域没有任何用途——例如，如果遗传密码的位置是随机排列的——那么杂交就没有任何优势。
遗传算法理论用模式（schema）思想来解释它是如何运作的，模式是指其中某些位未确定的子串。例如，模式246*****表示前3个皇后分别位于位置2、4和6的所有8皇后状态。与该模式相匹配的字符串（例如24613578）称作该模式的实例（instance）。可以证明，如果某模式实例的平均适应度高于平均值，那么该模式的实例数量将随着时间推移而不断增加。
进化和搜索
进化论是由查尔斯·达尔文（Charles Darwin）（Darwin, 1859）和艾尔弗雷德·拉塞尔·华莱士（Alfred Russel Wallace）（Wallace, 1858）各自独立提出的。它的中心思想很简单：变异发生在繁殖过程中，并将在后代中以一定比例保存下来，大概与它们对生殖适应度的影响成比例。
达尔文在《物种起源》（On the Origin of Species by Means of Natural Selection）中的理论没有解释生物体的特征是如何遗传和改变的。控制这些过程的概率定律由修道士格雷戈尔·孟德尔（Gregor Mendel）（Mendel, 1866）首先发现，他使用豌豆进行了实验。很久之后，沃森和克里克（Watson and Crick, 1953）确定了DNA分子的结构及其AGTC（腺嘌呤、鸟嘌呤、胸腺嘧啶、胞嘧啶）序列。在标准模型中，基因序列上某点发生突变和“杂交”（后代的DNA通过合成父母双方的DNA长片段产生）都会导致变异。
进化和局部搜索算法的相似性前文已经介绍过了；随机束搜索和进化的主要区别在于是否为有性生殖，有性生殖中后代是由多个而非单个个体产生的。然而，进化的实际机制比大多数遗传算法要丰富得多。例如，突变包括DNA的逆转、复制和大段移动；有些病毒会从一个生物体中借用DNA再将其自身插入另一个生物体；还有一些转座基因只是在基因组中把自己复制成千上万次。
甚至还有一些基因会破坏不携带该基因的可能配对对象的细胞，从而增加它们自身的复制机会。最重要的是，基因自身对基因组复制和翻译成生物体的机制进行编码。在遗传算法中，这些机制是单独的程序，不体现在被操作的字符串中。
达尔文进化论可能看起来效率很低，它盲目地产生了大约1043个生物体，却丝毫没有改进它的搜索启发式函数。但是学习在进化中确实起着作用。尽管另一位伟大的法国博物学家让·拉马克（Jean Lamarck）（Lamarck, 1809）曾错误地提出，生物体一生中通过适应而获得的特性会遗传给后代，但詹姆斯·鲍德温（James Baldwin）（Baldwin, 1896）提出的表面上相似的理论则是正确的：学习可以有效地放宽适应度要求，从而加快进化速度。如果一个生物体具有一种不太适应环境的特性，但它也具有足够的可塑性，可以学习以一种有益的方式适应环境，那么生物体会将这种特性传递下去。计算机仿真（Hinton and Nowlan, 1987）证实了鲍德温效应（Baldwin effect）是真实存在的，其结果是，难以学习的事情最终会存在于基因组中，而容易学习的事情不必进入基因组（Morgan and Griffiths, 2015）。
显然，如果相邻位之间完全不相关，效果就没那么显著，因为几乎不存在功能一致的连续区域。当模式对应于解中有意义的组件时，遗传算法效果最优。例如，如果字符串表示天线，那么模式则表示天线的各组成部分，如反射器和导向器。一个好的组件可能在各种不同的设计中都是好的。这表明，遗传算法的成功依赖于精细的表示工程。
实际上，遗传算法在广泛的最优化方法中占有一席之地（Marler and Arora, 2004），尤其是复杂结构问题，如电路布图或作业车间调度，以及最近的深度神经网络架构演变（Miikkulainen et al., 2019）。目前还不清楚遗传算法的吸引力是来自于它在特定任务上的性能优势，还是来自于进化本身。
4.2 连续空间中的局部搜索
在第2章中，我们解释了离散环境和连续环境之间的区别，并指出大多数的真实世界环境都是连续的。连续动作空间的分支因子是无限的，因此我们目前介绍的大多数算法（除了首选爬山法和模拟退火）都无法处理连续空间。
本节将非常简要地介绍一些连续空间的局部搜索技术。关于这个主题的文献有很多。许多基本技术起源于牛顿和莱布尼茨发明微积分之后的17世纪。[2]本书的一些章节会介绍这些技术的应用，包括学习、视觉和机器人技术相关的章节。
[2] 向量、矩阵和导数的知识对于学习本节内容很有帮助（见附录A）。
考虑一个实例。假设我们希望在罗马尼亚新建3个机场，使得地图上每个城市到其最近机场的直线距离平方和最小。（罗马尼亚地图见图3-1。）状态空间定义为3个机场的坐标：(x1, y1)、(x2, y2)和(x3, y3)。这是一个六维空间；我们也可以说状态由6个变量（variable）定义。一般地，状态定义为n 维向量，x。在这个空间中移动对应于移动地图上的一个或多个机场。对于任一特定状态，一旦计算出最近城市，目标函数f(x) = f (x1, y1, x2, y2, x3, y3)的计算就会变得相对容易。设Ci是最近机场（在状态x下）为机场 i 的城市集合。那么，我们有
（4-1）
这一方程不仅对于状态x是正确的，而且对于x局部邻域中的状态也是正确的。然而，对全局来说，它是不正确的；如果我们偏离x太远（通过大幅改变一个或多个机场的位置），那么该机场的最近城市集合会发生变化，我们需要重新计算Ci。
处理连续状态空间的一种方法是离散化（discretize）。例如，我们可以将(xi, yi)的位置限制在矩形网格上间距为
的固定点，而不是允许它的位置可以为连续二维空间中的任意点。那么，空间中的每个状态将存在12个后继（对应于将6个变量分别增加
），而不是之前的无限多个。然后我们就可以对离散空间应用任意局部搜索算法。或者，我们可以通过随机采样后继状态，即在随机方向上移动一个小量，使分支因子变为有限值。通过两个相邻点之间目标函数值的变化来衡量进度的方法称为经验梯度（empirical gradient）法。经验梯度搜索与离散化状态空间中的最陡上升爬山法相同。随着时间逐渐减小的值可以得到更准确的解，但不一定在极限范围内收敛到全局最优值。
通常我们有一个以数学形式表达的目标函数，这样我们就可以用微积分来解析地而非经验地求解问题。许多方法都试图利用地形图的梯度（gradient）来找到最大值。目标函数的梯度是一个向量∇f，它给出了最陡斜面的长度和方向。对于我们的问题，有
在某些情况下，我们可以通过解∇f = 0方程找到一个极大值。（这是可以做到的，例如，如果我们只新建一个机场；问题的解是所有城市坐标的算术平均值。）然而，在许多情况下，这个方程不存在闭式解。例如，对于3个机场的情况，梯度的表达式依赖于当前状态中哪些城市离各个机场最近。这意味着我们只能局部地（而非全局地）计算梯度，例如，
（4-2）
给定一个局部正确的梯度表达式，我们可以根据下式来更新当前状态从而实现最陡上升爬山法：
其中
是一个很小的常数，通常称为步长（step size）。存在很多调整的方法。基本问题是，如果太小，需要的迭代步太多；如果太大，搜索可能会越过最大值。线搜索（line search）技术试图通过不断延伸当前梯度方向——通常通过对反复加倍——直到f再次开始减小来克服上述困境。出现上述现象的点成为新的当前状态。在这点上如何选择新的方向，有几种不同的方法。
对于许多问题，最有效的算法是古老的牛顿-拉弗森法（Newton-Raphson method）。这是一种求函数根（即求解g(x) = 0形式的方程）的通用方法。它的工作原理是根据牛顿公式计算根x的一个新的估计值：
要找到f的最大值或最小值，需要找到使得梯度为零向量（即
）的x。因此，牛顿公式中的g(x)为
，更新方程可以写成矩阵-向量形式：
其中Hf(x)为二阶导数的黑塞矩阵（Hessian matrix），其元素Hij由
给出。对于上述机场问题实例，从式（4-2）可以看出，Hf(x)相当简单：非对角元素为零，机场i的对角线元素的值恰好为Ci中城市数目的两倍。每一时刻的计算表明，每一步更新将机场i直接移动到Ci的质心处，即式（4-1）中f的局部表达式的最小值。[3]然而，对于高维问题，计算黑塞矩阵的n2个元素以及对它求逆的开销可能非常昂贵，因此产生了许多牛顿-拉弗森法的近似版本。
[3] 一般来说，牛顿-拉弗森更新可以看作在x处用一个二次曲面拟合f，下一步则直接移动到该曲面的最小值——如果f是二次的，则也是f的最小值。
局部搜索方法在连续状态空间和离散状态空间中一样，同样受到局部极大值、岭和平台区的影响。随机重启和模拟退火通常很有用。然而，高维连续空间非常大，算法很容易陷入困境。
最后一个话题是约束优化（constrained optimization）。如果一个优化问题的解必须满足对变量值的一些硬性约束，那么这个问题就是受约束的。例如，在机场选址问题中，我们可能会将选址限制在罗马尼亚境内的陆地上（而不是某个湖中心）。约束优化问题的难度取决于约束和目标函数的性质。最著名的一类问题是线性规划（linear programming）问题，其约束必须是能构成凸集的线性不等式[4]，目标函数也必须是线性的。线性规划的时间复杂性是关于变量数目的多项式。
[4] 如果点集S中任意两点的连线也包含在S中，则称S是凸的。凸函数（convex function）是指其上方空间构成凸集的函数；根据定义，凸函数没有局部（相对于全局）极小值。
线性规划可能是最广泛研究和最有用的优化方法。它是更一般的凸优化（convex optimization）问题的一种特例，允许约束区域为任意凸区域，目标函数为约束区域内的任意凸函数。在一定条件下，凸优化问题也是多项式时间内可解的，即使有上千个变量，也可能是实际可行的。机器学习和控制理论中的几个重要问题可以形式化为凸优化问题（见第20章）。
4.3 使用非确定性动作的搜索
在第3章中，我们假设环境为完全可观测的、确定性的、已知的。因此，智能体可以观测到初始状态，计算出可以到达目标的动作序列，然后“闭着眼睛”执行这些动作，而不需要使用自己的感知。
然而，当环境部分可观测时，智能体并不确定它处于什么状态；当环境是非确定性的时，智能体不知道在执行某个动作后将转移到什么状态。这意味着智能体所思考的不再是“我现在位于s1状态，如果我执行a动作，我将会进入s2状态”，而是“我现在位于s1或s3状态，如果我执行a动作，我将会进入s2、s4或s5状态”。我们把智能体认为其可能位于的物理状态集合称为信念状态（belief state）。
在部分可观测的和非确定性的环境中，问题的解不再是一个序列，而是一个条件规划（conditional plan）（有时也称为应变规划或策略），条件规划根据智能体在执行规划时接收到的感知来指定动作。本节先讨论非确定性，部分可观测性留待4.4节讨论。
4.3.1 不稳定的真空吸尘器世界
如图4-9所示，第2章中的真空吸尘器世界具有8种状态。有3种动作——向左Left、向右Right和吸尘Suck，目标是清理所有的灰尘（状态7和8）。如果环境是完全可观测的、确定性的和完全已知的，那么使用第3章的任意算法都很容易求解这个问题，它的解是一个动作序列。例如，如果初始状态是1，那么动作序列[Suck, Right, Suck]可以到达目标状态8。
图4-9 真空吸尘器世界的8种可能状态；状态7和8是目标状态
现在假设我们以一个功能强大但不稳定的真空吸尘器的形式引入非确定性。在不稳定的真空吸尘器世界中，Suck的工作原理如下。
● 在一个脏的方格中，Suck会清理这一方格，有时也会清理它的相邻方格。
● 在一个干净方格中，Suck有时反而会把灰尘弄到地面上。[5]
[5] 我们假设大多数读者都会遇到类似的问题，并且会共情我们的智能体。我们向那些拥有现代化高效清洁设备从而无法利用这一教学设计的读者道歉。
为了更准确地形式化这一问题，我们需要推广第3章的转移模型概念。我们不使用返回单个结果状态的Result函数来定义转移模型，而是使用返回一组可能的结果状态的新的Result函数。例如，在不稳定的真空吸尘器世界中，状态1中的Suck动作要么只清理当前位置，要么同时清理两个位置：
如果我们是从状态1开始，那么没有任何一个单独的动作序列能够求解问题，因此我们需要如下的条件规划：
（4-3）
我们看到，条件规划可以包含if–then–else步骤；这意味着解是树而不是序列。这里的if语句中的条件用来测试当前状态；这是智能体在运行时能够观测到的，但规划时还不知道。或者，我们也可以用公式来测试感知而不是状态。真实物理世界中的许多问题都是应变问题，因为不可能对未来进行准确预测。因此，许多人在走路时都会睁着眼睛。
4.3.2 与或搜索树
我们如何得到这些非确定性问题的条件解？和第3章一样，我们首先从构造搜索树开始，但是这里的树有一个不同的特性。在确定性环境中，分支是由智能体在每个状态下自己的选择引入的：我可以执行这个动作或那个动作。我们称这些节点为或节点（OR node）。例如，在真空吸尘器世界中，智能体在或节点上选择Left、Right或Suck。而在非确定性环境中，环境对每个动作的结果的选择也会引入分支。我们称这些节点为与节点（AND node）。例如，状态1中的Suck动作会产生信念状态{5,7}，因此智能体需要为状态5与状态7分别找到一个规划。这两种节点交替出现，形成如图4-10所示的与或树（AND–OR tree）。
图4-10 不稳定的真空吸尘器世界搜索树的前两层。状态节点是必须选择某个动作的或节点。与节点（用圆圈表示）上的每个结果都必须处理，结果分支间用弧线连接。找到的解用粗线标识
与或搜索问题的解是完整搜索树的一棵子树：（1）每个叶子都是一个目标节点，（2）在每个或节点上选择一个动作，（3）每个与节点包括所有结果分支。解在图中用粗线标识；对应于式（4-3）中的规划。
图4-11给出了与或图搜索的深度优先递归算法。该算法的一个关键是它处理环的方法，环经常出现在非确定性问题中（例如，动作有时不起作用，或者一个意外的影响被纠正）。如果当前状态与从根到它的路径上的某个状态相同，就返回失败。这并不意味着从当前状态出发没有解；这仅仅意味着，如果存在一个非循环解，那么它肯定可以从当前状态的早期镜像到达，因此可以丢弃新的镜像。有了这一检查，可以确保算法在任何有限状态空间中都能终止，因为每条路径都必定到达一个目标、一个死胡同或一个重复状态。注意，该算法并不检查当前状态是否是从根出发的其他路径上的某个状态的重复状态，这一点对效率来说很重要。
图4-11 非确定性环境生成的与或图的搜索算法。解是一个条件规划，它考虑每一个非确定性的结果，并为每个结果制定规划
与或图也可以使用广度优先或最佳优先的方式进行探索。我们必须修改启发式函数的概念，即估计一个条件解而不是一个序列的代价，但可容许性的概念可以继续保留，而且存在类似的用于寻找最优解的A*算法（参见本章末尾的参考文献与历史注释）。
4.3.3 反复尝试
考虑一个光滑的真空吸尘器世界，它与普通的（稳定的）真空吸尘器世界基本相同，但移动操作有时会失效，使得智能体停在原地。例如，在状态1中执行Right将产生信念状态{1,2}。图4-12为部分搜索图；显然，从状态1出发不存在非循环解，And-Or-Search将返回失败。然而，存在一个循环解（cyclic solution），即反复尝试Right动作，直到它生效。我们可以用一个新的while结构来表示上述过程：
或者用标签（label）表示规划的某一部分，之后可以引用这个标签：
什么时候可以考虑将循环规划作为解？最小条件是每个叶节点都是一个目标状态，并且叶节点可以从规划中的任意点到达。除此之外，我们还要考虑造成非确定性的原因。如果情况确实是，真空吸尘器机器人的驱动机制在某些时间工作，但在其他时间真空吸尘器会发生随机、独立地滑动，那么智能体可以保证，如果动作重复足够多次，最终总会生效，规划也会成功。但是，如果这种非确定性来自机器人或环境的一些尚未观测到的原因（例如，传动带断了，那么机器人将永远不会移动），重复这个动作也没有用。
为了便于理解，我们可以认为，它是将初始问题形式（完全可观测的，非确定性的）转化为另一种形式（部分可观测的，确定性的），其中循环规划的失败正是由于传动带的某个不可观测的特性。在第12章中，我们将讨论如何判断几种不确定可能性中哪个可能性更大。
图4-12 光滑的真空吸尘器世界的部分搜索图，（一些）循环已经明确地标出。这个问题的所有解都是循环规划，因为真空吸尘器无法稳定地移动
4.4 部分可观测环境中的搜索
现在我们考虑部分可观测性问题，即智能体的感知不足以确定准确的状态。这意味着，智能体的一些动作将致力于减少当前状态的不确定性。
4.4.1 无观测信息的搜索
当智能体的感知根本不提供任何信息时，问题就变成了无传感器（sensorless）问题，或称一致性（conformant）问题。起初，你可能会认为，如果无传感器智能体不知道起始状态，那它就无法求解问题，但出人意料的是，无传感器解非常普遍且有用，主要是因为它们不依赖于传感器是否正常工作。例如，在制造系统中，已经开发出许多巧妙的方法，通过使用一系列行动而无须任何感知，从未知初始位置正确定位零件。有时，即使存在可感知的条件规划，无传感器规划也会更好。例如，医生通常会开一种广谱抗生素，而不是使用条件规划：先验血，接着等待结果，然后再开一种更具体的抗生素。这种无传感器规划节省了时间和金钱，并且避免了在检测结果出来之前感染恶化的风险。
考虑一个（确定性）真空吸尘器世界的无传感器版本。假设智能体知道它所在世界的地理环境，但不知道它自己的位置和灰尘的分布。在这种情况下，它的初始信念状态为{1, 2, 3, 4, 5, 6, 7, 8}（见图4-9）。现在，如果智能体执行Right动作，它将位于{2, 4, 6, 8}中的某个状态——智能体在没有感知的情况下获得了信息！执行[Right, Suck]之后，智能体将总是位于{4, 8}中的某个状态。最终，无论初始状态是什么，执行[Right, Suck, Left, Suck]之后，智能体必定会到达目标状态7。我们称，智能体可以强迫（coerce）世界到达状态7。
无传感器问题的解是一个动作序列，而不是条件规划（因为它没有感知）。但是，我们是在信念状态空间而非物理状态空间中进行搜索。[6]在信念状态空间中，问题是完全可观测的，因为智能体始终知道自己的信念状态。此外，无传感器问题的解（如果有的话）始终是一个动作序列。这是因为，正如第3章的原始问题一样，每个动作后接收到的感知是完全可预测的——它们总是空的！所以不存在需要规划的偶发事件。即使环境是非确定性的，这也是正确的。
[6] 在完全可观测的环境中，每个信念状态只包含一个物理状态。因此，我们可以将第3章的算法看作在信念状态为单元素的信念状态空间中搜索。
我们可以为无传感器搜索问题介绍新的算法。但是，如果我们将底层物理问题转化为信念状态问题，我们就可以使用第3章中现有的算法，即，对信念状态而非物理状态进行搜索。原问题P，由ActionsP、ResultP等组成，信念状态问题则包括以下部分。
● 状态：信念状态空间包含物理状态的每一个可能子集。如果原问题P有N个状态，那么信念状态问题有2N个信念状态，尽管有很多状态都无法从初始状态到达。
● 初始状态：通常，初始信念状态包含P中的所有状态，尽管在某些情况下，智能体具有更多的先验知识。
● 动作：这部分有点棘手。假设智能体位于信念状态
，但是
；那么智能体就无法确定哪些动作是合法的。如果我们假定非法动作不会对环境产生影响，那么执行当前信念状态b下的任意物理状态的所有动作的并集都是安全的。
但是，如果非法动作可能导致严重后果，那么只允许执行动作的交集（对所有状态都合法的动作的集合）更安全。对于真空吸尘器世界，每个状态都具有相同的合法动作，所以两种方法将给出相同的结果。
● 转移模型：对于确定性动作，对于每个当前可能状态，新的信念状态中都存在一个如下结果状态（尽管一些结果状态可能是相同的）。
（4-4）
对于非确定性动作，新的信念状态则包含了将该动作应用于当前信念状态中的任一状态的所有可能结果。
对于确定性动作，b'不会大于b，而对于非确定性动作，b'可能会大于b（见图4-13）。
图4-13 （a）预测在无传感器真空吸尘器世界执行确定性动作Right后的下一个信念状态；（b）在光滑的无传感器真空吸尘器世界中的同一状态下执行同一动作的预测
● 目标测试：如果信念状态中的任一状态s满足底层问题的目标测试，Is-GoalP(s)，则智能体有可能到达了目标。如果所有状态都满足Is-GoalP(s)，则智能体必定到达了目标。我们的目标是使得智能体必定到达了目标。
● 路径代价：这部分也很棘手。如果同一动作在不同状态下代价不同，那么在给定信念状态下执行动作的代价是几种不同值中的一种。（这导致了一类新的问题，我们将在习题4.MVAL中讨论。）现在我们假定同一动作在所有状态下具有相同代价，因此动作代价可以直接从底层物理问题中转换。
图4-14为确定性无传感器真空吸尘器世界的可达信念状态空间。在28 = 256种可能信念状态中只有12种可以到达。
图4-14 确定性无传感器真空吸尘器世界的信念状态空间的可达部分。每个矩形框对应一个信念状态。在任何给定点，智能体都有一个信念状态，但它不知道自己位于哪个物理状态。初始信念状态（完全未知）位于最上面的中间方框
上述定义确保信念状态问题的形式化能够从底层物理问题的定义自动构建。一旦完成，就可以用第3章的任何普通搜索算法求解无传感器问题。
在一般的图搜索中，需要检测新到达的状态之前是否已经到达过。这也适用于信念状态；例如，在图4-14中，动作序列[Suck, Left, Suck]从初始状态出发，到达与序列[Right, Left, Suck]相同的信念状态，即，{5, 7}。现在，考虑[Left]到达的信念状态，{1, 3, 5, 7}。显然，这与{5, 7}不同，但它是{5, 7}的超集。我们可以抛弃（剪枝）任何一个这样的信念状态超集。为什么？因为从{1, 3, 5, 7}出发的解一定也是任何单一状态1、3、5和7的解，因此，它也是这些单一状态任意组合的解，例如{5, 7}；因此我们没有必要试着求解{1, 3, 5, 7}，可以专注于求解更严格简单的信念状态{5, 7}。
反过来，如果已经生成{1, 3, 5, 7}，并且发现它是可解的，那么它的任何子集，如{5, 7}，可以确保也是可解的。（如果我有一个解，它在我对自己处于何种状态“非常困惑”时都是有效的，那么在我“不那么困惑”时它仍然是有效的。）这种额外剪枝可能会显著提高无传感器问题的求解效率。
然而，即使有这样的改进，我们所介绍的无传感器问题求解方法在实践中也几乎是不可行的。一个问题是信念状态空间非常庞大——我们在第3章中看到过，一个大小为N的搜索空间已经过于庞大，而现在我们搜索空间的大小为2N。此外，搜索空间中的每个元素都是一个不超过N个元素的集合。对于较大的N，内存空间甚至不足以表示单个的信念状态。
一种解决方案是用更紧凑的描述来表示信念状态。例如，在英语中，我们可以用“Nothing”表示初始状态；我们可以用“Not in the rightmost column”表示执行Left动作后的信念状态，等等。第7章介绍了如何在形式化表示模式中实现上述表示。
另一种方法是避免使用标准搜索算法，它们将信念状态看作和任何其他问题状态一样的黑盒。然而，我们可以选择查看信念状态内部，并设计增量信念状态搜索（incremental belief-state search）算法，即，每次只为一个物理状态建立解。例如，在无传感器真空吸尘器世界中，初始信念状态为{1, 2, 3, 4, 5, 6, 7, 8}，我们必须找到一个在所有8种状态下都有效的动作序列。我们可以先找到状态1的解；然后检查它对于状态2是否有效；如果无效，则回溯寻找状态1的另一个解，以此类推。
正如与或搜索必须为与节点上的每个分支找到解一样，这一算法也必须为信念状态下的每个物理状态找到解；区别在于与或搜索可以为每个分支找到不同的解，而增量信念状态搜索必须找到一个对所有状态都有效的解。
增量方法的主要优点是，它通常能够快速检测出失败——当一个信念状态无解时，通常情况下，它的子集（包含最先检测的几个状态）也是无解的。在某些情况下，这将导致与信念状态规模成正比的加速，信念状态本身可能就和物理状态空间一样大。
4.4.2 部分可观测环境中的搜索
对许多问题来说，没有感知就无法求解。例如，求解无传感器8数码问题是不可能的。但是，一点点感知可能就有很大帮助：如果我们能够看到左上角的方格，就能求解8数码问题。解包括依次将每个滑片移动到可观测的方格中，并从那时起记录该滑片的位置。
对于部分可观测问题，问题形式化将定义一个Percept(s)函数，它返回智能体在给定状态下接收到的感知。如果感知是非确定性的，那么我们可以使用Percepts函数返回可能感知的集合。对于完全可观测问题，每个状态s下，Percept(s) = s，对于无传感器问题，Percept(s)= null。
考虑一个局部感知真空吸尘器世界，智能体拥有一个位置传感器（在左侧方格中生成感知L，右侧方格中生成感知R）和一个灰尘传感器（当前方格内有灰尘时生成感知Dirty，否则生成Clean）。因此，状态1的Percept为[L, Dirty]。对于部分可观测的情况，通常会存在几个状态产生相同感知的情况；状态3也会产生[L, Dirty]。因此，给定这一初始感知，初始信念状态将为{1,3}。我们可以将部分可观测问题信念状态之间的转移模型分为3个阶段，如图4-15所示。
● 预测（prediction）阶段与无传感器问题相同，计算由动作所导致的信念状态，Result(b, a)。为了强调这是一个预测，我们将其记为bˆ = Result(b, a)，其中b上方的“hat”表示“估计值”，我们还可以使用Predict(b, a)代替Result(b, a)。
● 可能感知（possible percept）阶段计算在预测的信念状态下可以观测到的感知集合（用字母o表示观测到的感知）：
● 更新（update）阶段为每个可能感知计算其可能得到的信念状态。更新后的信念状态bo是bˆ中可能产生这一感知的状态集合：
● 智能体需要在规划阶段处理可能的感知，因为在执行规划之前它不知道实际的感知。注意，在预测阶段，物理环境中的非确定性会扩大信念状态，但每个更新后的信念状态bo不会大于预测的信念状态bˆ；观测到的感知只能帮助减少不确定性。此外，对于确定性感知，不同感知的信念状态是不相交的，从而形成原始预测信念状态的一个划分。
图4-15 局部感知真空吸尘器世界中的两个转移实例。（a）确定性世界中，在初始信念状态下执行Right动作，所得到的新的预测信念状态有两个可能的物理状态；对于这些状态，可能的感知是[R, Dirty]和[R, Clean]，从而得到两种信念状态，每种都只包含一个物理状态。（b）光滑世界中，在初始信念状态下执行Right动作，所得到的新的信念状态具有4个物理状态；对于这些状态，可能的感知是[L, Dirty]、[R, Dirty]和[R, Clean]，从而得到图中所示的3种信念状态
综合这3个阶段，我们可以得到由给定动作及后续的可能感知所产生的可能信念状态：
（4-5）
4.4.3 求解部分可观测问题
4.4.2节介绍了在给定Percept函数的情况下，如何从底层物理问题推导出非确定性信念状态问题的Results函数。使用这一形式化，可以直接应用图4-11的与或搜索算法得到问题的解。图4-16为局部感知真空吸尘器世界的部分搜索树，假定初始感知为[L, Dirty]。它的解是一个条件规划：
注意，因为我们是在信念状态问题中应用与或搜索算法，所以它返回的条件规划所测试的是信念状态，而非实际状态。这是应该的：在部分可观测环境中，智能体并不知道实际状态。
图4-16 局部感知真空吸尘器世界问题的第一层与或搜索树，Suck是解序列中的第一个动作
与标准搜索算法应用于无传感器问题的情况一样，与或搜索算法将信念状态看作和任何其他问题状态一样的黑盒。可以通过检查先前生成的信念状态——它们是当前状态的子集或超集——来改进这一点，就像求解无传感器问题一样。同样可以推导出与无传感器问题中描述的那些算法类似的增量搜索算法。与黑盒方法相比，它们提供了显著的加速。
4.4.4 部分可观测环境中的智能体
部分可观测环境中的智能体先对问题形式化，接着调用搜索算法（例如And-Or-Search）求解，然后执行解步骤。这种智能体和完全可观测确定性环境中的智能体之间有两个主要区别。首先，问题的解将是一个条件规划而不是一个序列；为了执行if-then-else表达式，智能体需要测试if语句中的条件并执行正确的条件分支。其次，智能体需要在执行动作和接收感知时维护其信念状态。这一过程类似于式（4-5）中的预测-观测-更新过程，但更加简单，因为感知是由环境给出的，而不是由智能体自己计算的。给定初始信念状态b、动作a、感知o，则新的信念状态为
（4-6）
考虑一个类幼儿园真空吸尘器世界，智能体只能感知当前方格的状态，任一方格在任一时刻都有可能变脏，除非智能体恰好在那一时刻主动清理该方格。[7]图4-17为此环境中所维护的信念状态。
[7] 向那些不熟悉幼儿对环境影响的人表示歉意。
在部分可观测环境中——涵盖绝大多数真实世界环境——维护自身的信念状态是任何智能系统的核心功能。这一功能有很多不同的名称，包括监视（monitoring）、过滤（filtering）和状态评估（state estimation）。式（4-6）称为递归状态评估器，因为它根据前一状态计算新的信念状态，而不是检查整个感知序列。如果智能体不想“落后”，计算速度必须和感知进入的速度一样快。随着环境越来越复杂，智能体将只有时间计算近似信念状态，它可能重点关注感知对当前感兴趣的环境方面的影响。关于这一问题的大部分工作都是用概率论的工具处理随机的连续状态的环境，详见第14章。
图4-17 在局部感知的类幼儿园真空吸尘器世界中，信念状态维护的两个预测-更新周期
在本节中，我们将展示一个离散环境中的实例，其传感器是确定性的，动作是非确定性的。这个实例中涉及的机器人具有特定的状态评估任务，该任务称为定位（localization）：即在给定世界地图和一系列感知及行动的情况下，找到自己的位置。机器人放置在图4-18所示的迷宫环境中。它配备了4个声呐传感器，可以判断在4个罗盘方向上是否存在障碍物——外墙或者图中的深色阴影方格。感知以位向量的形式出现，每一位依次代表北、东、南、西方向，所以1011表示北、南、西方向有障碍物。
图4-18 机器人的可能位置，⊙，（a）一次观测E1 = 1011后。（b）移动一个方格并进行第二次观测E2 = 1010后。如果传感器没有噪声且转移模型是准确的，那么只有一个可能位置与这两个观测序列一致
我们假设传感器所提供的数据完全正确，而且机器人拥有正确的环境地图。但遗憾的是，机器人的导航系统发生故障，所以当它执行Right动作时，会随机移动到一个相邻方格。机器人的任务是确定它的当前位置。
假设机器人刚刚启动，并不知道自己的位置——那么它的初始信念状态b为包含所有位置的集合。接着机器人接收到感知1011，并使用公式bo = Update(1011)进行更新，得到如图4-18a所示的4个位置。查看整个迷宫你会发现这是仅有的4个可以产生感知1011的位置。
接下来，机器人执行Right动作，但结果是非确定性的。新的信念状态，ba = Predict(bo, Right)，包含了与bo中的位置相邻的所有位置。当接收到第二个感知1010时，机器人执行Update(ba, 1010)，此时信念状态已经只剩图4-18b所示的一个位置。这是下式得到的唯一位置：
对于非确定性动作，Predict阶段信念状态增加，但是Update阶段信念状态又减少回去——只要感知提供了有用的识别信息。有时感知对定位帮助不大：如果存在一个或多个很长的东西向走廊，那么机器人可能会接收到一个很长的1010感知序列，但它永远不会知道它在走廊的哪一位置。但对于地理上存在合理差异的环境，定位往往会迅速收敛到单个点，即使动作是非确定性的。
如果传感器发生故障怎么办？如果我们只能用布尔逻辑进行推理，那么我们就无法判断每个传感器位的正误，相当于没有任何感知信息。但我们将看到，概率推理（第12章）允许我们从故障传感器中提取有用信息，只要它出错的时间不超过一半。
4.5 在线搜索智能体和未知环境
到目前为止，我们主要关注使用离线搜索（offline search）算法的智能体。它们在执行第一个动作之前就已经计算出一个完整的解。相比之下，在线搜索（online search）[8]智能体则交替进行计算和动作：它首先执行一个动作，然后观测环境并计算下一个动作。在线搜索适用于动态或半动态环境，因为在这些环境中停止不动或计算时间太长都要付出代价。在线搜索在非确定性领域也很有用，因为它允许智能体将计算精力集中在实际发生的偶然事件上，而不是那些也许会发生但很可能不会发生的事件。
[8] 这里的“在线”指的是必须在接收到输入时立即进行处理的算法，而不是等待整个输入数据集都可用时再进行处理。“在线”的这种用法与“因特网连接”的概念无关。
当然，这里需要权衡：智能体提前规划得越多，发现自己陷入困境的频率越低。在未知环境中，智能体不清楚存在什么状态或者动作会产生什么结果，必须使用自身的动作作为实验来了解环境。
在线搜索的一个典型实例是地图构建问题（mapping problem）：机器人放置在一个未知建筑中，它必须进行探索以绘制一个从A到B的地图。逃离迷宫的方法——有抱负的古代英雄所需的知识——也是在线搜索算法的实例。然而，空间探索并不是在线探索的唯一形式。以一个新生儿为例：它可能可以做许多举动，却不知道这些动作的后果，而且它只体验过少数几个它能达到的可能状态。
4.5.1 在线搜索问题
求解在线搜索问题需要交替进行计算、感知和动作。我们首先假设环境是确定性的和完全可观测的（第17章放宽了这些假设），并规定智能体只知道以下内容。
● Actions(s)，状态s下的合法动作。
● c(s, a, s')，在状态s下执行动作a到达状态s'的代价。注意，前提是智能体知道s'是结果。
● Is-Goal(s)，目标测试。
特别要注意的是，智能体不能确定Result(s, a)的值，除非它确实在s中执行了a。例如，在图4-19所示的迷宫问题中，智能体并不知道从(1, 1)执行Up动作会到达(1, 2)；也不知道再执行Down动作会回到(1, 1)。在某些应用中可以减少这种无知——例如，机器人探测器可能知道它是如何移动的，只是不知道障碍物的位置。
最后，智能体可能可以访问一个可容许的启发式函数h(s)，该函数对从当前状态到目标状态的距离进行估计。例如，在图4-19中，智能体可能知道目标的位置，从而可以使用曼哈顿距离启发式函数（3.6节）。
图4-19 一个简单的迷宫问题。智能体必须从S出发到达G，但它对环境一无所知
通常，智能体的目标是以最小代价到达目标状态。（另一个可能目标是简单地探索整个环境。）代价是智能体在移动过程中产生的总的路径代价。通常将它与智能体事先知道搜索空间时所产生的路径代价（即已知环境中的最优路径）进行比较。在在线算法的术语中，这种比较被称为竞争比（competitive ratio），我们希望它尽可能地小。
在线探索器很容易陷入死胡同（dead-end）：无法到达任何目标状态的状态。如果智能体不知道每个动作的后果，它可能会“跳进陷阱”，因此永远无法到达目标。一般来说，没有一种算法能在所有状态空间中都避免进入死胡同。以图4-20a中的两个死胡同状态空间为例。对已经访问过状态S和A的在线搜索算法来说，它无法分辨自己是处于顶部的状态还是底部的状态；根据智能体观测到的感知信息，这两个状态看起来是相同的。因此，它不可能知道如何在两个状态空间中选择正确的动作。这是一个对手论证（adversary argument）的实例——想象对手在智能体探索状态空间时构建状态空间，并将目标和死胡同放在它所选择的任何地方，如图4-20b所示。
图4-20 （a）两个可能将在线搜索智能体引入死胡同的状态空间。任何给定智能体都会在至少一个空间中失败。（b）二维环境实例，将导致在线搜索智能体沿着一条任意低效的路线到达目标。无论智能体做出何种选择，对手都会用另一堵很长很薄的墙来阻挡这条路线，这样智能体所走的路径就会比最优可能路径长得多
死胡同是机器人探索中的一个真正的难点——楼梯、斜坡、悬崖、单行道甚至自然地形中都存在从它出发某些动作不可逆（irreversible）的状态——没有办法回到之前的状态。我们提出的探索算法只保证在可安全探索（safely explorable）的状态空间中是有效的，也就是说，从每个可达状态出发都存在可以到达的目标状态。所有动作都可逆的状态空间，如迷宫和8数码，显然是可安全探索的（如果它们有解的话）。我们将在22.3.2节中更深入地讨论安全探索的话题。
即使在可安全探索的环境中，如果存在代价无界的路径，也不能保证竞争比有界。在动作不可逆的环境中，很容易发现上述结论，但事实上，可逆情况下也是如此，如图4-20b所示。因此，通常会根据整个状态空间的大小来描述在线搜索算法的性能，而不是仅仅根据最浅层目标的深度。
4.5.2 在线搜索智能体
可观测环境中的在线智能体在每个动作之后都会接收到一个感知，告诉它目前到达了哪一状态，通过这些信息，智能体可以更新它的环境地图。更新后的地图将用于规划下一步。规划和动作交替进行意味着在线搜索算法与之前介绍的离线搜索算法有很大不同：离线算法探索其状态空间模型，而在线算法探索真实世界。例如，A*可以在空间的某部分扩展一个节点，然后马上在空间的另一相距很远的部分扩展另一个节点，因为节点扩展设计的是模拟动作而非真实动作。
另外，在线算法只能找到其实际占据的状态的后继。为了避免长途跋涉到一个相距较远的状态来扩展下一个节点，按照局部顺序扩展节点似乎更好。深度优先搜索恰好具有这一性质，因为（如果算法不用回溯）下一个扩展节点是前一个扩展节点的子节点。
图4-21为在线深度优先探索智能体（动作是确定性但未知的）。智能体将它的地图存储在一个result[s, a]表中，记录了在状态s下执行动作a所产生的状态。（对于非确定性动作，智能体可以在results[s, a]中记录状态集合。）只要当前状态存在未探索过的动作，智能体就会尝试其中一个动作。当智能体尝试完某个状态下的所有动作时，问题就来了。在离线深度优先搜索中，我们只是将状态从队列中删除；而在线搜索中，智能体必须在物理世界中回溯。在深度优先搜索中，这意味着回溯到智能体进入当前状态前的最近状态。为了实现这一点，算法需要维护另一个表，表中列出了每个状态尚未回溯到的前驱状态。如果智能体已经没有可回溯的状态，那么搜索就完成了。
图4-21 使用深度优先探索的在线搜索智能体。智能体只有在每个动作都可以被其他动作“撤消”的状态空间中才能安全地探索
我们建议读者在求解图4-19中的迷宫问题时跟踪Online-DFS-Agent的进度。很容易看到，最坏情况下，智能体最终恰好要遍历状态空间中的每个连接两次。对探索来说，这是最优的；但是，对寻找目标来说，如果在初始状态旁边恰好有一个目标状态，智能体的竞争比将变得无限差。在线迭代加深算法可以解决这一问题；对于均衡树环境，这样一个智能体的竞争比是一个很小的常数。
由于其回溯方法，Online-DFS-Agent只在动作可逆的状态空间中有效。在一般的状态空间中，有一些更复杂的算法，但是这类算法的竞争比都不是有界的。
4.5.3 在线局部搜索
与深度优先搜索一样，爬山搜索在节点扩展上也有局部性。事实上，因为爬山搜索在内存中只保存一个当前状态，它已经是在线搜索算法！遗憾的是，基础算法并不适用于探索，因为智能体会陷入局部极大值而无路可走。此外，不能使用随机重启，因为智能体无法将自己瞬移到一个新的初始状态。
相比于随机重启，我们可以考虑使用随机游走（random walk）来探索环境。随机游走只是从当前状态中随机选择一个可用动作，可以优先考虑尚未尝试的动作。容易证明，当空间有限且可安全探索时，随机游走最终会找到一个目标或完成探索。[9]但是，这一过程可能非常慢。图4-22为一个环境实例，在这个环境中，随机游走将耗费指数级的步骤来寻找目标，因为对于第一行除S之外的每个状态，后退的可能性是前进的两倍。当然，这个例子是人为设计的，但是真实世界中许多状态空间的拓扑结构都会导致这类随机游走“陷阱”。
[9] 随机游走在无限的一维和二维网格上是完备的。在三维网格上，游走返回起点的概率只有大约0.3405（Hughes, 1995）。
图4-22 环境实例，随机游走需要耗费指数级的步骤来寻找目标
事实证明，增加爬山法的内存而非随机性是一种更有效的方法。基本思想是，存储从已访问的每个状态出发到达目标所需代价的“当前最佳估计”H(s)。H(s)开始时只是启发式估计，然后根据智能体在状态空间中获得的经验不断更新。
图4-23为一维状态空间中的一个简单示例。在图4-23a中，智能体似乎陷入了位于红色状态的局部极小值。智能体不应该停留在原地，而应该根据其邻居节点的当前代价估计值选择到达目标的最优路径。经由邻居节点s'到达目标的估计代价等于到达s'的代价加上从s'到达目标的估计代价，即c(s, a, s') + H(s')。在这个示例中，有2个动作，估计代价分别为向左1 + 9，向右1 + 2，因此最好向右移动。
在图4-23b中，显然，将图4-23a中红色状态的代价估计为2是过于乐观的。因为最佳移动的代价为1，而且其结果状态离目标状态至少还有2步，所以红色状态离目标一定至少还有3步，所以应该相应地更新红色状态的H，如图4-23b所示。继续上述过程，智能体将再来回移动两次，每次都会更新H并“拉平”局部极小值，直到它逃逸到右侧。
能够实现上述方案的智能体称为实时学习A*（learning real-time A*，LRTA*）智能体，如图4-24所示。同Online-DFS-Agent一样，它用result表构建环境地图。它首先更新刚刚离开的状态的代价估计值，然后根据当前的代价估计值选择“显然最佳”移动。一个重要的细节是，在状态s下尚未尝试的动作总是被假定为以最少的可能代价，即h(s)直接到达目标。这种不确定性下的乐观主义（optimism under uncertainty）鼓励智能体去探索新的、可能更有希望的路径。
图4-23 一维状态空间上LRTA*的5次迭代。每个状态都标有H(s)，即到达目标的当前代价估计值，每个连接的动作代价为1。红色状态表示智能体的位置，每次迭代所更新的代价估计值以双圈标记
图4-24 LRTA*-Agent根据相邻状态的值选择动作，智能体在状态空间中移动时更新状态值
LRTA* 智能体保证在任何有限的、可安全探索的环境中都能找到目标。然而，不同于A*，LRTA*在无限状态空间中是不完备的——在某些情况下，它可能被无限地引入歧途。在最坏情况下，探索状态数为n的环境可能需要O(n2)步，但通常情况下会比这种情况好得多。LRTA* 智能体只是一个庞大的在线智能体家族中的一员，可以通过以不同方式指定动作选择规则和更新规则来定义。我们将在第22章中详细讨论这一发源于随机环境的在线智能体家族。
4.5.4 在线搜索中的学习
在线搜索智能体初始时对环境的无知为我们提供了一些学习的机会。首先，智能体通过记录它们的每一次经验来学习环境“地图”——更准确地说，学习每种状态下每个动作的结果。其次，当智能体以正确的方式探索状态空间时，局部搜索智能体可以利用局部更新规则获得每个状态代价更准确的估计值。一旦知道代价的准确值，只需移动到代价最低的后继状态就能实现最优决策，也就是说，纯粹的爬山法就是一个最优策略。
如果按照我们的建议在图4-19的环境中跟踪Online-DFS-Agent的行为，你会注意到智能体不是非常聪明。例如，在它已经知道Up动作能够从(1, 1)到达(1, 2)后，它仍然不知道Down动作能回到(1, 1)，或者Up动作还能从(2, 1)到(2, 2)，从(2, 2)到(2, 3)，等等。一般来说，我们希望智能体能够学到，Up在不遇到墙的情况下使得y坐标值增加，Down则使得y坐标值降低，等等。
要实现这一点，我们需要做两件事。首先，需要对这类一般规则有一个形式的、可显式操纵的表示；到目前为止，信息都被隐藏在名为Result函数的黑盒中。第8～11章将专门讨论这个问题。其次，需要能够根据智能体所得到的具体观测信息构造合适的一般规则的算法。这些内容将在第19章中讨论。
如果我们预计将来会被要求求解多个类似问题，那么投入时间（和内存）使得这些未来搜索更容易是有意义的。有几种方法可以做到这一点，它们都属于增量搜索（incremental search）的范畴。我们可以将搜索树保留在内存中，并复用在新问题中未发生改变的部分。我们可以保留启发式代价函数h的值，并在获得新信息时更新它们——要么是因为世界发生改变，要么是因为我们计算出了更好的估计值。或者我们可以保留最优路径的g值，用它们拼凑出一个新的解，并在世界发生改变时对它们进行更新。
小结
本章讨论了部分可观测的、非确定性的、未知的和连续的环境中问题的搜索算法。
● 局部搜索算法，如爬山法，在内存中只保留少量状态。这些方法已被应用于优化问题，其思想是找到一个高分值的状态，而不考虑进入该状态的路径。研究人员已经开发了一些随机局部搜索算法，包括模拟退火，当给定适当的冷却方案时它能返回最优解。
● 许多局部搜索方法同样适用于连续空间中的问题。线性规划和凸优化问题服从状态空间形状和目标函数性质上的某些限制，并且允许多项式时间算法，这些算法在实践中往往非常高效。对于一些数学上合式的问题，我们可以使用微积分找到梯度为零的最大值；对于其他问题，我们必须使用经验梯度，即测量两个邻近点间的适应度差值。
● 进化算法是一种维护状态种群的随机爬山搜索。通过突变和杂交（结合状态对）产生新状态。
● 在非确定性环境中，智能体可以应用与或搜索算法生成应变规划，无论执行过程中出现何种结果，它都能实现目标。
● 如果环境是部分可观测的，信念状态表示智能体可能位于的可能状态的集合。
● 标准搜索算法可以直接应用于信念状态空间求解无传感器问题，而信念状态与或搜索算法可以求解一般的部分可观测问题。在一个信念状态中逐状态构造解的增量算法通常效率更高。
● 探索问题发生在智能体对环境的状态和动作一无所知时。对于可安全探索的环境，在线搜索智能体能够构建地图并找到目标（如果存在的话）。根据经验来更新启发式估计值提供了一种避免局部极小值的有效方法。
读者服务：
微信扫码关注【异步社区】微信公众号，回复“e59810”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。