资源描述：
《《超越经典搜索》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章超越经典搜索中国科大计算机学院第Ⅱ部分问题求解本章内容4.1局部搜索算法和最优化问题4.2连续空间中的局部搜索4.3使用不确定动作的搜索4.4使用部分可观察信息的搜索4.5联机搜索Agent和未知环境本节内容联机搜索问题联机搜索智能体联机局部搜索联机搜索的学习智能体和环境智能体可以被视为通过传感器感知所处环境并通过执行器对该环境产生作用的东西。Agent传感器？执行器环境感知行动真空吸尘器世界只有两个地点的真空吸尘器世界PerceptsequenceAction[A,Clean][A,Dirty]
2、[B,Clean][B,Dirty][A,Clean],[A,Clean][A,Clean],[A,Dirty]……[A,Clean],[A,Clean],[A,Clean][A,Clean],[A,Clean],[A,Dirty]RightSuckLeftSuckRightSuck……RightSuck联机搜索问题脱机搜索：在涉足实际问题之前先计算出完整的解决方案，然后不需要感知就能够执行解决方案。联机搜索智能体：通过计算和行动的交叉来完成。智能体首先采取一个行动；然后观察问题的环境并且计算下一个行动
3、。脱机搜索：通常需要考虑所有可能发生的情况而制定可能是指数级大小的偶发事件处理计划。联机搜索：只需要考虑实际发生的情况。联机搜索问题应用领域：动态或半动态的问题领域；对于停留不动或者计算时间太长都会有惩罚的领域；甚至是一个完全随机的领域。探索问题必须用联机搜索。例如：放在新建大楼里的机器人，要求它探索大楼，绘制出一张从A到B的地图。联机搜索只能通过智能体执行行动解决，而不是纯粹的计算过程。联机搜索问题假设智能体仅知道如下信息：ACTIONS(s)，返回状态s下可能行动的列表；单步耗散函数c(s,a,s׳
4、)，但必须在智能体知道行动的结果为s׳时才能用；GOAL-TEST(s)。注意：智能体不能访问一个状态的后继，除非它实际尝试了该状态下的所有行动。联机搜索问题迷宫问题：目标是从状态S出发到达状态G。但智能体对环境一无所知。智能体不知道从状态（1，1）采取Up行动能到达状态（1，2）；或者，当已经到达状态（1，2）时，不知道行动Down能回到状态（1，1）。在某些应用中，这种“无知程度”可以降低。比如，机器人探测器也许知道其移动的行动是如何运转的，只是对障碍物一无所知。联机搜索问题假设：智能体总能够认出它
5、以前已经达到过的状态，并且它的动作是确定性的。智能体将使用一个能够估计从当前状态到目标状态的距离的可采纳启发函数h(s)。例如，对于迷宫问题，智能体知道目标的位置并且可以使用曼哈顿距离启发式。联机搜索问题理想的竞争率为1。联机搜索问题具有死路的状态空间。死路是机器人探索中的实际困难——楼梯、斜坡、悬崖和各种各样的自然地形都可能会是死路。联机搜索问题假设：状态空间是可安全探索的。从每个可到达的状态出发都有某些目标状态是可到达的。即使在可安全探索的环境里，如果有无界耗散的路径就一定会有无界的竞争率。不管智能
6、体选择那条路，对手都用细长的墙封锁路径，所以智能体所走的路径比最佳路径可能要长得多。本章内容联机搜索问题联机搜索智能体联机局部搜索联机搜索的学习联机搜索智能体智能体在每个行动之后，都能够接收到感知信息，告诉它到了那个状态。根据这个状态，智能体可以逐步扩展自己的环境地图。当前的地图用来决定下一步往哪里走。联机搜索智能体联机搜索算法：规划和行动交叉进行。脱机搜索算法，如A*：可以在状态空间的一部分扩展一个节点，然后马上又在空间的另一部分扩展另一个节点。因为脱机算法节点扩展涉及的是模拟的而不是实际的行动。联机
7、搜索智能体联机搜索算法：只会扩展它实际占据的节点。为了避免遍历整个搜索树去扩展下一个节点，按照局部顺序扩展节点看来更好一些。例如，采用深度优先搜索。如下图，假设智能体已经到了节点8。但是，从已搜索的状态空间看，从节点4继续搜索似乎更好一些？智能体应该回溯回去搜索吗？联机深度优先搜索智能体；该智能体可用于双向搜索空间。functionOnline-DFS-Agent(s')returnsanactioninputs:s',aperceptthatidentifiesthecurrentstateifGoa
8、l-Test(s')thenreturnstopifs'isanewstatethenunexplored[s']Action(s')ifsisnotnullthendo；s是前一个状态，初值为空result[a,s]s'；a是前一个行动，即actionaddstothefrontofunbacktracked[s']ifunexplored[s']isemptythenifunbacktracked[s']isemptythenret
