第4章超越经典搜索课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 超越经典搜索,中国科大 计算机学院,第,部分 问题求解,第4章 超越经典搜索第部分 问题求解,本章内容,4.1,局部搜索算法和最优化问题,4.2,连续空间中的局部搜索,4.3,使用不确定动作的搜索,4.4,使用部分可观察信息的搜索,4.5,联机搜索,Agent,和未知环境,本章内容4.1 局部搜索算法和最优化问题,本节内容,联机搜索问题,联机搜索智能体,联机局部搜索,联机搜索的学习,本节内容联机搜索问题,智能体和环境,智能体,可以被视为通过传感器感知所处环境并通过执行器对该环境产生作用的东西。,Agent,传感器,？,执行器,环境,感知,行动,智能体和环境智能体可以被视为通过传感器感知所处环境并通过执行,真空吸尘器世界,只有两个地点的真空吸尘器世界,Percept sequence,Action,A,Clean,A,Dirty,B,Clean,B,Dirty,A,Clean,A,Clean,A,Clean,A,Dirty,A,Clean,A,Clean,A,Clean,A,Clean,A,Clean,A,Dirty,Right,Suck,Left,Suck,Right,Suck,Right,Suck,真空吸尘器世界只有两个地点的真空吸尘器世界Percept s,联机搜索问题,脱机搜索：,在涉足实际问题之前先计算出完整的解决方案，然后不需要感知就能够执行解决方案。,联机搜索智能体：,通过计算和行动的交叉来完成。,智能体首先采取一个行动；,然后观察问题的环境并且计算下一个行动。,脱机搜索：,通常需要考虑所有可能发生的情况而制定可能是指数级大小的偶发事件处理计划。,联机搜索：,只需要考虑实际发生的情况。,联机搜索问题脱机搜索：在涉足实际问题之前先计算出完整的解决方,联机搜索问题,应用领域：,动态或半动态的问题领域；,对于停留不动或者计算时间太长都会有惩罚的领域；,甚至是一个完全随机的领域。,探索问题,必须用联机搜索。,例如：放在新建大楼里的机器人，要求它探索大楼，绘制出一张从,A,到,B,的地图。,联机搜索只能通过智能体执行,行动,解决，而不是纯粹的计算过程。,联机搜索问题应用领域：,联机搜索问题,假设智能体仅知道如下信息：,ACTIONS(s),，返回状态,s,下可能行动的列表；,单步耗散函数,c(s,a,s,),，但必须在智能体知道行动的结果为,s,时才能用；,GOAL-TEST(s),。,注意：,智能体不能访问一个状态的后继，除非它,实际,尝试了该状态下的所有行动。,联机搜索问题假设智能体仅知道如下信息：,联机搜索问题,迷宫问题：,目标是从状态,S,出发到达状态,G,。但智能体对环境一无所知。,智能体不知道从状态（,1,，,1,）采取,Up,行动能到达状态（,1,，,2,）；,或者，当已经到达状态（,1,，,2,）时，不知道行动,Down,能回到状态（,1,，,1,）。,在某些应用中，这种“无知程度”可以降低。比如，,机器人探测器,也许知道其移动的行动是如何运转的，只是对障碍物一无所知。,联机搜索问题迷宫问题：目标是从状态S出发到达状态G。但智能体,联机搜索问题,假设：,智能体总能够,认出,它以前已经达到过的状态，并且它的动作是确定性的。,智能体将使用一个能够,估计,从当前状态到目标状态的距离的可采纳启发函数,h(s),。,例如，对于迷宫问题，智能体知道目标的位置并且可以使用,曼哈顿距离,启发式。,联机搜索问题假设：,联机搜索问题,理想的竞争率为,1,。,联机搜索问题理想的竞争率为1。,联机搜索问题,具有,死路,的状态空间。,死路是机器人探索中的实际困难,楼梯、斜坡、悬崖和各种各样的自然地形都可能会是死路。,联机搜索问题具有死路的状态空间。,联机搜索问题,假设：,状态空间是,可安全探索,的。,从每个可到达的状态出发都有某些目标状态是可到达的。,即使在可安全探索的环境里，如果有无界耗散的路径就一定会有,无界的竞争率,。,不管智能体选择那条路，对手都用细长的墙封锁路径，所以智能体所走的路径比最佳路径可能要长得多。,联机搜索问题假设：状态空间是可安全探索的。不管智能体选择那条,本章内容,联机搜索问题,联机搜索智能体,联机局部搜索,联机搜索的学习,本章内容联机搜索问题,联机搜索智能体,智能体在每个行动之后，都能够接收到,感知信息,，告诉它到了那个状态。,根据这个状态，智能体可以逐步扩展自己的,环境地图,。,当前的地图用来决定下一步往哪里走。,联机搜索智能体智能体在每个行动之后，都能够接收到感知信息，告,联机搜索智能体,联机搜索算法：,规划和行动交叉进行。,脱机搜索算法，如,A*,：,可以在状态空间的,一部分,扩展一个节点，然后马上又在空间的,另一部分,扩展另一个节点。,因为脱机算法节点扩展涉及的是,模拟的,而不是实际的行动。,联机搜索智能体联机搜索算法：规划和行动交叉进行。,联机搜索智能体,联机搜索算法：,只会扩展它实际占据的节点。,为了避免遍历整个搜索树去扩展下一个节点，按照,局部顺序,扩展节点看来更好一些。,例如，采用,深度优先搜索,。,如下图，假设智能体已经到了节点,8,。,但是，从已搜索的状态空间看，从节点,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,unexplored,s,Action(,s,),if,s,is not null,then,do,；,s,是前一个状态，初值为空,result,a,s,s,；,a,是前一个行动，即,action,add,s,to the front of,unbacktracked,s,if,unexploreds is empty,then,if,unbacktrackeds is empty,then,return,stop,else,a,an action b such that,resultb,s,Pop(unbacktrackeds),else,a,Pop(unexploreds),s,s,return,a,联机深度优先搜索智能体 ；该智能体可用于双向搜索空间。,联机深度优先搜索智能体,例如，,迷宫问题。,因为使用了回溯的办法，,ONLINE-DFS-AGENT,只能,用于,行动可逆的状态空间,中。,联机深度优先搜索智能体例如，迷宫问题。因为使用了回溯的办法，,本章内容,联机搜索问题,联机搜索智能体,联机局部搜索,联机搜索的学习,本章内容联机搜索问题,联机局部搜索,爬山法,搜索在内存中只存放一个当前状态。,因此，它是一个联机搜索算法。,易使智能体呆在,局部极大值,上而无处可去。,改进方法：,随机重新开始,是不可能的。因为智能体不能把自己传送到一个新的状态。,不妨考虑,随机行走,。,联机局部搜索爬山法搜索在内存中只存放一个当前状态。,联机局部搜索,使用“,随机行走,”取代“随机重新开始”来探索环境。,从当前状态中随机选择可能的行动之一；,选择的时候也可以偏向,未尝试过的行动,。,可以证明：,如果状态是有限的，随机行走最终会找到目标或完成探索。,联机局部搜索使用“随机行走”取代“随机重新开始”来探索环境。,随机行走算法的例子,随机行走算法的例子：,将耗尽,指数级,步骤来达到目标。,因为每一步往回走的概率都是向前走的两倍。,现实世界中的许多状态空间都有此类对“随机行走”是“,陷阱,”的拓扑结构。,怎么办？,随机行走算法的例子随机行走算法的例子：现实世界中的许多状态空,联机局部搜索,提高爬山法算法的内存利用率：,存储每个已经访问过的状态到目标状态的耗散的“,当前最佳估计耗散,H(s),”,。,H(s),从启发式估计,h(s),出发，在智能体从状态空间中获得经验时对,H(s),进行更新。,联机局部搜索提高爬山法算法的内存利用率：存储每个已经访问过的,提高爬山法算法的内存利用率,例、,（,a,）智能体已经进入局部最优。,此时智能体根据对邻居状态的当前耗散估计来选择到达目标的最佳路径，而不是停下来。,经过邻居,s,到达目标的估计耗散为：,c(s,a,s,)+H(s,),。,（,b,）两个邻接的耗散分别为（,1,9,）和（,1,2,），选择向右移动。此时，,原来的状态,到达,目标状态,至少需要（,1,2,）步，因此它的,H,需要更新。,提高爬山法算法的内存利用率例、（a）智能体已经进入局部最优。,实时学习,A*,（,LRTA*),智能体,function,LRTA*-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(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*-Cost(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*,智能体只是庞大的,联机智能体家族,中的一员。,这些联机智能体通过采用,不同的行动选择规则和更新规则,来定义。,实时学习A*（LRTA*)智能体在状态s从未尝试过的行动总被,本章内容,联机搜索问题,联机搜索智能体,联机局部搜索,联机搜索的学习,本章内容联机搜索问题,联机搜索的学习,联机搜索智能体,仅仅根据它的经历学习到环境的“地图”。,每个状态经过每个行动的结果。,环境是确定的。因此，每个行动经历一次就够了。,局部搜索智能体,（如,LTRA*,智能体）利用局部更新规则可以得到每个状态更精确的估计值。,倘若智能体按照正确的方式探索状态空间，这些更新最终会收敛到每个状态的精确值。,涉及：“,第,21,章，强化学习,”,一旦知道了状态的精确值，最优决策就可以简单地移动到值最高的后继而完成,即此时纯粹的爬山法算法也是一个最优策略。,联机搜索的学习联机搜索智能体仅仅根据它的经历学习到环境的“地,联机搜索的学习,当智能体已经到达状态（,1,，,2,）时，不知道行动,Down,能回到状态（,1,，,1,）。,智能体不知道行动,Up,还能从状态（,2,，,1,）到状态（,2,，,2,），从状态（,2,，,2,）到状态（,2,，,3,），等等。,通常，希望智能体,能学习到,Up,能使,y,坐标值增长,，除非遇到墙；,Down