资源描述
单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,人 工 智 能,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放置到桌面上。要求动作之前机械手已抓住积木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-系统的结构,8.4 具有学习能力的规划系统,28,分层规划的思想,长度优先搜索,NOAH规划系统,29,8.5 基于专家系统的机器人规划,机器人规划专家系统就是用专家系统的结构和技术建立起来的机器人规划系统,。,管理式学习能力的机器人规划系统的不足：,表达子句的语义网络结构过于 复杂。,与复杂的系统内部数据结构有关的是，,PULP-系统具有许多子系统。而且需要,花费大量时间来编写程序。,尽管PULP-系统的执行速度要比 STRIPS,系列快得多，然而它仍然不够快
展开阅读全文