第4章越经典搜索

1、第第4章章 超越经典搜索超越经典搜索中国科大中国科大 计算机学院计算机学院第第部分部分 问题求解问题求解本章内容本章内容 4.1 局部搜索算法和最优化问题局部搜索算法和最优化问题 4.2 连续空间中的局部搜索连续空间中的局部搜索 4.3 使用不确定动作的搜索使用不确定动作的搜索 4.4 使用部分可观察信息的搜索使用部分可观察信息的搜索 4.5 联机搜索联机搜索agent和未知环境和未知环境本节内容本节内容 联机搜索问题联机搜索问题 联机搜索智能体联机搜索智能体 联机局部搜索联机局部搜索 联机搜索的学习联机搜索的学习智能体和环境智能体和环境 智能体智能体可以被视为通过传感器感知所处环境并通过可以

2、被视为通过传感器感知所处环境并通过执行器对该环境产生作用的东西。执行器对该环境产生作用的东西。 agent传感器传感器 ？执行器执行器环境环境感知感知行动行动真空吸尘器世界真空吸尘器世界 只有两个地点的真空吸尘器世界只有两个地点的真空吸尘器世界percept sequenceactiona, cleana, dirtyb, cleanb, dirtya, clean, a, cleana, clean, a, dirtya, clean, a, clean, a, cleana, clean, a, clean, a, dirtyrightsuckleftsuckrightsuckrights

3、uck联机搜索问题联机搜索问题脱机搜索：脱机搜索：在涉足实际问题之前先计算出完整的解在涉足实际问题之前先计算出完整的解决方案，然后不需要感知就能够执行解决方案。决方案，然后不需要感知就能够执行解决方案。联机搜索智能体：联机搜索智能体：通过计算和行动的交叉来完成。通过计算和行动的交叉来完成。 智能体首先采取一个行动；智能体首先采取一个行动； 然后观察问题的环境并且计算下一个行动。然后观察问题的环境并且计算下一个行动。脱机搜索：脱机搜索：通常需要考虑所有可能发生的情况而制通常需要考虑所有可能发生的情况而制定可能是指数级大小的偶发事件处理计划。定可能是指数级大小的偶发事件处理计划。联机搜索：联机搜索

4、：只需要考虑实际发生的情况。只需要考虑实际发生的情况。联机搜索问题联机搜索问题应用领域：应用领域： 动态或半动态的问题领域；动态或半动态的问题领域； 对于停留不动或者计算时间太长都会有惩罚的领对于停留不动或者计算时间太长都会有惩罚的领域；域； 甚至是一个完全随机的领域。甚至是一个完全随机的领域。探索问题探索问题必须用联机搜索。必须用联机搜索。 例如：放在新建大楼里的机器人，要求它探索大例如：放在新建大楼里的机器人，要求它探索大楼，绘制出一张从楼，绘制出一张从a到到b的地图。的地图。联机搜索只能通过智能体执行联机搜索只能通过智能体执行行动行动解决，而不是纯解决，而不是纯粹的计算过程。粹的计算过程

5、。联机搜索问题联机搜索问题 假设智能体仅知道如下信息：假设智能体仅知道如下信息：actions( s )，返回状态，返回状态s下可能行动的列表；下可能行动的列表；单步耗散函数单步耗散函数c( s, a, s? )，但必须在智能体知道，但必须在智能体知道行动的结果为行动的结果为s?时才能用；时才能用；goal-test( s )。 注意：注意：智能体不能访问一个状态的后继，除非它智能体不能访问一个状态的后继，除非它实实际际尝试了该状态下的所有行动。尝试了该状态下的所有行动。联机搜索问题联机搜索问题 迷宫问题：迷宫问题：目标是从状态目标是从状态s出发到达状态出发到达状态g。但智能体对环境。但智能体

6、对环境一无所知。一无所知。 智能体不知道从状态（智能体不知道从状态（1，1）采取）采取up行动能到达状态（行动能到达状态（1，2）；）； 或者，当已经到达状态（或者，当已经到达状态（1，2）时，不知道行动）时，不知道行动down能能回到状态（回到状态（1，1）。）。 在某些应用中，这种在某些应用中，这种“无知程度无知程度”可以降低。比如，可以降低。比如，机器机器人探测器人探测器也许知道其移动的行动是如何运转的，只是对障也许知道其移动的行动是如何运转的，只是对障碍物一无所知。碍物一无所知。联机搜索问题联机搜索问题假设：假设： 智能体总能够智能体总能够认出认出它以前已经达到过的状态，它以前已经达到

7、过的状态，并且它的动作是确定性的。并且它的动作是确定性的。 智能体将使用一个能够智能体将使用一个能够估计估计从当前状态到目标从当前状态到目标状态的距离的可采纳启发函数状态的距离的可采纳启发函数h(s)。例如，对于迷宫问题，智能体知道目标的位置并且可例如，对于迷宫问题，智能体知道目标的位置并且可以使用以使用曼哈顿距离曼哈顿距离启发式。启发式。联机搜索问题联机搜索问题事先了解搜索空间）实际最短的路径（如果路径的总耗散智能体实际旅行经过的竞争率 理想的竞争率为理想的竞争率为1。联机搜索问题联机搜索问题 具有具有死路死路的状态空间。的状态空间。 死路是机器人探索中的实际困难死路是机器人探索中的实际困难

8、楼梯、斜坡、楼梯、斜坡、悬崖和各种各样的自然地形都可能会是死路。悬崖和各种各样的自然地形都可能会是死路。联机搜索问题联机搜索问题 假设：假设：状态空间是状态空间是可安全探索可安全探索的。的。 从每个可到达的状态出发都有某些目标状态是可从每个可到达的状态出发都有某些目标状态是可到达的。到达的。 即使在可安全探索的环境里，如果有无界耗散的路即使在可安全探索的环境里，如果有无界耗散的路径就一定会有径就一定会有无界的竞争率无界的竞争率。不管智能体选择那条不管智能体选择那条路，对手都用细长的路，对手都用细长的墙封锁路径，所以智墙封锁路径，所以智能体所走的路径比最能体所走的路径比最佳路径可能要长得多。佳路

9、径可能要长得多。本章内容本章内容 联机搜索问题联机搜索问题 联机搜索智能体联机搜索智能体 联机局部搜索联机局部搜索 联机搜索的学习联机搜索的学习联机搜索智能体联机搜索智能体 智能体在每个行动之后，都能够接收到智能体在每个行动之后，都能够接收到感知信息感知信息，告，告诉它到了那个状态。诉它到了那个状态。 根据这个状态，智能体可以逐步扩展自己的根据这个状态，智能体可以逐步扩展自己的环境地图环境地图。 当前的地图用来决定下一步往哪里走。当前的地图用来决定下一步往哪里走。联机搜索智能体联机搜索智能体 联机搜索算法：联机搜索算法：规划和行动交叉进行。规划和行动交叉进行。 脱机搜索算法，如脱机搜索算法，如

10、a*：可以在状态空间的可以在状态空间的一部分一部分扩扩展一个节点，然后马上又在空间的展一个节点，然后马上又在空间的另一部分另一部分扩展另扩展另一个节点。一个节点。 因为脱机算法节点扩展涉及的是因为脱机算法节点扩展涉及的是模拟的模拟的而不是实而不是实际的行动。际的行动。联机搜索智能体联机搜索智能体 联机搜索算法：联机搜索算法：只会扩展它实际占据的节点。只会扩展它实际占据的节点。 为了避免遍历整个搜索树去扩展下一个节点，按照为了避免遍历整个搜索树去扩展下一个节点，按照局部顺序局部顺序扩展节点看来更好一些。扩展节点看来更好一些。 例如，采用例如，采用深度优先搜索深度优先搜索。 如下图，假设智能体已经

11、到了节点如下图，假设智能体已经到了节点8。 但是，从已搜索的状态空间看，从节点但是，从已搜索的状态空间看，从节点4继续搜索似乎更继续搜索似乎更好一些？好一些？ 智能体应该回溯回去搜索吗？智能体应该回溯回去搜索吗？联机深度优先搜索智能体联机深度优先搜索智能体 ；该智能体可用于双向搜索空间。；该智能体可用于双向搜索空间。 function online-dfs-agent(s) returns an action inputs: s, a percept that identifies the current state1. if goal-test(s) then return stop2. i

12、f s is a new state then unexploreds action(s)3. if s is not null then do ；s是前一个状态，初值为空是前一个状态，初值为空4. resulta, s s ；a是前一个行动，即是前一个行动，即action5. add s to the front of unbacktrackeds6. if unexploreds is empty then7. if unbacktrackeds is empty then return stop8. else a an action b such that resultb, spop(u

13、nbacktrackeds)9. else a pop(unexploreds)10. s s11. return a联机深度优先搜索智能体联机深度优先搜索智能体 例如，例如，迷宫问题。迷宫问题。 因为使用了回溯的办法，因为使用了回溯的办法，online-dfs-agent只只能能用于用于行动可逆的状态空间行动可逆的状态空间中。中。本章内容本章内容 联机搜索问题联机搜索问题 联机搜索智能体联机搜索智能体 联机局部搜索联机局部搜索 联机搜索的学习联机搜索的学习联机局部搜索联机局部搜索 爬山法爬山法搜索在内存中只存放一个当前状态。搜索在内存中只存放一个当前状态。 因此，它是一个联机搜索算法。因此，

14、它是一个联机搜索算法。 易使智能体呆在易使智能体呆在局部极大值局部极大值上而无处可去。上而无处可去。 改进方法：改进方法： 随机重新开始随机重新开始是不可能的。因为智能体不能把自是不可能的。因为智能体不能把自己传送到一个新的状态。己传送到一个新的状态。 不妨考虑不妨考虑随机行走随机行走。联机局部搜索联机局部搜索 使用使用“随机行走随机行走”取代取代“随机重新开始随机重新开始”来探索环来探索环境。境。 从当前状态中随机选择可能的行动之一；从当前状态中随机选择可能的行动之一； 选择的时候也可以偏向选择的时候也可以偏向未尝试过的行动未尝试过的行动。 可以证明：可以证明：如果状态是有限的，随机行走最终

15、会找如果状态是有限的，随机行走最终会找到目标或完成探索。到目标或完成探索。随机行走算法的例子随机行走算法的例子 随机行走算法的例子：随机行走算法的例子： 将耗尽将耗尽指数级指数级步骤来达到目标。步骤来达到目标。 因为每一步往回走的概率都是向前走的两倍。因为每一步往回走的概率都是向前走的两倍。 现实世界中的许多状态空间都有此类对现实世界中的许多状态空间都有此类对“随机行走随机行走”是是“陷阱陷阱”的拓扑结构。的拓扑结构。怎么办？怎么办？联机局部搜索联机局部搜索 提高爬山法算法的内存利用率：提高爬山法算法的内存利用率：存储每个已经访问存储每个已经访问过的状态到目标状态的耗散的过的状态到目标状态的耗

16、散的“当前最佳估计耗散当前最佳估计耗散h(s) ” 。 h(s)从启发式估计从启发式估计h(s)出发，在智能体从状态空出发，在智能体从状态空间中获得经验时对间中获得经验时对h(s)进行更新。进行更新。提高爬山法算法的内存利用率提高爬山法算法的内存利用率 例、例、（a）智能体已经进入局部最优。）智能体已经进入局部最优。 此时智能体根据对邻居状态的当前耗散估计来选择到达目此时智能体根据对邻居状态的当前耗散估计来选择到达目标的最佳路径，而不是停下来。标的最佳路径，而不是停下来。经过邻居经过邻居s 到达目标的估计耗散为：到达目标的估计耗散为：c(s, a, s )+h(s )。 （b）两个邻接的耗散分

17、别为（）两个邻接的耗散分别为（19）和（）和（12），选择），选择向右移动。此时，向右移动。此时，原来的状态原来的状态到达到达目标状态目标状态至少需要（至少需要（12）步，因此它的）步，因此它的h需要更新。需要更新。实时学习实时学习a*（lrta*)智能体智能体 function lrta*-agent(s) returns an action inputs: s, a percept that identifies the current state1. if goal-test(s) then return stop2. if s is a new state (not in h) the

18、n hs h(s)3. unless s is null ；s是前一个状态，初值为空是前一个状态，初值为空4. resulta, s s ；a是前一个行动，即是前一个行动，即action5. hs min lrta*-cost(s, b, resultb,s, h) | bactions(s)6. a an action b in actions(s) that7. minimizes lrta*-cost(s, b, resultb, s, h)8. s s9. return a function lrta*-cost(s, a, s, h) returns a cost estimate1

19、. if s is undefined then return h(s)2. else return c(s, a, s)hs实时学习实时学习a*（lrta*)智能体智能体 在状态在状态s从未尝试过的行动从未尝试过的行动总被假设为能用总被假设为能用最小可能耗散最小可能耗散（即（即h(s)）直接到达目标。）直接到达目标。 这种这种不确定条件下的乐观主义不确定条件下的乐观主义鼓励智能体探索新的、可能鼓励智能体探索新的、可能更有希望的路径。更有希望的路径。 lrta*智能体智能体在任何有限的、可安全探索的环境中都能保证在任何有限的、可安全探索的环境中都能保证找到目标。找到目标。 lrta*智能体智能

20、体不同于不同于a*： lrta*智能体对于智能体对于无限的状态空间无限的状态空间是不完备的是不完备的有些情况能把它引入无限的歧途。有些情况能把它引入无限的歧途。 lrta*智能体只是庞大的智能体只是庞大的联机智能体家族联机智能体家族中的一员。中的一员。 这些联机智能体通过采用这些联机智能体通过采用不同的行动选择规则和更新规则不同的行动选择规则和更新规则来定义。来定义。本章内容本章内容 联机搜索问题联机搜索问题 联机搜索智能体联机搜索智能体 联机局部搜索联机局部搜索 联机搜索的学习联机搜索的学习联机搜索的学习联机搜索的学习 联机搜索智能体联机搜索智能体仅仅根据它的经历学习到环境的仅仅根据它的经历

21、学习到环境的“地图地图”。 每个状态经过每个行动的结果。每个状态经过每个行动的结果。 环境是确定的。因此，每个行动经历一次就够了。环境是确定的。因此，每个行动经历一次就够了。 局部搜索智能体局部搜索智能体（如（如ltra*智能体）利用局部更新规则可以智能体）利用局部更新规则可以得到每个状态更精确的估计值。得到每个状态更精确的估计值。 倘若智能体按照正确的方式探索状态空间，这些更新最终倘若智能体按照正确的方式探索状态空间，这些更新最终会收敛到每个状态的精确值。会收敛到每个状态的精确值。 涉及：涉及：“第第21章，强化学习章，强化学习” 一旦知道了状态的精确值，最优决策就可以简单地移动到一旦知道了

22、状态的精确值，最优决策就可以简单地移动到值最高的后继而完成值最高的后继而完成即此时纯粹的爬山法算法也是一即此时纯粹的爬山法算法也是一个最优策略。个最优策略。联机搜索的学习联机搜索的学习 当智能体已经到达状态（当智能体已经到达状态（1，2）时，不知道行动）时，不知道行动down能回到状态（能回到状态（1，1）。）。 智能体不知道行动智能体不知道行动up还能从状态（还能从状态（2，1）到状态）到状态（2，2），从状态（），从状态（2，2）到状态（）到状态（2，3），等等。），等等。 通常，希望智能体通常，希望智能体能学习到能学习到up能使能使y坐标值增长坐标值增长，除非遇到墙；除非遇到墙；down能使能使y坐标值降低坐标值降低，等等。，等等。联机搜索的学习联机搜索的学习通常，希望智能体能通常，希望智能体能学习学习到到up能使能使y坐标值增长，坐标值增长，除非遇到墙；除非遇到墙；down能使能使y坐标值降低，等等。坐标值降低，等等。此时，必须满足如下两个要求：此时，必须满足如下两个要求： 需要一个对这类一般规则的形式化的和明确的需要一个