《状态空间法》PPT课件_第1页
《状态空间法》PPT课件_第2页
《状态空间法》PPT课件_第3页
《状态空间法》PPT课件_第4页
《状态空间法》PPT课件_第5页
已阅读5页,还剩51页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第二章 人工智能的基本方法,2.1 符号方法 物理符号系统(符号操作系统) 假设 有限合理性原理 搜索 Computer Science Empirical Inquiry:Symbols and Search,Herbert Alexander Simon (1916-2001) 1975年第一届图灵奖获得者,LT发明者之一,1978年诺贝尔经济学奖获得者,Allen Newell (1927-1992 ) 1975年第一届图灵奖获得者,LT发明者之一,美国人工智能学会AAAI的发起人之一,LT 逻辑理论家 ILP 归纳逻辑程序设计 2.1.1 状态空间法 1)问题描述 状 态:问题求解中每

2、一步问题状况的数据结构 状态描述:符号、字符串、向量、二维数组、树、表等数据结构表示的问题状态 例 2-1 八数码难题,初始状态 目标状态 图 2-1 八数码难题,状 态:棋盘布局每一步的状态 状态描述:图表、二维矩阵 算 符:把问题从一种状态描述转变为另一种状态描述的运算 算符集合:问题求解中所有算符的集合,八数码算符:EL- 空格左移 ER-空格右移 EU-空格上移 ED-空格下移 约 束:E1,4,6 - 禁止EL E1,2,3 - 禁止EU E3,5,8 - 禁止ER E6,7,8 - 禁止ED,例2-2 代数式简化问题。 (AB+CD)/BC A/C+D/B 状态描述:二元树法 非

3、终 端:节点算术运算符号+、-、*、/ 终端节点:变量、常量 树图,图2-2 代数简化树图,算符:代数规则: 分配律、结合律、。 字符串法: ABCDBC ACDB 前缀(只作用于两个运算数) 目标状态 单一目标状态 多目标状态:某一条件下产生的子状态集合。例如,象棋、围棋的终局,八数码难题目标状态:最上面一行不存在编号大于5的棋子,最优化问题:寻找遵循某种规则的最优路径例如,八数码难题求解中使用的算符最少,走步最少(最优解搜索问题) 状态描述三原则: (1)状态描述方式选择,尤其是初始状态 (2)算符集合及其对状态描述的作用 (3)目标状态描述特性 2)图示法(问题求解的抽象描述) (1)图

4、论的几个概念,图:节点的集合,包括有限节点或无限节点。 有向图:节点之间用有向弧线联结的图。 节点,路径:存在某个节点序列Nn=(ni1, ni2, nij ,nik), 令j=2,3, ,k,对每一个nij-1,如果都存在后裔nij,则称序列Nn为长度为k的路径 可达节点:如果两节点之间存在路径,则后裔是祖先的可达节点 弧线费用:弧线表示的算符计算的费用 c(ni, nj) 路径费用:路径上所有弧线费用之和 优化问题:寻求图中最小费用路径,路径:k=10 ,k=6 可达节点:j=2,3,。,k 路径费用,ni1,ni2,ni3,nik,C(ni4, ni5,优化问题:寻求图中最小费用路径 (

5、2) 问题求解的图描述 初始节点S与目标节点集合ti中任一节点之间的路径。 初始节点集合si中任一节点与目标节点T之间的路径。 初始节点集合si中任一节点与目标节点集合ti中任一节点之间的路径。 (3) 图分类,显式图:各节点及其费用的弧线可以用图表或表格的形式明确给出 隐式图:已知无限集合si 及后裔算符L,则si和L规定的图 3)状态空间求解举例 例 2-3 推销员旅行问题。一个推销员计划作一次旅行,必须访问图2-4所示的每个城市。从城市A出发,访问每一个城市一次,且最多一次,并返回城市A,求最短距离路线,状态描述:目前为止访问过的城市列表(A) 初始状态:(A) 目标状态: (A A,1

6、3,图2 4 推销员旅行问题地图,算符:下一步走向的城市 (a)(b)(c)(d)(e) 约束:每个城市只能走过一次,A除外,AE,例2-2猴子和香蕉问题,图 2-8 猴子和香蕉问题,状态描述模式:用变量描述状态集合的表达式 猴子状态: 水平走动 w 上下箱子 x0,1,( 1=箱上,0 =箱下) 摘取香蕉 z0,1,(1= 拿到,0 = 未拿到)。 箱子状态:水平移动Y 四种状态:(W, x, Y, z) 算符集合: goto(U) (a,0,b,0) goto(U) (U,0,b,0) pushbox(V) (b,0,b,0) pushbox(V) (V,0,V,0) climbbox (

7、V,0,V,0) climbbox (V,1,V,0) grasp (c,1,c,0) grasp (c,1,c,1,人工智能经典问题: 1 设有三个传教士和三个野人来到河边,打算乘一只船从河右岸渡到河左岸去。该船的最大负荷能力为两人。在任何时候,如果野人人数超过传教士人数,野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去? 2 把八个皇后摆在一个标准的国际象棋棋盘上,使得每行、每列以及每个对角线上都只包含不多于一个皇后。画出部分状态空间图,写出算符规则,图2 - 10 过河问题,图 2- 11 八皇后问题,4)状态空间搜索策略 搜索过程要点: 图论法:起始节点 -算符扩展后

8、继节点(子节点)-加指针 - -检查后继节点是否为目标节点 -是,终止搜索。上述路径为问题的解。否,继续扩展。 搜索控制:宽度优先搜索 深度优先搜索 启发式搜索,图2-12 宽度优先搜索 图2-13 深度优先搜索 盲目搜索: 宽度优先搜索,深度优先搜索 启发式搜索:利用启发式信息进行搜索的过程 启发式信息:用来加速搜索的特别信息,图 2 - 12 人工智能系统计算费用,如何选择下一节点,如何决定选定下一个节点的过程中生成的节点数,如何决定搜索树中抛弃或修剪的节点,估价函数(启发信息):估计节点可扩展“希望”程度的 函数,S,1,2,3,4,5,6,S,1,2,3,4,5,6,a)节点1扩展前

9、(b)节点1扩展后,修剪:节点1扩展前后的搜索树,已扩展节点 未扩展节点,启发式搜索算法:有序状态空间搜索 定义: S - 问题初始状态 T - 问题目标状态 ni - i时刻的问题状态 f(n) - 估价函数,单调减 OPEN表-节点未扩展时,搜索图的数据结构 CLOSED表-节点扩展后,搜索图数据结构,S入OPEN 标出f(S,失败,退出,计算f(ni),i=1,2. MINf(ni)入CLOSED,Y,N,Y,N,扩展ni,生成全部后继节点。计算每个后继节点f(nij,nij,加入OPEN,从nj加一指向节点nij的指针。计算f(nij),按 f(n)小-大排序,N,N,f(nij)取代

10、 f(nij-1) 指针改指j,f(nij)取代 f(nij-1) nij移回OPEN,成功,退出,启发式有序搜索算法,Y,Y,N,Y,Y,N,Y,N,例 八数码难题。 估价函数:f(n)=d(n)+w(n) d(n)-搜索树节点n的深度 w(n)-节点n错放棋子数,2 8 3 1 6 4 7 5,1 2 3 8 4 7 6 5,初始状态S 目标状态T,2 8 3 1 6 4 7 5,2 8 3 1 6 4 7 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,8 3 2 1 4

11、7 6 5,2 8 3 7 1 4 6 5,2 3 1 8 4 7 6 5,2 3 1 8 4 7 6 5,1 2 3 8 4 7 6 5,1 2 3 8 4 7 6 5,2 3 1 8 4 7 6 5,八数码难题解图之一,f(S)=d(n)+w(n,A*算法 证明 h*(n)= k (n,T) :从节点n到目标节点最小路径费用 g*(n) = k (S,n):从起始节点S到节点n最小路径费用 f(n) = g(n) + h(n) : f*(n)的一个估计 f*(S) = h*(S) :从起始节点到目标节点的最佳路径,S,n,T,f*(n)=g*(n)+h*(n,A*的可纳性 可纳性:对于任意

12、图G,如果存在从S到T的路径,那么,搜索算法总能终止在一条从S到T的最佳路径上,则此搜索算法可纳 证明: (1)每当一个目标节点可达时,算法终止。 结论1:A*对有限图总是终止的 结论1:A*对无限图也是终止的 证明:反证法 ,假设A*不终止,设:d*(n) : A*产生的搜索树中从S到任一节点n的搜索隐含图中最短路经长度 e :图中所有弧的最小长度 g(n) g*(n) d*(n) e h(n) 0 f(n) g(n) d*(n) e 说明:即使A*扩展的节点n的f(n)最小,但仍具有任意大的d*(n),如果A*不终止,节点就具有任意大的f(n),这与节点扩展最小f(n)相矛盾,所以,算法终

13、止,证明: A*终止之前,OPEN表上总有一个节点使得f(n)f*(s) 设:S=n0,n1,,nt 是S到T的一条最佳路径 A*终止前,令n是OPEN表上这个序列的一 个节点 存在: f(n) = g(n) + h(n) n在最佳路径上, g(n) = g*(n) f(n) = g*(n) + h(n) 又 h(n) h*(n) f(n) g*(n) + h*(n)=f*(n,在最佳路径上的任一节点费用 f(n) f*(S) 说明即使在A*还没有终止的OPEN表上,节点的最小f值也不会变为无界。因此,对于无限图来说,A*必须终止。 结论1:只要存在一条从S到某个目标节点的路径,则A*必须终止

14、。 推论1:OPEN表上任一具有f(n)f*(S)的节点n,最终都将被A*选为扩展节点,可纳性证明: a. A*一定会找到一个目标节点而终止。 如果存在一条从S到目标节点T的路径,终止之前OPEN表不会空。因为结论1,总会有一个节点在OPEN表上,且是最佳路径上。 b. A*只能找到一条最佳路径而终止。 假定A*未找到一条最佳路径而在目标节点t终止,则:f(t)=g(t)f*(S,根据结论1,终止前OPEN表上存在一个节点n,且满足: f(n)f*(S)f(t) 因此,这一步A*将选取n而不是t进行扩展,与假设A*已终止矛盾。 得证。 结论2:A*算法可纳,A*算法的最优性 h(n) = 0(

15、无启发信息)是h*(n)的下界 设两种A*算法A1,A2有下式: f1(n) = g1(n) + h1(n) f2(n) = g2(n) + h2(n) 设: n T ,h2(n)h1(n),且存在一条从S到T的最佳路径, A1, A2都中止在最佳路径上,证明:在终止的地方,如果图G的节点n能够用A2来扩展,那么,也必定能用A1来扩展。因此, A1扩展的节点数至少与用A2扩展的节点数一样多。 n = S,若S=T,两种算法都不必扩展节点 b. 若ST,两种算法都要扩展S 归纳法假设:A1扩展了A2搜索树中深度 k 的所有节点 证明:A2搜索树中由A2扩展的深度k+1的任意节点n也可由A1扩展,

16、根据假设,A2搜索树中n的任一父辈节点都可由A1扩展。因此,节点n也在搜索树A1中 存在: g1(n) g2 (n) (1) 反证:A1不能扩展由A2扩展的节点n A1终止的地方,节点n必须在OPEN表上。因为A1已扩展了n的一个父辈节点。由于A1没有扩展节点n而在最小路径上终止。所以: f1(n)=g1(n)+h1(n) f*(S) (2) g2(n)+h1(n)g1(n)+h1(n)f*(S) (3) h1(n)f*(S)g2(n) (4,由A*选来扩展的任一节点n,满足: f(n) f*(S) 由于A2已经扩展了节点n,所以: f2(n) = g2(n)+h2(n) f*(S) (5)

17、h2(n) f*(S) g2(n) (6) 比较(4),(6)两式得: h2(n) f*(S) g2(n) h1(n) 至少在节点n,h1(n)=h2(n),与A2比A1有更多信息的假设矛盾,结论4: 若A1和A2是A*的两种搜索形式,且A2比A1有更多的信息。则在从S到T的路径搜索终止处,由A2所扩展的每一个节点,也可以由A1扩展。因此,A1扩展的节点数至少和A2一样多。 h的单调限制 为避免生成的后继节点在OPEN或CLOSED表中,给h一个合理的限制 单调限制:如果对所有节点ni 及其后继节点nj,使得当h(t)=0时下式成立: 0 h(ni) h(nj) c(ni,nj) 则h满足单调

18、,结论5:如果h满足单调限制,若A*选n扩展,则g(n)=g*(n) 证明: 设 n为A*要扩展的节点 a. 若n=S,则A*已找到一条最佳路径 b. 若nS,设序列S=n0,n1, ,nk=n是S到n的一条最佳路径。令nl是这个序列的最后一个节点。 A*扩展时nl在CLOSED表上,nk,nl+1在OPEN 表上,h单调: h(ni) c(ni,ni+1)+ h(ni+1) g*(ni)+h(ni) g*(ni)+h(ni+1)+c(ni,ni+1) 又 ni和ni+1在最佳路径上 g*(ni+1)=g*(ni)+c(ni,ni+1) g*(ni)+h(ni) g*(ni+1)+h(ni+1

19、) g*(nl+1)+h(nl+1) g*(nk)+h(nk) f(nl+1) g*(n)+h(n)=f(n) 当A*选择节点n而不是节点nl+1时,g(n) g*(n)必须成立,否则,f(n)可能大于f(nl+1)。但是,由定义,对搜索树中所有节点m存在: g(m) g*(m) 必有 g(n)=g*(n) 证毕,结论6:如果满足单调限制,那么由A*所扩展的节点序列的f值非递减。 证明: a. 设扩展n1时,n2在OPEN表上 f(n1) f(n2) b. 设扩展n1时,n2不在OPEN表上,则 f(n2)=g(n2)+h(n2)= g*(n2)+h(n2) =g*(n1)+c(n1,n2)+

20、h(n2) =g(n1)+ c(n1,n2)+h(n2) c(n1,n2)+h(n2) h(n1) f(n2) g(n1)+h(n1)=f(n1) 证毕,h的启发能力 例: 八数码难题的较好估计:h(n)=P(n)+3S(n) P(n): 每个棋子离家距离的总和。 S(n): 棋子排列顺序的计分值。依次检验非中心方格的棋子,如果某棋子后跟的棋子和目标顺序不同,则该棋子得2分,一致得0分,所有棋子得分综合为S(n)。 影响启发能力的因素 路径费用 寻找路径时所扩展的节点数目 h的计算量,美卫星首次实现在轨自动补给燃料 2007年4月5日美国宇航局太空网报道,ASTRO卫星(左)与NextSat卫

21、星(右) ASTRO卫星的太阳能帆板,美国“轨道快车计划”(Orbital Express,发起单位:美国国防预先研究计划局(DARPA) 美国首创技术:卫星修复、自主机器人、在轨燃料加注 任务:发送低成本航天器对更昂贵的故障卫星进行修复和燃料燃料补给 平台:航天器(3亿美元) ASTRO:主动航天器,模拟自主空间转移及机器人轨道器 NextSat:扮演补给站,又扮演被修复的客户卫星的角色,航天器制造:波音幻影工作室和鲍尔宇航公司建造 实验过程:2007年3月8日从卡纳维拉尔角空军基地发射。两颗卫星绕距地球300英里(483公里)高的轨道飞行。系列实验包括:利用机器臂进行多次交会、捕获与转移操

22、作 “情景0”试验: ASTRO推进剂箱中的肼燃料泵入到NextSat中, ASTRO携带约重300磅(136千克)的推进剂,用于燃料加注试验和之后的交会操作,燃料输送试验:尝试以不同的流动速率,利用泵式加注和压力加注两种方法进行试验 机械臂目标捕获试验:机器臂将从ASTRO抓取替换单元(一节电池、传感器处理计算机)备用电池,并插入到NextSat上。(机器臂数次将电池在ASTRO和NextSat之间进行来回转移,但在不进行转移时,电池将会留在NextSat上提供外部动力。依照设计程序,在任务后期加入传感器处理计算机,将其从ASTRO移走后再放置回去,以试验传感器处理计算机的接口界面,情景1(

23、Scenario 1):重达156磅的机器臂抓住NextSat,把它推离ASTRO,预计持续11天。试验中,NextSat未固定,以便丢弃连接两颗卫星的结合环。此后,ASTRO还将再次抓取NextSat进行燃料补给试验,转移备用轨道替换单元。NextSat可通过对接或利用ASTRO上的机器臂被抓取 在情景2(Scenarios 2) 情景5:设计了一系列渐进的步骤,将使ASTRO与NextSat分离,在3周内逐渐增大它们之间的距离 情景6(Scenarios 6) 情景8:为进行远距离交会验证试验,ASTRO将上升至距离NextSat7千米的高度上。当NextSat再次对接时,ASTRO将再次向NextSat输送燃料

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论