人工智能及其应用蔡自兴第四.pptx

单击此处编辑母版标题样式,*,,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,人 工 智 能,1,第八章 自动规划,,8.1,,机器人规划的作用与任务,,8.2 积木机器的机器人规划,8.3 STRIPS规划系统,8.4 具有学习能力的规划系统,8.5 基于专家系统的机器人规划,8.6 小结,,2,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放置到桌面上要求动作之前机械手已抓住积木a8.2 积木世界的机器人规划,8,研究内容,是综合机器人的动作序列，即在某个给定初始情况下，经过某个动作序列而达到指定的目标机器人问题的状态描述和目标描述均可用谓词逻辑公式构成：,ON(a,b)：,积木a在积木b之上ONTABLE(a)：,积木a在桌面上CLEAR(a)：,积木a顶上没有任何东西HOLDING(a)：,机械手正抓住积木aHANDEMPTY：,机械手为空手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)andON(A,B),8.2,积,积木,世,世界,的,的机,器,器人,规,规划,11,用,用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),先决,条,条件,：,：HANDEMPTY∧ON(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.3STRIPS,规,规划系统,STRIPS的介,绍,绍,STRIPS是由Fikes、Hart和Nilsson3人,在,在1981及1982研究,成,成功的，,它,它是夏凯(Shakey),机,机器人程,序,序控制系,统,统的一个,组,组成部分,STRIPS系统,组,组成,世界模型,：,：为一阶谓,词,词演算公,式,式；,操作符(F规则),：,：包括先决,条,条件、删,除,除表和添,加,加表；,操作方法,：,：应用状态,空,空间表示,和,和中间-,结,结局分析,17,Strips是Shakey机器人,系,系统的一,个,个组成部,分,分，Shakey,机,机器人系,统,统包括：,（1）车,轮,轮及其推,进,进系统；,（2）传,感,感器，由,电,电视摄像,机,机和接触,杆,杆组成；,（3）计,算,算机，接,受,受机器人,的,的传感器,信,信息与输,入,入指令，,经,经过计算,后,后向车轮,及,及其推进,系,系统发出,信,信号；,（4）无,线,线通信系,统,统，用于,在,在车轮与,计,计算机之,间,间的数据,传,传递,,8.3Strips规划,系,系统,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.3Strips规划,系,系统,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.3Strips规划,系,系统,,差别,操作符,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)andINROOM(Robot,r1) and CONNECTS(d,r1,r2),采用置换,：,：R2/r1 ，D1/d 则G1为：,INROOM(BOX1,R2)andINROOM(Robot,R2)andCONNECTS(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.3Strips规划,系,系统,21,最后的规,划,划为：,{,gothru(D1,R1,R2),pushthru(BOX1,D1,R2,R1),},,,8.3Strips规划,系,系统,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-Ⅰ系统的结构,,8.4,具,具有,学,学习,能,能力,的,的规,划,划系,统,统,28,分层,规,规划,的,的思,想,想,长度,优,优先,搜,搜索,,NOAH,规,规划,系,系统,29,8.5,基,基于,专,专家,系,系统,的,的机,器,器人,规,规划,机器,人,人规,划,划专,家,家系,统,统就,是,是用,专,专家,系,系统,的,的结,构,构和,技,技术,建,建立,起,起来,的,的机,器,器人,规,规划,系,系统,。

管理,式,式学,习,习能,力,力的,机,机器,人,人规,划,划系,统,统的,不,不足,：,：,表达,子,子句,的,的语,义,义网,络,络结,构,构过,于,于,复,复杂,与复,杂,杂的,系,系统,内,内部,数,数据,结,结构,有,有关,的,的是,，,，,PULP-Ⅰ,系,系统,具,具有,许,许多,子,子系,统,统而,而且,需,需要,花费,大,大量,时,时间,来,来编,写,写程,序,序尽管PULP-Ⅰ,系,系统,的,的执,行,行速,度,度要,比,比STRIPS,系列,快,快得,多,多，,然,然而,它,它仍,然,然不,够,够快,30,8.5.1系,统,统结,构,构和,规,规划,机,机理,系统,结,结构,及,及规,划,划机,理,理,机,器,人,用,户,机,器,人,专,家,知,识,,用,户,接,口,知识库,推理机,控制,策略,工具,专家系统,知识获取,说明与分析,问题输入或,新情况描述,回答问题或,建议与解释,图8.20 机器人规划专家系统的结构,31,基于,规,规划,的,的机,器,器人,规,规划,专,专家,系,系统,由,由5,个,个部,分,分组,成,成，,如,如图8.20,所,所示,知识,库,库,控制,策,策略,推理,机,机,知识,获,获取,解释,与,与说,明,明,,基于,规,规则,的,的专,家,家系,统,统的,目,目标,就,就是,要,要通,过,过逐,条,条执,行,行规,则,则及,其,其有,关,关操,作,作来,逐,逐步,地,地改,变,变总,数,数据,库,库的,状,状况,，,，直,到,到得,到,到一,个,个可,接,接受,的,的数,据,据库(称,为,为目,标,标数,据,据库)为,止,止。

8.5,基,基于,专,专家,系,系统,的,的机,器,器人,规,规划,32,任务,级,级机,器,器人,规,规划,三,三要,素,素,,任务,规,规划,是,是机,器,器人,高,高层,规,规划,最,最重,要,要的,一,一个,方,方面,，,，它,包,包含,下,下列3个,要,要素,：,：,建立,模,模型,建立,机,机器,人,人工,作,作环,境,境的,世,世界,模,模型,任务,说,说明,程序,综,综合,任务,级,级机,器,器人,规,规划,的,的最,后,后一,步,步是,综,综合,机,机械,手,手的,程,程序,8.5,基,基于,专,专家,系,系统,的,的机,器,器人,规,规划,33,8.6,小,小结,本章,在,在说,明,明了,机,机器,人,人规,划,划的,作,作用,和,和任,务,务后,，,，主,要,要讨,论,论了,几,几种,机,机器,人,人规,划,划的,方,方法,：,：,规划,演,演绎,法,法逻辑,演,演算,和,和通,用,用搜,索,索法,具有,学,学习,能,能力,的,的规,划,划系,统,统,基于,专,专家,系,系统,的,的规,划,划,,值得,指,指出,：,：第一,，,，机,器,器人,规,规划,已,已发,展,展为,综,综合,应,应用,多,多种,方,方法,的,的规,划,划。

第,第二,，,，机,器,器人,规,规划,方,方法,已,已广,泛,泛应,用,用于,图,图象,处,处理,、,、计,算,算机,视,视觉,等,等各,领,领域,第,三,三，,机,机器,人,人规,划,划尚,有,有一,些,些进,一,一步,研,研究,的,的问,题,题，,如,如多,机,机器,人,人协,调,调规,划,划和,实,实时,规,规划,等,等34,演讲完毕,，,，谢谢观,看,看！,。