《08-8-第八章自动规划.ppt.ppt》由会员分享，可在线阅读，更多相关《08-8-第八章自动规划.ppt.ppt（53页珍藏版）》请在三一办公上搜索。
1、第八章自动规划,http:/rengongzhineng/kejian/AI/Ai/LiuLan_left.htm,教学内容：介绍自动规划的基本概念和各种规划系统。教学重点：机器人规划的作用与任务、积木世界的规划系 统、具有学习能力的规划系统、基于专家系统 的规划机理。教学难点：具有学习能力的规划系统。教学方法：课堂教学为主，注意结合例子来说明抽象概念。教学要求：本章为选修内容，掌握机器人规划的作用与任 务，并一般了解有哪几种规划方法。,第一节机器人规划的作用与任务,8.1.1 规划的作用与问题分解途径 1、规划的概念及作用 规划的概念：规划是一种重要的问题求解技术，它从某个特定的问题状态出发
2、，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。规划的作用：规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。,子规划的分层结构例子,2、问题分解途径及方法 把某些较复杂的问题分解为一些较小的子问题。有两条实现这种分解的重要途径。第一条重要途径是当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题。,3、域的预测和规划的修正(1)域的预测 规划方法的成功取决于问题论域的另一特性-预测。如果
3、通过在实际上执行某个操作序列来寻找问题的解答，那末在这个过程的任何一步都能确信该步的结果。但对于不可预测的论域，最好能考虑可能的结果的集合，这些结果很可能按照它们出现的可能性以某个次序排列。然后，产生一个规划，并试图去执行这个规划。(2)规划的修正 如果规划在执行中失败了，那么就需要对它进行修订，为便于修订，在规划过程中不仅要记下规划的执行步骤，而且也要记下每一步骤必须被执行的理由。大多规则的执行主要是按目标定向模式工作的。在种模式下，规划系统从目标状态向可达到的初始状态进行搜索。,8.1.2 机器人规划系统的任务与方法 在规划系统中，必须具有执行下列各项任务的方法：(1)根据最有效的启发信息
4、，选择应用于下一步的最好规则。(2)应用所选取的规则来计算由于应用该规则而生成的新状态。(3)对所求得的解答进行检验。(4)检验空端，以便舍弃它们，使系统的求解工作向着更有效的方向进行。(空端：即死端，指无法从它到达目标的端点。)(5)检验殆正确的解答，并应用具体的技术使之完全正确。,下面讨论能够执行上述 5 项任务的方法。1、选择和应用规则 在选择合适的应用规则时最广泛采用的技术是：首先要查出期望目标状态与现有状态之间的差别集合，然后辨别出那些与减少这些差别有关的规则。2、检验解答与空端 当规划系统找到一个能够把初始问题状态变换为目标状态的操作符序列时，此系统就成功地求得问题的一个解答。如果
5、搜索过程是从初始状态正向推理的，那么可以删去任何导致某种状态的路径，从这种状态出发是无法达到目标状态的。（空端）如果搜索过程是从目标状态逆向推理的，那么当确信无法达到初始状态，或者搜索过程进展甚微时，可以终止该路径的搜索。,3、修正殆正确解 一个求解殆可分解问题的办法是：当执行与所提出的解答相对应的操作符序列时，检查求得的状态，并把它与期望目标加以比较。修正一个殆正确的解答的较好办法是:注意有关出错的知识，然后加以直接修正。修正一个殆正确的解答的更好办法是:实际上不是对解答进行全面的修正,而是不完全确定地让它们保留到最后的可能时刻。,第二节积木世界的机器人规划,8.2.1 积木世界的机器人问题
6、 机器人问题既比较简单，又很直观。在机器人问题的典型表示中，机器人能够执行一套动作。在这个例子中机器人能够执行的动作举例如下：unstack(a,b)：把堆放在积木 b 上的积木 a 拾起。在进行这个动作之前，要求机器人的手为空手，而且积木 a 的顶上是空的。stack(a,b)：把积木a堆放在积木 b 上。动作之前要求机械手必须已抓住积木 a，而且积木 b 顶上必须是空的。pickup(a)：从桌面上拾起积木 a，并抓住它不放。在动作之前要求机械手为空手，而且积木 a 顶上没有任何东西。putdown(a)：把积木 a 放置到桌面上。要求动作之前机械手已抓住积木 a。,采用状态描述作为数据库
7、的产生式系统是一种最简单的问题求解系统。机器人问题的状态描述和目标描述均可用谓词逻辑公式构成。为了指定机器人所执行的操作和执行操作的结果，需要应用下列谓词：ON(a,b)：积木 a 在积木 b 之上。ONTABLE(a)：积木 a 在桌面上。CLEAR(a)：积木 a 顶上没有任何东西。HOLDING(a)：机械手正抓住积木 a。HANDEMPTY：械手为空手。,举例：积木世界由一些有标记的立方形积木，互相堆迭在一 起构成；机器人有个可移动的机械手，它可以抓起积 木块并移动积木从一处至另一处。提问：请同学就图8.1 积木世界的机器人问题应用谓词公式 的合取描述此目标为：ON(B，C)ON(A，
8、B)。?初始状态的描述:,图8.1 积木世界的机器人问题,8.2.2 用F规则求解规划序列 采用 F 规则表示机器人的动作，这是一个叫做 STRIPS 规划系统的规则，它由 3 部分组成。第一部分是先决条件。为了使 F 规则能够应用到状态描述中去。第二部分是一个叫做删除表的谓词。当一条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表的内容。第三部分叫做添加表。当把某条规则应用于某数据库时，就把该添加表的内容添进该数据库。,对于堆积木的例子中 move 这个动作可以表示如下：move(x,y,z)：把物体 x 从物体 y 上面移到物体 z 上面。先决条件：CLEAR(x),CLEAR(
9、z)，ON(x,y)删除表：ON(x,y)，CLEAR(z)添加表：ON(x,z)，CLEAR(y),如果move为此机器人仅有的操作符或适用动作，那么，可以生成如下图所示的搜索图或搜索树：,8.2 表示 move 动作的搜索树,下面更具体地考虑图8.1 中所示的例子，机器人的 4 个动作(或操作符)可用 STRIPS 形式表示如下：(1)stack(X,Y)先决条件和删除表：HOLDING(X)CLEAR(Y)添加表：HANDEMPTY，ON(X，Y)(2)unstack(X,Y)先决条件：HANDEMPTYON(X，Y)CLEAR(X)删除表：ON(X，Y)，HANDEMPTY 添加表：H
10、OLDING(X)，CLEAR(Y),(3)pickup(X)先决条件：ONTABLE(X)CLEAR(X)HANDEMPTY 删除表：ONTABLE(X)HANDENPTY 添加表：HOLDING(X)(4)putdown(X)先决条件和删除表：HOLDING(X)添加表：ONTABLE(X)，HANDEMPTY 假定目标为8.1 所示的状态，即 ON(B,C)ON(A,B),从图8.1（a）所示的初始状态描述开始正向操作，只有 unstack(C,A)和 pickup(B)两个动作可以应用 F 规则。图8.3所示给出这个问题的全部状态空间，并用粗线指出了从初始状态(用S0标记)到目标状态(
11、用G标记)的解答路径。,与习惯的状态空间图画法不同的是，这个状态空间图显出问题的对称性，而没有把初始节点S0放在图的顶点上。此外，要注意到本例中的每条规则都有一条逆规则，如图7.3 所示。,例:积木世界机器人问题的状态空间(见P216-217),图8.3 积木世界机器人问题的状态空间（217）,沿着粗线所示的支路，从初始状态开始，正向地依次读出连接弧线上的 F 规则，就得到一个能够达到目标状态的动作序列于下：unstack(C,A),putdown(C),pickup(B)，stack(B,C),pickup(A),stack(A,B)就把这个动作序列叫做达到这个积木世界机器人问题目标的规划。
12、,第三节STRIPS 规划系统,8.3.1 STRIPS系统的组成 STRIPS（Stanford Research Institute Problem Solver）整个 STRIPS 系统的组成如下：(1)世界模型。为一阶谓词演算公式。(2)操作符(F规则)。包括先决条件、删除表和添加表。(3)操作方法。应用状态空间表示和中间-结局分析。例如：状态：(M，G)，包括初始状态、中间状态和目标状态。初始状态：(M0，(G0)目标状态：得到一个世界模型，其中不遗留任何未满足的目标。,8.3.2 STRIPS系统规划过程 每个 STRIPS 问题的解答为某个实现目标的操作符序列，即达到目标的规划。
13、下面举例说明 STRIPS 系统规划的求解过程。例1 考虑 STRIPS 系统一个比较简单的情况，即要求机器人到邻室去取回一个箱子。机器人的初始状态和目标状态的世界模型示于图8.4。,BOX1,机器人,箱子,r1,r2,d,BOX1,机器人,箱子,r1,r2,d,图8.4 STRIPS的一个简化模型,设有两个操作符，即 gothru 和 pushthru(“走过”和“推过”)，分别描述于下：OP1：gothru(d,r1,r2)；机器人通过房间 r1 和房间 r2 之间的 d，即机器人从房间r1 走过门 d 而进入房间 r2。先决条件：机器人在房间 r1 内，而且门 d 连接 r1 和 r2
14、两个房间。INROOM(ROBOT，r1)CONNECTS(d,r1,r2)；删除表：INROOM(ROBOT，S)；对于任何 S 值。添加表：INROOM(ROBOT，r2)。,OP2：pushthru(b,d,r1,r2)机器人把物体 b 从房间 r1 经过门 d 推到房间 r2。先决条件：INROOM(b,r1)INROOM(ROBOT,r1)CONNECTS(d,r1,r2)删除表：INROOM(ROBOT,S)，INROOM(b,S);对于任何S。添加表：INROOM(ROBOT，r2),INROOM(b,r2)。,例:采用中间-结局分析方法来逐步求解机器人规划(见P219-221)
15、,表 6.1 差别表,假定这个问题的初始状态M0和目标G0如下：M0：INROOM(ROBOT，R1)INROOM(BOX1,R2)CONNECTS(D1，R1，R2)G0：INROOM(ROBOT,R1)INROOM(BOX1，R1)CONNECTS(D1，R1，R2),假定这个问题的初始状态M0和目标G0如下：M0：INROOM(ROBOT，R1)INROOM(BOX1,R2)CONNECTS(D1，R1，R2)G0：INROOM(ROBOT,R1)INROOM(BOX1，R1)CONNECTS(D1，R1，R2),BOX1,机器人,箱子,R1,R2,D,BOX1,机器人,箱子,R1,R2
16、,D,图8.4 STRIPS的一个简化模型,基于中间结局分析方法的规划求解:,采用中间结局分析方法来逐步求解这个机器人规划：do GPS的主循环迭代，until M0与G0匹配为止。begin。G0不能满足M0，找出M0与G0的差别。尽管这个问题不能马上得到解决，但是如果初始数据库含有语句INROOM(BOX1，R1)，那么这个问题的求解过程就可以得到继续。GPS找到它们的差别:d1 为 INROOM(BOX1，R1)，即要把箱子(物体)放到目标房间 R1内。选取操作符：一个与减少差别d1有关的操作符。根据差别表，STRIPS选取操作符为：OP2：pushthru(BOX1,d,r1,R1),
17、消去差别d1,为OP2设置先决条件G1为：G1：INROOM(BOX1,r1)INROOM(ROBOT,r1)CONNECTS(d,r1,R1)这个先决条件被设定为子目标，而且STRIPS试图从M0到达G1。尽管G1仍然不能得到满足，也不可能马上找到这个问题的直接解答。不过STRIP发现：如果 r1=R2,d=D1，当前数据库含有INROOM(ROBOT，R1)那么此过程能够继续进行。现在新的子目标G1为：G1：INROOM(BOX1，R2)INROOM(ROBOT，R2)CONNECTS(D1，R2，R1),GPS(p)；重复第3步至第5步，迭代调用，以求解此问题。步骤3：G1和M0的差别d
18、2为 INROOM(ROBOT，R2)即要求机器人移到房间R2。步骤4：根据差别表，对应于d2的相关操作符为 OP1：gothru(d,r1,R2)步骤5：OP1的先决条件为：G2：INROOM(ROBOT，R1)CONNECTS(d,r1,R2)步骤6：应用置换式r1=R1和d=D1，STRIPS系统能够达到G2。,把操作符gothru(D1,R1,R2)作用于M0，求出中间状态M1：删除表：INROOM(ROBOT，R1)添加表：INROOM(ROBOT，R2)M1：INROOM(ROBOT，R2)INROOM(BOX1，R2)CONNECTS(D1，R1，R2)把操作符pushthru应
19、用中间状态M1，删除表：INROOM(ROBOT，R2)，INROOM(BOX1，R2)添加表：INROOM(ROBOT，R1)，INROOM(BOX1，R1),得到另一中间状态M2为：M2：INROOM(ROBOT，R1)INROOM(BOX1，R1)CONNECTS(D1，R1，R2)M2=G0 end。,由于M2与G0匹配，所以通过中间结局分析解答了这个机器人规划问题。在求解过程中，所用到的STRIPS规则为操作符OP1和OP2，即 gothru(D1,R1,R2),pushthru(BOX1,D1,R2,R1)中间状态模型M1和M2，即子目标G1和G2，M2与目标世界模型G0相同。因此
20、，得到的最后规划为OP1，OP2，即 gothru(D1，R1，R2)，pushthru(BOX1,D1,R2,R1),BOX1,机器人,箱子,R1,R2,D,BOX1,机器人,箱子,R1,R2,D,图8.5 中间目标状态的目标模型,（a）中间目标状态 M1,（b）中间目标状态 M2,图 8.6 机器人规划例题的搜索图,第四节具有学习能力的规划系统,8.4.1 PULP-系统的结构与操作方式 1、PULP-系统的结构 字典、模型和过程是系统的内存部分，它们集中了所有信息。“字典”是英语词汇的集合，它的每个词汇都保持在 LISP 的特性表上。“模型”部分包括模型世界内物体现有状态的事实。模型的信
21、息不是固定不变的，它可能随着环境而改变。此外，无论什么时候应用某个操作符，此模型就被适时修正。“过程”集中了予先准备好的过程知识。这种过程知识是一个表式结构，包含一个指令序列。每个指令可能是一个任务语句，这些语句与该任务的过程、局部定义的物体或某个操作符有关。,2、PULP-系统的操作方式 PULP-系统具有两种操作方式，即学习方式和规划方式。在学习方式下，输入至系统的知识是由操作人员或者所谓“教师”提供 的。系统首先把给出的过程知识分解为一个子过程的集合，本原过程知识被分解为几个知识块，每块为一知识包。然后，由任务分析程序进行试验，这个程序对知识包进行分析，并通过一个语义匹配程序求得其提取表
22、示。,当某个命令句子送入系统时，PULP-就进入规划方式。此规划系统的主要作用是形成一个能够把现有世界变换为满足给定命令的世界状态的规划。所生成的规划由一些本原操作符的有序排列组成。当求得一个成功的规划之后，对世界模型进行修正，而且系统输出规划时间和规划细节，以满足输入命令。,8.4.2 PULP-的世界模型和规划结果,提问：请同学比较具有学习能力的机器人规划系统与一般规划系统的异同，并总结前者的特点。,第五节分层规划,8.5.1 长度优先搜索 探索规划时首先只考虑一层的细节，然后再注意规划中比这一层低一层的细节，所以把它叫做长度优先搜索。,8.5.2 NOAH规划系统 1、应用最小约束策略
23、一个寻找非线性规划而不必考虑操作符序列的所有排列的方法是把最少约束策略应用来选择操作符执行次序的问题。问题求解系统 NOAH 采用一种网络结构来记录它所选取的操作符之间所需要的排序。它也分层进行操作运算，即首先建立起规划的抽象轮廓，然后在后续的各步中，填入越来越多的细节。,2、检验准则 准则法已被应用于各种规划生成系统。对于早期的系统，如 HACKER 系统，准则只用于舍弃不满足的规划。在 NOAH 系统中，准则被用来提出推定的方法以便修正所产生的规划。第一个涉及的准则是归结矛盾准则。第二个准则叫做消除多余先决条件准则，包括除去对子目标的多余说明。可以把分层规划和最少约定策略十分直接地结合起来
24、，以求得非线性规划而不产生一个庞大的搜索树。,第六节基于专家系统的机器人规划,8.6.1 系统结构和规划机 1、系统结构及规划机理(1)知识库：用于存储某些特定领域的专家知识和经验，包括机器人工作环境的世界模型、状态、物体描述等事实和可行操作或规则等。(2)控制策略：包含综合机理，确定系统应当应用什么规则以及采取什么方式去寻找该规则。(3)推理机：用于记忆所采用的规则和控制策略及推理策略。,(4)知识获取：首先获取某特定域的专家知识。然后用程序设计语言把这些知识变换为计算机程序。最后把它们存入知识库待用。(5)解释与说明：通过用户接口，在专家系统与用户之间进行对话，从而使用户能够输入数据、提出
25、问题、知道推理结果以及了解推理过程等。,2、任务级机器人规划三要素(1)建立模型。(2)任务说明。(3)程序综合。,8.6.2 ROPES机器人规划系统,作业：根据简化框图8.18，举例说明应用专家系统的机器人规划系统。,第七节小 结,本章在说明了机器人规划的作用和任务后，主要讨论了几种机器人规划的方法：(1)规划演绎法。用F规则求解规划序列。(2)逻辑演算和通用搜索法。STRIPS 和 ABSTRIPS 系统即属此法。(3)具有学习能力的规划系统。如 PULP-系统，它采用类比技术和语义网络表示。(4)分层规划方法。如 NOAH 规划系统，它特别适用于非线性规划。(5)基于专家系统的规划。如 ROPES 规划系统，它具有更快的规划速度、更强的规划能力和更大的适应性,
