联机局部搜索

4.5.3 联机局部搜索

像深度优先搜索一样，爬山法搜索在节点扩展的时候也有局部性。实际上，因为它在内存中只存放一个当前状态，爬山法搜索已经是一个联机搜索算法了！不幸的是，它最简单的形式没什么用，因为它使智能体呆在局部极大值上而无处可去。另外，随机重新开始算法是不可用的，因为智能体不能把自己传送到一个新状态。

取代随机重新开始，可以考虑使用随机行走来探索环境。随机行走简单地从当前状态随机选择可能的行动之一；选择的时候可以偏向尚未尝试过的行动。容易证明倘若状态空间有限[21]，随机行走最终会找到目标或完成探索。另一方面，这个过程会很慢。图4.21显示了一个环境，在其中随机行走算法将耗费指数级的步数来找到目标，因为每一步往回走的概率都是向前走的两倍。当然这个例子是设计出来的，但是许多现实世界的状态空间的拓扑结构都能造成此类对随机行走而言的“陷阱”。

图4.21 一个使随机行走耗费指数级步数才能找到目标的环境

提高爬山法算法的内存利用率而不是随机性是个更有效的方法。基本思想是存储一个从每个已经访问过的状态到达目标状态的耗散中的“当前最佳估计耗散”H(s)。H(s)从启发式估计h(s)出发，在智能体从状态空间中获得经验时对H(s)进行更新。图4.22显示了一个一维状态空间的简单例子。在（a）中，智能体看起来会被平坦的局部极小值卡住，即图中阴影部分所示状态。智能体应该根据对邻居状态的当前耗散估计来选择到达目标的最佳路径，而不是停留下来。经过邻居s ' 到达目标的估计耗散是到达s ' 的耗散加上从s ' 到达目标的估计耗散——即c(s, a, s ')+H(s ')。在例子中，有两个行动的估计耗散为1+9和1+2，因此看来最好是向右移动。现在，显然对阴影状态的耗散估计为2过于乐观了。因为最佳移动消耗为1并且会到达一个离目标状态至少2步的状态，阴影状态到目标状态至少需要3步，因此它的H需要相应的更新，如图4.22（b）所示。继续这个过程，智能体将再来回运动两次，每次都更新H并“平滑”局部极小值，直到它能向右逃离为止。

图4.22 在一个一维状态空间上LRTA*的五次迭代。每个状态都标出到达目标的当前耗散估计H(s)，每条弧则标出其单步耗散。阴影状态表示智能体所在的位置，每次迭代的更新值画上圆圈标记出来

实现这个方案的智能体被称为实时学习A*（LRTA*）智能体，如图4.23所示。像ONLINE-DFS-AGENT一样，它用result表建造了一个环境地图。它更新了刚刚离开的状态的耗散估计，然后根据当前的耗散估计选择“显然最佳的”移动。一个重要的细节是：在状态s从未尝试过的行动总被假设为能用最小可能耗散（也就是 h(s)）直接达到目标。这种不确定条件下的乐观主义鼓励智能体探索新的、可能更有希望的路径。

LRTA*智能体在任何有限的、可安全探索的环境中都保证能找到目标。然而，不同于A*，它对于无限的状态空间不是完备的——有些情况能把它引入无限的歧途。它在最坏情况下可以用 O(n2)步探索一个n状态的环境，不过经常做得更好。LRTA*智能体只是庞大的联机智能体家族中的一员，这些联机智能体通过指定不同方式的行动选择规则和更新规则来定义。我们将在第二十一章中详细讨论从随机环境发源的联机智能体家族。

图4.23 LRTA*-AGENT根据邻居状态的值选择一个行动，智能体在状态之间移动时更新状态值