联机搜索问题

4.5.1 联机搜索问题

联机搜索问题只能通过智能体执行行动解决，而不是纯粹的计算过程。我们假设智能体仅知道以下信息：

• ACTIONS(s)，返回状态s下可能行动的列表；

• 单步耗散函数c(s, a, s ') ——注意直到智能体知道行动的结果为状态s ' 时才能用；

• GOAL-TEST(s)。

需要注意的是，智能体不能访问一个状态的后继，除非实际尝试了该状态下的所有行动。例如，在图4.18中所示的迷宫问题中智能体不知道从状态（1,1）采取行动Up能到达状态（1,2）；或者当已经到达状态（1, 2）时，不知道行动Down能回到状态（1, 1）。在某些应用中这种无知程度可以降低——例如，机器人探测器也许知道其移动的行动是如何运转的，只是对障碍物的位置是无知的。

图4.18 一个简单的迷宫问题。智能体从状态S出发要到达状态G，但是智能体对环境一无所知

我们假设智能体总能认出它以前已经到达过的状态，并且假设它的动作是确定性的。（这两个假设条件在第十七章中将得到放松。）最后，智能体将使用一个能够估计从当前状态到目标状态的距离的可采纳启发函数 h(s)。例如，在图 4.18中，智能体知道目标的位置并且可以使用曼哈顿距离启发式。

典型地，智能体的目标是用最小的代价到达目标状态。（另一个可能的目标是完全探索整个环境。）代价是指智能体实际旅行经过的路径的总耗散。把这个耗散与智能体要走的路径的耗散相比较是常见的，如果它事先了解搜索空间——即知道实际最短的路径（或最短的完全探索）。在联机算法的术语中，这被称为竞争率；我们希望这个值尽可能小。

虽然这听起来是一个合理的要求，但是容易看到在某些情况下最好的可达到的竞争率也是正无穷。例如，如果一些行动是不可逆的，那么联机搜索有可能偶然进入一个无法到达目标状态的死状态。也许你发现“偶然”这个词并不可信——毕竟也许有算法刚好不会探索到死路。更精确地，我们说的是没有算法能够在所有的状态空间中避免死路。考虑图4.19（a）所示的两个有死路的状态空间。对于一个已经访问过状态S和A的联机搜索算法而言，这两个状态空间看起来是一样的，所以它必然在这两个状态空间中做出相同的决策。因此，它对其中之一就会失败。这是一个敌对参数的例子——我们可以想象一个对手在智能体探索的时候构造状态空间，并且它可以随意放置目标状态和死状态。

死路是机器人探索中的实际困难——楼梯、斜坡、悬崖和各种各样自然的地形都提供了不可逆行为的机会。为了取得进展，我们可以简单地假设状态空间是可安全探索的——就是说，从每个可到达的状态出发都有某些目标状态是可到达的。具有可逆行动的状态空间，例如迷宫问题和八数码游戏，可以视为无向图并且显然是可安全探索的。

图 4.19 （a）两个能导致联机搜索智能体陷入死路的状态空间。任何一个给定的智能体至少在其中一个状态空间中陷入死路。（b）一个能使联机搜索智能体跟随到达目标的任意低效率的路径的二维环境。不管智能体选择哪条路，对手都用细长的墙封锁路径，所以智能体所走的路径比最佳可能路径要长很多

即使在可安全探索的环境里，如果有无界耗散的路径就一定会有无界的竞争率。这在行动不可逆的环境中很容易显示出来，不过事实上它在行动可逆的情况下也是成立的，如图 4.19（b）所示。由于这个原因，通常根据整个状态空间的大小而不是仅根据最浅的目标的深度来描述联机搜索算法的性能。