人工智能及其应用第四版-35页课件.ppt

1、1人 工 智 能2第八章 自动规划8.1 机器人规划的作用与任务机器人规划的作用与任务 8.2 积木机器的机器人规划积木机器的机器人规划8.3 STRIPS规划系统规划系统8.4 具有学习能力的规划系统具有学习能力的规划系统8.5 基于专家系统的机器人规划基于专家系统的机器人规划8.6 小结小结38.18.1 机器人规划的作用与任务机器人规划的作用与任务8.1.18.1.1规划的作用与问题分解途径规划的作用与问题分解途径w 规划的概念及作用规划的概念 规划是一种重要的问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。图8.1 子规划的分层结

2、构例子工工 作作 日日 规规 划划上午子规划上午子规划中午子规划中午子规划下午子规划下午子规划吃夹心面包吃夹心面包阅读阅读写作写作回家回家去上班去上班阅读文章阅读文章4规划的作用 规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。w 问题分解途径及方法把某些比较复杂的问题分解为一些比较小的子问题。有两条能够实现这种分解的重要途径。第一条重要途径是当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题。w 问

3、题域的预测于规划的修正（1）问题论域的预测（2）规划的修正，问题分解使得影响局部化 8.1自动规划的作用与任务58.1.2机器人规划系统的任务与机器人规划系统的任务与方法方法w 在规划系统中，必须具有执行下列各项任务的方法：根据最有效的启发信息，选择应用于下一步的最好规则。应用所选取的规则来计算由于应用该规则而生成的新状态。对所求得的解答进行检验。检验空端，以便舍弃它们，使系统的求解工作向着更有效的方向进行。检验殆正确的解答，并应用具体的技术使之完全正确。8.1自动规划的作用与任务6w 选择于应用规则w 检验解答与空端w 修正殆正确解78.2 积木世界的机器人规划积木世界的机器人规划 8.2.

4、1 积木世界的机器人问题积木世界的机器人问题 积木世界由一些有标记的立方形积木，互相堆迭在一起构成；机器人有个可移动的机械手，它可以抓起积木块并移动积木从一处至另一处。CBA机械手8w 在这个例子中机器人能够执行的动作举例如下：unstack(a,b)：把堆放在积木b上的积木a拾起。在进行这个动作之前，要求机器人的手为空手，而且积木a的顶上是空的。stack(a,b)：把积木a堆放在积木b上。动作之前要求机械手必须已抓住积木a，而且积木b顶上必须是空的。pickup(a)：从桌面上拾起积木a，并抓住它不放。在动作之前要求机械手为空手，而且积木a顶上没有任何东西。putdown(a)：把积木a放

5、置到桌面上。要求动作之前机械手已抓住积木a。8.2 积木世界的机器人规划9 研究内容是综合机器人的动作序列，即在某个给定初始情况下，经过某个动作序列而达到指定的目标。机器人问题的状态描述和目标描述均可用谓词逻辑公式构成：ON(a,b)：积木a在积木b之上。ONTABLE(a)：积木a在桌面上。CLEAR(a)：积木a顶上没有任何东西。HOLDING(a)：机械手正抓住积木a。HANDEMPTY：机械手为空手。8.2 积木世界的机器人规划10 图8.4(a)所示为初始布局的机器人问题。目标在于建立一个积木堆，其中，积木B堆在积木C上面，积木 A又堆在积木B上面，如图8.4(b)所示。CBA机械手

6、ABC机械手（a）初始布局 （b）目标布局图8.4 积木世界的机器人问题8.2 积木世界的机器人规划11w 初始布局可由下列谓词公式的合取来表示：CLEAR(B)：积木B顶部为空CLEAR(C)：积木C顶部为空ON(C，A)：积木C堆在积木A上ONTABLE(A)：积木A置于桌面上ONTABLE(B)：积木B置于桌面上HANDEMPTY：机械手为空手w 目标布局：ON(B,C)and ON(A,B)8.2 积木世界的机器人规划128.2.2用用F规则求解规划序列规则求解规划序列 STRIPS规划系统的规则由3部分组成：第一部分是先决条件。第二部分是一个叫做删除表的谓词。第三部分叫做添加表。8.

7、2 积木世界的机器人规划13w 例：表示堆积木的例子中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)w 如果move为此机器人仅有的操作符或适用动作，那么，可以生成如图8.5所示的搜索图或搜索树。CLEAR(X)CLEAR(X)CLEAR(Z)CLEAR(Z)ON(X,Y)ON(X,Y)ONTABLE(Y)ONTABLE(Y)ONTABLE(Z)ONTABLE(Z)CLEAR(X)CLEAR(X)CLEAR(Y)

8、CLEAR(Y)ON(X,Z)ON(X,Z)ONTABLE(Y)ONTABLE(Y)ONTABLE(z)ONTABLE(z)move(X,Y,Z)图8.5 表示move动作的搜索树8.2 积木世界的机器人规划14机器人的4个动作(或操作符)可用STRIPS形式表示如下：w stack(X,Y)先决条件和删除表：HOLDING(X)CLEAR(Y)添加表：HANDEMPTY，ON(X，Y)w unstack(X,Y)先决条件：HANDEMPTYON(X，Y)CLEAR(X)删除表：ON(X，Y)，HANDEMPTY 添加表：HOLDING(X)，CLEAR(Y)w pickup(X)先决条件：O

9、NTABLE(X)CLEAR(X)HANDEMPTY 删除表：ONTABLE(X)HANDENPTY 添加表：HOLDING(X)w putdown(X)先决条件和删除表：HOLDING(X)添加表：ONTABLE(X)，HANDEMPTY8.2 积木世界的机器人规划15 从初始状态开始，正向地依次读出连接弧线上的F规则，我们就得到一个能够达到目标状态的动作序列（如图8.3中粗线所示）于下：unstack(C,A),putdown(C),pickup(B),stack(B,C),pickup(A),stack(A,B)就把这个动作序列叫做达到这个积木世界机器人问题目标的规划。8.2 积木世界的

10、机器人规划16178.3 STRIPS规划系统w STRIPS的介绍 STRIPS是由Fikes、Hart和Nilsson3人在1981及1982研究成功的，它是夏凯(Shakey)机器人程序控制系统的一个组成部分。w STRIPS系统组成 世界模型：为一阶谓词演算公式；操作符(F规则)：包括先决条件、删除表和添加表；操作方法：应用状态空间表示和中间-结局分析。18w Strips是Shakey机器人系统的一个组成部分，Shakey机器人系统包括：（1）车轮及其推进系统；（2）传感器，由电视摄像机和接触杆组成；（3）计算机，接受机器人的传感器信息与输入指令，经过计算后向车轮及其推进系统发出信号

11、；（4）无线通信系统，用于在车轮与计算机之间的数据传递8.3 Strips规划系统19Strips的规划过程w 问题：(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)w 操作符OP1:gothru(d,r1,r2);先决条件：INROOM(b,r1)and CONNECTS(d,r1,r2)删除表：对所有S,INROOM(Robot,s)添加表：INROOM(Robot,r2)8.3

12、Strips规划系统20w 操作符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)w 问题的差别表：8.3 Strips规划系统差别操作符gothrupushthru物体不在目标房间内机器人不在目标房间内机器人和物体不在同一房间内机器人和物体在同一房间内，但不是目标房间XXXX21w 采用中间结局分析方法求解步骤：do GPS的主循环迭代，unt

13、il 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,R

14、2)采用置换：R1/r1，D1/d 则 G2满足 把gothru(D1,R1,R2)作用于M0，得中间状态M1；把pushthru(BOX1,D1,R2,R1)于M1得中间状态M2=G0END8.3 Strips规划系统22w 最后的规划为：gothru(D1,R1,R2),pushthru(BOX1,D1,R2,R1)8.3 Strips规划系统2324含有多重解答的规划w 例如：要求机器人ROBOT把3个不同区域的箱子推倒同一区域；w 采用归结反演和中间-结局分析来求解；w 得到多重解答。258.4 具有学习能力的规划系统w PULP-机器人规划系统 PULP-机器人规划系统是一种具有学习

15、能力的系统，它采用管理式学习，其作用原理是建立在类比(analogue)的基础上的。w STRIPS的弱点 需要极其大量计算机内存和时间等。应用具有学习能力的规划系统能够克服这一缺点。268.4.1 PULP-系统的结构与操作方式w PULP-系统的结构“字典”是英语词 汇的集合。“模型”部分包括模型世界 物体现有状态的事实。“过程”集中了予先准备好的过程知识。“方块”集中了LISP程序，它配合“规划”对“模型”进行搜索和修正。SENEF程序程序规划与学习规划与学习字典字典模型模型过程过程方块方块响应输入图 8.14 PULP-系统的总体结构 8.4 具有学习能力的规划系统27w PULP-系

16、统的操作方式 PULP-系统具有两种操作方式：学习方式 在学习方式下，输入至系统的知识是由操作人员或者所谓“教师”提供的。图8.15表示出在学习方式下的系统操作。存储存储任务分析任务分析方块方块匹配匹配过程过程分解分解学习学习教师输入任务知识响应图8.15 PULP-系统结构 8.4 具有学习能力的规划系统28规划方式当某个命令句子送入系统时，PULP-就进入规划方式。上图表示PULP-系统在规划方式下的结构。检索检索混合规划混合规划方块方块目标检目标检验匹配验匹配单一规划单一规划规划规划输入命令响应过程过程模型模型图8.16 规划方式下PULP-系统的结构 8.4 具有学习能力的规划系统29

17、分层规划的思想w 长度优先搜索w NOAH规划系统308.5 基于专家系统的机器人规划w 机器人规划专家系统就是用专家系统的结构和技术建立起来的机器人规划系统。w 管理式学习能力的机器人规划系统的不足：表达子句的语义网络结构过于 复杂。与复杂的系统内部数据结构有关的是，PULP-系统具有许多子系统。而且需要 花费大量时间来编写程序。尽管PULP-系统的执行速度要比 STRIPS 系列快得多，然而它仍然不够快。318.5.1系统结构和规划机理w 系统结构及规划机理机机器器人人用用户户机机器器人人专专家家知知识识用用户户接接口口知识库知识库推理机推理机控制控制策略策略 工具工具 专家系统专家系统知

18、识获取说明与分析问题输入或新情况描述回答问题或建议与解释图8.20 机器人规划专家系统的结构32基于规划的机器人规划专家系统由5个部分组成，如图8.20所示。知识库 控制策略 推理机 知识获取 解释与说明基于规则的专家系统的目标就是要通过逐条执行规则及其有关操作来逐步地改变总数据库的状况，直到得到一个可接受的数据库(称为目标数据库)为止。8.5 基于专家系统的机器人规划33w 任务级机器人规划三要素任务级机器人规划三要素任务规划是机器人高层规划最重要的一个方面，它包含下列3个要素：建立模型 建立机器人工作环境的世界模型。任务说明 程序综合 任务级机器人规划的最后一步是综合机械手的程序。8.5 基于专家系统的机器人规划348.6 小结 本章在说明了机器人规划的作用和任务后，主要讨论了几种机器人规划的方法：规划演绎法。逻辑演算和通用搜索法 具有学习能力的规划系统 基于专家系统的规划 值得指出：第一，机器人规划已发展为综合应用多种方法的规划。第二，机器人规划方法已广泛应用于图象处理、计算机视觉等各领域。第三，机器人规划尚有一些进一步研究的问题，如多机器人协调规划和实时规划等。