4.5.2 联机搜索智能体
在每个行动之后，联机智能体都能接收到感知信息，告诉它到达了哪个状态；根据这个信息，它可以扩展自己的环境地图。当前的地图用来决定下一步往哪里走。这种规划和行动的交叉意味着联机搜索算法和我们看到的脱机搜索算法是相当不同的。例如，有些脱机算法如A*有能力在状态空间的一部分扩展一个节点，然后马上在空间的另一部分扩展另一个节点，因为节点扩展涉及的是模拟的而不是实际的行动。相反，联机算法只会扩展它实际占据的节点。为了避免遍历整个搜索树去扩展下一个节点，按照局部顺序扩展节点看来更好一些。深度优先搜索就有这个性质，因为（除了回溯的时候）下一个要扩展的节点总是前一个被扩展节点的子节点。
图4.20中显示了一个联机深度优先搜索智能体。这个智能体将它的环境地图存储在一个表里， result[a, s]，记录了在状态s执行行动a得到的结果状态。只要从当前状态出发的某个行动还没有被探索过，智能体就要尝试这个行动。难题来自智能体尝试完一个状态的所有行动之后。在脱机深度优先搜索中，状态很简单地被从队列中删除；而在联机搜索中，智能体不得不实际地回溯。在深度优先搜索中，这意味着回溯到智能体进入当前状态前最近的那个状态。这要通过维护一个表来达到，该表列出每个状态的所有还没有回溯的前辈状态。如果智能体已经没有可回溯的状态了，那么它的搜索完成了。
我们建议读者跟踪图4.18中所示的用于迷宫问题的ONLINE-DFS-AGENT的过程。很容易看出在最坏的情况下，智能体在状态空间中最终要通过每个连接刚好两次。对于探索来说，这是最优的；另一方面，对于寻找目标来说，当一个目标状态就在初始状态旁边的时候，如果智能体要通过很长的旅程才找到目标，它的竞争率就太差了。联机的迭代深入解决了这个问题；对于可表示为一致搜索树的环境，这样一个智能体的竞争率是一个很小的常数。
因为用了回溯的方法，ONLINE-DFS-AGENT只能用在行动可逆的状态空间中。稍微复杂一些的算法可以在一般的状态空间中工作，但是这样的算法没有具备一个有界的竞争率。
图4.20 使用深度优先探索的一个联机搜索智能体。这个智能体只能用于双向搜索空间
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
