人工智能及其应用第四版课件

单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,人 工 智,能,第八章 自动规划,8.1,机器人规划的作用与任务,8.2,积木机器的机器人规划,8.3,STRIPS,规划系统,8.4,具有学习能力的规划系统,8.5,基于专家系统的机器人规划,8.6,小结,8.1,机器人规划的作用与任务,8.1.1,规划的作用与问题分解途径,规划的概念及作用,规划的概念,规划,是一种重要的问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止,。,图,8.1,子规划的分层结构例子,工 作 日 规 划,上午子规划,中午子规划,下午子规划,吃夹心面包,阅读,写作,回家,去上班,阅读文章,3,规划的作用,规划,可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。,规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。,问题分解途径及方法,把某些比较复杂的问题分解为一些比较小的子问题。有两条能够实现这种分解的重要途径。,第一条重要途径,是当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。,第二条重要途径,是把单一的困难问题分割为几个有希望的较为容易解决的子问题。,问题域的预测于规划的修正,（1）问题论域的预测,（2）规划的修正，问题分解使得影响局部化,8.1,自动规划的作用与任务,4,8.1.2,机器人规划系统的任务与方法,在规划系统中，必须具有执行下列各项任务的方法：,根据最有效的启发信息，选择应用于下一步的最好规则。,应用所选取的规则来计算由于应用该规则而生成的新状态。,对所求得的解答进行检验。,检验空端，以便舍弃它们，使系统的求解工作向着更有效的方向进行。,检验殆正确的解答，并应用具体的技术使之完全正确。,8.1,自动规划的作用与任务,5,选择于应用规则,检验解答与空端,修正殆正确解,6,8.2,积木世界的机器人规划,8.2.1,积木世界的机器人问题,积木世界由一些有标记的立方形积木，互相堆迭在一起构成；机器人有个可移动的机械手，它可以抓起积木块并移动积木从一处至另一处,。,C,B,A,机械手,7,在这个例子中机器人能够执行的动作举例如下：,unstack,(a,b)：,把堆放在积木,b,上的积木,a,拾起。在进行这个动作之前，要求机器人的手为空手，而且积木,a,的顶上是空的。,stack(a,b)：,把积木,a,堆放在积木,b,上。动作之前要求机械手必须已抓住积木,a，,而且积木,b,顶上必须是空的。,pickup(a)：,从桌面上拾起积木,a，,并抓住它不放。在动作之前要求机械手为空手，而且积木,a,顶上没有任何东西。,putdown(a)：,把积木,a,放置到桌面上。要求动作之前机械手已抓住积木,a。,8.2,积木世界的机器人规划,8,研究内容,是综合机器人的动作序列，即在某个给定初始情况下，经过某个动作序列而达到指定的目标。,机器人问题的状态描述和目标描述均可用谓词逻辑公式构成：,ON(a,b)：,积木,a,在积木,b,之上。,ONTABLE(a)：,积木,a,在桌面上。,CLEAR(a)：,积木,a,顶上没有任何东西。,HOLDING(a)：,机械手正抓住积木,a。,HANDEMPTY：,机械手为空手。,8.2,积木世界的机器人规划,9,图,8.4(,a),所示为初始布局的机器人问题。,目标在于建立一个积木堆，其中，积木,B,堆在积木,C,上面，积木,A,又堆在积木,B,上面，如图,8.4(,b),所示。,C,B,A,机械手,A,B,C,机械手,（,a）,初始布局 （,b）,目标布局,图8.4,积木世界的机器人问题,8.2,积木世界的机器人规划,10,初始布局可由下列谓词公式的合取来表示：,CLEAR(B)：,积木,B,顶部为空,CLEAR(C)：,积木,C,顶部为空,ON(C，A)：,积木,C,堆在积木,A,上,ONTABLE(A)：,积木,A,置于桌面上,ONTABLE(B)：,积木,B,置于桌面上,HANDEMPTY：,机械手为空手,目标布局：,ON(B,C)and ON(A,B),8.2,积木世界的机器人规划,11,8.2.2用,F,规则求解规划序列,STRIPS,规划系统的规则由,3,部分组成：,第一部分是,先决条件,。,第二部分是,一个叫做删除表的谓词,。,第三部分叫做,添加表,。,8.2,积木世界的机器人规划,12,例：,表示堆积木的例子中,move,这个动作，如下所示：,move(x,y,z),表示把物体,x,从物体,y,上面移到物体,z,上面。,先决条件：,CLEAR(x),CLEAR(z)，ON(x,y),删除表：,ON(x,y)，CLEAR(z),添加表：,ON(x,z)，CLEAR(y),如果,move,为此机器人仅有的操作符或适用动作，那么，可以生成如图,8.5,所示的搜索图或搜索树。,CLEAR(X),CLEAR(Z),ON(X,Y),ONTABLE(Y),ONTABLE(Z),CLEAR(X),CLEAR(Y),ON(X,Z),ONTABLE(Y),ONTABLE(z),move(X,Y,Z),图8.5,表示,move,动作的搜索树,8.2,积木世界的机器人规划,13,机器人的,4,个动作,(,或操作符,),可用,STRIPS,形式表示如下：,stack(X,Y),先决条件和删除表：,HOLDING(X)CLEAR(Y),添加表：,HANDEMPTY，ON(X，Y),unstack,(X,Y),先决条件：,HANDEMPTYON(X，Y)CLEAR(X),删除表：,ON(X，Y)，HANDEMPTY,添加表：,HOLDING(X)，CLEAR(Y),pickup(X),先决条件：,ONTABLE(X)CLEAR(X)HANDEMPTY,删除表：,ONTABLE(X)HANDENPTY,添加表：,HOLDING(X),putdown(X),先决条件和删除表：,HOLDING(X),添加表：,ONTABLE(X)，HANDEMPTY,8.2,积木世界的机器人规划,14,从初始状态开始，正向地依次读出连接弧线上的,F,规则，我们就得到一个能够达到目标状态的动作序列（如图,8.,3中粗线所示）于下：,unstack,(C,A),putdown(C),pickup(B),stack(B,C),pickup(A),stack(A,B),就把这个动作序列叫做达到这个积木世界机器人问题目标的规划。,8.2,积木世界的机器人规划,15,16,8.3,STRIPS,规划系统,STRIPS,的介绍,STRIPS,是由,Fikes,、Hart,和,Nilsson3,人在,1981及1982,研究成功的，它是夏凯,(,Shakey,),机器人程序控制系统的一个组成部分。,STRIPS,系统组成,世界模型：,为一阶谓词演算公式；,操作符,(,F,规则,),：,包括先决条件、删除表和添加表；,操作方法：,应用状态空间表示和中间,-,结局分析。,17,Strips,是,Shakey,机器人系统的一个组成部分，,Shakey,机器人系统包括：,（1）车轮及其推进系统；,（2）传感器，由电视摄像机和接触杆组成；,（3）计算机，接受机器人的传感器信息与输入指令，经过计算后向车轮及其推进系统发出信号；,（4）无线通信系统，用于在车轮与计算机之间的数据传递,8.,3,Strips,规划系统,18,Strips,的规划过程,问题：,(1)初始状态：,INROOM(Robot,R1)and INROOM(Box1,R2)and CONNECTS(D1,R1,R2),(2),目标状态：,INROOM（Robot,R1)and INROOM(BOX1,R1)and CONNECTS(D1,R1,R2),操作符,OP1:,gothru,(d,r1,r2);,先决条件：,INROOM(b,r1)and CONNECTS(d,r1,r2),删除表：对所有,S,INROOM(Robot,s),添加表：,INROOM(Robot,r2),8.,3,Strips,规划系统,19,操作符,OP2:,pushthru,(b,d,r1,r2),先决条件：,INROOM(b,r1)and INROOM(Robot,r1)and CONNECTS(d,r1,r2),删除表：对所有,S,INROOM(b,s),INROOM(Robot,s),添加表：,INROOM(b,r2),INROOM(Robot,r2),问题的差别表：,8.,3,Strips,规划系统,差别,操作符,gothru,pushthru,物体不在目标房间内,机器人不在目标房间内,机器人和物体不在同一房间内,机器人和物体在同一房间内，但不是目标房间,X,X,X,X,20,采用中间结局分析方法求解步骤：,do GPS,的主循环迭代，,until M0,与,G0,匹配为止,Begin,G0,不能满足,M0，,找出,M0,与,G0,的差别；,选择操作符,OP2：,一个与减少差别,d1,有关的操作符；,消去差别,d1,为操作符,OP2,设置先决条件,G1：,INROOM(b,r1)and INROOM(Robot,r1)and CONNECTS(d,r1,r2),采用置换：,R2/r1，D1/d,则,G1,为：,INROOM(BOX1,R2)and INROOM(Robot,R2)and CONNECTS(D1,R2,R1),重复上述步骤，,差异：,INROOM(Robot，R2)；,选择操作符,OP1；,设置先决条件,G2：INROOM(Robot,R1)and CONNECTS(d,r1,R2),采用置换：,R1/r1，D1/d,则,G2,满足,把,gothru,(D1,R1,R2),作用于,M0，,得中间状态,M1；,把,pushthru,(BOX1,D1,R2,R1),于,M1,得中间状态,M2=G0,END,8.,3,Strips,规划系统,21,最后的规划为：,gothru,(D1,R1,R2),pushthru,(BOX1,D1,R2,R1),8.,3,Strips,规划系统,22,23,含有多重解答的规划,例如：要求机器人,ROBOT,把3个不同区域的箱子推倒同一区域；,采用归结反演和中间-结局分析来求解；,得到多重解答。,24,8.4,具有学习能力的规划系统,PULP-,机器人规划系统,PULP-,机器人规划系统是一种具有学习能力的系统，它采用管理式学习，其作用原理是建立在类比,(,analogue),的基础上的。,STRIPS,的弱点,需要极其大量计算机内存和时间等。,应用具有学习能力的规划系统能够克服这一缺点。,25,8.4.,1,PULP-,系统的结构与操作方式,PULP-,系统的结构,“字典,”,是英语词,汇的集合。,“,模型,”,部分包括模型世界 物体现有状态的事实。,“,过程,”,集中了予先准备好的过程知识。,“,方块,”,集中,了,LISP,程序，它配合,“,规划,”,对,“,模型,”,进行搜索和修正。,SENEF,程序,规划与学习,字典,模型,过程,方块,响应,输入,图,8.14,PULP-,系统的总体结构,8.4,具有学习能力的规划系统,26,PULP-,系统的操作方式,PULP-,系统具有两种操作方式：,学习方式,在学习方式下，输入,至系统的知识是由操作人,员或者所谓,“,教师,”,提供,的。图,8.15,表示出在学习,方式下的系统操作。,存储,任务分析,方块,匹配,过程,分解,学习,教师,输入任务知识,响应,图8.15,PULP-,系统结构,8.4,具有学习能力的规划系统,27,规划方式,当某个命令句子,送入系统时，,PULP-,就进入,规划方式。上图,表示,PULP-,系统在,规划方式下的结构,。,检索,混合规划,方块,目标检,验匹配,单一规划,规划,输入命令,响应,过程,模型,图8.16,规划方式下,PULP