第4章超越经典搜索.ppt
《第4章超越经典搜索.ppt》由会员分享,可在线阅读,更多相关《第4章超越经典搜索.ppt(34页珍藏版)》请在三一文库上搜索。
1、第4章 超越经典搜索,中国科大 计算机学院,第部分 问题求解,本章内容,4.1 局部搜索算法和最优化问题 4.2 连续空间中的局部搜索 4.3 使用不确定动作的搜索 4.4 使用部分可观察信息的搜索 4.5 联机搜索Agent和未知环境,本节内容,联机搜索问题 联机搜索智能体 联机局部搜索 联机搜索的学习,智能体和环境,智能体可以被视为通过传感器感知所处环境并通过执行器对该环境产生作用的东西。,真空吸尘器世界,只有两个地点的真空吸尘器世界,联机搜索问题,脱机搜索:在涉足实际问题之前先计算出完整的解决方案,然后不需要感知就能够执行解决方案。 联机搜索智能体:通过计算和行动的交叉来完成。 智能体首
2、先采取一个行动; 然后观察问题的环境并且计算下一个行动。 脱机搜索:通常需要考虑所有可能发生的情况而制定可能是指数级大小的偶发事件处理计划。 联机搜索:只需要考虑实际发生的情况。,联机搜索问题,应用领域: 动态或半动态的问题领域; 对于停留不动或者计算时间太长都会有惩罚的领域; 甚至是一个完全随机的领域。 探索问题必须用联机搜索。 例如:放在新建大楼里的机器人,要求它探索大楼,绘制出一张从A到B的地图。 联机搜索只能通过智能体执行行动解决,而不是纯粹的计算过程。,联机搜索问题,假设智能体仅知道如下信息: ACTIONS( s ),返回状态s下可能行动的列表; 单步耗散函数c( s, a, s
3、),但必须在智能体知道行动的结果为s时才能用; GOAL-TEST( s )。 注意:智能体不能访问一个状态的后继,除非它实际尝试了该状态下的所有行动。,联机搜索问题,迷宫问题:目标是从状态S出发到达状态G。但智能体对环境一无所知。 智能体不知道从状态(1,1)采取Up行动能到达状态(1,2); 或者,当已经到达状态(1,2)时,不知道行动Down能回到状态(1,1)。 在某些应用中,这种“无知程度”可以降低。比如,机器人探测器也许知道其移动的行动是如何运转的,只是对障碍物一无所知。,联机搜索问题,假设: 智能体总能够认出它以前已经达到过的状态,并且它的动作是确定性的。 智能体将使用一个能够估
4、计从当前状态到目标状态的距离的可采纳启发函数h(s)。 例如,对于迷宫问题,智能体知道目标的位置并且可以使用曼哈顿距离启发式。,联机搜索问题,理想的竞争率为1。,联机搜索问题,具有死路的状态空间。 死路是机器人探索中的实际困难楼梯、斜坡、悬崖和各种各样的自然地形都可能会是死路。,联机搜索问题,假设:状态空间是可安全探索的。 从每个可到达的状态出发都有某些目标状态是可到达的。 即使在可安全探索的环境里,如果有无界耗散的路径就一定会有无界的竞争率。,不管智能体选择那条路,对手都用细长的墙封锁路径,所以智能体所走的路径比最佳路径可能要长得多。,本章内容,联机搜索问题 联机搜索智能体 联机局部搜索 联
5、机搜索的学习,联机搜索智能体,智能体在每个行动之后,都能够接收到感知信息,告诉它到了那个状态。 根据这个状态,智能体可以逐步扩展自己的环境地图。 当前的地图用来决定下一步往哪里走。,联机搜索智能体,联机搜索算法:规划和行动交叉进行。 脱机搜索算法,如A*:可以在状态空间的一部分扩展一个节点,然后马上又在空间的另一部分扩展另一个节点。 因为脱机算法节点扩展涉及的是模拟的而不是实际的行动。,联机搜索智能体,联机搜索算法:只会扩展它实际占据的节点。 为了避免遍历整个搜索树去扩展下一个节点,按照局部顺序扩展节点看来更好一些。 例如,采用深度优先搜索。 如下图,假设智能体已经到了节点8。 但是,从已搜索
6、的状态空间看,从节点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是前一个状态,初值为空 resulta, s s ;
7、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-DFS-AGENT只能用于行动可逆的状态空间中。,本章内容,联机搜索问题 联机
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 超越 经典 搜索
链接地址:https://www.31doc.com/p-2550362.html