第4章超越经典搜索课件.ppt

《第4章超越经典搜索课件.ppt》由会员分享，可在线阅读，更多相关《第4章超越经典搜索课件.ppt（34页珍藏版）》请在三一办公上搜索。

1、第4章 超越经典搜索,中国科大 计算机学院,第部分 问题求解,第4章 超越经典搜索第部分 问题求解,本章内容,4.1 局部搜索算法和最优化问题4.2 连续空间中的局部搜索4.3 使用不确定动作的搜索4.4 使用部分可观察信息的搜索4.5 联机搜索Agent和未知环境,本章内容4.1 局部搜索算法和最优化问题,本节内容,联机搜索问题联机搜索智能体联机局部搜索联机搜索的学习,本节内容联机搜索问题,智能体和环境,智能体可以被视为通过传感器感知所处环境并通过执行器对该环境产生作用的东西。,智能体和环境智能体可以被视为通过传感器感知所处环境并通过执行,真空吸尘器世界,只有两个地点的真空吸尘器世界,真空吸

2、尘器世界只有两个地点的真空吸尘器世界Percept s,联机搜索问题,脱机搜索：在涉足实际问题之前先计算出完整的解决方案，然后不需要感知就能够执行解决方案。联机搜索智能体：通过计算和行动的交叉来完成。智能体首先采取一个行动；然后观察问题的环境并且计算下一个行动。脱机搜索：通常需要考虑所有可能发生的情况而制定可能是指数级大小的偶发事件处理计划。联机搜索：只需要考虑实际发生的情况。,联机搜索问题脱机搜索：在涉足实际问题之前先计算出完整的解决方,联机搜索问题,应用领域：动态或半动态的问题领域；对于停留不动或者计算时间太长都会有惩罚的领域；甚至是一个完全随机的领域。探索问题必须用联机搜索。例如：放在新

3、建大楼里的机器人，要求它探索大楼，绘制出一张从A到B的地图。联机搜索只能通过智能体执行行动解决，而不是纯粹的计算过程。,联机搜索问题应用领域：,联机搜索问题,假设智能体仅知道如下信息：ACTIONS(s)，返回状态s下可能行动的列表；单步耗散函数c(s,a,s)，但必须在智能体知道行动的结果为s时才能用；GOAL-TEST(s)。注意：智能体不能访问一个状态的后继，除非它实际尝试了该状态下的所有行动。,联机搜索问题假设智能体仅知道如下信息：,联机搜索问题,迷宫问题：目标是从状态S出发到达状态G。但智能体对环境一无所知。智能体不知道从状态（1，1）采取Up行动能到达状态（1，2）；或者，当已经到

4、达状态（1，2）时，不知道行动Down能回到状态（1，1）。在某些应用中，这种“无知程度”可以降低。比如，机器人探测器也许知道其移动的行动是如何运转的，只是对障碍物一无所知。,联机搜索问题迷宫问题：目标是从状态S出发到达状态G。但智能体,联机搜索问题,假设：智能体总能够认出它以前已经达到过的状态，并且它的动作是确定性的。智能体将使用一个能够估计从当前状态到目标状态的距离的可采纳启发函数h(s)。例如，对于迷宫问题，智能体知道目标的位置并且可以使用曼哈顿距离启发式。,联机搜索问题假设：,联机搜索问题,理想的竞争率为1。,联机搜索问题理想的竞争率为1。,联机搜索问题,具有死路的状态空间。死路是机器

5、人探索中的实际困难楼梯、斜坡、悬崖和各种各样的自然地形都可能会是死路。,联机搜索问题具有死路的状态空间。,联机搜索问题,假设：状态空间是可安全探索的。从每个可到达的状态出发都有某些目标状态是可到达的。即使在可安全探索的环境里，如果有无界耗散的路径就一定会有无界的竞争率。,不管智能体选择那条路，对手都用细长的墙封锁路径，所以智能体所走的路径比最佳路径可能要长得多。,联机搜索问题假设：状态空间是可安全探索的。不管智能体选择那条,本章内容,联机搜索问题联机搜索智能体联机局部搜索联机搜索的学习,本章内容联机搜索问题,联机搜索智能体,智能体在每个行动之后，都能够接收到感知信息，告诉它到了那个状态。根据这

6、个状态，智能体可以逐步扩展自己的环境地图。当前的地图用来决定下一步往哪里走。,联机搜索智能体智能体在每个行动之后，都能够接收到感知信息，告,联机搜索智能体,联机搜索算法：规划和行动交叉进行。脱机搜索算法，如A*：可以在状态空间的一部分扩展一个节点，然后马上又在空间的另一部分扩展另一个节点。因为脱机算法节点扩展涉及的是模拟的而不是实际的行动。,联机搜索智能体联机搜索算法：规划和行动交叉进行。,联机搜索智能体,联机搜索算法：只会扩展它实际占据的节点。为了避免遍历整个搜索树去扩展下一个节点，按照局部顺序扩展节点看来更好一些。例如，采用深度优先搜索。如下图，假设智能体已经到了节点8。但是，从已搜索的状

7、态空间看，从节点4继续搜索似乎更好一些？智能体应该回溯回去搜索吗？,联机搜索智能体联机搜索算法：只会扩展它实际占据的节点。,联机深度优先搜索智能体,；该智能体可用于双向搜索空间。function Online-DFS-Agent(s)returns an action inputs:s,a percept that identifies the current state if Goal-Test(s)then return stop if s is a new state then unexploreds Action(s)if s is not null then do；s是前一个状态，初

8、值为空 resulta,s s；a是前一个行动，即action add s to the front of unbacktrackeds if unexploreds is empty then if unbacktrackeds is empty then return stop else a an action b such that resultb,sPop(unbacktrackeds)else a Pop(unexploreds)s s return a,联机深度优先搜索智能体；该智能体可用于双向搜索空间。,联机深度优先搜索智能体,例如，迷宫问题。,因为使用了回溯的办法，ONLINE

9、-DFS-AGENT只能用于行动可逆的状态空间中。,联机深度优先搜索智能体例如，迷宫问题。因为使用了回溯的办法，,本章内容,联机搜索问题联机搜索智能体联机局部搜索联机搜索的学习,本章内容联机搜索问题,联机局部搜索,爬山法搜索在内存中只存放一个当前状态。因此，它是一个联机搜索算法。易使智能体呆在局部极大值上而无处可去。改进方法：随机重新开始是不可能的。因为智能体不能把自己传送到一个新的状态。不妨考虑随机行走。,联机局部搜索爬山法搜索在内存中只存放一个当前状态。,联机局部搜索,使用“随机行走”取代“随机重新开始”来探索环境。从当前状态中随机选择可能的行动之一；选择的时候也可以偏向未尝试过的行动。可

10、以证明：如果状态是有限的，随机行走最终会找到目标或完成探索。,联机局部搜索使用“随机行走”取代“随机重新开始”来探索环境。,随机行走算法的例子,随机行走算法的例子：将耗尽指数级步骤来达到目标。因为每一步往回走的概率都是向前走的两倍。,现实世界中的许多状态空间都有此类对“随机行走”是“陷阱”的拓扑结构。怎么办？,随机行走算法的例子随机行走算法的例子：现实世界中的许多状态空,联机局部搜索,提高爬山法算法的内存利用率：存储每个已经访问过的状态到目标状态的耗散的“当前最佳估计耗散H(s)”。H(s)从启发式估计h(s)出发，在智能体从状态空间中获得经验时对H(s)进行更新。,联机局部搜索提高爬山法算法

11、的内存利用率：存储每个已经访问过的,提高爬山法算法的内存利用率,例、（a）智能体已经进入局部最优。此时智能体根据对邻居状态的当前耗散估计来选择到达目标的最佳路径，而不是停下来。经过邻居s到达目标的估计耗散为：c(s,a,s)+H(s)。（b）两个邻接的耗散分别为（19）和（12），选择向右移动。此时，原来的状态到达目标状态至少需要（12）步，因此它的H需要更新。,提高爬山法算法的内存利用率例、（a）智能体已经进入局部最优。,实时学习A*（LRTA*)智能体,function LRTA*-Agent(s)returns an action inputs:s,a percept that iden

12、tifies the current state if Goal-Test(s)then return stop if s is a new state(not in H)then Hs h(s)unless s is null；s是前一个状态，初值为空 resulta,s s；a是前一个行动，即action Hs min LRTA*-Cost(s,b,resultb,s,H)|bActions(s)a an action b in Actions(S)that minimizes LRTA*-Cost(s,b,resultb,s,H)s s return a function LRTA*-C

13、ost(s,a,s,H)returns a cost estimate if s is undefined then return h(s)else return c(s,a,s)Hs,实时学习A*（LRTA*)智能体 function LR,实时学习A*（LRTA*)智能体,在状态s从未尝试过的行动总被假设为能用最小可能耗散（即h(s)）直接到达目标。这种不确定条件下的乐观主义鼓励智能体探索新的、可能更有希望的路径。LRTA*智能体在任何有限的、可安全探索的环境中都能保证找到目标。LRTA*智能体不同于A*：LRTA*智能体对于无限的状态空间是不完备的有些情况能把它引入无限的歧途。LRTA*

14、智能体只是庞大的联机智能体家族中的一员。这些联机智能体通过采用不同的行动选择规则和更新规则来定义。,实时学习A*（LRTA*)智能体在状态s从未尝试过的行动总被,本章内容,联机搜索问题联机搜索智能体联机局部搜索联机搜索的学习,本章内容联机搜索问题,联机搜索的学习,联机搜索智能体仅仅根据它的经历学习到环境的“地图”。每个状态经过每个行动的结果。环境是确定的。因此，每个行动经历一次就够了。局部搜索智能体（如LTRA*智能体）利用局部更新规则可以得到每个状态更精确的估计值。倘若智能体按照正确的方式探索状态空间，这些更新最终会收敛到每个状态的精确值。涉及：“第21章，强化学习”一旦知道了状态的精确值，

15、最优决策就可以简单地移动到值最高的后继而完成即此时纯粹的爬山法算法也是一个最优策略。,联机搜索的学习联机搜索智能体仅仅根据它的经历学习到环境的“地,联机搜索的学习,当智能体已经到达状态（1，2）时，不知道行动Down能回到状态（1，1）。智能体不知道行动Up还能从状态（2，1）到状态（2，2），从状态（2，2）到状态（2，3），等等。通常，希望智能体能学习到Up能使y坐标值增长，除非遇到墙；Down能使y坐标值降低，等等。,联机搜索的学习当智能体已经到达状态（1，2）时，不知道行动D,联机搜索的学习,通常，希望智能体能学习到Up能使y坐标值增长，除非遇到墙；Down能使y坐标值降低，等等。此时

16、，必须满足如下两个要求：需要一个对这类一般规则的形式化的和明确的可操作描述。到目前为止，这些信息隐藏在称为后继函数的黑盒子里。涉及：“知识表示和推理”。需要有算法能够根据智能体得到的特定的观察资料来构造合适的一般规则。涉及：“从观察中学习”。,联机搜索的学习通常，希望智能体能学习到Up能使y坐标值增长，,小结,联机搜索问题联机搜索智能体联机局部搜索避免局部极小值联机搜索的学习,小结联机搜索问题,课堂练习,（1）设计一个用于解决八数码问题的爬山法搜索算法，给出算法伪代码。（2）对于下图所示的八数码问题的初始状态，请分析您的算法是否能够到达目标状态？模拟退火搜索SIMULATED-ANNEALING函数中的参数schedule，是从时间到“温度”的一个映射。请为schedule给出一个合理的例子。,课堂练习（1）设计一个用于解决八数码问题的爬山法搜索算法，给,作业,对下图所示的环境进行探索。假设对于任意状态s，h(s)已知，即h(s)|GX-sX|+GY-sY|，其中G为目标状态。请问使用最简单爬山法算法进行联机搜索，智能体会卡在局部最小值吗？在这种情况下，LRTA*是怎样避免局部极小值的？请简要解释。,作业对下图所示的环境进行探索。假设对于任意状态s，h(s)已,